A collection of algorithms written in python, which are required by the irrelevant Polish IT curriculum. Yet to ideally pass the exam well above the desired score, one should at least know their existence.
Clone the repository with:
git clone https://github.com/Rafisto/MaturaAlgorithms.git
- Primality test - Czy liczba jest liczbą pierwszą?
- Base converter - Zamiana systemów liczbowych, na (10) oraz (dowolny) z (10)
- LCM, GCD Calculator - Liczenie NWW oraz NWD
- Text comparison - Porównywanie tekstów
- Naive pattern matching - Wyszukiwania Wzorca (WW) metodą naiwną
- Caesar cipher - Szyfr przestawieniowy Cezara (ROT13), w ogólności ROT(n)
- Insertion Sort - Metoda sortowania poprzez wstawianie
- Bubble Sort - Metoda sortowania bąbelkowego
- Iterative progression - Liczenie wyrazów ciągu metodą iteracyjną
- Recursive progression - Liczenie wyrazów ciągu metodą rekurencyjną
- Fibonacci sequence - Liczenie wyrazów ciągu Fibonacciego
- Bisection method - Wyszukiwanie pierwiastków wielomianu metodą połowienia
- Euclidean algorithm - algorytm Euklidesa w wersji iteracyjnej i rekurencyjnej
- Binary search - wyszukiwanie binarne
- Eratosthenes sieve - generowanie liczb pierwszych z użyciem sita Eratostenesa
- Merge sort - sortowanie ciągu poprzez scalanie
- Babylonian method - wyszukiwanie pierwiastków kwadratowych metodą babilońską
- Horner's method - wartości wielomianu schematem Hornera
- Exponentiation by squaring - szybkie potęgowanie liczb w wersji iteracyjnej i rekurencyjnej
- Prime factorization - rozkładanie liczby na czynniki pierwsze
- Progression properties - najdłuższy spójny podciąg niemalejący, spójny podciąg o największej sumie
- Postfix notation - implementacja kalkulatora przy użyciu odwróconej notacji polskiej
-
planuje kolejne kroki rozwiązywania problemu, z uwzględnieniem podstawowych etapów myślenia komputacyjnego (określenie problemu, definicja modeli i pojęć, znalezienie rozwiązania, zaprogramowanie i testowanie rozwiązania).
-
stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej oraz algorytmy:
- a) na liczbach: badania pierwszości liczby
- zamiany reprezentacji liczb między pozycyjnymi systemami liczbowymi,
- działań na ułamkach z wykorzystaniem NWD i NWW,
- b) na tekstach: porównywania tekstów,
- wyszukiwania wzorca w tekście metodą naiwną,
- szyfrowania tekstu metodą Cezara i przestawieniową,
- c) porządkowania ciągu liczb: przez wstawianie
- oraz metodą bąbelkową,
- d) obliczania wartości elementów ciągu metodą iteracyjną i rekurencyjną,
- ^^w tym wartości elementów ciągu Fibonacciego.
-
wyróżnia w problemie podproblemy i charakteryzuje:
- metodę połowienia
- stosuje podejście zachłanne i rekurencję;
-
zapisuje za pomocą listy kroków, schematu blokowego lub pseudokodu, i implementuje w wybranym języku programowania, algorytmy poznane na wcześniejszych etapach oraz algorytmy:
- a) algorytm Euklidesa w wersji iteracyjnej i rekurencyjnej wraz z zastosowaniami,
- b) znajdowania określonego elementu w zbiorze: elementu w zbiorze uporządkowanym metodą binarnego wyszukiwania,
- c) generowania liczb pierwszych metodą sita Eratostenesa,
- d) sortowania ciągu liczb przez scalanie,
- e) wyznaczania miejsc zerowych funkcji metodą połowienia,
- f) obliczania przybliżonej wartości pierwiastka kwadratowego,
- g) obliczania wartości wielomianu za pomocą schematu Hornera,
- h) szybkiego potęgowania liczb w wersji iteracyjnej i rekurencyjnej,
-
wykorzystuje znane sobie algorytmy przy rozwiązywaniu i programowaniu rozwiązań następujących problemów:
- a) rozkładania liczby na czynniki pierwsze,
- b) wykonywania działań na liczbach w systemach innych niż dziesiętny,
- c) znajdowania w ciągu podciągów o różnorodnych własnościach, np. najdłuższego spójnego podciągu niemalejącego, spójnego podciągu o największej sumie,
- d) zamiany wyrażenia na postać w odwrotnej notacji polskiej i obliczanie jego wartości na podstawie tej postaci,
-
objaśnia, a także porównuje podstawowe metody i techniki algorytmiczne oraz struktury danych, wykorzystując przy tym przykłady problemów i algorytmów, w szczególności:
- a) wyszukiwanie elementów liniowe i przez połowienie (do znajdowania elementów w zbiorze, sortowania przez wstawianie, przybliżonego rozwiązywania równań),
- b) rekurencję (do generowania ciągów liczb, potęgowania, sortowania liczb, generowania fraktali),
- c) metodę dziel i zwyciężaj (sortowanie przez scalanie i szybkie),
- d) podejście zachłanne,
- e) programowanie dynamiczne,
- f) struktury dynamiczne: stos, kolejka, lista (do realizacji algorytmu ONP)
As clearly visible on the plot, basic exams - polish, mathematics and english are specifically fixed to enable the highest number of students to pass.
Polish and english on a basic level was failed by no more than 5% of the students and basic mathematics less than 15%. Congratulations to all who received a reasonable score.
My score on the advanced mathematics: 100%
My score on the advanced physics: 78%
My score on the advanced informatics: 78%
Notably won an olympiad.
In 2023 Matura was a little (up to 10%) easier than a year prior.