Myślenie algorytmiczne

Myślenie algorytmiczne jest częścią szerszego myślenia informatycznego i polega na projektowaniu i analizowaniu algorytmów.

Co obejmuje myślenie algorytmiczne?

Algorytm to dokładnie określony sposób postępowania prowadzący do rozwiązania danego problemu. Myślenie algorytmiczne najczęściej wykorzystuje się podczas programowania, czyli zapisywania algorytmów wykonywanych przez komputer. Ma ono jednak zastosowanie także w życiu codziennym – przykładami prostych algorytmów są przepisy kulinarne czy instrukcje pozwalające dotrzeć z jednego miejsca do drugiego.

Myślenie algorytmiczne obejmuje nie tylko tworzenie algorytmu, ale także inne powiązane działania:

• Zrozumienie i precyzyjne sformułowanie problemu.
• Abstrakcję, rozkład problemu na mniejsze części, odróżnianie elementów istotnych od mniej ważnych.
• Rozważanie różnych sposobów rozwiązania problemu, porównywanie efektywności algorytmów, optymalizację procedur.
• Zrozumienie algorytmu stworzonego przez kogoś innego oraz jego wykonanie.
• Wyszukiwanie i poprawianie błędów.

Myślenie algoryticzne na

Zagadnienie podzieliliśmy na kilka podtematów:

• Rozpoznawanie wzorów – wyszukiwanie wspólnych cech i zależności, wzorców w ciągach, opisywanie wcorców
• Sekwencje poleceń – budowanie algorytmów z kilku poleceń
• Pętle i warunki – powtarzanie i warunkowe wykonywanie poleceń
• Zmienne – praca z informacją o stanie, zapisywanie wartości w zmiennych
• Funkcje i uogólnianie – uogólnianie (abstrakcja) wzorców, rozkładanie problemów na części (dekompozycja), stosowanie funkcji
• Tworzenie programów – debugowanie, wyszukiwanie błędów

Przykłady w tej części opierają się głównie na „mikrośrodowiskach”, czyli prostych, intuicyjnych przestrzeniach z ograniczoną liczbą poleceń, ale ciekawą dynamiką.

Przed przystąpieniem do ćwiczeń z bardziej złożonymi wzorcami warto poćwiczyć rozpoznawanie wzorców, które są takie same. Nie zawsze jest to proste. Czasem trzeba uważniej przyjrzeć się szczegółom, a innym razem wzorce mogą być identyczne, ale inaczej obrócone – wówczas do ich rozpoznania potrzebna jest wyobraźnia przestrzenna.

Abyśmy mogli wyszukiwać wzorce i tworzyć algorytmy, musimy umieć zauważyć wspólne cechy między rzeczami, które na pierwszy rzut oka mogą wyglądać różnie. Szukanie cech wspólnych to szczególny przypadek Abstrakcji, którą bardzo często wykorzystujemy podczas algorytmizacji. Ta umiejętność przydaje się na przykład w Rozkładaniu obrazka na elementy.

Na przykład:

• kot, dom, las, sok – wspólna cecha: ta sama liczba liter (3)
• wróbel, sowa, bocian, gil – wspólna cecha: ta sama kategoria (ptaki)
• garaż, pokaż, montaż – wspólna cecha: litery (słowa zakończone na -aż)

Szukanie regularności i wzorców w ciągach to przydatne ćwiczenie rozwijające umiejętność rozpoznawania wzorców. Do podstawowego treningu najczęściej wykorzystuje się ciągi liczb lub obrazków o ściśle określonym, regularnym zachowaniu. Przykłady tego typu są czasem wykorzystywane również w testach inteligencji.

W bardziej zaawansowanych wariantach szukanie wzorców w ciągach znajduje wiele zastosowań w informatyce: dzięki znalezionym wzorcom można na przykład przewidywać przyszłe zachowania, wykrywać błędy w danych lub przeprowadzać kompresję danych.

