PLATFORMA

Algorytmy na maturę z informatyki – 28 algorytmów maturalnych

  • Mateusz Oracz
  • 15 września 2024 · aktualizacja 24 maja 2026

28 algorytmów maturalnych – algorytmy na maturę z informatyki

Jakie algorytmy trzeba opanować na maturę z informatyki? I, co równie ważne, jak je wszystkie zapamiętać i zrozumieć, żeby w dniu egzaminu podejść ze spokojem do arkusza maturalnego? To pytania, które co roku zadają sobie tysiące maturzystów przygotowujących się do matury rozszerzonej z informatyki. Odpowiedź jest prosta, ale wymagająca: musisz mieć w małym palcu konkretny zestaw algorytmów, które od lat są wymagane w zakresie matury z informatyki. Bez ich znajomości realnie nie jesteś w stanie liczyć na wynik powyżej 80%, ponieważ stanowią one fundament zadań programistycznych – czyli tej części arkusza, która waży najwięcej.

W tym artykule znajdziesz 28 algorytmów maturalnych, które pozwoliły naszym uczniom osiągnąć wynik 100% z matury z informatyki. Są to algorytmy obejmujące pełen zakres wymagań CKE – od podstawowych operacji matematycznych, przez sortowania i przeszukiwania, aż po klasyczne metody szyfrowania.

Jak korzystać z tego zestawienia?

Najważniejsza zasada przy nauce algorytmów na maturę: nie uczymy się kodu na pamięć. Wystarczy, że zapamiętamy schemat działania danego algorytmu, a jego implementacja w wybranym języku programowania – w Pythonie, w C++ czy w pseudokodzie – nie będzie dla nas problemem, o ile oczywiście perfekcyjnie opanowaliśmy podstawy programowania.

Uczniowie, którzy osiągali najwyższe wyniki maturalne, znali te schematy na wylot. Dodatkowo każdy z nich przerobił dziesiątki zadań z optymalizacjami oraz najróżniejszymi wariacjami i wariantami tych algorytmów – bo to właśnie ekspozycja na różne warianty buduje pewność potrzebną w dniu egzaminu. Przejdźmy zatem do pierwszego algorytmu.

Algorytm Euklidesa – algorytmy na maturę z informatyki

Algorytm Euklidesa – algorytm maturalny z informatyki

Zaczynamy od najprostszego algorytmu, czyli algorytmu Euklidesa. Jest to sposób na znalezienie największego wspólnego dzielnika (NWD) dwóch liczb. Polega on na wykonywaniu kolejnych dzieleń z resztą, gdzie za każdym razem zamieniamy liczby miejscami, aż jedna z nich będzie równa zero. Wtedy druga liczba to obliczany największy wspólny dzielnik.

Obliczanie NWD(78, 48) za pomocą algorytmu Euklidesa – największy wspólny dzielnik

Z kolei najmniejszą wspólną wielokrotność (NWW) można obliczyć, korzystając z NWD, według wzoru: NWW dwóch liczb a i b to (a * b) / NWD(a, b).

Wzór na NWW: NWW(a, b) = (a × b) / NWD(a, b) – najmniejsza wspólna wielokrotność
Przykład obliczania NWW(78, 48) z wykorzystaniem NWD – algorytm Euklidesa na maturze z informatyki

Sprawdzanie pierwszości liczby – algorytmy na maturę z informatyki

Sprawdzanie pierwszości liczby – algorytm maturalny z informatyki

Kolejnym trywialnym algorytmem potrzebnym na maturę jest sprawdzanie pierwszości liczby. Algorytm ten polega na upewnieniu się, że liczba nie dzieli się przez żadną mniejszą od siebie liczbę, poza 1.

Sprawdzenie czy liczba nie dzieli się przez żadną mniejszą od siebie liczbę, poza 1

Najpierw sprawdzamy, czy liczba nie jest mniejsza od 2, bo 0 i 1 nie są liczbami pierwszymi. Potem sprawdzamy podzielność tej liczby przez wszystkie liczby od 2 do samej siebie minus 1. Jeśli znajdziemy liczbę, przez którą dana liczba dzieli się bez reszty, to nie jest ona pierwsza. Jeśli żadna liczba nie spełni tego warunku, oznacza to, że liczba jest pierwsza.

