Dziel problem na kawałki

🎯 Po co Ci to?

Nikt na świecie nie umie „napisać systemu bankowego". Serio — to zadanie jest za duże dla każdej pojedynczej głowy. A jednak systemy bankowe istnieją. Sekret: nikt ich nie pisze w całości. Ktoś podzielił problem na logowanie, przelewy, historię operacji; przelewy na sprawdzenie salda, księgowanie, powiadomienie; i tak dalej, aż na dole zostały kawałki na tyle małe, że da się je ogarnąć jednym spojrzeniem. Ta technika — najpotężniejsza broń informatyki — nazywa się dekompozycją. Dziś ją poznasz, a przy okazji spotkasz po raz pierwszy trzy pomysły, które wrócą w tej książce jako osobne działy.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • rozłożyć problem na podproblemy i narysować jego drzewo;
  • scharakteryzować metodę połowienia i wyjaśnić, skąd bierze się jej szybkość;
  • opisać na przykładach, czym jest podejście zachłanne i myślenie rekurencyjne.

📘 Wyjaśnienie

📐 DEFINICJA — dekompozycja: podział problemu na mniejsze podproblemy, z których każdy można rozwiązać osobno, a z rozwiązań złożyć rozwiązanie całości.

Po ludzku: nie jedz słonia w całości — pokrój go. Czym NIE jest: odkładaniem problemu na później. Dekompozycja wymaga też pomysłu, jak kawałki skleić z powrotem.

Weź problem szkolny: „przygotuj gazetkę klasową na koniec roku". W całości — paraliżuje. Po dekompozycji:

                     GAZETKA KLASOWA
          ┌───────────────┼───────────────┐
       treści          oprawa          wydanie
     ┌────┴────┐      ┌───┴───┐       ┌───┴───┐
  zebrać    napisać  zdjęcia  skład   druk   kolportaż
  wspomnienia teksty

Każdy liść tego drzewa to zadanie, które może wziąć jedna osoba — i które ma szansę być skończone do piątku. Dokładnie tak samo informatyk kroi program na funkcje (poznasz je w dziale 3): każda robi jedną małą rzecz, a program jest drzewem takich klocków.

Dekompozycja to rama. A teraz trzy słynne pomysły na rozwiązywanie podproblemów — na razie w wersji „do posmakowania", każdy dostanie później własny dział.

Pomysł 1: połowienie. Wróćmy do zgadywanki z jednostki 1.2: ktoś myśli liczbę od 1 do 100, Ty pytasz, a on mówi „za dużo / za mało / trafione".

💭 Pomyśł: Strategia A: pytaj po kolei — 1? 2? 3?… Strategia B: pytaj zawsze o środek pozostałego przedziału. Ile pytań najwyżej potrzebuje każda strategia, żeby na pewno trafić?

Sprawdź odpowiedź

Strategia A: w najgorszym razie 100 pytań (pomyślana liczba to 100). Strategia B: pierwsze pytanie „50?" zostawia najwyżej 50 kandydatów, drugie — 25, potem 13, 7, 4, 2, 1. Siedem pytań zawsze wystarcza. Sekret: każde pytanie przepoławia liczbę możliwości, a połowienie zabija wielkie liczby zdumiewająco szybko — po $k$ pytaniach zostaje $100/2^k$ kandydatów.

To jest metoda połowienia: jeśli po jednym kroku umiesz odrzucić połowę możliwości, to nawet z miliona kandydatów zostanie jeden po dwudziestu krokach. Na tym pomyśle stoi wyszukiwanie binarne (dział 6), rozwiązywanie równań przez połowienie przedziału (dział 7) i — jak zobaczysz w dziale 12 — szybkość baz danych.

Pomysł 2: podejście zachłanne. Masz wydać 76 groszy reszty monetami 50, 20, 10, 5, 2, 1 gr, możliwie najmniejszą liczbą monet. Naturalny odruch: bierz zawsze największą monetę, która się mieści. 50 (zostaje 26), 20 (zostaje 6), 5 (zostaje 1), 1. Cztery monety — i to jest optimum.

📐 DEFINICJA — podejście zachłanne: strategia, która w każdym kroku wybiera opcję najlepszą w tej chwili, nie analizując dalszych konsekwencji.

Po ludzku: bierz największy kęs, jaki się mieści, i nie oglądaj się za siebie. Czym NIE jest: metodą zawsze skuteczną. Dla polskich nominałów wydawanie reszty zachłannie daje optimum; przy nominałach 1, 3, 4 i reszcie 6 zachłanność bierze 4+1+1 (trzy monety), a da się 3+3 (dwie). Kiedy zachłanność jest bezpieczna, a kiedy zdradza — to jeden z tematów działu 8.

