Jako ludzie dążymy do wypracowania najbardziej skutecznych metod rozwiązywania problemów, z którymi się stykamy. Stawiamy pytania: co zrobić, żeby osiągnąć cel w przewidywalny sposób? jak wykonać pracę szybciej lub mniejszym kosztem? Odpowiadając, tworzymy wzorce rozwiązywania problemów i realizowania zadań. Wzorce te możemy nazwać algorytmami życia codziennego.

Algorytmy w życiu codziennym

Kiedy wyjaśniamy, czym jest algorytm, często odwołujemy się do przepisu kulinarnego, który można traktować jako listę kroków prowadzących do ugotowania jakiegoś dania. Podobnie w tym materiale przywoływaliśmy różne życiowe sytuacje, w których kolejne działania mają rozwiązywać jakieś problemy dnia codziennego. Czy można nazwać je algorytmami?

We właściwym znaczeniu „algorytm” jako opis sposobu osiągnięcia jakiegoś celu lub rozwiązania problemu musi cechować się precyzją. Oznacza to, że cel lub problem muszą być dokładnie określone. Realizujemy to, podając specyfikację problemu, na którą składają się dokładnie określone dane wejściowe oraz wynik (lub cel).

Czy przepis kulinarny spełnia te wymogi? W przepisach danymi wejściowymi są składniki spożywcze, ale często traktowane są wymiennie, a ich ilość nie jest precyzyjnie określona, np. zupa warzywna zawierać może trochę pora, ale nie musi, jeśli dodamy selera. Podobnie jest z przyprawami, które dodajemy, oraz ich ilością, często określaną miarą „szczypty”, co dla każdego oznacza coś innego. Podobnie jest z wynikiem – nie do końca jest on powtarzalny i przewidywalny, co zresztą wiemy z doświadczenia, kiedy jemy to samo danie przygotowane według tego samego przepisu, ale przez dwie różne osoby.

Podsumowując: możemy powiedzieć, że właściwe algorytmy badane w ramach nauki o nich – algorytmiki – są opisami sformalizowanymi, logicznymi i abstrakcyjnymi. Cechuje je poprawność, skończoność i efektywność. Wiele z nich to algorytmy optymalne, tzn. najlepsze w rozwiązywaniu danego problemu.

Kiedy natomiast mówimy o algorytmach w życiu codziennym, możemy mieć na myśli kilka rzeczy. Na przykład to, że podczas wykonywania różnych zwykłych czynności stosujemy podobne strategie jak w algorytmach: porównywanie, powtarzanie, dzielenie problemów na mniejsze czy intuicyjne szukanie rozwiązania. Możemy również mieć na myśli fakt, że życie codzienne jest źródłem algorytmów, ale i odwrotnie – myślenie algorytmiczne można świadomie wykorzystywać do rozwiązywania problemów w życiu codziennym. Informacje na temat tego ostatniego zagadnienia znajdziesz w e‑materiale Rozwiąż to inaczej, czyli myślenie komputacyjne i jego metodyPL2Yyi0mQRozwiąż to inaczej, czyli myślenie komputacyjne i jego metody.

Instrukcje krok po kroku

Przyjrzyjmy się myciu zębów. Możemy ją przedstawić w postaci listy kroków:

1. Weź szczoteczkę.

2. Nałóż 1 g pasty na szczoteczkę.

3. Myj zęby szczoteczką.

4. Wypłucz zęby 250 ml wody.

5. Wypłucz szczoteczkę.

6. Odłóż szczoteczkę.

R1S23ZgZTiwYF

Ilustracja przedstawia sześć kroków mycia zębów.
1: Dłoń z szczoteczką dłoni,
2: Szczoteczka z pastą do zębów,
3: Szczoteczka i zęby,
4: Szklanka z wodą.
5: Szczoteczka pod kranem z wodą,
6: Szczoteczka w szklance.

Przez całe życie uczymy się instrukcji, które wymagają wykonania krok po kroku ciągu operacji. Odnoszą się nie tylko do codziennych czynności, ale też urządzeń, np. ekspresu do kawy. Wymienić można również instrukcje budowania modelu z klocków, składania mebli itp. Cechą wspólną jest to, że są to listy kroków (czasem w formie instrukcji obrazkowych), które mają prowadzić do osiągnięcia jakiegoś rezultatu.