Sprawdzenie czy liczba 7 jest pierwsza – przykład algorytmu sprawdzania pierwszości liczby

Ciąg Fibonacciego – algorytmy na maturę z informatyki

Wyznaczanie n-tego wyrazu ciągu Fibonacciego – algorytm maturalny z informatyki

Kolejnym ulubionym algorytmem maturzystów, na bazie którego uczą się rekurencji, jest wyznaczanie n-tego wyrazu ciągu Fibonacciego. Ciąg Fibonacciego to ciąg liczb naturalnych, w którym każdy kolejny wyraz jest sumą dwóch poprzednich, zaczynając od faktu, że pierwszymi elementami ciągu są 0 i 1.

Tabela wyrazów ciągu Fibonacciego od F0 do F19

Aby obliczyć n-ty wyraz ciągu, czyli np. 2., 3., 4. wyraz itd., zaczynamy od dwóch pierwszych liczb ciągu (0 i 1) i obliczamy kolejne wyrazy, dodając do siebie dwie poprzednie liczby. Przykładowo, jeśli n jest równe 2, to sumą dwóch poprzednich jest 1, a jeśli n wynosi 3, to wynikiem jest 2. Robimy tak aż do momentu, gdy uzyskamy n-ty wyraz, który zwracamy jako wynik.

Obliczanie wyrazów ciągu Fibonacciego F0–F5: Fn = Fn-1 + Fn-2

Sito Eratostenesa – algorytmy na maturę z informatyki

Sito Eratostenesa – algorytm maturalny z informatyki

Sito Eratostenesa to algorytm do znajdowania wszystkich liczb pierwszych w przedziale od 2 do n. Działa poprzez wykreślanie z tego zakresu liczb, które są wielokrotnościami liczb pierwszych.

Liczby od 2 do 100 – początek sita Eratostenesa
Wykreślamy liczby podzielne przez 2...√n – zasada sita Eratostenesa

Zaczynamy od najmniejszej liczby pierwszej, czyli 2, i wykreślamy wszystkie jej wielokrotności. Potem przechodzimy do następnych liczb, które nie zostały wykreślone, i znów usuwamy ich wielokrotności. Proces ten kontynuujemy aż do pierwiastka z n. Po zakończeniu wszystkie liczby, które pozostały niewykreślone, są liczbami pierwszymi.

Przykładowo dla n=100 wyrzucamy liczby podzielne przez 2...10
Wykreślamy liczby podzielne przez 2 – krok 1 sita Eratostenesa
Wykreślamy liczby podzielne przez 3 – krok 2 sita Eratostenesa
Wykreślamy liczby podzielne przez 5 – krok 3 sita Eratostenesa
Wykreślamy liczby podzielne przez 7 – krok 4 sita Eratostenesa

Pamiętajmy, że spośród algorytmów do znajdowania liczb pierwszych w danym przedziale sito Eratostenesa wyróżnia się efektywnością w porównaniu ze standardowym sprawdzaniem pierwszości liczby.

Liczby pierwsze w przedziale 1–100 – wynik sita Eratostenesa

Konwersja z systemu dziesiętnego na dowolny – algorytmy na maturę z informatyki

Zamiana liczby z systemu dziesiętnego na dowolny – algorytm maturalny z informatyki

Teraz przenosimy się do systemów liczbowych. Aby zamienić liczbę z systemu dziesiętnego na dowolny inny system, dzielimy ją przez podstawę nowego systemu i zapisujemy resztę z dzielenia. Proces powtarzamy, aż liczba stanie się równa 0. Te reszty, zapisane w odwrotnej kolejności, tworzą liczbę w nowym systemie.

Zamiana 270₁₀ na system szesnastkowy – przykład konwersji liczby dziesiętnej

Konwersja z systemu dowolnego na dziesiętny – algorytmy na maturę z informatyki

Zamiana liczby z systemu dowolnego na dziesiętny – algorytm maturalny z informatyki

Aby zamienić liczbę odwrotnie, przechodzimy po cyfrach liczby i każdą cyfrę mnożymy przez podstawę systemu podniesioną do potęgi odpowiadającej pozycji cyfry. Pierwsza cyfra od końca ma potęgę 0, kolejna 1 itd. Następnie sumujemy wyniki potęgowania i mnożenia, aby otrzymać zapis liczby w systemie dziesiętnym.

