Algorytm i program: przepis krok po kroku (i co znaczy „wykonalny")

🎯 Po co Ci to?

To jednostka o pojęciu, które jest sercem informatyki i punktem, w którym za chwilę rozejdą się dwie drogi całej tej książki. Algorytm to przepis na rozwiązanie problemu. Klasyczne programowanie polega na tym, że przepis wymyśla człowiek. Uczenie maszynowe (Dział 3 i dalej) polega na tym, że przepis znajduje maszyna. Żeby zobaczyć, jak wielka to różnica, trzeba najpierw dokładnie wiedzieć, czym przepis jest.

✅ Czego się nauczysz

Po tej lekcji potrafisz:

• odróżnić algorytm od programu;
• wymienić trzy typy elementarnych instrukcji, na jakie rozkłada się każdy program;
• zapisać prosty algorytm w postaci ponumerowanych kroków (pseudokodu);
• wyjaśnić, co znaczy, że algorytm jest „wykonalny", i podać przykład zadania, dla którego nikt nie potrafi napisać algorytmu.

🔁 Przypomnij sobie

Z Jednostki 2.2: programowanie to wysyłanie maszynie jednoznacznych poleceń. Z Jednostki 1.3: mechanizacja myślenia to przekonanie, że rozumowanie da się rozłożyć na jednoznaczne, powtarzalne kroki. Algorytm jest właśnie takim rozłożeniem — i to nie metaforycznym, a całkiem dosłownym.

📘 Wyjaśnienie

Programowanie to wprowadzanie instrukcji, które mówią komputerowi, co ma robić krok po kroku, zgodnie z intencją programistki. Zbiór takich instrukcji nazywa się programem komputerowym. I choć instrukcje zawarte w programie potrafią być bardzo złożone, a profesjonalne oprogramowanie może składać się nawet z milionów linii kodu, to zawsze kod ten można rozłożyć na prostsze instrukcje postaci:

• Zrób to!
• Jeżeli jest tak a tak, zrób to, w przeciwnym razie zrób co innego!
• Wykonaj to 10 razy!

To wszystko. Sekwencja, warunek i powtórzenie — trzy klocki, z których zbudowany jest każdy program, jaki kiedykolwiek napisano, od kalkulatora po model językowy.

📐 DEFINICJA — program komputerowy: zbiór instrukcji, które mówią komputerowi, co ma robić krok po kroku, zgodnie z intencją programisty lub programistki.

Po ludzku: przepis zapisany w języku, który maszyna potrafi wykonać. Czym to NIE jest: program to nie opis celu („zrób streszczenie"), a opis drogi do celu.

Algorytm to nie to samo co program

Zanim napiszesz program, musisz wiedzieć, jak rozwiązać problem. Ta wiedza — uporządkowana w skończony ciąg jednoznacznych kroków — to algorytm.

📐 DEFINICJA — algorytm: skończony, jednoznaczny ciąg kroków prowadzący od danych wejściowych do rozwiązania problemu.

Po ludzku: przepis. Niezależny od języka, w jakim go zapiszesz, i od maszyny, która go wykona. Czym to NIE jest: algorytm to nie kod. Ten sam algorytm zapiszesz w Pythonie, w Javie, po polsku na kartce i wykonasz w głowie.

Różnica jest jak między przepisem na ciasto a upieczonym ciastem: algorytm jest ideą rozwiązania, program — jej zapisem w konkretnym języku, gotowym do wykonania przez maszynę. Algorytm dzielenia pisemnego znasz ze szkoły podstawowej i wykonujesz go ołówkiem; nikt nie musi go dla Ciebie kompilować.

Dobry algorytm ma cztery cechy:

1. skończoność — kończy się po skończonej liczbie kroków (przepis „mieszaj, aż zgęstnieje" nie jest algorytmem, jeśli nigdy nie zgęstnieje);
2. jednoznaczność — każdy krok da się wykonać tylko na jeden sposób („dodaj sól do smaku" nie jest jednoznaczne);
3. określone dane wejściowe i wynik — wiadomo, co dostajesz i co ma wyjść;
4. wykonalność — każdy krok jest realnie do zrobienia przez wykonawcę („odgadnij liczbę, o której myśli sąsiad" nie jest wykonalne).

💭 Pomyśl: Zapisz w ponumerowanych krokach algorytm znajdowania największej liczby na liście dziesięciu liczb — tak dokładnie, żeby wykonał go ktoś, kto nie wie, po co to robi. Ile kroków Ci wyszło?

Sprawdź odpowiedź

Typowe rozwiązanie ma trzy kroki i jedną pętlę:

1. Zapamiętaj pierwszą liczbę z listy jako „największa dotąd".
2. Dla każdej kolejnej liczby z listy: jeżeli jest większa niż „największa dotąd", zapamiętaj ją jako nową „największą dotąd".
3. Gdy lista się skończy, podaj „największą dotąd" jako wynik.

Zwróć uwagę, że użyłeś dokładnie trzech klocków: sekwencji (kroki 1–3), warunku („jeżeli jest większa") i powtórzenia („dla każdej kolejnej"). Zauważ też, czego tu nie ma: żadnej wiedzy o tym, czym są liczby ani po co szukamy największej. Wykonawca może być całkowicie bezmyślny — i to jest cecha, nie wada.

Pseudokod: przepis dla człowieka, prawie dla maszyny

Zapis, jakiego użyłeś powyżej — ponumerowane, jednoznaczne kroki po polsku — nazywa się pseudokodem. Jest wygodny, bo pozwala myśleć o algorytmie bez walki ze składnią konkretnego języka. W tej książce będziemy z niego korzystać zawsze, gdy pojawi się procedura warta rozpisania (na przykład przy uczeniu sieci neuronowej w Dziale 11).

Jeśli zdecydujesz się na naukę programowania, do czego serdecznie zachęcam, zaczniesz od tych prostych instrukcji i sukcesywnie będziesz uczyć się składać je w większe programy.

Kiedy przepisu nie ma

I tu dochodzimy do sedna. Dla ogromnej liczby zadań algorytm da się wymyślić: posortowanie listy, obliczenie pierwiastka, znalezienie najkrótszej drogi na mapie, sprawdzenie poprawności numeru PESEL. Ale spróbuj napisać jednoznaczny ciąg kroków, który dla dowolnego zdjęcia rozstrzygnie, czy jest na nim kot.

Zaczniesz od „jeśli ma wąsy" — tylko jak wykryć wąsy w tablicy liczb opisujących piksele? „Jeśli ma trójkątne uszy" — a kot odwrócony tyłem? Śpiący? Za mgłą? Czarny kot na czarnym tle? Po kilkudziesięciu regułach zorientujesz się, że każda ma wyjątki, a wyjątki mają wyjątki. Nie chodzi o to, że jesteś słabym programistą. Chodzi o to, że wiedza potrzebna do tego zadania jest w Tobie niejawna — rozpoznajesz kota natychmiast i nie potrafisz powiedzieć, na jakiej podstawie.

To jest dokładnie ta granica, o którą rozbiła się symboliczna AI z Części II (Dział 7 — systemy ekspertowe i dwie zimy AI). I to jest powód, dla którego wymyślono podejście odwrotne: skoro nie umiemy zapisać przepisu, dajmy maszynie tysiące przykładów i pozwólmy jej przepis znaleźć samodzielnie. Tym zajmie się cały Dział 3 i cała Część III.

⚠️ Uwaga, pułapka

„Algorytm" bywa dziś używany jako straszak: „algorytm mediów społecznościowych zdecydował", „to wina algorytmu". Brzmi jak byt autonomiczny, podejmujący decyzje. Tymczasem algorytm to przepis — sam z siebie nie chce niczego. Jeśli serwis pokazuje Ci treści, które Cię irytują, to nie dlatego, że algorytm coś postanowił, ale dlatego, że ktoś ustalił cel (na przykład „maksymalizuj czas na stronie"), a przepis ten cel realizuje. Pytanie „kto ustawił cel i dlaczego" jest zawsze ciekawsze niż „co zrobił algorytm". Wrócimy do tego w Dziale 20.

📐 Definicje tej lekcji

• Algorytm — skończony, jednoznaczny ciąg kroków od danych wejściowych do rozwiązania.
• Program komputerowy — zbiór instrukcji mówiących komputerowi, co robić krok po kroku.
• Pseudokod — zapis algorytmu w jednoznacznych krokach języka naturalnego, niezależny od języka programowania.
• Sekwencja, warunek, powtórzenie — trzy elementarne konstrukcje, z których zbudowany jest każdy program.
• Wykonalność — cecha algorytmu: każdy krok jest realnie do zrobienia przez wykonawcę.

📌 Najważniejsze w pigułce

• Algorytm to przepis; program to przepis zapisany w języku wykonywalnym przez maszynę.
• Każdy program rozkłada się na trzy klocki: zrób to, sprawdź warunek, powtórz.
• Dobry algorytm jest skończony, jednoznaczny, ma określone wejście i wyjście oraz jest wykonalny.
• Dla wielu ludzkich umiejętności (rozpoznanie kota, ocena emocji) nie potrafimy zapisać algorytmu — nasza wiedza jest niejawna.
• Ta niemożność jest historycznym powodem powstania uczenia maszynowego.

🎒 Zadania

Zadanie 2.3.1. Zapisz w pseudokodzie algorytm, który dla podanego roku rozstrzyga, czy jest przestępny (reguła: rok jest przestępny, jeśli dzieli się przez 4, chyba że dzieli się przez 100 i nie dzieli się przez 400).

Pokaż rozwiązanie

1. Weź rok R.
2. Jeżeli R dzieli się przez 400 — odpowiedz „przestępny" i zakończ.
3. W przeciwnym razie, jeżeli R dzieli się przez 100 — odpowiedz „nieprzestępny" i zakończ.
4. W przeciwnym razie, jeżeli R dzieli się przez 4 — odpowiedz „przestępny" i zakończ.
5. W przeciwnym razie odpowiedz „nieprzestępny".

Zauważ, że kolejność warunków ma znaczenie: gdybyś zaczął od dzielenia przez 4, musiałbyś potem cofać decyzję. To typowa własność algorytmów — poprawność zależy od porządku kroków.

Zadanie 2.3.2. Wskaż, która z cech dobrego algorytmu jest naruszona w każdym z poniższych „przepisów": (a) „Mieszaj składniki, aż uzyskasz idealną konsystencję"; (b) „Dodaj przyprawy do smaku"; (c) „Wybierz najlepszą inwestycję na najbliższe dziesięć lat"; (d) „Powtarzaj krok 2, dopóki nie znudzi Ci się liczenie".

Sprawdź odpowiedź

(a) jednoznaczność (i pośrednio skończoność) — „idealna konsystencja" nie jest zdefiniowana; (b) jednoznaczność — „do smaku" zależy od wykonawcy; (c) wykonalność — wymaga wiedzy o przyszłości, której nikt nie ma; (d) skończoność i jednoznaczność — warunek zakończenia zależy od stanu emocjonalnego wykonawcy, więc dwa wykonania dadzą różny wynik.

Zadanie 2.3.3. Wybierz jedną czynność, którą wykonujesz codziennie i uważasz za łatwą (na przykład rozpoznanie, czy koleżanka jest w złym nastroju). Spróbuj zapisać dla niej algorytm w pięciu krokach. Następnie wypisz co najmniej trzy sytuacje, w których Twój algorytm zawiedzie, i napisz, czego to dowodzi.

Pokaż rozwiązanie

Przykład: 1. Spójrz na twarz. 2. Jeżeli kąciki ust opuszczone — zły nastrój. 3. Jeżeli mówi mniej niż zwykle — zły nastrój. 4. Jeżeli nie odpowiada na żarty — zły nastrój. 5. W przeciwnym razie — dobry nastrój.

Kontrprzykłady: koleżanka jest zmęczona, nie smutna; ukrywa zły nastrój i żartuje więcej niż zwykle; milczy, bo się koncentruje; ma taką mimikę na stałe; jesteście na rozmowie wideo o słabej jakości.

Wniosek: rozpoznajesz nastrój, korzystając z ogromnej liczby subtelnych, kontekstowych przesłanek, których nie potrafisz w pełni wyartykułować. Tej wiedzy nie da się przepisać na reguły — trzeba by ją odtworzyć z przykładów. To dokładnie punkt wyjścia uczenia maszynowego (Dział 3) i jednocześnie powód, dla którego takie systemy popełniają błędy tam, gdzie człowiek ich nie popełnia.

🔍 Sprawdź, czy umiesz

• [ ] Odróżnić algorytm od programu na własnym przykładzie.
• [ ] Wymienić trzy typy elementarnych instrukcji.
• [ ] Wymienić cztery cechy dobrego algorytmu.
• [ ] Zapisać prosty algorytm w pseudokodzie.
• [ ] Wyjaśnić, dlaczego dla rozpoznania kota na zdjęciu nie potrafimy napisać algorytmu.

---