Za pomocą programów możemy zapisywać złożone algorytmy i opisywać skomplikowane wzorce. Jednak do zapisu prostych wzorców nie potrzebujemy języków programowania — możemy spokojnie używać zapisu za pomocą strzałek. Nawet to nie musi być całkiem proste. Na przykład zamiana kolejności strzałek może prowadzić do zupełnie innego wzorca.

Niezwykle przydatnym podejściem do rozwiązywania problemów jest podzielenie ich na części składowe, które są w miarę możliwości jak najbardziej niezależne, a następnie rozwiązywanie tych części jedna po drugiej.

Przykład z życia codziennego: Musimy przygotować się do wędrówki po górach. Trzeba załatwić wiele spraw i możemy czuć się przytłoczeni, łatwo zapominając o czymś ważnym. Pomóc może podział całego problemu pt. przygotowanie do wycieczki w góry na mniejsze podproblemy: 1) zaplanować trasę i znaleźć połączenie, 2) opracować jadłospis i zrobić zakupy, 3) przygotować sprzęt turystyczny i sprawdzić jego stan, 4) skompletować i spakować odpowiednie ubrania. Te mniejsze zadania są w dużej mierze niezależne i mogą być realizowane przez różne osoby. A nawet jeśli wykonuje je ta sama osoba, podczas rozwiązywania danego podproblemu może skupić się tylko na nim, co znacznie ułatwia cały proces.

Przykład z programowania: Programów nie piszemy jako długich list poleceń, lecz dzielimy je na funkcje, z których każda rozwiązuje jakiś mniejszy problem. Podział na podproblemy jest kluczowym elementem dobrze zaprojektowanego programu.

Podział problemu na części to skomplikowana umiejętność, której człowiek uczy się w długim procesie praktyki. Dla podstawowego treningu oferujemy przykłady z obrazkami. Obraz, który wygląda na skomplikowany, często można stworzyć z prostych części, odpowiednio je ze sobą łącząc.

Algorytmy składają się z sekwencji poleceń, które określają, co komputer ma wykonać (wypisz znak A, narysuj jabłko, idź do przodu). Dlatego podczas programowania musimy wiedzieć, jakie polecenia mamy do dyspozycji i jakie jest ich dokładne znaczenie. Następnie poszczególne polecenia łączymy w sekwencje, tworząc w ten sposób bardziej złożone programy. Ważna jest kolejność poleceń, ponieważ inna kolejność może prowadzić do znacznie odmiennego działania (jeśli obrócimy się w prawo i zrobimy krok naprzód, trafimy w inne miejsce, niż gdy najpierw zrobimy krok naprzód, a dopiero potem się obrócimy).

• Podstawowe polecenia – proste przykłady pomagające zrozumieć znaczenie podstawowych czynności, z których będziemy później tworzyć bardziej złożone programy
• Kolejność poleceń – rozróżnianie różnych kolejności poleceń, przyporządkowywanie wyników do sekwencji poleceń
• Równoległość – przykłady, w których polecenia wykonywane są jednocześnie
• Zmiana stanu – sytuacje, w których podczas wykonywania programu zmienia się stan środowiska, co wpływa na dalsze działanie programu

Programy składają się z pojedynczych poleceń. W naszych ćwiczeniach możesz na przykład spotkać:

• polecenia wyświetlania tekstu lub rysowania prostego obrazka: wypisz, narysuj,
• polecenia ruchu (do przodu, skręć w prawo),
• wykonania czarów (wyczaruj kapelusz, zamień w żabę).

W praktycznym programowaniu używamy na przykład poleceń wyświetlania tekstu na monitorze, rysowania obrazka, wczytywania informacji z pliku lub zapisywania wyniku obliczeń w pamięci komputera.

Następnie z pojedynczych poleceń tworzymy programy, korzystając z sekwencji poleceń, powtórzeń, warunków i innych metod.