Analiza liczby 1101₂ i zamiana na system dziesiętny – przykład konwersji z binarnego

Przeszukiwanie liniowe – algorytmy na maturę z informatyki

Przeszukiwanie liniowe – algorytm maturalny z informatyki

Kolejno przechodzimy do tematu, o którym można mówić wiele w kontekście złożoności obliczeniowej – czyli do przeszukiwania liniowego i binarnego.

Zaczynamy od przeszukiwania liniowego, czyli najprostszego możliwego przeszukiwania tablicy. Przechodzimy po kolei przez każdy element tablicy i sprawdzamy, czy jest on równy elementowi, którego szukamy. Możemy zakończyć działanie, gdy znajdziemy szukaną wartość.

Przykład przeszukiwania liniowego – wyszukiwanie liczby 2 w tablicy, index wynikowy to 5

Przeszukiwanie binarne – algorytmy na maturę z informatyki

Przeszukiwanie binarne – algorytm maturalny z informatyki

Następnie mamy przeszukiwanie binarne. Jest to algorytm do przeszukiwania, uwaga – tylko posortowanej tablicy. Opiera się on na zasadzie „dziel i zwyciężaj” – za każdym razem dzielimy tablicę na pół i wybieramy tę część, w której może znajdować się poszukiwany element. Proces powtarzamy, aż znajdziemy element lub zmniejszymy przedział do zera.

Przeszukiwanie binarne – tylko dla posortowanej tablicy
Przykład przeszukiwania binarnego – wyszukiwanie liczby 76, kroki 1 i 2
Przykład przeszukiwania binarnego – wyszukiwanie liczby 76, index wynikowy to 9

Przeszukiwanie liniowe, jak sama nazwa wskazuje, ma złożoność liniową, natomiast binarne ma złożoność logarytmiczną, czyli działa efektywniej niż przeszukiwanie liniowe.

Wyznaczanie miejsca zerowego funkcji – algorytmy na maturę z informatyki

Wyznaczanie miejsca zerowego funkcji – algorytm maturalny z informatyki

Następnie przechodzimy do algorytmów związanych z matematyką, a zaczynamy od wyznaczania miejsca zerowego funkcji za pomocą metody połowienia. Metoda ta polega na stopniowym zawężaniu przedziału, w którym znajduje się miejsce zerowe.

Podobnie jak w przeszukiwaniu binarnym, dzielimy przedział na pół i sprawdzamy, w której części znajduje się miejsce zerowe. Proces ten powtarzamy, aż różnica między końcami przedziału będzie mniejsza od zadanej dokładności.

Przykład wyznaczania miejsca zerowego – funkcja f(x) = x³ − 2x, przedział [1, 2], dokładność ε = 0,5
Metoda bisekcji krok 1 – gdy f(a)·f(środek) < 0, ustawiamy b = środek
Metoda bisekcji krok 2 – gdy f(a)·f(środek) > 0, ustawiamy a = środek
Metoda bisekcji – dokładność ε = 0,5 została osiągnięta, przybliżone miejsce zerowe w f(2,75)

Wyszukiwanie wzorca w tekście metodą naiwną – algorytmy na maturę z informatyki

Wyszukiwanie wzorca w tekście metodą naiwną – algorytm maturalny z informatyki

Metoda naiwna polega na przesuwaniu wzorca wzdłuż tekstu i porównywaniu go z odpowiadającym mu fragmentem. Jeśli wzorzec pasuje do fragmentu tekstu, oznacza to, że wzorzec został znaleziony. Algorytm działa, dopóki nie przeanalizuje całego tekstu.

Przykład wyszukiwania wzorca BAR w tekście KAPIBARA metodą naiwną

Obliczanie pierwiastka kwadratowego – algorytmy na maturę z informatyki

Obliczanie pierwiastka kwadratowego – algorytm maturalny z informatyki

Metoda Newtona-Raphsona oblicza pierwiastek kwadratowy liczby przez iteracyjne poprawianie przybliżenia. Zaczynamy od początkowego przybliżenia i używamy wzoru iteracyjnego do obliczenia kolejnych przybliżeń. Proces powtarzamy, aż różnica między kolejnymi przybliżeniami będzie mniejsza niż zadana dokładność. Każde nowe przybliżenie jest obliczane na podstawie poprzedniego, co pozwala na szybkie zbliżenie się do rzeczywistej wartości pierwiastka.