Niektóre listy są bardzo proste. W przypadku mycia zębów, upraszczając, lista polega na wykonaniu za każdym razem takiej samej sekwencjisekwencjasekwencji czynności w określonym porządku. To definicja algorytmu liniowegoalgorytm liniowyalgorytmu liniowego.

Podejmowanie wyboru

Równie często osiągnięcie jakiegoś celu wymaga podejmowania decyzji czy też dokonywania wyboru. Wtedy na liście kroków zobaczymy sformułowanie: „jeżeli …, to …”.

Gdy montujemy drzwiczki do szafki, możemy zdecydować, czy mają otwierać się na lewą czy prawą stronę. Inny przykład to wybór środka transportu, żeby dotrzeć do szkoły czy pracy. Możemy powiedzieć: jeżeli będzie padać, pojadę autobusem, w przeciwnym razie wybiorę rower.

Sposób podejmowania decyzji w problemach tego typu wymaga rozważenia co najmniej dwóch możliwości (może być ich więcej). Mamy wtedy do czynienia z algorytmami warunkowymialgorytm warunkowyalgorytmami warunkowymi, które podpowiadają, co zrobić, aby skutecznie osiągnąć cel w zależności od spełnienia jednego lub wielu warunków.

Powtarzanie

Rozważmy inną sytuację. Próbujemy zapamiętać listę słów z języka obcego. Jak wiemy, nie wystarczy przeczytać ich jeden raz, trzeba je powtórzyć co najmniej kilka razy. Podobnie jeżeli uprawiamy jakiś sport, musimy powtarzać ćwiczenia, żeby osiągnąć założoną sprawność. Powtarzanie, czyli iteracjaiteracjaiteracja, to jedna z technik algorytmicznych.

Porządkowanie

Porządkowanie, szeregowanie, sortowanie to synonimy oznaczające jedną z najczęściej wykonywanych przez nas czynności. Porządkujemy przecież wszystko: książki w bibliotece, towary w sklepie, materiały w składzie itd. Porządek ułatwia odnajdywanie rzeczy i informacji. Gdy zastanowimy się, w jaki sposób odbywa się proces porządkowania, zauważymy, że zazwyczaj wymaga on operacji porównywania i powtarzania.

Przyjrzyjmy się takiej czynności, jak ustawianie książek na pustej półce w porządku alfabetycznym (według nazwisk autorów). Po wzięciu pierwszej książki ze stosu i odstawieniu jej na półkę bierzemy ze stosu następną w kolejności, porównujemy nazwiska autorów, wyszukujemy właściwe miejsce w szeregu i wstawiamy tam książkę. Czynność powtarzamy dla każdej następnej książki. Być może nie zdajemy sobie sprawy, że takie postępowanie przypomina jeden z algorytmów sortowania, nazywany sortowaniem przez wstawianie.

Inny przykład to segregacja śmieci. Również w tej czynności występuje porównywanie umożliwiające zakwalifikowanie danego odpadu do odpowiedniej kategorii oraz powtarzanie tej operacji.

Wyszukiwanie

Załóżmy, że chcemy sprawdzić, czy w zbiorze znajduje się pewna książka, której nazwisko autora zaczyna się na literę C. Jeżeli zbiór jest nieuporządkowany, musimy zacząć przeglądać książki po kolei i w w najgorszym razie (czyli w tak zwanym przypadku pesymistycznym) dopiero po przejrzeniu wszystkich będziemy wiedzieli, że danej pozycji nie mamy w kolekcji. Jeżeli jednak książki są uporządkowane alfabetycznie według nazwisk autorów, to możemy zastosować inne podejście: na początku zawęzić poszukiwanie mniej więcej do połowy, czyli do zakresu A‑K, później do połówki tejże połowy, czyli zakresu A‑F itd. W ten sposób odpowiedź na pytanie, czy mamy w swoich zbiorach daną książkę, uzyskamy o wiele szybciej.

Kiedy uogólnimy opisaną metodę postępowania, zauważymy, że opiera się ona na podziale problemu wyjściowego na podproblemy, rozwiązaniu ich i powtarzaniu podziału aż do uzyskania odpowiedzi – tak właśnie działają algorytmy oparte na metodzie „dziel i zwyciężaj”dziel i zwyciężaj„dziel i zwyciężaj”. W algorytmach tych jedną z podstawowych operacji jest powtarzanie, które w niektórych przypadkach przyjmuje charakter rekurencji.