Podstawowym elementem każdego algorytmu jest wykonywanie serii działań w określonej kolejności. To, w jakiej kolejności wykonujemy działania, ma ogromne znaczenie. Czasem jest to oczywiste. Kiedy przygotowujemy naleśniki, najpierw musimy wymieszać ciasto, a dopiero potem wylać je na patelnię. Gdybyśmy odwrócili kolejność, efekt raczej nie przypominałby naleśników. Podobnie wygląda to w przypadku programowania robotów. Jeśli robot najpierw się obróci, a potem zrobi krok, rezultat będzie zupełnie inny, niż gdyby najpierw zrobił krok, a dopiero potem się obrócił.

Znaczenie kolejności działań widać bardzo dobrze w ćwiczeniu ProgMalowanie, w którym ostateczny wygląd obrazka zależy od tego, który element narysujemy wcześniej, a który później.

Kolejność poleceń w programach zapisujemy tak samo jak zwykły tekst: od góry do dołu (lub od lewej do prawej).

W zaawansowanej informatyce rozróżniamy równoległość i współbieżność, ale tutaj nie będziemy zagłębiać się w te szczegóły. Chodzi o sytuacje, w których wiele procesów dzieje się jednocześnie. Takie zjawisko obserwujemy w naszym codziennym świecie cały czas. Jednak gdy próbujemy opracowywać algorytmiczne rozwiązania problemów, równoległość może stanowić nie lada wyzwanie. Nie jest łatwo zaplanować, żeby wiele zdarzeń przebiegało poprawnie w tym samym czasie.

Do ćwiczenia myślenia o równoległości będziemy korzystać głównie z zadań na kratkowanej siatce, gdzie w tym samym czasie porusza się kilku agentów.

Polecenia wejścia i wyjścia umożliwiają programom interakcję ze światem. Podstawowy przebieg obliczeń obejmuje sekwencję wejście → przetwarzanie → wyjście, ale programy mogą też zawierać więcej poleceń wejścia i wyjścia. W grze po każdym naciśnięciu strzałki (wejście) wyświetlana jest nowa pozycja sterowanej postaci (wyjście).

Polecenia wejścia