Przykład obliczania pierwiastka kwadratowego z 7 – metoda babilońska, wynik ≈ 2,64575

Schemat Hornera – algorytmy na maturę z informatyki

Obliczanie wartości wielomianu za pomocą schematu Hornera – algorytm maturalny z informatyki

Schemat Hornera to algorytm służący do szybkiego obliczenia wartości wielomianu. Zmniejsza on liczbę mnożeń do minimum.

Wielomian W(x) = 2x³ + x² + 3x + 9 w postaci standardowej – 5 mnożeń

Czyli przykładowo z takiego wielomianu, mającego 5 mnożeń, robimy wielomian w postaci zagnieżdżonej, który ma już tylko 3 mnożenia.

Ten sam wielomian w schemacie Hornera – tylko 3 mnożenia

Aby obliczyć wartość wielomianu dla danej liczby, zaczynamy od najwyższego współczynnika i stopniowo przetwarzamy kolejne współczynniki. Wykonujemy operacje mnożenia i dodawania w jednym kroku: mnożymy aktualny wynik przez wartość zmiennej i dodajemy kolejny współczynnik. Kontynuujemy ten proces aż do uwzględnienia wszystkich współczynników, co pozwala nam szybko uzyskać wartość wielomianu.

Potęgowanie sposobem naiwnym – algorytmy na maturę z informatyki

Potęgowanie sposobem naiwnym – algorytm maturalny z informatyki

Potęgowanie sposobem naiwnym to najprostsza metoda obliczania potęgi liczby. Działa to tak, że zaczynamy od wartości 1 i wielokrotnie mnożymy ją przez podstawę potęgi, tyle razy, ile wynosi wykładnik.

Na przykład, jeśli chcemy obliczyć 2^4, to po kolei mnożymy 1 przez 2, potem znowu przez 2 i tak dalej, aż osiągniemy liczbę mnożeń równą wykładnikowi, czyli w tym przypadku 4 razy.

Przykład potęgowania sposobem naiwnym – 2⁴ = 1 × 2 × 2 × 2 × 2

Chociaż jest to najprostsza metoda, może być mniej wydajna dla dużych wykładników, ponieważ wymaga wielu operacji mnożenia.

Potęgowanie szybkie – algorytmy na maturę z informatyki

Potęgowanie szybkie – algorytm maturalny z informatyki

Potęgowanie szybkie jest efektywniejszym sposobem potęgowania. Algorytm polega na zmniejszeniu liczby operacji mnożenia, dzięki czemu działa znacznie szybciej.

Dzielimy wykładnik na mniejsze części i obliczamy potęgowanie rekurencyjnie dla tych mniejszych części. Jeśli wykładnik jest nieparzysty, dodajemy dodatkowe mnożenie przez podstawę do rezultatu.

Przykładowo dla 4^10 będziemy mieli: 4^10 = 16^5 = 256^2 * 16 = 65536^1 * 16.

Przykład szybkiego potęgowania – obliczanie 4¹⁰ = 1 048 576

Potęgowanie modulo – algorytmy na maturę z informatyki

Potęgowanie modulo – algorytm maturalny z informatyki

Algorytm potęgowania modulo polega na obliczeniu reszty z dzielenia potęgi danej liczby przez inną liczbę. Ta operacja jest przydatna szczególnie w kryptografii. Algorytmy kryptograficzne (np. RSA) opierają się na obliczaniu potęg modulo dużych liczb pierwszych. Proces ten znacznie utrudnia łamanie szyfrów.

Uzyskanie reszty z dzielenia poprzez obliczanie najpierw wartości potęgi może prowadzić do bardzo dużych liczb, które są niepraktyczne do obliczeń. Aby uprościć i przyspieszyć ten proces, wystarczy wybrać któryś z poprzednich algorytmów potęgowania i przy każdej operacji mnożenia wykonać operację modulo.

Potęgowanie naiwne modulo – przykład 26⁵ mod 33 = 23
Potęgowanie szybkie modulo – przykład 26⁵ mod 33 = 23

Wydawanie reszty – algorytm zachłanny – algorytmy na maturę z informatyki

Wydawanie reszty z użyciem algorytmu zachłannego – algorytm maturalny z informatyki

