| « poprzedni punkt | następny punkt » |
Rozważmy algorytm, w którym występują jedynie instrukcje przypisania i instrukcja pętli "while"
{
y:=1; s:= 1; k:= 1;
while k < 100 do
y := operacja1(y, 2);
s := operacja2(s, y);
k := operacja3(k,1);
od;
}
Czy można powiedzieć co robi ten algorytm? Na początku sprawa jest prosta: zmiennym y, s i k przypisano jako wartość liczbę 1. Pętla "while" przy każdym przebiegu sprawdza, czy k< 100 i domyślamy się, że chodzi tu o relację mniejszości < w zbiorze liczb rzeczywistych. Co jednak robi ta pętla? Jak zmieniają się wartości zmiennych y, s i k? O tym decydują operacja1, operacja2 i operacja3. Jeśli wiemy, że wszystkie trzy operacje, to po prostu dodawanie w zbiorze liczb naturalnych, to nasz algorytm w każdej iteracji do zmiennej y dodaje 2, do zmiennej s dodaje y, a do k dodaje 1. Łatwo teraz wywnioskujemy, że k jest licznikiem iteracji, y przyjmuje jako wartość kolejne liczby nieparzyste postaci 2k+1, a s sumuje je. Przy takiej interpretacji możemy już powiedzieć, że pętla wykonywać się będzie dokładnie 99 razy, a wartością zmiennej s po wykonaniu wszystkich instrukcji będzie 1+3+5+...+(2*99+1) = 100*100 (por. wykład 8).
Gdybyśmy jednak zinterpretowali operacje pierwszą i drugą jako dodawanie, a operację trzecią jako mnożenie, wówczas zmienna k nie zmieniałaby wartości (stale k=1) i pętla w naszym algorytmie nigdy nie zakończyłaby się.
Wynika stąd, że aby zrozumieć co robi algorytm (program) musimy znać nie tylko język programowania, w którym algorytm został napisany, ale także strukturę danych, w której wykonywane są instrukcje. Musimy wiedzieć jakiego typu są zmienne występujące w tym algorytmie, wiedzieć jak interpretowane są relacje i operacje w nim występujące.
Cóż to takiego struktura danych? Najogólniej jest to trójka
Zbiór + operacje + relacje.
Taki system nazywa się systemem algebraicznym.
O relacjach i operacjach mówiliśmy obszerniej w wykładach 2, 3, 4, 5. Przypomnijmy tylko, że operacja n-argumentowa w zbiorze X, to nic innego jak wieloargumentowa funkcja określona na elementach produktu kartezjańskiego Xn i o wartościach w X. W szczególnym przypadku rozważa się też operacje zeroargumentowe, tzn. stałe.
Definicja 15.1.1
O zbiorze X powiemy, że jest zamknięty ze względu na n-argumentową operację o wtedy i tylko wtedy, gdy wynik operacji o dla dowolnych argumentów wziętych z X należy do X:
jeśli x1 ∈ X, x2 ∈X, ..., xn ∈ X, to o( x1,x2,..., xn) ∈ X.
Operacje, z którymi mamy do czynienia w praktyce, są często funkcjami częściowymi, tzn. ich wartość nie zawsze jest określona dla wszystkich możliwych układów danych. Taką operacją jest np. dzielenie w zbiorze liczb rzeczywistych, czy pierwiastkowanie. Ponadto, zdarza się, że typy argumentów operacji (czy relacji) nie są identyczne. Przykładem niech będzie operacja dołączania nowego obiektu do zbioru obiektów: mając dany element e i pewien zbiór elementów X otrzymujemy, jako wynik działania operacji, nowy zbiór złożony ze wszystkich elementów zbioru X i z elementu e. Argumentami operacji są więc: zbiór i element zbioru, czyli obiekty różnych typów.
Definicja 15.1.2
Systemem algebraicznym (relacyjnym) nazywamy układ
< A, o1, o2,...,
on ; r1, r2, ..., rm >,
A jest niepustym zbiorem, zwanym uniwersum systemu,
o1, o2,..., on są operacjami w A,
r1, r2, ..., rm są relacjami w A.
Jeśli uniwersum systemu składa się z obiektów różnych typów, to mówimy o systemie wielosortowym. Każda operacja systemu relacyjnego ma określony typ, tzn. liczbę i typy argumentów oraz typ wyniku. Podobnie, każda relacja systemu ma określony typ, tzn. liczbę i typy argumentów. Na relację w systemie relacyjnym będziemy zwykle patrzyli jako na funkcję charakterystyczną zbioru reprezentowanego przez tę relację. Zatem typ wyniku takiej funkcji jest booleowski.
Typy operacji i relacji systemu algebraicznego tworzą razem sygnaturę systemu. Systemy algebraiczne o takiej samej sygnaturze nazywa się podobnymi. Oczywiście, to podobieństwo jest czysto formalne: dwa systemy podobne mają tyle samo relacji i tyle samo operacji, a odpowiadające sobie operacje i relacje mają takie same arności (liczby argumentów). Wszystkie te pojęcia wyjaśnimy na przykładach w następnym punkcie wykładu.
Jeśli w systemie nie rozważa się relacji, to wówczas mówimy po prostu o algebrze.
Zbiór liczb naturalnych z dodawaniem i mnożeniem tworzy system algebraiczny (algebrę) <N, +,* >. Rzeczywiście wynik dodawania i mnożenia dwóch liczb naturalnych zawsze jest liczbą naturalną. Dodawanie i mnożenie są operacjami dwuargumentowymi w N, czyli sygnatura tego systemu składa się z dwóch dwuargumentowych operacji:
+ : N × N → N
* : N × N → N
Podobnie, zbiór liczb parzystych z dodawaniem i mnożeniem też jest algebrą <P,+,*>, bo suma dwóch liczb parzystych jest liczbą parzystą i iloczyn dwóch liczb parzystych jest liczbą parzystą. Systemy <N, +,* > i <P,+,* > są podobne: oba mają po dwie dwuargumentowe operacje.
Nie można tego powiedzieć o zbiorze liczb nieparzystych NP: suma dwóch liczb nieparzystych nie jest liczbą nieparzystą. Wynika stąd, że dodawanie nie jest dobrze określoną operacją w zbiorze NP.
Przykładem systemu algebraicznego jest też krata <A, inf, sup, r>, tzn. dowolny zbiór uporządkowany przez relację r z dwoma operacjami dwuargumentowymi inf i sup określonymi dla dowolnych x, y ∈ A następująco: inf(x,y) = kres dolny zbioru {x,y} w sensie porządku r, sup(x,y) = kres górny zbioru {x,y} ze względu na porządek r.
Pytanie 15.1.1: Czy zbiór {2i : i ∈ N} jest zamknięty ze względu na dodawanie?