Algorytm — przepis, który nie zostawia wątpliwości

🎯 Po co Ci to?

Przepis babci mówi: „dodaj szczyptę soli i piecz, aż będzie gotowe". Babcia wie, ile to szczypta i po czym poznać gotowość — przepis działa, bo wykonawca myśli. Teraz wyobraź sobie, że ten sam przepis wykonuje bankomat. „Wypłać trochę pieniędzy, jak uznasz, że klient zasługuje"? Maszyna nie uznaje. Potrzebuje przepisu doprowadzonego do postaci, w której nie ma czego interpretować. Taki przepis to algorytm — i jest głównym bohaterem całej informatyki.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

rozpoznać, czy przepis jest algorytmem (i wskazać, czego mu brakuje, jeśli nie jest);
wymienić własności dobrego algorytmu: jednoznaczność, skończoność, ogólność;
sprawdzić poprawność algorytmu na przykładowych danych — w tym na danych brzegowych.

🔁 Przypomnij sobie

Z jednostki 1.1: specyfikacja mówi, co ma być zrobione. Algorytm to odpowiedź na pytanie jak — ale wciąż bez ani jednej linijki kodu.

📘 Wyjaśnienie

💭 Pomyśl: Instrukcja gry w „zgadnij liczbę": „Pomyśl liczbę. Ja będę zgadywał, a ty mów, czy za dużo, czy za mało. I tak aż zgadnę." Czy komputer mógłby wykonać rolę zgadującego według tej instrukcji? Czego brakuje?

Sprawdź odpowiedź

Brakuje reguły, jaką liczbę zgadywać. „Będę zgadywał" nie mówi: od czego zacząć? co zrobić z odpowiedzią „za dużo"? Człowiek to sobie dopowie; maszyna stanie. Wystarczy jedno zdanie — „zgaduj zawsze środek przedziału, który pozostał" — i instrukcja staje się wykonywalna mechanicznie. Zapamiętaj ten pomysł: wróci w jednostce 1.4 jako metoda połowienia.

📐 DEFINICJA — algorytm: skończony ciąg jednoznacznie określonych kroków, który dla każdych poprawnych danych wejściowych prowadzi do wyniku zgodnego ze specyfikacją.

Po ludzku: przepis tak dokładny, że wykona go ktoś (lub coś), kto w ogóle nie rozumie, po co to robi. Czym NIE jest: programem. Algorytm to pomysł, przepis; program to jego zapis w konkretnym języku. Ten sam algorytm można zaprogramować w Pythonie, w arkuszu kalkulacyjnym albo wykonać ręcznie na kartce.

Z definicji wynikają trzy własności, które odróżniają algorytm od dobrej rady:

Jednoznaczność — każdy krok ma dokładnie jedną interpretację. „Weź dużą liczbę" odpada; „weź największą liczbę z listy" — zostaje.
Skończoność — algorytm musi się zatrzymać. Przepis „powtarzaj, aż zadziała" bez gwarancji, że kiedyś zadziała, algorytmem nie jest.
Ogólność — algorytm rozwiązuje klasę problemów, nie jeden przypadek. „Jak znaleźć największą z liczb 3, 8, 5" to odpowiedź (8), nie algorytm; algorytm znajduje największą z dowolnych trzech liczb.

Zobacz to na przykładzie. Specyfikacja: dane — trzy liczby $a$, $b$, $c$; wynik — największa z nich.

Algorytm (lista kroków):

Przyjmij, że kandydatem na największą jest $a$.
Jeżeli $b$ jest większe od kandydata, kandydatem zostaje $b$.
Jeżeli $c$ jest większe od kandydata, kandydatem zostaje $c$.
Podaj kandydata jako wynik i zakończ.

Każdy krok jest mechaniczny: porównaj dwie liczby, ewentualnie podmień kandydata. Żadnej inwencji, żadnego „jak uznasz".

Poprawność sprawdzamy na danych. Wykonaj algorytm ręcznie — to najważniejszy nawyk z całej tej książki:

dane $a, b, c$	po kroku 1	po kroku 2	po kroku 3	wynik
3, 8, 5	kandydat = 3	kandydat = 8	kandydat = 8	8 ✓
9, 2, 4	kandydat = 9	kandydat = 9	kandydat = 9	9 ✓
2, 2, 2	kandydat = 2	kandydat = 2	kandydat = 2	2 ✓

Trzeci wiersz to dane brzegowe: wszystkie liczby równe. Algorytmy najczęściej psują się właśnie na brzegach — dlatego do zestawu testów zawsze dokładamy przypadki „dziwne": równe wartości, zera, liczby ujemne, najmniejsze i największe dopuszczalne dane.

💭 Pomyśl: Ktoś „ulepszył" krok 2 na: „Jeżeli $b$ jest większe lub równe kandydatowi, kandydatem zostaje $b$". Czy algorytm dalej jest poprawny?

Sprawdź odpowiedź

Tak — wynik będzie ten sam dla każdych danych, bo podmiana kandydata na równą mu liczbę niczego nie psuje. To ciekawa lekcja: różne algorytmy (i różne wersje kroków) mogą być tak samo poprawne. Poprawność ocenia się po zgodności wyniku ze specyfikacją, nie po tym, czy kroki wyglądają tak jak u kolegi.