Przejdźmy teraz do wydawania reszty z użyciem algorytmu zachłannego. Algorytm opiera się na dwóch założeniach: po pierwsze, mamy nieskończoną liczbę monet o określonych nominałach; po drugie, chcemy wydać konkretną kwotę, używając jak najmniejszej liczby monet.

Dla przykładu: chcemy wydać 63 grosze. Nominały, którymi dysponujemy, to 1, 2, 5, 10, 20 i 50 groszy. Algorytm polega na tym, że najpierw wybieramy monetę o największym nominale, która nie przekracza pozostałej kwoty do wydania. Postępujemy tak, dopóki nie uzbieramy całej kwoty.

Przykład wydawania reszty algorytmem zachłannym – reszta 63 groszy, nominały: 50, 10, 2, 1

Odwrotna Notacja Polska (ONP) – algorytmy na maturę z informatyki

Odwrotna Notacja Polska (ONP) – algorytm maturalny z informatyki

Odwrotna Notacja Polska to metoda zapisu wyrażeń arytmetycznych bez zastosowania nawiasów. W tej notacji symbole operacji występują po argumentach.

Tabela porównawcza notacji normalnej i ONP – przykłady działań

Algorytm obliczania wartości wyrażenia ONP działa tak, że odczytujemy po kolei każdy znak wyrażenia. Jeśli jest on liczbą, to zapisujemy go na stosie. Jeśli jest operatorem, to pobieramy dwie ostatnie liczby ze stosu, wykonujemy na nich działanie i wynik umieszczamy z powrotem na stosie. Powtarzamy to działanie, dopóki nie przejdziemy przez całe wyrażenie ONP. Pozostała liczba na stosie będzie naszym wynikiem.

Obliczanie wyrażenia 5 + 7 × 3 − 10 ^ (2 + 1) w ONP – krok 1, stos: 5, 7, 3 → 5, 21
Obliczanie wyrażenia w ONP – krok 2, stos: 26, 10, 2, 1
Obliczanie wyrażenia w ONP – wynik końcowy: −974

Sortowanie bąbelkowe – algorytmy na maturę z informatyki

Sortowanie bąbelkowe – algorytm maturalny z informatyki

A teraz przechodzimy do sortowań, zaczynając od ulubionego algorytmu maturzystów – czyli sortowania bąbelkowego.

Jest to najprostszy algorytm sortujący. Polega on na porównywaniu ze sobą sąsiadujących elementów w tablicy, dopóki nie zostanie ona posortowana. Dodatkowo możemy wprowadzać optymalizacje, aby zmniejszyć liczbę porównań w każdej z iteracji.

Przykład sortowania bąbelkowego krok po kroku – tablica [8, 20, 10, 21, 1, 2] → [1, 2, 8, 10, 20, 21]

Sortowanie przez wybór – algorytmy na maturę z informatyki

Sortowanie przez wybór – algorytm maturalny z informatyki

Sortowanie przez wybór polega na znajdowaniu najmniejszego elementu po prawej stronie od aktualnego elementu, czyli w nieposortowanej części tablicy. Po znalezieniu, aktualny element i minimalny zamieniają się miejscami. Tę czynność wykonuje się do momentu przejścia po całej tablicy.

Przykład sortowania przez wybór krok po kroku – wyszukiwanie minimum i zamiana elementów
Sortowanie przez wybór – kroki 4–6, wyszukiwanie minimum i zamiana elementów
Sortowanie przez wybór – kroki 7–9, tablica posortowana: [2, 3, 4, 4, 5, 6, 7, 7, 8]

Sortowanie przez wstawianie – algorytmy na maturę z informatyki

Sortowanie przez wstawianie – algorytm maturalny z informatyki

Bardzo podobne jest sortowanie przez wstawianie. Polega ono na pobieraniu pierwszego elementu z prawej strony tablicy, czyli części nieposortowanej, i wstawianiu go w odpowiednie miejsce po lewej stronie tablicy, czyli części posortowanej. Algorytm rozpoczyna się od pierwszego indeksu, a wykonuje się do momentu dojścia do końca tablicy.

Przykład sortowania przez wstawianie krok po kroku – tablica [8, 5, 7, 2, 3, 5, 2] → [2, 2, 3, 5, 5, 7, 8]

Sortowanie kubełkowe – algorytmy na maturę z informatyki

Sortowanie kubełkowe – algorytm maturalny z informatyki

