Algorytmy i struktury danych
Informatyka, sem IV

Wykład 1: Podstawowe pojęcia

Algorytm definiuje się jako ciąg dobrze określonych,
podstawowych operacji. Dlatego przed opisywaniem algorytmów
nalezy zdefiniować te podstawowe operacje. Oczywiste jest,
że ich konkretny zbiór będzie zależny od realizacji algorytmu
(języka programowania, dostepnych bibliotek), ale możliwe są
pewne matematyczne uogólnienia.

Dziedziną algorytmiczną nazywamy układs
(A ,f_1 , ... ,f_n , r_1 , ... , r_m),
gdzies:
A jest niepustym zbiorem,s
f_1 , ... ,f_n są funkcjami określonymi dla argumentów ze zbioru A
i przyjmującymi wartości w zbiorze A,
r_1 , ... , r_m są relacjami zachodzącymi między elementami zbioru A.

Relacja r_i określona na iloczynie kartezjańskim A^k. Mówimy, że
relacja ( x_1, ... x_k ) jest spełniona, gdy układ ( x_1, ... x_k )
nalezy do tej relacji.

Przykład: A - zbiór liczb całkowitych, r1 - relacja większości,
r2 - relacja równości, r3 - relacja mniejszości, r4 - relacja nierówności.

Funkcja f_i to k+1 argumentowa relacja taka, że dla ustalonego
układu ( x_1, ..., x_k ) istnieje dokładnie jeden element x_(k+1)
taki, że ( x_1, ..., x_k, x_(k+1) ) należy do relacji.
(x_1, ... x_k) nazywamy argumentami, a x_(k+1) wartością funkcji.

Funkcja może być całkowita - zdefiniowana nad całym iloczynem
kartezjańskim A^k lub częściowa, jeżeli nie jest określona dla
pewnych jego podzbiorów.

Podstawowe dziedziny algorytmiczne to:

- dziedzina liczb całkowitych,
- dziedzina liczb rzeczywistych,
- dziedzina wartości logicznych,
- dziedzina napisów

są one powszechnie spotykane w językach programowania.

Algorytm jest więc określony jako przepis postępowania prowadzący
do przejścia od jednego zbioru wartości określonych na wybranym
(wybrannych) zbiorach A (B,C,...) przez stosowanie instrukcji w
zakresie wybranych dziedzin algorytmicznych.

Algorytm składa się z:
deklaracji tworzących zmienne i stałe
instrukcji

Instrukcje składają się z termów: napisów odpowiadających relacjom
i funkcjom. Termy w dziedzinie liczb nazywamy wyrażeniami arytmetycznymi.

Rodzaje instrukcji podstawowych:
- instrukcja pusta
- instrukcja podstawienia
- instrukcja złożona
- instrukcja wyboru (warunkowa)
- instrukcja pętli (iteracji)

Semantyka instrukcji

Funkcja jako opakowanie algorytmu