Rekurencja

Rekurencja polega na powtarzaniu. Przykład jej wykorzystania w życiu codziennym zaprezentował rosyjski informatyk Andriej Jerszow – jest to jedzenie kaszy.

Algorytm rekurencyjny w tym przypadku ma następującą postać: Jedz kaszę, a jeżeli talerz jest pusty, przerwij. W przeciwnym razie jedz kaszę.

Warto zwrócić uwagę, że aby samopowtarzanie się zakończyło, musi być określony warunek, zwany często warunkiem początkowym.

Przeanalizujmy jeszcze jeden przykład. Za pomocą palików i taśmy mamy wyznaczyć działkę budowlaną w kształcie kwadratu o boku równym 100 m. Możemy postąpić następująco: najpierw przejść prosty odcinek równy założonej długości boku działki i obrócić się o 90 stopni w prawo. Następnie, dopóki nie znajdziemy się w tym samym punkcie początkowym, powtarzać przejście i obrót.

Zapamiętajmy zatem, że rekurencja w naturalny sposób wspiera metodę „dziel i zwyciężaj” – podproblemy są rozwiązywane w taki sam sposób, ale dla mniejszej liczby elementów czy też prostszych przypadków.

Wybór zachłanny

Jeśli w sklepie płacimy gotówką, nie mając wyliczonej kwoty, często osoba obsługująca musi wydać nam resztę.

Zastanówmy się, jakimi regułami mogłaby kierować się osoba obsługująca kasę, przy założeniu, że chce zrealizować zadanie jak najszybciej.

Warto zwrócić uwagę, że podczas rozwiązywania problemu za każdym razem wybieramy największy dostępny nominał. W oparciu o zasadę wyboru najkorzystniejszego w danym momencie rozwiązania działają algorytmy zachłannealgorytm zachłannyalgorytmy zachłanne. Stosowane są na przykład do rozwiązywania problemu plecakowegoproblem plecakowyproblemu plecakowego lub problemu marszrutyzacjiproblem marszrutyzacjiproblemu marszrutyzacji.

Więcej na ten temat znajdziesz w e‑materiałach:

• Algorytmy zachłanneP1Ed8GL2MAlgorytmy zachłanne,

• Problem plecakowyP1G01KROiProblem plecakowy.

Pakowanie

Z pakowaniem przedmiotów mamy do czynienia dość często. Pakujemy podręczniki do szkoły, ubrania na wycieczkę, rzeczy podczas przeprowadzki itd. Czasami istotne jest, żeby czynność wykonana została optymalnie z jakiegoś punktu widzenia. Jeśli mamy np. spakować podręczny bagaż lotniczy, który nie może ważyć więcej niż 10 kg, to wybierając przedmioty do spakowania, w dużej mierze kierować się będziemy ich wagą. Innym przykładem może być umieszczanie naczyń w zmywarce – tutaj z kolei liczyć się może maksymalne jej zapełnienie.

Tego typu sytuacje przypominają problem plecakowy, który dotyczy optymalnego z jakiegoś punktu widzenia sposobu wyboru rzeczy do spakowania. Często ilustruje się go przykładem złodzieja, który do plecaka o ograniczonej wadze ma zapakować najbardziej wartościowe przedmioty.

Wyznaczanie trasy

Wytyczanie optymalnych tras to rzecz ważna nie tylko dla firm przewozowych czy dostawczych, ale również przeciętnej osoby. Wyobraźmy sobie, że planujemy wycieczkę objazdową i zastanawiamy się, w jakiej kolejności odwiedzać różne miejsca, żeby nie zmarnować czasu i pieniędzy. Jednym z rozwiązań jest kierowanie się odległością: z miejsca początkowego jedziemy do kolejnego, które jest najbliżej – i tak dalej. Warto zauważyć, że z punktu widzenia czasu przejazdu, a także konieczności powrotu do jakiegoś miejsca, takie podejście niekoniecznie da najlepsze rozwiązanie. Dlatego metody zachłanne zalicza się do grupy metod heurystycznychmetody heurystycznemetod heurystycznych, które dają rozwiązania przybliżone.

Słownik