Test maturalny:  Algorytmy zaawansowane

Rekurencja

Technika, w której funkcja wywołuje samą siebie z mniejszymi/prostszymi argumentami, aż osiągnie przypadek bazowy.

silnia(n) = jeśli n≤1 zwróć 1; w przeciwnym razie zwróć n * silnia(n-1)

Programowanie dynamiczne (PD)

Strategia, w której zapamiętujemy wyniki podproblemów w tablicy/słowniku, aby unikać ponownego obliczania.

fib[i] = fib[i-1] + fib[i-2], buduj od fib[0]=fib[1]=1

Algorytm Kadane

Liniowy O(n) algorytm znajdowania spójnego podciągu o największej sumie.

ost = max(t[i], ost+t[i]); maks = max(maks, ost)

Najdłuższy podciąg rosnący (LIS)

Problem znalezienia najdłuższego (niekoniecznie spójnego) podciągu ściśle rosnącego.

O(n²) z dl[i]=max(dl[j])+1 dla j<i z t[j]<t[i]

Dziel-i-zwyciężaj

Strategia: dziel problem na ~równe części, rozwiąż rekurencyjnie, scal wyniki.

Merge sort, quicksort, binary search, potęgowanie szybkie

Algorytm zachłanny (greedy)

Strategia: w każdym kroku wybieraj lokalnie najlepszą opcję.

Działa dla: harmonogramowanie, plecakowy ciągły, Huffman, MST

Wyszukiwanie połówkowe

Algorytm O(log n) szukania elementu w posortowanej tablicy.

l=0, p=n-1; dopóki l≤p: m=(l+p)/2, porównaj t[m] z x

Złożoność O()

Asymptotyczne oszacowanie liczby operacji w funkcji rozmiaru danych n.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Przypadek bazowy

Najprostszy przypadek w rekurencji, dla którego znamy odpowiedź bez dalszych wywołań.

Bez niego = nieskończona rekursja = Stack Overflow

Stos wywołań

Struktura pamięci przechowująca aktywne wywołania funkcji. Każda rekurencja zużywa stos.

Głębokość rekurencji > 10⁵ często powoduje przepełnienie

Memoizacja

Wariant PD: pamiętamy wyniki funkcji rekurencyjnej w słowniku/tablicy i nie liczymy dwukrotnie.

Top-down PD vs bottom-up PD

Łańcuch przedziałów

Ciąg przedziałów P₁, P₂, ..., Pₖ taki, że każdy następny zawiera poprzedni.

Znajdowane przez sortowanie + PD analogiczne do LIS

1. 1 To 30 minut, które oszczędzą tygodnie błędnego uczenia się z arkuszy.
2. 2 Po każdym pytaniu „Algorytm” przeczytaj uważnie feedback AI — system pokazuje nie tylko poprawną odpowiedź, ale i wzorzec, który warto zapamiętać, plus odnośnik do podobnego zadania CKE.
3. 3 Trenuj „Programowanie” w blokach: jeden dzień rekurencja, kolejny PD, kolejny dziel-i-zwyciężaj.
4. 4 Sprawdzaj zawsze rozmiar danych przed wybraniem algorytmu — quiz wprost premiuje świadomy wybór rzędu O(). Dla n ≤ 100 obronisz brute force, dla n ≥ 10⁵ musisz mieć rozwiązanie liniowe lub n log n.
5. 5 Symuluj timing: 15 pytań w 30 minut to 2 minuty na zadanie — porównywalne z arkuszem CKE. Jeśli przekraczasz limit, problemem jest zwykle planowanie algorytmu, nie sama składnia języka.
6. 6 Przed częścią praktyczną przeklikaj jedną sesję „Otwarte (wyjaśnij)” — wymusisz wytłumaczenie algorytmu słowami, co świetnie aktywuje nawyk pisania komentarzy w kodzie oddawanym na egzaminie.
7. 7 Wtedy przejdź do quizu z grafów, drzew BST i ONP, by domknąć całą algorytmikę PR.

Powiązane tematy

Te działy łączą się z tematem „Algorytmy zaawansowane” – przećwicz je w Quizie.