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

Zadanie domowe:

1. Spróbować dla większej ilości klocków.
2. 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.

PROGRAM KOMPUTEROWY TO AUTOMAT DZIAŁAJĄCY W ŚWIECIE WIRTUALNYM

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.

Zadanie domowe: zapoznać się z hasłem „System” w Wikipedii: https://pl.wikipedia.org/wiki/System

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ŚCIA

Pawlak posługuje się przykładem kostki do gry.

Pomoc dydaktyczna: kostka do gry lub kostka Rubika

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