Polecenia wejścia pobierają dane do przetwarzania. Wejście można odczytywać albo od użytkownika za pomocą różnych urządzeń wejścia (np. mysz, klawiatura, ekran dotykowy), z pliku zapisanego w komputerze (np. zapisany stan gry) albo z czujników odbierających informacje z otoczenia (np. odległość robota od przeszkody, rozpoznanie koloru pola, wykrycie krawędzi w Platformówce.

Polecenia do wczytywania wejścia zazwyczaj czekają na pobranie danych (np. dopóki użytkownik nie poda odpowiedzi), a dopiero potem program wykonuje kolejne polecenie. Alternatywą jest zdefiniowanie kodu, który uruchamia się przy określonym zdarzeniu wejściowym (np. kliknięciu myszy). Takie rozwiązanie jest często wykorzystywane w grach (również w Platformówce) oraz innych aplikacjach graficznych.

Polecenia wyjścia

Polecenia wyjścia przekazują wynik przetwarzania. Wyjście można przekazać użytkownikowi za pomocą różnych urządzeń wyjścia (monitor, głosnik) albo zapisać do pliku w celu późniejszego wykorzystania (np. zapis aktualnego stanu gry). Wyjście może mieć różną formę, na przykład tekstu (wypis na ekranie), grafiki (wyświetlenie sceny gry), dźwięku (sygnał ostrzegawczy) lub działania robota maszyny wykonującej program (np. ruch robota).

Programy z wejściem i wyjściem

Program może zawierać różne kombinacje poleceń wejścia, wyjścia, a także poleceń przetwarzających, które nie należą do żadnej z tych dwóch kategorii.

Niektóre programy nie muszą mieć żadnego wejścia – wykonują za każdym razem to samo (Na przykład programy w żółwiej grafice zawsze rysują jeden konkretny obrazek.) Niemniej wszystkie użyteczne programy mają jakieś wyjście.

Gdy już opanujemy podstawowe sekwencje poleceń, możemy zacząć tworzyć bardziej złożone programy przy użyciu pętli i warunków:

• Powtórz N× – podstawowa pętla z podaną liczbą powtórzeń

  powtórz 4×: krok do przodu, skręć w prawo

• Zdarzenia – polecenia reagujące na to, gdy coś wydarzy się w środowisku

  po naciśnięciu klawisza: narysuj kropkę

• Warunki i rozgałęzienia – program wykona polecenie tylko wtedy, gdy spełniony jest warunek

  jeśli stoisz na piasku: obróć się w prawo

• Powtarzaj dopóki – pętla wykonywana jest dopóty, dopóki spełniony jest warunek

  dopóki przed tobą jest wolne pole: krok do przodu

Pętle i warunki można ze sobą łączyć. Nie potrzebujemy do tego żadnych specjalnych poleceń, ale nauczenie się tworzenia takich programów nie jest aż takie proste. Dlatego przygotowaliśmy specjalnie ćwiczenia:

• Wielokrotne decydowanie – pętla połączona z warunkiem
• Pętle zagnieżdżone – pętla w środku innej pętli.

Podczas programowania możemy chcieć, aby pewne akcje były wykonywane w momencie zajścia określonego zdarzenia. W Platformówce może być potrzebne, aby postać podskoczyła po kliknięciu lub obróciła się po zderzeniu z kaktusem. Nagłówek bloku określa zdarzenie, na które czekamy (kliknięcie myszy, naciśnięcie klawisza, wysłanie wiadomości). Ciało bloku zawiera polecenia, które mają zostać wykonane po wystąpieniu danego zdarzenia.

Programy ze zdarzeniami

Akcja jest wykonywana za każdym razem, gdy dane zdarzenie nastąpi. Jeśli zdarzenie powtarza się wielokrotnie, akcja zostanie wykonana tyle razy, ile zdarzeń wystąpi. Natomiast jeśli zdarzenie nigdy nie nastąpi, akcja nie wykona się ani razu. Jeden program może zawierać wiele zdarzeń. W takim przypadku może się zdarzyć, że kilka zdarzeń wystąpi jednocześnie – wówczas w jednej chwili zostanie wykonanych kilka akcji. (Zdarzenia mają więc związek z równoległością.) Tworzenie programów opartych na zdarzeniach nazywa się programowaniem sterowanym zdarzeniami.

Zastosowanie zdarzeń

Zdarzenia umożliwiają tworzenie interaktywnych programów reagujących na działania użytkownika. Jest to powszechnie stosowane w grach (naciśnięcie spacji powoduje, że postać podskakuje), w aplikacjach z graficznym interfejsem użytkownika (edytor tekstu reaguje na naciśnięty klawisz, wyświetlając odpowiedni znak) oraz w aplikacjach internetowych (po kliknięciu przycisku „Wyślij” wiadomość zostaje wysłana). Można również reagować na zdarzenia zachodzące wewnątrz programu (gdy postać wejdzie w drzwi, zmienia się scena).

W programowaniu zmienna to miejsce w pamięci, które przechowuje jakąś wartość. Wartość ta może zmieniać się w trakcie obliczeń – stąd nazwa zmienna.

Typowym przykładem użycia zmiennej jest obliczanie całkowitej ceny zakupów. Na początku program w kasie zapisuje w zmiennej sum wartość 0. Po wczytaniu każdego artykułu dodaje do tej zmiennej jego cenę.

Inny przykład: W programie gry kółko i krzyżyk musimy sprawdzić, czy któryś z graczy już wygrał. Przechodzimy więc przez poszczególne kierunki na planszy i w każdym z nich liczymy, ile krzyżyków (lub kółek) występuje kolejno po sobie. Tę liczbę zapisujemy w zmiennej. Oprócz tego w jakiejś zmiennej musimy jeszcze zapisać cały plan gry. Jednak w podstawowych ćwiczeniach pozostaniemy tylko przy zmiennych liczbowych, które będą działać głównie jako proste liczniki.

Przydatnym przygotowaniem do pracy ze zmiennymi są zadania, w których programy zmieniają stan przedstawiony na schemacie – na przykład kolor skrzata lub obecność kamieni. Zmieniane atrybuty (kolor skrzata, obecność kamieni) można postrzegać jako zmienne. Podstawy pracy ze zmiennymi obejmują przypisywanie wartości zmiennym, zmianę wartości (zwiększenie, zmniejszenie), używanie zmiennej w wyrażeniach oraz porównywanie zmiennych. Pełna użyteczność zmiennych ujawnia się jednak dopiero w połączeniu z pętlami i instrukcjami warunkowymi.

Każda zmienna ma swój typ danych. Typ danych określa, jakie wartości może przechowywać zmienna oraz jakie operacje można na niej wykonywać. Niektóre języki programowania wymagają, aby typ zmiennej został jawnie podany w programie, inne automatycznie go wywnioskowują na podstawie przypisanej wartości. Języki programowania różnią się również tym, jakie typy danych oferują. Do najczęściej spotykanych typów danych należą:

• liczba całkowita (123, −7) – na liczbach można wykonywać operacje arytmetyczne (1 + 2) oraz je porównywać (1 < 2)
• liczba zmiennoprzecinkowa (1,23, –0,05) – służy do przechowywania liczb rzeczywistych, czyli takich, które mogą mieć część dziesiętną. Pozwala zapisywać bardzo duże i bardzo małe wartości, ale z ograniczoną dokładnością. Oznacza to, że niektóre liczby mogą być przechowywane tylko w przybliżeniu.
• wartość logiczna (prawda, fałsz) – reprezentuje informację o prawdziwości, można na niej wykonywać operacje logiczne (nie x, x lub y, x i y). (Ten typ często nazywany jest jako „bool“ lub „boolean“ od George’a Boole’a, który opracował zasady logiki matematycznej.)
• łańcuch znaków (“słowo”, “więcej słów”) – reprezentuje tekst dowolnej długości. Aby odróżnić go od nazw zmiennych, zapisuje się go w “cudzysłowie” lub ‘apostrofach’. Należy rozróżniać łańcuch znaków zawierający liczbę od liczby – “123” to nie to samo co 123. (Ten typ często nazywa się „string”, od angielskiego słowa oznaczającego łańcuch.)
• lista (tablica) ([1, 2, 3], [‘x’, ‘y’, ‘z’]) – pozwala przechowywać wiele powiązanych wartości w jednej zmiennej. (Często dostępne są także inne typy do przechowywania różnych kolekcji danych.)

Istnieją także inne typy przeznaczone do specjalnych zastosowań (np. czas, data, plik). Zazwyczaj możliwe jest również definiowanie własnych typów danych.Typ wyliczeniowy (enum) pozwala definiować zmienne, które mogą przyjmować tylko kilka wcześniej określonych wartości (np. kierunki świata, dni tygodnia). Rekordy pozwalają definiować złożone zmienne, które składają się z kilku nazwanych pól (np. rekord klienta może zawierać jego imię, wiek oraz datę ostatniego zakupu).

Funkcje są podstawowym elementem, za pomocą którego tworzymy programy. Stanowią konkretną realizację ogólnej zasady rozkładu problemu na części.

Mówiąc obrazowo, funkcja jest jak magiczne zaklęcie, któremu coś przekazujemy (dane wejściowe), a ono wyczarowuje dla nas coś innego (wynik).

• Przykład bajkowy: Powiększająca magiczna różdżka, którą dotkniemy warzywo, a ona powiększy je do dwukrotnie większego rozmiaru.
• Przykład matematyczny: Funkcja pierwiastka kwadratowego, której podajemy na wejściu liczbę, a ona zwraca inną liczbę (np. dla wartości wejściowej 25 zwraca wynik 5).
• Przykład programistyczny: Funkcja polygon(n, długość), której przekazujemy na wejściu dwie liczby (liczbę boków i długość boku), a ona rysuje obraz wielokąta.

Proste funkcje bez parametrów pozwalają jedynie na wielokrotne wykonanie dokładnie tego samego kodu (np. zawsze kwadratu o takim samym rozmiarze). Funkcje mogą jednak zawierać również parametry, które wpływają na ich działanie (np. rozmiar kwadratu). Funkcje mogą wywoływać inne funkcje, a czasami nawet same siebie – takie funkcje nazywamy rekurencyjnymi.

Przy wprowadzaniu funkcji musimy umieć abstrahować – czyli pomijać nieistotne szczegóły – a następnie uogólniać kod – czyli zastępować zmienne szczegóły zmiennymi, z których później tworzymy parametry funkcji. Złożony program, szczególnie taki, w którym powtarza się podobny kod, można rozłożyć na kilka funkcji, dzięki czemu staje się prostszy i bardziej przejrzysty.

Abstrakcja to umiejętność pomijania szczegółów, które nie są istotne dla rozwiązania analizowanego problemu. Skupiamy się na wspólnych elementach i właściwościach, dzięki którym możemy znaleźć bardziej ogólne rozwiązanie.

Przykład z życia codziennego: Toffik, Bruno i Reks to trzy konkretne zwierzęta domowe. Możemy je nazwać abstrakcyjnym pojęciem „pies” – pomijamy w ten sposób wiele ich cech (np. wiek, kolor sierści czy rasę) i koncentrujemy się tylko na tym, co mają wspólnego. Gdybyśmy mieli w domu również kota Mruczka, to do nazwania ich wszystkich moglibyśmy użyć na przykład kategorii „ssak”.

Przykład z programowania: Podczas rysowania obrazków możemy napisać funkcję squareA(), która rysuje niebieski kwadrat o boku 100, oraz squareB(), która rysuje żółty kwadrat o boku 200. Lepszym rozwiązaniem jest jednak stworzenie bardziej abstrakcyjnej funkcji square(length, color), która narysuje kwadrat o dowolnym rozmiarze i kolorze (zgodnie z przekazanymi parametrami). Możemy też pójść jeszcze dalej i napisać funkcję, która narysuje dowolny wielokąt (o określonej liczbie wierzchołków).

Rzadko udaje się napisać za pierwszym razem kod całkowicie pozbawiony błędów. Ryzyko wystąpienia błędów zmniejsza dbałość o wysoką jakość kodu, jednak nie da się ich całkowicie uniknąć, dlatego należy aktywnie ich szukać. Błędy w kodzie są czasem określane angielskim terminem bug. Proces sprawdzania poprawności kodu nazywamy testowaniem, natomiast proces ustalania przyczyny błędu i jego usuwania debugowaniem.

Typy błędów

Rozróżniamy błędy składniowe (niepoprawny zapis programu – programu nie można uruchomić) oraz semantyczne (program wykonuje się, ale nie działa zgodnie z oczekiwaniami). Szczególnym przypadkiem błędu semantycznego jest zapętlenie (program nigdy nie kończy działania, np. dlatego, że warunek pętli nigdy nie przestaje być spełniony).

Proces debugowania programu

Jeżeli program nie daje poprawnych wyników, uruchamiamy go krok po kroku i obserwujemy, w którym momencie odbiega od naszych oczekiwań. Jeżeli program nie tworzy wyjścia graficznego, możemy na bieżąco wypisywać wartości zmiennych albo użyć narzędzia, które umożliwia wykonywanie programu krok po kroku i obserwowanie wartości zmiennych (tzw. debugger). Fragment programu, w którym jego działanie odbiega od naszych oczekiwań, próbujemy poprawić.