Sortowanie kubełkowe ma kilka różnych wersji, ale zajmijmy się jedną z nich. Polega ona na utworzeniu liczników dla każdej wartości w tablicy i ustawieniu ich na 0. Te liczniki to właśnie nasze kubełki. Kubełki mogą być tablicą o długości największej wartości tablicy plus 1.

Przechodząc po tablicy, każde wystąpienie danej liczby odnotowujemy, zwiększając zawartość danego kubełka o 1. Po zliczeniu wszystkich elementów wypisujemy numer danego kubełka tyle razy, ile wynosi jego zawartość. W ten sposób otrzymujemy posortowaną tablicę.

Przykład sortowania kubełkowego krok po kroku – tablica [9, 1, 2, 8, 0, 4, 3, 2, 2, 2] → [0, 1, 2, 2, 2, 2, 3, 4, 8, 9]

Sortowanie szybkie – algorytmy na maturę z informatyki

Sortowanie szybkie – algorytm maturalny z informatyki

A teraz sortowania rekurencyjne. Zacznijmy od sortowania szybkiego, które polega na wybraniu elementu podziału, czyli pivota. Po lewej stronie od pivota umieszczamy elementy od niego mniejsze, a po prawej większe. Wtedy następuje podział tablicy na elementy mniejsze i większe od pivota. W tych tablicach również wybieramy pivota, dokonujemy podziału i powtarzamy czynność, aż do momentu, gdy przedział będzie jednoelementowy.

Sortowanie szybkie – partycjonowanie tablicy, kroki 1–3, pivot = 4
Sortowanie szybkie – partycjonowanie tablicy, kroki 4–7
Sortowanie szybkie – partycjonowanie tablicy, kroki 8–10, pivot na pozycji końcowej
Sortowanie szybkie – rekurencyjne partycjonowanie, kroki 11–15
Sortowanie szybkie – rekurencyjne partycjonowanie, kroki 16–20
Sortowanie szybkie – kroki 21–24, tablica posortowana: [1, 1, 2, 2, 3, 4, 7, 8, 8]

Sortowanie przez scalanie – algorytmy na maturę z informatyki

Sortowanie przez scalanie – algorytm maturalny z informatyki

Kolejne sortowanie rekurencyjne to sortowanie przez scalanie. Polega ono na dzieleniu tablicy na dwie części, dopóki nie pozostanie jeden element. Powstałe posortowane tablice łączy się w jeden posortowany ciąg.

Przykład sortowania przez scalanie krok po kroku – tablica [5, 8, 7, 2, 3, 2, 6, 8] → [2, 2, 3, 5, 6, 7, 8, 8]

Najdłuższy wspólny podciąg – algorytmy na maturę z informatyki

Szukanie najdłuższego wspólnego podciągu – algorytm maturalny z informatyki

Przejdźmy teraz do algorytmu, który również znajdziesz w wymaganiach maturalnych, czyli do szukania najdłuższego wspólnego podciągu.

Problem szukania najdłuższego wspólnego podciągu jest klasycznym problemem w dziedzinie informatyki. Polega on na znalezieniu najdłuższego ciągu znaków, który jest podciągiem dwóch danych ciągów, zachowując kolejność występowania znaków. Do znalezienia takiego podciągu wykorzystujemy tablicę.

Znajdowanie największego wspólnego podciągu dla ciągów XMJYAUZ i MZJAXU

Implementacja krok po kroku wygląda następująco. Najpierw tworzymy macierz o wymiarach (długość pierwszego ciągu + 1) na (długość drugiego ciągu + 1). Pomoże ona zapisać wyniki podproblemów.

Następnie wypełniamy pierwszy wiersz i pierwszą kolumnę zerami. Wynika to z faktu, że pusty ciąg nie ma wspólnych podciągów z żadnym innym ciągiem.

Tabela dynamicznego programowania LCS – wypełnianie kroków 1–4

Teraz przechodzimy przez tabelę i porównujemy znaki z obu ciągów. Jeśli znaki są takie same, dodajemy 1 do wartości z lewego górnego rogu tabeli. Jeśli są różne, bierzemy większą wartość z lewej lub górnej komórki. Dzięki temu budujemy rozwiązanie krok po kroku.

Tabela dynamicznego programowania LCS – wypełnianie kroków 5–8, długość LCS = 4

