Algorytmy i Struktury Danych

[ Pobierz całość w formacie PDF ]
AISD str. A
Algorytmy i Struktury Danych
Literatura
S. Sengupta, C. Ph. Korobkin, "C++ Object-Oriented Data Structures", Springer-Verlag, 1994.
N. Wirth.”Algorytmy + struktury danych = programy” WNT Warszawa 1980,
B. Stroustrup, "The C++ Programming Language", Second Edition, Addison Wesley, 1991,
W. Iszkowski, "Struktury i typy danych", Wydawnictwa Politechniki Warszawskiej, Warszawa,
1990.
Program wykładu
1.
Algorytmy i struktury danych w ujęciu praktyczno-teoretycznym.
2.
Liniowe struktury danych.
3.
Sortowanie i wyszukiwanie.
4.
Drzewa.
5.
Rekursja.
6.
Grafy.
ALGORYTMY I STRUKTURY DANYCH W UJĘCIU PRAKTYCZNO-
TEORETYCZNYM
ALGORYTMY I STRUKTURY DANYCH, A TYPY DANYCH
Dwa fundamentalne składniki programów to:
struktury danych
(wartości danych zorganizowane w pewien sposób
umożliwiający dostęp do nich)
algorytmy
(opis zasady przetwrzania wartości o ich organizacji)
Przy tworzeniu złożonych programów struktury i algorytmy grupuje się dla uzyskania większej
przejrzystości, a grupy te nazywa się modułami, typami danych, klasami, czy definicjami typów
danych.
Pojęcie typów danych pozwala umożliwia mówienie o oprogramowaniu w sposób bardziej
abstrakcyjny niż przedstawianie szczegółowego sposobu reprezentowania danych i szczegółów
działania algorytmów. Pojęcie typów danych i w szczególności abstrakcyjnych typów danych
było promowane przez wielu autorów w latach 70-tych i zostało zaadoptowane przez praktyków
programowania w latach 80-tych.
Def.
Specyfikacja (opis nieformalny lub prezentacja algebraiczna lub kod programu):
Specyfikacją (formalną) jest opis (formalny) systemu typów danych, to jest opis rodzajów,
rodzajów argumentów i wyników operacji oraz opis zależności pomiędzy wartościami
argumentów, a wartościami wyników operacji.
1
AISD str. B
Przykład 1.1. Specyfikacja nieformalna automatycznego parkingu samochodowego: Parking
może przyjąć lub wydać samochód identyfikowany numerem rejestracyjnycm. Parking nie
może przyjąć kolejno dwóch samochodów o tym samym numerze. Jeżeli parking przyjął
samochód to zawsze można go odebrać przez wywołanie operacji zwracania. Jeżeli
samochodu nie ma na parkingu, to na żądanie zwrotu samochodu odpowiedzią jest sygnał
błędu.
Przykład 1.2. Specyfikacja typu stos z aksjomatami dla top i pop.
Nazwy rodzajów nośnika: stack,elem
Nazwy operacji i ich arność: empty:->stack, push:stack x elem -> stack, top:stack -> elem,
pop:stack -> stack
Równania opisujące sposób działania operacji:
s:stack,e:elem top(push(s,e))=e
s:stack,e:elem pop(push(s,e))=s
Przykład 1.3. Przykład klasy - licznik działający cyklicznie.
class Count {
nat s;
public:
Count() { s = 0; }
void inc() { s = s + 1; if (s == 32) s = 0; }
bool is_zero() { return s == 0; }
}
STRUKTURY DANYCH A POJĘCIE OBIEKTOWOŚCI
W praktyce informatyki pojęcie obiektu jest utożsamiane z fragmentem pamięci operacyjnej
gdzie przechowywana jest w formie binarnej wartość jakiegoś typu, na której można
wykonywać operacje zdefiniowane przez typ danych. Jednak wygodniej jest myśleć o
obiekcie jako o wartości (elemencie zbioru wartości określonego przez system typów danych).
Def.
Struktura danych (zbiór obiektów z funkcjami wyznaczania następnika)
Strukturę danych stanowi skończony zbiór węzłów-obiektów oraz opis bezpośredniego
następstwa węzłów w strukturze. Bezpośrednie następstwo opisuje się z użyciem funkcji, które
odwzorowują stan obiektu zawierającego strukturę i węzeł struktury na jego następnik
.
Poszczególne powiązania par węzłów nazywa się też krawędziami.
W podejściu obiektowym strukturę danych wraz z algorytmami zamyka się w jedną całość
tworząc typ danych. Konkretne struktury są wtedy obiektami utworzonego typu.
W praktyce informatyki pojęcie zmiennej jest utożsamiane z fragmentem pamięci operacyjnej
gdzie przechowywana jest w formie binarnej wartość jakiegoś typu, na której można
wykonywać operacje zdefiniowane przez ten typ danych. O zmiennej obiektu można też
myśleć jako o funkcji odwzorowującej wartość obiektu na wartość składowej reprezentowanej
nazwą tej zmiennej.
2
AISD str. C
Główne cechy obiektowego podejścia do implementacji typów danych to:
1.
Struktura danych nie występuje samodzielnie, ale wraz z zestawem operacji-funkcji
udostępniających wartości ze struktury, lub modyfikujących tą strukturę.
2.
Typ danych jest postrzegany jako spójna definicja, według której można tworzyć konkretne
obiekty.
3.
Bezpośredni dostęp do elementów struktury danych (np. przez adres) nie jest możliwy. W
konsekwencji tego wewnętrzna reprezentacja struktury danych jest ukryta w obiekcie, a
rodzaj struktury może być zmieniony bez zmiany działania programu jako całości.
4.
Wartości struktury, pomocnicze dane, czy pomocnicze struktury są ukryte i niedostępne z
zewnątrz obiektu.
5.
W metodologii projektowania obiektowego program jest traktowany jako grupa obiektów
wzajemnie oddziałujących na siebie (w odróżnieniu od podejścia strukturalnego, w którym
program jest zbiorem wzajemnie powiązanych funkcji).
Metodologia programowania (projektowania) obiektowego w naturalny sposób wspiera (i
wykorzystuje) koncepcję ADT. Język C++ jest zdecydowanie bogatszy, niż byłoby to niezbędne
do programowania obiektowego. Daje to z jednej strony korzyści polegające na tym, że
programista może kodować ten sam algorytm dla optymalizowania szybkości na wiele
sposobów stosując różne mechanizmy "niskiego poziomu" jak bezpośredni dostęp w dowolne
miejsce pamięci operacyjnej, czy operacje bitowe na słowach maszynowych przechowujących
informacje tekstowe i liczbowe. Z drugiej jednak strony swobodne - niezorganizowane
wykorzystanie takiego dostępu i przydziału/zwalniania pamięci prowadzi do powstania
zagmatwanych nieczytelnych programów obarczonych zwykle znaczną liczbą błędów, które nie
dają się usunąć w tym sensie, że ich zlokalizowanie i skorygowanie kosztowałoby więcej niż
zaprojektowanie i zakodowanie programu od nowa w poprawnym stylu.
Przykład 1.4: Połączenie danych i operacji w klasę zgodnie z metodyką programowania
obiektowego.
//* (C) 1994, Saumyendra Sengupta and Carl P. Korobkin *
//* and Springer-Verlag Publishing Company *
// Object-oriented implementation of interval
// numbers, [a, b], where a <= b.
#include <stdio.h>
class Interval {
private:
float lft_end_pt, // Left end point "a"
rgt_end_pt; // Right end point "a"
public:
Interval(float new_lft, float new_rgt); // Constructor
Interval(float new_lft_rgt); // Constr. for degenerate
friend Interval operator+(Interval A, Interval B);
void print_interval(char *hdr);
};
Interval::Interval(float new_lft, float new_rgt)
{
lft_end_pt = new_lft;
rgt_end_pt = new_rgt;
}
Interval::Interval(float new_lft_rgt)
{
3
AISD str. D
lft_end_pt = new_lft_rgt;
rgt_end_pt = new_lft_rgt;
}
Interval operator+ (Interval A, Interval B)
{
return ( Interval( A.lft_end_pt + B.lft_end_pt,
A.rgt_end_pt + B.rgt_end_pt));
}
void Interval::print_interval(char *hdr)
{
printf("Interval %s is: [ %f, %f] \n",
hdr, lft_end_pt, rgt_end_pt);
}
void main(void)
{
Interval intrvl_obj1 (-2, 4), intrvl_obj2 (6, 9);
printf("\n == OOP IMPLEMENTATION %s == \n",
"OF INTERVAL NUMBERS");
intrvl_obj1.print_interval("A");
intrvl_obj2.print_interval("B");
(intrvl_obj1 + intrvl_obj2).print_interval("A + B");
}
ZŁOŻONOŚĆ OBLICZENIOWA
Ważnym kryterium oceny własności algorytmów jest złożoność obliczeniowa. Dla oceny
algorytmu można wyznaczyć funkcję kosztu wykonania algorytmu. W zależności od sytuacji za
jednostkowy krok obliczeniowy do wyznaczania kosztu przyjmuje się: operację arytmetyczną
(algorytmy numeryczne), osiągnięcie kolejnego elementu struktury danych (algorytmy na
strukturach danych), jedno przesunięcie głowicy dysku (bazy danych). Rozróżnia się koszt
maksymalny, średni ewentualnie minimalny. Notacja
O(n)
[rzędu n] jest stosowana jako miara
przy określaniu złożoności obliczeniowej.
Dla dwu matematycznych funkcji
u(n)
i
v(n)
, gdzie
n
jest liczbą całkowitą,
u(n) jest rzędu
O(v(n))
, jeżli dla pewnych dodatnich stałych
p
i
q
u(n) <= p*v(n)
dla wszystkich
n >= q
(dla wszystkich odpowiednio dużych
n
)
Złożoności wielomianowe:
O(n)
- liniowa
np.
u(n) =
230n
O(n
2
)
- kwadratowa
np.
u(n) =
12n
2
+ 135n - 23
O(n
3
)
- sześciena
np.
u(n) =
n
3
+ 20n
2
- 19n + 1
Złożoności ograniczone przez wielomian:
O(log n) - logarytmiczna np.
3log (n+1) - 2
O(nlog n) - quasiliniowa np.
u(n) =
3nlog (n+1) - 2
Złożoności niewielomianowe:
NP-zupełna
O(a
n
)
- ykładnicza
np.
u(n) =
e
n
+ n
13
- n
2
4
AISD str. E
silnie NP-zupełna
NP-trudna
STRUKTURY DANYCH, A TYPY DANYCH I PROJEKTOWANIE
Abstrakcyjne typy danych określają operacje działające na obiekcie w sposób niezależny od
konkretnej implementacji. Natomiast struktury danych stanowią szczegółowe rozwiązanie
implementacyjne sposobu przechowywania danych. W rezultacie przy przy projektowaniu
oprogramowania najpierw pojawiają się typy danych - ich nazwy, operacje, nazwy argumentów i
sposób odwzorowania argumentów na wyniki. W końcowej fazie projektowania wprowadzane
są struktury danych do celów implementacji kodu operacji. Oczywiście projekt może być
prowadzony z zamiarem wykorzystania określonego rodzaju struktury, ale nie powinno to w
istotny sposób wpływać na początkowe fazy projektowania, w szczególności, w początkowych
fazach projektowania nie powinny się pojawiać żadne informacje na temat używanych
zmiennych wskaźnikowych, czy powiązań w strukturze danych. Te informacje szczegółowe
wprowadza się w ostatnim kroku projektowania (kodowanie) dla każdego z typów osobno.
Wobec powyższego niezręcznie jest mówić o typie danych "Drzewo", dlatego bo użycie
drzewiastej struktury danych jest jedną z możliwości implementacji jakiegoś projektowanego
typu danych. Podobnie niezbyt zręcznie jest mówić o abstrakcyjnym typie danych tablica. Lepiej
byłoby powiedzieć w tej sytuacji kolekcja jednoindeksowa, dwuindeksowa czy wieloindeksowa.
DEFINICJE ZWIĄZANE ZE STRUKTURAMI DANYCH
Przy omawianiu rodzajów struktur danych wygodnie będzie odwoływać się do pewnych
własności tych struktur.
Def.
Spójność
Struktura danych jest spójna jeśli dla każdych dwóch różnych jej obiektów A, B istnieje ciąg
obiektów rozpoczynający się w A i kończący w B, a dla każdych dwóch kolejnych obiektów w
ciągu pierwszy z nich jest następnikiem drugiego lub drugi jest następnikiem pierwszego.
Def.
Poprzednik
Poprzednikiem obiektu X w strukturze danych jest każdy obiekt Y taki, że X jest następnikiem
dla Y.
Def.
Początkowy
Obiektem początkowym struktury jest każdy taki obiekt X, że dla każdego innego obiektu Y w
strukturze istnieje ciąg obiektów rozpoczynający się w X i kończący w Y, a dla każdych dwóch
kolejnych obiektów w ciągu drugi z nich jest następnikiem pierwszego.
Def.
Obiekt beznastępnikowy
Obiektem beznastępnikowym struktury jest każdy obiekt, który nie ma innych następników niż
wartość null
.
5
[ Pobierz całość w formacie PDF ]