Pomysł 3: myślenie rekurencyjne. Spójrz jeszcze raz na drzewo gazetki. Zadanie „treści" rozwiązaliśmy… dokładnie tą samą metodą, co całą gazetkę: podzieliliśmy je na mniejsze. A gdyby „napisać teksty" wciąż było za duże — podzielilibyśmy i je. Metoda wywołuje samą siebie na coraz mniejszych kawałkach, aż kawałki staną się trywialne. To jest myślenie rekurencyjne. Brzmi jak sztuczka? W dziale 7 zobaczysz, że to jedna z najgłębszych idei informatyki — i że rysuje fraktale.

🌍 Powiązania

Dekompozycję znasz z matematyki (zadanie z gwiazdką kroisz na „najpierw policzę pole, potem obwód"), z historii (praca nad projektem: źródła → notatki → prezentacja) i z każdej kuchni świata (mise en place: najpierw przygotuj składniki, potem gotuj). Informatyka niczego tu nie wymyśliła — tylko potraktowała pomysł śmiertelnie poważnie i zrobiła z niego przemysł.

🛠️ Teraz Ty

Narysuj drzewo dekompozycji dla problemu „zorganizuj klasową wycieczkę trzydniową". Minimum trzy poziomy. Potem oznacz gwiazdką te liście, które dałoby się powierzyć komputerowi (np. „porównaj ceny noclegów"), a kółkiem te, które wymagają człowieka („przekonaj wychowawcę"). Zobaczysz granicę między tym, co algorytmiczne, a tym, co (na razie) nie.

📐 Definicje tej lekcji

  • Dekompozycja — podział problemu na podproblemy rozwiązywane osobno, z pomysłem na sklejenie rozwiązań.
  • Metoda połowienia — technika odrzucania połowy możliwości w każdym kroku.
  • Podejście zachłanne — wybieranie w każdym kroku opcji najlepszej lokalnie, bez patrzenia w przód.
  • Myślenie rekurencyjne — rozwiązywanie problemu tą samą metodą zastosowaną do jego mniejszych kopii.

📌 Najważniejsze w pigułce

  • Wielkich problemów nie rozwiązuje się w całości — kroi się je, aż kawałki zmieszczą się w głowie.
  • Połowienie: po $k$ krokach zostaje $1/2^k$ możliwości — dlatego 7 pytań wystarcza na 100 liczb, a 20 na milion.
  • Zachłanność jest szybka i naturalna, ale nie zawsze optymalna; rekurencja to dekompozycja, która wywołuje samą siebie.

🎒 Zadania

  1. Ile pytań „tak/nie" wystarczy, żeby na pewno odgadnąć liczbę od 1 do 1000? A od 1 do miliona? (Wskazówka: licz połowienia.)
Wskazówka i odpowiedź

1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1: dziesięć połowień, bo $2^{10} = 1024 \ge 1000$. Dla miliona: $2^{20} = 1,048,576 \ge 10^6$, więc 20 pytań. Podwojenie „mocy" pytań (z 10 do 20) obsłużyło tysiąckrotnie większy zakres — to połowienie w pełnej krasie. W jednostce 2.7 nadamy tej obserwacji imię i nazwisko.

  1. Wydaj zachłannie resztę 99 gr monetami 50, 20, 10, 5, 2, 1. Ile monet wyszło? Czy da się mniej?
Wskazówka i odpowiedź

50 (zostaje 49), 20 (29), 20 (9), 5 (4), 2 (2), 2 (0) — sześć monet. Mniej się nie da: to optimum, a dla nominałów używanych w Polsce zachłanność zawsze je znajduje (dlaczego „polskie" nominały są takie grzeczne — dowiesz się w dziale 8).

  1. Wskaż w codziennym życiu jedną sytuację, w której strategia zachłanna („bierz to, co teraz najlepsze") prowadzi do złego wyniku w dłuższej perspektywie. Opisz ją w dwóch zdaniach.
Wskazówka i odpowiedź

Przykłady: nauka „zachłannie" wieczorem przed sprawdzianem (lokalnie: maksimum czasu na inne rzeczy; globalnie: brak trwałej wiedzy); wybieranie zawsze najkrótszej kolejki w sklepie, w której akurat ktoś płaci bilonem; wydawanie kieszonkowego na pierwszą atrakcję z brzegu. Sedno: zachłanność ignoruje przyszłe konsekwencje — czasem bezkarnie, czasem nie.

🔍 Sprawdź, czy umiesz

  • Narysować drzewo dekompozycji dowolnego dużego zadania z życia szkoły.
  • Wyjaśnić młodszemu koledze, dlaczego zgadywanie „od środka" bije zgadywanie „po kolei".
  • Podać przykład, gdzie zachłanność działa, i taki, gdzie zawodzi.

Ucz się tej jednostki z asystentem