🐞 Znajdź błąd

Algorytm ma znajdować największą z listy liczb (nie trzech — dowolnie wielu):

Przyjmij, że kandydatem jest 0.
Dla każdej liczby z listy: jeżeli jest większa od kandydata, zostaje kandydatem.
Podaj kandydata i zakończ.

Dla listy 4, 7, 2 daje 7. Działa? Znajdź dane, dla których kłamie.

Sprawdź odpowiedź

Lista samych liczb ujemnych, np. −5, −2, −9. Żadna nie jest większa od 0, więc algorytm zwróci… 0 — liczbę, której w ogóle nie ma na liście. Błąd tkwi w kroku 1: kandydatem nie może być wymyślona wartość, tylko pierwsza liczba z listy. To klasyk wśród błędów i wzorcowy przykład, dlaczego testujemy na danych brzegowych, a nie tylko „miłych".

🕰️ Skąd to wiemy

Słowo „algorytm" pochodzi od nazwiska perskiego uczonego al-Chwarizmiego (IX wiek), którego podręcznik rachunku na cyfrach indyjskich Europa czytała po łacinie jako dzieło „Algorismi". Jego algorytmy — jak pisemne dodawanie, którego uczyłeś się w podstawówce — były przeznaczone dla ludzi. Musiało minąć tysiąc lat, zanim pojawiła się maszyna zdolna je wykonywać; przepisy były gotowe wcześniej niż wykonawca.

🛠️ Teraz Ty

Ułóż listę kroków dla algorytmu sprawdzającego, czy rok $r$ jest przestępny (specyfikację masz z jednostki 1.1). Potem wykonaj go ręcznie dla lat: 2024, 1900, 2000, 2023. Jeśli choć jeden wynik się nie zgadza — popraw kroki, nie wyniki.

📐 Definicje tej lekcji

Algorytm — skończony ciąg jednoznacznych kroków prowadzący od danych do wyniku zgodnego ze specyfikacją.
Dane brzegowe — dane z „krawędzi" dopuszczalnego zakresu (zera, wartości równe, skrajne, puste), na których algorytmy psują się najczęściej.

📌 Najważniejsze w pigułce

Algorytm ≠ program: algorytm to przepis, program to jego zapis w języku maszyny.
Trzy własności: jednoznaczność kroków, gwarancja zatrzymania, ogólność (klasa problemów, nie jeden przykład).
Poprawność sprawdzasz, wykonując algorytm ręcznie — zwłaszcza na danych brzegowych.

🎒 Zadania

Które z przepisów są algorytmami, a którym czego brakuje? (a) „Mieszaj, aż masa będzie puszysta." (b) „Podziel liczbę przez 2; jeśli wynik jest całkowity, napisz «parzysta», w przeciwnym razie «nieparzysta»." (c) „Wybieraj drogę, która wygląda na szybszą."

Wskazówka i odpowiedź

(a) niejednoznaczne („puszysta" — wg kogo?) i bez gwarancji końca. (b) algorytm: kroki jednoznaczne, zawsze się kończy, działa dla każdej liczby całkowitej. (c) niejednoznaczne („wygląda na szybszą" wymaga oceny, której nie zdefiniowano) — choć zapowiada ciekawą rodzinę metod „mniej więcej dobrych", o których w jednostce 1.6.

Wykonaj ręcznie algorytm „największa z trzech" dla danych $a=5$, $b=5$, $c=1$, notując kandydata po każdym kroku. Potem odpowiedz: czy algorytm kiedykolwiek porównuje $b$ z $c$? Dlaczego nie musi?

Wskazówka i odpowiedź

Kandydat: 5 → 5 → 5, wynik 5. Algorytm nie porównuje $b$ z $c$ bezpośrednio — nie musi, bo kandydat po kroku 2 jest już większą (lub równą) z pary $a, b$; krok 3 porównuje z nim $c$, więc pośrednio „pamięta" oba wcześniejsze porównania. Przechowywanie częściowego wyniku zamiast porównywania wszystkiego ze wszystkim to pomysł, który wróci wielokrotnie.

Ułóż algorytm (listę kroków) liczący, ile liczb parzystych jest na danej liście. Przetestuj go na: (a) 2, 4, 6; (b) 1, 3, 5; (c) liście pustej. Co zwraca w przypadku (c) i czy to sensowny wynik?

Wskazówka i odpowiedź

Np.: 1. Licznik ← 0. 2. Dla każdej liczby z listy: jeśli dzieli się przez 2 bez reszty, zwiększ licznik o 1. 3. Podaj licznik. Wyniki: (a) 3, (b) 0, (c) 0. Zero dla pustej listy jest poprawne: „na pustej liście jest zero parzystych". Zauważ, że algorytm obsłużył brzeg bez żadnego specjalnego kroku — dobrze zaprojektowana pętla często załatwia brzegi za darmo.

🔍 Sprawdź, czy umiesz

Podać przepis z życia, który NIE jest algorytmem, i doprowadzić go do postaci algorytmu.
Wyjaśnić, czym różni się algorytm od programu.
Zaproponować trzy zestawy danych testowych (w tym jeden brzegowy) dla algorytmu „policz średnią z listy".

Ucz się tej jednostki z asystentem