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, wzorów w ciągach, opisywanie wzorów
• Ciągi 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) wzoró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 wzorami warto poćwiczyć rozpoznawanie wzorów, które są takie same. Nie zawsze jest to takie proste. Czasem trzeba uważniej przyjrzeć się szczegółom, innym razem wzory mogą być identyczne, ale inaczej obrócone – wówczas do ich rozpoznania potrzebna jest wyobraźnia przestrzenna.

Abyśmy mogli wyszukiwać wzory 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 wzorów w ciągach to przydatne ćwiczenie rozwijające umiejętność rozpoznawania wzoró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 wzorów w ciągach znajduje wiele zastosowań w informatyce: dzięki znalezionym wzorom można na przykład przewidywać przyszłe zachowania, wykrywać błędy w danych lub przeprowadzać kompresję danych.

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).

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.

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).