Po wypełnieniu macierzy ostatnia komórka w prawym dolnym rogu zawiera długość najdłuższego wspólnego podciągu. Aby znaleźć sam podciąg, śledzimy, skąd pochodzi każda wartość w tabeli, cofając się w kierunku lewego górnego rogu.

Odtwarzanie najdłuższego wspólnego podciągu – backtracking kroki 9–12, wynik: AU
Odtwarzanie najdłuższego wspólnego podciągu – backtracking kroki 13–16, wynik: MJAU

Szyfrowanie Cezara – algorytmy na maturę z informatyki

Szyfrowanie Cezara – algorytm maturalny z informatyki

Teraz przechodzimy do szyfrowań, zaczynając od szyfru Cezara. To jedna z najprostszych i najstarszych metod szyfrowania tekstu – rodzaj szyfru podstawieniowego, w którym każda litera tekstu jawnego jest zastępowana inną literą, oddaloną od niej o klucz, czyli stałą liczbę pozycji w alfabecie.

Mamy więc tekst jawny, który chcemy zaszyfrować, i klucz będący wartością, o którą będziemy przesuwać litery. Na przykład, jeśli klucz wynosi 3, to litera A stanie się D, B stanie się E i tak dalej.

Przykład szyfrowania Cezara – tekst jawny ZUPA, klucz 3, szyfrogram CXSD

Szyfrowanie płotkowe – algorytmy na maturę z informatyki

Szyfrowanie płotkowe – algorytm maturalny z informatyki

Szyfrowanie płotkowe to rodzaj szyfru przestawieniowego, czyli takiego, w którego szyfrogramie występują wszystkie litery tekstu jawnego, jednak w innej kolejności. Polega ono na zapisaniu tekstu jawnego w sposób przypominający płotek. Wysokość płotka jest definiowana przez klucz szyfrujący. Następnie, dzięki odpowiedniemu odczytaniu tekstu z płotka, powstaje szyfrogram.

Przykład szyfrowania płotkowego – tekst jawny WSZYSTKO, klucz 3, szyfrogram WSSYTOZK

Szyfrowanie Vigenère'a – algorytmy na maturę z informatyki

Szyfrowanie Vigenère'a – algorytm maturalny z informatyki

A teraz szyfrowanie o mojej ulubionej nazwie, czyli szyfrowanie Vigenère'a.

Polega ono na wykorzystaniu wielu różnych podstawień cezarowych w zależności od litery klucza. Zaczynamy od wypełnienia macierzy literami alfabetu. Następnie każdą literę tekstu jawnego zamieniamy według klucza przy pomocy macierzy, a kluczem w tym szyfrze jest inne słowo.

Tabula recta – tablica Vigenère'a do szyfrowania wieloalfabetycznego – algorytm maturalny z informatyki
Przykład użycia tablicy Vigenère'a – szyfrowanie litery H kluczem J daje literę Q
Przykład szyfrowania Vigenère'a krok po kroku – tekst jawny INFORMATYKA, klucz MATURA, litery 1–6
Przykład szyfrowania Vigenère'a krok po kroku – tekst jawny INFORMATYKA, klucz MATURA, litery 7–11, szyfrogram UNYIIMMTRER

Szyfrowanie Playfair – algorytmy na maturę z informatyki

Szyfrowanie Playfair – algorytm maturalny z informatyki

Ostatnie jest szyfrowanie Playfair. Jest to szyfr blokowy, który szyfruje litery parami. Klucz jest napisem używanym do wygenerowania macierzy 5×5 złożonej z liter alfabetu. Litery są wpisywane do macierzy zgodnie z kolejnością w kluczu, a następnie w porządku alfabetycznym.

Tabela 5×5 z hasłem SZYFR do szyfrowania Playfair – algorytm maturalny z informatyki

W macierzy może zmieścić się tylko 25 liter, a alfabet angielski ma ich 26. Zatem najczęściej stosuje się rozwiązanie, w którym I oraz J są traktowane jako ta sama litera. Powyżej mamy przykładową macierz wygenerowaną na podstawie klucza SZYFR.

Następnie postępujemy zgodnie z poniższymi zasadami. Jeśli litery tekstu jawnego są w tej samej kolumnie, to zamieniamy każdą z liter na literę znajdującą się poniżej. Jeśli litery są w tym samym wierszu, to zamieniamy każdą z liter na literę znajdującą się po jej prawej stronie. Jeśli litery tworzą prostokąt, to zamieniamy każdą z liter na literę znajdującą się w tym samym wierszu, ale w kolumnie drugiej litery z pary.

