Algorytm – program – system
| Moduł: Podstawy |
| Poziom: Podstawowy |
| Profil: Dla wszystkich |
Od łamigłówki do programu
Łamigłówka „Wieże Hanoi” (https://pl.wikipedia.org/wiki/Wieże_Hanoi) polega na przełożeniu krążków z pierwszego na trzeci słupek zgodnie z regułami:
- za każdym razem jeden;
- nie wolno kłaść większego krążka na mniejszy
Pomoc dydaktyczna: klocki Wieże Hanoi.Oznaczmy liczbami krążki (od najmniejszego do największego).
Opracowujemy plan działania:
| Lp | działanie |
| 1 | 1-C |
| 2 | 2-B |
| 3 | 1-B |
| 4 | 3-C |
| 5 | 1-A |
| 6 | 2-C |
| 7 | 1-C |
Przetestujmy: https://pl.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/e/move-three-disks-in-towers-of-hanoi
- Spróbować dla większej ilości klocków.
- Czy daje się to uogólnić dla n klocków (zadanie bardzo zaawansowane)?
Ułożenie takiego planu działania wymaga abstrakcyjnego myślenia. Abstrakcja – czyli abstrahowanie od fizycznych elementów. Klocki, słupki i działania zmieniają się w abstrakcyjny zapis – na przykład 1-B. Umiejętność abstrakcyjnego myślenia jest najważniejsza dla programisty. Jeśli ktoś tego nie potrafi – nie może być programistą i nigdy nie zrozumie matematyki.
Taki abstrakcyjny plan działania nazywa się algorytmem.
Program to algorytm wykonywany przez automat.
Ilustracja: program Hanoi (dołączone do kursu źródła UWAGA! Program został napisany w przestarzałej technologii Flash - może nie działać na nowych przeglądarkach).
http://otwartaedukacja.pl/programowanie/hanoi/
Każdy program jest uruchamiany w pewnym środowisku. Tutaj środowiskiem są trzy słupki z krążkami. Dla programów (Hanoi, https://pl.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/e/move-three-disks-in-towers-of-hanoi) środowiskiem jest przeglądarka internetowa w której uruchomiono program napisany w języku JavaScript.
Przejście od środowiska fizycznego (klocki) do przeglądarki internetowej wydaje się nam czymś naturalnym. To jednak wymaga pewnej refleksji – gdyż w ten sposób wchodzimy do świata wirtualnego. Wirtualny – czyli nie istniejący realnie.
Najważniejszą cechą automatu jest determinizm – czyli kolejne działanie jest ściśle określone i zależy wyłącznie od stanu w jakim znajduje się maszyna. Programowanie maszyn = dążenie do determinizmu (ścisłego określenia co ma się wydarzyć w danym stanie maszyny, a nie tylko co może się wydarzyć).
System
Elementy automatu są powiązane ze sobą w taki sposób, aby w całości uzyskać pożądaną funkcjonalność. Na przykład bankomat składa się z liczarki banknotów, klawiatury, monitora, obudowy, czytnika kart i sterującego wszystkim komputera. Jego podstawową funkcją jest wydawanie pieniędzy. Taki zbiór elementów powiązanych ze sobą w sposób umożliwiający uzyskanie pewnej funkcjonalności nazywa się systemem.
Złożone systemy komputerowe uzyskuje się poprzez składanie ich z systemów prostszych (modułów, podprogramów). Idąc w kierunku przeciwnym – do rzeczy coraz prostszych sięgamy do istoty obliczeń. Polski matematyk Zdzisław Pawlak taki najprostszy system nazwał „systemem iteracyjnym”.
Składa się on z pamięci i funkcji przejścia. Pamięć wyraża stan aktualny automatu, a funkcja przejścia determinuje (określa) stan następny.
System iteracyjny:
MASZYNA OBLICZENIOWA = PAMIĘĆ + FUNKCJA PRZEJŚCIA
FUNKCJA PRZEJŚCIA WYZNACZA STAN NASTĘPNY (NOWĄ ZAWARTOŚĆ PAMIĘCI)
PROGRAMOWANIE = BUDOWANIE FUNKCJI PRZEJŚCIAPawlak posługuje się przykładem kostki do gry.
Przykład programu:
| STAN | NASTĘPNY |
| 1 | STOP |
| 2 | STOP |
| 3 | 1 |
| 4 | 2 |
| 5 | 1 |
| 6 | 2 |
Pytanie: co ten program wylicza?
Odpowiedź: zatrzymuje się na 1 lub 2 w zależności od tego, czy początkowo była ilość parzysta lub nieparzysta oczek.
Pisząc program określamy warunki jego zatrzymania się. Najczęściej jest to zakończenie wykonywania algorytmu (zakończenie obliczeń).
Zadanie domowe: zapoznać się z problemem stopu https://pl.wikipedia.org/wiki/Problem_stopu
Arkusz kalkulacyjny jako środowisko w którym uruchamiamy programy
KOMÓRKI = PAMIĘĆ REGUŁY = FUNKCJA PRZEJŚCIA
Zmienna
W arkuszu kalkulacyjnym wiadomo gdzie zapisać wynik – w tej samej komórce, w której zapisano regułę. W programie musimy zarezerwować miejsce w pamięci. Komórka arkusza kalkulacyjnego ma swoją nazwę. W programie posługujemy się nazwą zmiennej (identyfikatorem).
Nazwa komórki = identyfikator zmiennej
Przykład identyfikatora w języku php: $a1 (użyto identyfikatora zgodnie z konwencją nazywania komórek w arkuszu kalkulacyjnym).
Najprostsze programy to formuły w arkuszu.
Na przykład:
= $a1 + 10
Odpowiednia instrukcja w języku php:
$wynik = $a1+10;
Zarezerwowane dwa miejsca w pamięci – zmienne $a1 i $wynik
Algorytm a program
Często spotyka się z wyjaśnieniem, że program jest implementacją algorytmu. Czyli takim zapisem algorytmu, by mogła go wykonać maszyna. To wyjaśnienie wymaga komentarza. Algorytmy jakie spotykamy na co dzień są najczęściej trywialne. Na przykład: aby otworzyć drzwi, włóż klucz do zamka, przekręć w prawo do oporu a następnie naciśnij klamkę.
Jednak algorytmy bywają też bardzo trudne. Nawet najprostszy algorytm sortowania liczb wymaga odrobiny wysiłku intelektualnego, aby go zrozumieć. Naukę programowania często myli się z algorytmiką (czyli układaniem algorytmów), co jest trudne. Dla większości zadań z jakimi spotyka się programista ich trudność można porównać z algorytmem otwierania drzwi (sama czynność jest prostsza, niż jej ścisłe opisanie).
Algorytmika jest trudna. Programowanie jest łatwe. Układanie i implementacja algorytmów wymaga wiedzy, umiejętności i talentu. Programować może każdy. I każdy, kto ma styczność z tworami nowoczesnej techniki to robi (choćby programując programy w telewizorze).
MOLIER „MIESZCZANIN SZLACHCICEM” (w oryginale bohater był zdziwiony, że mówi prozą!)
Podsumowanie
- Programowanie komputerów wymaga abstrakcyjnego myślenia.
- Układamy algorytmy i zapisujemy je przy pomocy abstrakcyjnych symboli.
- Programy są uruchamiane w środowisku tworzącym system obliczeniowy.
- Istotę działania takiego systemu wyjaśnia system iteracyjny.
- Najprostszym środowiskiem jest arkusz kalkulacyjny.
- Przechodząc od arkusza do zwykłych programów – wprowadzamy pojęcie zmiennej (zastępujące komórkę arkusza).
- Programowanie nie jest trudne! Programy pisze każdy użytkownik arkusza kalkulacyjnego (a nawet gdy tylko układa w myśli plan działania)! Trudne natomiast może być układanie algorytmów (czym zajmuje się algorytmika).