[WikiDyd] [TitleIndex] [WordIndex

To jeszcze nie jest gotowe

Algorytmy i struktury danych

Podstawowe pojęcia

Algorytm

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ład

gdzie:

Relacja ri określona na iloczynie kartezjańskim Ak. Mówimy, że relacja ( x1, ... xk ) jest spełniona, gdy układ ( x1, ... xk ) należy do tej relacji.

Przykład:

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

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

Podstawowe dziedziny algorytmiczne to:

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:

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:

Semantyka instrukcji określa jej działanie. Najczęściej jest to opis niesformalizowany, wyrażony potocznym językiem, ale posługujacy się pojęciami z dziedziny opisu algorytmówm.

Funkcja jako opakowanie algorytmu: algorytm można zamknąć w postaci funkcji. Umożliwia to wykorzystywanie prostszych algorytmów jako elementarnych cegiełek do budowy algorytmów bardziej złożonych. Tworząc funkcję określamy jej specyfikację, to znaczy formalnie określamy typ argumentów i typ wyniku oraz nieformalnie podajemy, jak funkcja modyfikuje dane i jaki wynik zwraca.

Specyfikacja funkcji staje się k o n t r a k t e m pomiędzy twórcą funkcji, a jej użytkownikiem.

Struktura danych

Logiczne uporządkowanie danych w pamięci komputera określające sposób dostępu do tych danych. Struktura danych określa przynajmniej częściowo sposób implementacji.

Przykłady:

Abstrakcyjny typ danych

Określenie zbioru danych i zbioru operacji, które można na nich wykonywać.

Atd (ADT - Abstract Data Type) określa funkcjonalność (interfejs) obiektów, nie definiując sposobu implementacji.

Przykłady:


2015-09-23 06:32