Przejdź do treści
Matura 2027 • Zadania praktyczne

Analiza Algorytmów na Suchej Kartce

Przed Tobą 6 zadań zamkniętych. Sprawdź, czy Twoja wiedza z działu Analiza Algorytmów na Suchej Kartce wystarczy, by zdobyć 100% punktów w części pierwszej.

Pytanie 1 / 6Algorytmika i Logika
Algorytm zachłanny, niezależnie od instancji problemu, znajduje zawsze rozwiązanie optymalne.
▸ Wszystkie 6 pytań z wyjaśnieniamiRozwiń, jeśli wolisz przejrzeć zestaw bez rozwiązywania testu.

Złożoność czasowa, struktury danych (LIFO/FIFO), NWD i własności optymalnych algorytmów (Dry Run).

1.Algorytm zachłanny, niezależnie od instancji problemu, znajduje zawsze rozwiązanie optymalne.

  • A.Prawda
  • B.Fałsz— poprawna
Dlaczego: Algorytmy zachłanne podejmują lokalnie najlepsze decyzje, co w skomplikowanych problemach nie zawsze prowadzi do globalnego optimum (np. problem wydawania reszty przy nietypowych nominałach).

2.Stos jest strukturą danych typu LIFO.

  • A.Prawda— poprawna
  • B.Fałsz
Dlaczego: LIFO to skrót od 'Last In, First Out', czyli ostatni dodany element jest zdejmowany jako pierwszy, co dokładnie definiuje działanie stosu.

3.Problem sortowania nn liczb ma złożoność O(n2)O(n^2).

  • A.Prawda
  • B.Fałsz— poprawna
Dlaczego: Tylko najprostsze algorytmy (np. bąbelkowe) mają taką złożoność. Sam problem da się rozwiązać znacznie szybciej – optymalne algorytmy (Merge Sort, Quick Sort) działają w czasie O(nlog⁡n)O(n \log n).

4.Złożoność wyszukiwania binarnego w posortowanej nn-elementowej tablicy to O(log⁡n)O(\log n).

  • A.Prawda— poprawna
  • B.Fałsz
Dlaczego: W każdym kroku algorytm ten dzieli przeszukiwany przedział na pół, co z definicji gwarantuje logarytmiczny czas działania operacji.

5.Niech funkcja M(a,b)M(a, b) wyznacza Największy Wspólny Dzielnik (NWD). Dla każdej liczby całkowitej x>1x > 1 zachodzi równość M(x,x)=1M(x, x) = 1.

  • A.Prawda
  • B.Fałsz— poprawna
Dlaczego: Największym wspólnym dzielnikiem dwóch identycznych liczb jest zawsze dokładnie ta sama liczba. Zatem NWD(x,x)=xNWD(x, x) = x, a nie 11.

6.Niech funkcja M(a,b)M(a, b) wyznacza Największy Wspólny Dzielnik (NWD). Dla każdej liczby całkowitej x>1x > 1 wartość M(x,x+1)M(x, x+1) jest liczbą parzystą.

  • A.Prawda
  • B.Fałsz— poprawna
Dlaczego: Dwie bezpośrednio sąsiadujące ze sobą liczby całkowite są zawsze względnie pierwsze. Ich NWD wynosi więc 11, a jedynka jest liczbą nieparzystą.

O czym musisz pamiętać w zadaniach Algorytmika i Logika?

Zadania w Arkuszu I na maturze bardzo często wymagają doskonałego czytania ze zrozumieniem (analiza pseudokodu), znajomości własności matematycznych i swobody w konwersjach systemów liczbowych.

  • ✓ Opanuj szacowanie złożoności obliczeniowej. Rozróżniaj złożoność rzędu $O(1)$, $O(\log n)$, $O(n)$ i $O(n^2)$.
  • ✓ Systemy liczbowe to pewniak maturalny. Ćwicz dodawanie, odejmowanie i mnożenie w systemie binarnym i heksadecymalnym.
  • ✓ Logika i bramki – pamiętaj o prawach de Morgana, pomogą Ci one szybko uprościć skomplikowane wyrażenia logiczne.

Strategia Maturalna (Algorytmika i Logika):

"Gdy masz przed sobą pseudokod i musisz przewidzieć jego wynik – nigdy nie zgaduj z samej nazwy zmiennych! Zawsze na marginesie narysuj tzw. tabelkę zmiennych. Prześledź na sucho pierwsze 2-3 obiegi pętli, zapisując, jak zmieniają się wartości. To najpewniejszy sposób na uniknięcie głupiego błędu w indeksowaniu (np. przesunięcia o 1)."

To nie koniec powtórki!

Przećwicz kolejny zestaw pytań i utrwal swoją wiedzę algorytmiczną.

Dalej: Reprezentacja Danych - Quiz z teorii →
Wolisz zadania przy komputerze? Zobacz Pewniaki Bazodanowe →