Szyfrowanie pary MA w tej samej kolumnie w szyfrze Playfair – M→T, A→G
Szyfrowanie pary TU w tym samym wierszu w szyfrze Playfair – T→U, U→V
Szyfrowanie pary RA w szyfrze Playfair – R→S, A→E (reguła wiersza z zawijaniem)

Podsumowanie – algorytmy na maturę z informatyki

Najważniejszy wniosek z tego zestawienia jest taki, że nie ma sensu uczyć się tych algorytmów na pamięć linijka po linijce. To, co realnie odróżnia uczniów z wynikiem 100% od tych z wynikiem 60%, to zrozumienie schematu działania każdego z tych algorytmów oraz umiejętność jego samodzielnej implementacji w wybranym języku programowania. Druga kluczowa rzecz to praktyka na wariacjach. Na maturze rzadko trafisz na czysty, podręcznikowy algorytm – znacznie częściej pojawia się on jako element większego zadania, w nieco zmodyfikowanej formie lub z dodatkowymi warunkami. Dlatego nasi uczniowie, którzy osiągali najwyższe wyniki, przerabiali dziesiątki zadań wykorzystujących te schematy w różnych kombinacjach. To właśnie powtarzalność i ekspozycja na liczne warianty budują pewność, której potrzebujesz w dniu egzaminu.

Jeśli chcesz mieć pewność, że na maturze poradzisz sobie z każdym zadaniem programistycznym, opanuj te 28 algorytmów do tego stopnia, żeby móc każdy z nich zaimplementować bez zaglądania do notatek. To jest absolutne minimum, na którym budujesz całą resztę przygotowań.


Komentarze

  • @gdhdbxhebsgx9604
    @gdhdbxhebsgx9604
    1 grudnia 2024 19:29
    ❤️ 4

    Zrobisz film o wszystko co musisz wiedzieć o bazach danych do maturki. Mega by się przydało. Z góry dzięki!

  • @marcin2x4
    @marcin2x4
    16 maja 2025 13:59

    Sztos lista!
    A zrobiłbyś film o dokładnym, krok po kroku, rozkminieniu "Szukania najdłuższego wspólnego podciągu (Longest common substring)"?

  • @zuzannakies3691
    @zuzannakies3691
    18 lutego 2025 14:43
    ❤️ 1

    tylko te trzeba umieć ? i czy tylko te algorytmy są potrzebne czy też trzeba samemu umieć wymyślić ?

    • @mateuszoraczkmi
      @mateuszoraczkmi
      20 lutego 2025 07:33
      ❤️ 4

      Cześć!

      Podstawą matury z informatyki nie jest jedynie zapamiętanie konkretnych algorytmów, ale przede wszystkim umiejętność ich samodzielnej analizy oraz opracowania optymalnego rozwiązania dla danego problemu. Nauczenie się "kodu" na pamięć nie ma tu większego sensu. Osobiście polecam zapamiętać 1-2 kluczowe zdania, które obrazują działanie algorytmu na przykładowym zestawie danych – to właśnie na ich podstawie powinnaś być w stanie napisać kod realizujący założenia.

      Warto też zaznaczyć, że algorytmy, które wymieniłem, są między innymi zawarte w informatorach CKE, dlatego dbamy o to, aby każdy uczeń był z nimi w pełni zaznajomiony.

  • @jolantagawronska9484
    @jolantagawronska9484
    23 lutego 2025 07:54

    Jejku czarny las😮😮😮

    • @mateuszoraczkmi
      @mateuszoraczkmi
      23 lutego 2025 08:49
      ❤️ 1

      @jolantagawronska9484 A w lesie drzewa czerwono-czarne 😅😅😅

Powiązane artykuły
Krytyczny problem w Microsoft Access wersji 2604. Zgłoś administratorowi, zanim będzie za późno.
Krytyczny problem w Microsoft Access wersji 2604. Zgłoś administratorowi, zanim będzie za późno.
Więcej
Wyniki matury z informatyki 2026 – Analiza, klucz odpowiedzi
Wyniki matury z informatyki 2026 – Analiza, klucz odpowiedzi
Więcej