Pojęcie algorytmu pojawiło się dużo wcześniej niż komputer. Algorytmy liczbowe znane są od czasów antycznych,  np. algorytm Euklidesa znajdowania największego wspólnego dzielnika dwóch liczb naturalnych. Samo słowo "algorytm" pochodzi od nazwiska matematyka perskiego z 9 wieku n.e.: Abu Ja'Far Mohammed Ibn Mûsâ al-Khowâ-rismî, który poszukiwał metod wykonywania podstawowych operacji arytmetycznych. Nieformalnie, algorytm jest metodą postępowania, określającą ściśle kolejne etapy i wykonywane operacje, w celu rozwiązania danego problemu.

Takie rozumienie algorytmu jest bardzo ogólne i nie zawsze odpowiada procesowi postępowania, który ma być realizowany przez komputer. Na ogół mamy do dyspozycji tylko skończoną przestrzeń do przechowywania danych i skończony czas, w którym chcemy zakończyć postępowanie. Matematycy  początków XX wieku, jeszcze przed powstaniem pierwszego komputera, wiele uwagi poświęcili sformalizowaniu pojęcia algorytmu. Powstały formalne definicje obliczalności, oparte o abstrakcyjne modele liczące, np. funkcje rekurencyjne, algorytmy Markova, maszyny Turinga. Okazało się też wkrótce, że wszystkie zaproponowane modele są równoważne, w tym sensie, że definiują tę samą klasę funkcji obliczalnych. W związku z tym Church sformułował hipotezę (tzw. Teza Churcha), że wszystkie "rozsądne " pojęcia algorytmu są sobie równoważne.  Obecnie, w dobie komputerów, można uznać, że każdy język programowania definiuje pewną klasę algorytmów. Pojęcie algorytmu jest jednak ogólniejsze i nie musi się wiązać z żadnym konkretnym komputerem, ani żadnym konkretnym językiem programowania. Tym niemniej, musimy stosować taką notację do opisu algorytmów, która umożliwi nam ich analizę.

Idealny algorytm to taki, który jest krótki, łatwo go zrozumieć,  który liczy szybko, zawsze daje dobre wyniki i zajmuje mało miejsca w pamięci komputera. Aby sprostać tym wymaganiom, trzeba przede wszystkim zapisać algorytm w języku o prostej składni. Wydaje się, że język (Algolopodobny) zawierający  instrukcję przypisania oraz instrukcje: złożenia, warunkową i pętli, spełnia te wymogi. Z czasem rozszerzymy go o procedury i funkcje, tak by można było opisywać procesy rekurencyjne. Każdy algorytm będzie miał jedną z wymienionych postaci

nazwa_algorytmu{ instrukcje}    
 lub   
typ_wyniku nazwa_algorytmu(parametry){instrukcje}.

Algorytmy pierwszego typu nazywać będziemy czasem procedurami, a drugiego funkcjami. W tym wykładzie, będziemy zapisywali algorytmy używając :

• instrukcji przypisania postaci
  zmienna := wyrażenie,
  która zmiennej przypisuje wartość wyrażenia po prawej stronie symbolu przypisania :=,

• instrukcji składania
  {P₁;... ;P_n},
  która pozwala łączyć algorytmy w większe bloki,
• instrukcji warunkowej
  if g then P₁ else P₂ fi,
  która, w zależności od warunku g, umożliwia wykonanie algorytmu P₁ lub algorytmu P₂,
• instrukcji pętli
  while g do P od,

która umożliwia wielokrotne powtarzanie algorytmu P, dopóki prawdziwy jest warunek g.

Uwaga. Czasami dla wygody, stosować będziemy instrukcję "for"  zamiast instrukcji  pętli "while". Instrukcja  "for i:= k to n do P od"  oznaczać będzie to samo co program {i := k; while i< n+1 do P; i := i+1 od}.

Instrukcje składania, warunkowa i instrukcja pętli są podstawowymi metodami konstruowania algorytmów. Dodatkowo, dopuszczać będziemy instrukcję wywołania wcześniej zdefiniowanej procedury lub funkcji. Takie wywołanie zapiszemy w postaci:

nazwa_algorytmu(parametry_aktualne).

Jak Czytelnik zauważył, w opisie algorytmów, nie będziemy używali instrukcji skoku typu "go to". Wiadomo, że taką instrukcję można wyeliminować z każdego programu: możemy programować strukturalnie, bez użycia instrukcji skoku. Jednak w pewnych wypadkach, szczególnie w pętlach lub procedurach, wygodnie jest użyć specjalnej instrukcji exit, która przerywa działanie pętli, lub instrukcji return pozwalającej przerwać wykonanie funkcji lub procedury i wrócić do instrukcji następującej po jej wywołaniu.

By ułatwić zrozumienie algorytmów, będziemy się starali rozbić dłuższe i bardziej skomplikowane algorytmy na moduły.  Rolę każdego modułu określać będziemy stosując komentarze (zaznaczone symbolem //) albo w języku polskim,  albo w postaci formuł logicznych. Takie formalne komentarze, specyfikujące zachowanie fragmentów programu, są bardzo pomocne przy uzasadnianiu semantycznej poprawności programu.

Zamiast formy tekstowej, czasami  jest wygodnie użyć formy graficznej programu, zwanej  grafem programu.  Tłumaczenie z języka instrukcji na język grafów, i odwrotnie, jest jednoznaczne: każdy graf programu jest jednej z czterech możliwych postaci:

     lub           lub          lub    
 

Rysunek 2.1 Grafy podstawowych instrukcji.

Węzłami takiego grafu są prostokąty, odpowiadające akcjom, i owale odpowiadające testom wykonywanym przez algorytm. Orientacja krawędzi wskazuje na kolejność wykonywania instrukcji.  

Z punktu widzenia semantyki, algorytm opisuje funkcję częściową przeprowadzającą dane początkowe w wyniki. Ponieważ dane początkowe, to początkowe wartości zmiennych, a wyniki końcowe, to też wartości pewnych zmiennych, które uznaliśmy za ważne, zatem każdy algorytm  Alg możemy rozumieć jako funkcję częściową:

odwzorowującą zbiór wartościowań W (tzn. zbiór wartości zmiennych) w zbiór wartościowań.  Jest to funkcja częściowa ponieważ może się zdarzyć, że algorytm nie zatrzymuje się dla pewnych danych początkowych.  Zakładamy, że Czytelnik zna i rozumie semantykę podstawowych instrukcji. Zresztą, dość dobrze wyjaśniają ją przedstawione wyżej grafy programów.

Pytanie 2: Jaką funkcję w zbiorze liczb rzeczywistych wyznacza algorytm { x := 2 ´ x + 3;  x := x  ´  x;}? .

« poprzedni punkt

następny punkt »