Algorytm - zespoł reguł w procesie przetwarzania danych. Cechy: Określoność, Jednoznaczność, Skończoność, Ogolność, Efektywność
Typ danych - zbior wartości, jakie przyjmować mogą zmienne tego typu. Aspekt statyczny - systemem plikow zw. ze zbiorem wart. odniesionym do konkretnego typu. Aspekt dynamiczny - zw. z operacjami na wart. z
definiowanego zb.. Przykłady typow w C: int, double, long double.
Struktura danych - zb. zm. określonych typow, posiadający swoistą strukturę i zw. z nią sposob korzystania z danych. 1. SD opisują sposob org. oraz metody dostępu do danych. 2. Podst. jednost. tworzącymi SD są komorki. 3. SD tworzy się poprzez agregacje komorek. Mechanizmy agregujące np: tablica, rekord, plik. 6. Typowe SD: listy powiązane, stosy, tablice, tablice asocjacyjne, drzewa, kolejki, grafy. Tablica - liniową strukturą zawierająca elementy tego samego typu. Do i-tegoelementu tablicy A można odwołać się za pośrednictwem pojedynczej instrukcji indeksowania A[i]. Lista - liniowa struktura elementow tego samego typu o dostępie sekwencyjnym. Dostęp do kolejnych elementow wymaga wcześniejszego dostępu do elementu poprzedzającego. Każdy element zawiera informacje. Odnośnie przejścia do kolejnego elementu.
Drzewa.
Drzewo - struktura rozgałęziona o dostępie sekwencyjnym. Rozgałęzienia
pozwalają na uporządkowane przechowywanie danych hierarchicznych, a także
na efektywne wyszukiwanie tylko w wybranych fragmentach struktury.
Drzewa stanowią podstawowy budulec złożonych struktur danych.
_ Istnieje kilka sposobow reprezentowania drzew wykorzystujących zarowno
wskaźniki dynamiczne, jak też indeksy.
Abstrakcyjne typy danych
ADT - narzędzie umożliwiające definiowanie operacji wykonywanych na
ustalonym zestawie danych (modelu danych).
ADT - specyfikacja zestawu danych i operacji, ktore są dostepne za
pośrednictwem interfejsu,
ADT - połączenie modelu danych i zbioru operacji jakie można na tym modelu
wykonać. Dwa identyczne modele danych, połączone z rożnymi zbiorami
operacji określają rożne ADT.
ADT - model danych, z ktorym skojarzono zestaw operacji.
Etapy projektowania algorytmow:
_ Sformułowanie problemu, wybor modelu ADT,
_ Specyfikacja algorytmu,
_ Analiza algorytmu - poprawność i złożoność obliczeniowa,
_ Testowanie programow implementujących algorytmy.
Aspekty analizy algorytmow:
_ Poprawność semantyczna
_ Złożoność obliczeniowa (czasowa, pamięciowa).
Algorytm jest poprawny jeśli:
_ Posiada własność określoności obliczeń względem warunku początkowego α.
_ Posiada własność stopu względem warunku początkowego α.
_ Jest cześciowo poprawny względem warunku początkowego α i
warunku końcowego β, co oznacza, że jeśli dla każdego zestawu
danych wejściowych spełniających warunek α obliczenie zakończy się
w punkcie końcowym to wyniki spełniają warunek β.
Algorytm jest niepoprawny, jeśli dla pewnych danych spełniających
warunek początkowy:
_ Działanie algorytmu zostaje przerwane,
_ Działanie algorytmu jest nieskończone (algorytm zapętlą się).
_ Algorytm wykonuje się do końca, lecz wyniki nie spełniają warunku końcowego
(są niepoprawne).
Quick_Sort (T. Hoare, 1962)
Cechy algorytmu:
_ Przeciętna złożoność obliczeniowa O(nlgn),
_ Pesymistyczna złożoność O(n2),
_ Sortowanie „w miejscu”,
_ Niestabilny,
_ Zastosowanie techniki „dziel i rządź”,
_ Rozproszone sortowanie,
_ Wpływ danych wejściowych na złożonoość obliczeniową,
_ Łatwa implementacja,
_ Wymaga stosunkowo mało zasobow,
_ Sprawdza się w sortowaniu średnich i dużych zbiorow danych.
Złożoność algorytmu zależy od sposobu podziału tablicy:
1. Podział niezrownoważony,
2. Podział zrownoważony.
Pesymistyczna złożoność algorytmu dla podziału niezrownoważonego.
Podział niezrownoważony - gdy procedura Partition tworzy dwie tablice:
_ 1-elementową,
_ (n-1) elementową,
Zakładamy, że podziały niezrownoważone będą wykonywane w każdym kroku
algorytmu.
Na najwyższym poziomie wywołania procedury Partition żaden element nie zostaje
umieszczony po lewej stronie elementu osiowego.
Po prawej stronie, elementu osiowego otrzymujemy tablicę pomniejszoną tylko o
jeden element.
1. Głębokość d (depth) węzła - liczba krawędzi leżących na unikalnej
ścieżce, prowadzącej od korzenia drzewa do tego węzła,
2. Wysokość h (height) - największa głębokość węzła,
3. Liść (leaf) - dowolny węzeł nie mający potomkow,
4. Węzeł wewnętrzny (interior node) - dowolny węzeł, mający
przynajmniej jednego potomka.
Pełne drzewo binarne (complete binary tree) spełnia warunki:
- wszystkie wewnętrzne węzły mają dwa potomki,
- głębokość wszystkich liści jest jednakowa (d = lgn ).
Zrownoważone drzewo binarne (balanced binary tree) spełnia
warunki:
- jest pełnym drzewem binarnym do głębokości d-1,
- wszystkie węzły na głębokości d = lgn znajdują się po lewej
stronie.
Kopiec (heap) - tablicowa implementacja zrownoważonego drzewa
binarnego.
Własności kopca (heap property):
1. Maksymalny element znajduje się w korzeniu,
2. Poddrzewo w swoim korzeniu zawiera maksymalny element z
elementow tego poddrzewa (partially ordered tree property).
3. Wartość w każdym węźle jest większa lub rowna wartościom w jego
węzłach potomnych.
4. Na ścieżkach od korzenia do liścia, elementy są posortowane
nierosnąco.
5. Podstawowe operacje na węzłach działają w czasie O(lgn).
Grafem nazywamy uporządkowaną parę G=(V, E):
V = {v1, v2,..., vn} - zbior wierzchołkow (węzłow) (nodes),
E = {(vi, vi+1), i=1,2,...n-1} - zbior krawędzi (arcs).
• Każda krawędź postaci (u,v)∈E jest reprezentowana poprzez u → v.
• Wierzchołek nazywamy początkiem krawędzi (head), zaś wierzchołek v końcem
krawędzi (tail).
• Krawędź (v, v) nazywamy pętlą (loop
•Poprzednik (predecessor), następnik (successor):
u→v, u - poprzednik v - następnik
• Etykieta (label) - identyfikatory wierzchołkow lub krawędzi.
• Ścieżka (path):
Lista wierzchołkow (v1, v2,..., vk) taka, że: vi→ vi+1 dla i=1,2,...,k-1.
• Cykl (cycle): Ścieżka, ktora zaczyna się i kończy w tym samym wierzchołku.
Grafy skierowane (zorientowane) (directed graph): krawędzie są
uporządkowanymi parami wierzchołkow.
• Grafy nieskierowane (undirected): krawędzie są dwuelementowymi
podzbiorami zbioru wierzchołkow.
Drzewo - hierarchiczna struktura danych
Drzewo stanowi kolekcję węzłow (nodes), z ktorych jeden wyrożniony jest jako
korzeń (root).
• Węzły powiązane są ze sobą relacją rodzicielstwa (parenthood).
• Węzły, ktore mają tego samego rodzica nazywamy węzłami siostrzanymi
(siblings).
• Wysokość węzła - liczba krawędzi na najdłuższej, prostej ścieżce prowadzącej
od tego węzła do liścia.
• Głębokość (depth) węzła - długość ścieżki łączącej węzeł z korzeniem.
• Poziom węzła - długość ścieżki od korzenia do węzła plus 1 (liczba węzłow na
ścieżce).
• Wysokością (height) drzewa - największy z poziomow węzłow w drzewie.
Pusta struktura jest drzewem pustym.
• Pojedynczy węzeł jest zarazem drzewem i korzeniem.
• Założmy, że n jest węzłem, a T1, T2, ...,Tk, są drzewami o korzeniach
odpowiednio n1, n2, ..., nk.
• Jeśli węzeł n jest przodkiem (ancestor) węzłow n1, n2, ..., nk to drzewa
T1, T2, ...,Tk stają się poddrzewami (subtrees) utworzonego drzewa, a węzły
potomkami (descendents) węzła n.
Drzewo binarne BT (binary trees) - drzewo, ktorego każdy z węzłow posiada:
- lewe i prawe poddrzewo,
- posiada jedno z nich,
- nie posiada poddrzew (drzewo puste).
Drzewo BST - dowolne drzewo binarne, w ktorym elementy zbioru
są wpisane do wierzchołkow zgodnie z porządkiem symetrycznym
Przeglądanie poprzeczne inorder:
• klucz korzenia poddrzewa zostaje wypisany między wartościami z jego lewego
poddrzewa a wartościami z jego prawego poddrzewa.
Przeglądanie wzdłużne (preorder):
• Klucz korzenia poddrzewa zostaje wypisany przed wypisaniem kluczy w obu
poddrzewach.
Przeglądanie wsteczne (postorder):
• klucz korzenia poddrzewa zostaje wypisany po wypisaniu kluczy w obu
poddrzewach.
Złożoność obliczeniowa operacji na drzewach BST jest proporcjonalna do
wysokości drzewa,
• Zrownoważone drzewo binarne - rożnica wysokości obu poddrzew każdego węzła
w drzewie wynosi 0 lub 1,
• Drzewo w pełni zrownoważone - jeśli jest zrownoważone, a wszystkie liście
znajdują się na jednym lub dwoch poziomach.
• Drzewa zrownoważone są drzewami BST gwarantującymi wysokość O(lg n).
Zrownoważone drzewa AVL:
• Drzewa rownoważone lokalnie,
• Dla każdego węzła wysokość poddrzew rożni się nie więcej niż o jeden poziom,
• Wspołczynnik zrownoważenia: 1, -1, 0.
Dla drzewa AVL zachodzi zależność:
lg (n+1) ≤ h < 1.44 lg ( n+2 )
Słownik (Dictionary) : ADT z zestawem operacji: INSERT, DELATE, SEARCH
(LOOKUP, MEMBER).
Reprezentacje słownika:
• Tablica lub lista nieposortowana,
• Tablica lub lista posortowana,
• Drzewa BST, drzewa AVL,
• Tablica haszowana (Hash Table).
1. Wyszukiwanie sekwencyjne
2. Wyszukiwanie binarne
3. Wyszukiwanie w drzewach: BST, AVL
Wybor funkcji haszującej.
Funkcja haszująca powinna:
• Być łatwo obliczalna,
• Dawać rownomierne haszowanie, (każdy indeks [0, 1, ..., m-1]
winien być jednakowo prawdopodobny jako wartość funkcji).
Warunek prostego rownomiernego haszowania:
Σx:h(x)=k P(x) = 1/m dla k=0,1, ...m-1
W przedziale 0 ≤ x < 1 funkcja haszująca postaci:
h(x) = m x
spełnia warunek rownomiernego haszowania.
Haszowanie modularne:
h(x) = x mod m
• Wartości m będące potęgami dwojki są niekorzystne,
• Jeśli kluczami są ciągi znakow x=a1, a2 ...ak to obliczyć y= a1+ a2+ ... +ak, oraz y
mod m (otrzymamy wartość z przedziału [0, m-1]).
Haszowanie przez mnnożenie:
• Pomnożyć klucz x przez (0<<1), a następnie wyznaczyć część ułamkową x
• Pomnożyć otrzymaną wartość przez m i wyznaczaczyć funkcję:
h(x) = m(x mod 1) ,
gdzie: x mod 1 oznacza ułamkową część x tj. x - x
≈ (√5 - 1)/2 ≈ 0,618
Rozwiązywanie kolizji.
HASH_h ( x ) //x tablica znakow;
{
s:=0;
i:=0;
DOPOKI ( x[i] ≠ ` ∇ ' ) { //∇ - znak pusty;
s:=s+x[i];
i++
}
ZWROC ( s mod m ); // zakładamy m = 5;
}
Haszowanie otwarte (Open hashing).
Funkcja haszująca:
h(x, i) = y
gdzie: x - klucz,
i - liczba dotychczasowych probkowań,
y - uzyskany kod haszowania.
Funkcja haszująca z adresowaniem (probkowaniem) liniowym:
h(x, i)=(h'(x) +i) mod m, dla i=0, 1, 2, ..., m-1
h' (x) =x mod m
Dla każdego klucza x jego ciąg probkowania zaczyna się od pozycji H[h'(x)],
H[h'(x)+1],..., H[m-1]. Dalej występują pozycje: H[0], H[1], ..., H[h'(x) -1].
Generowanych jest m rożnych ciągow kontrolnych.
Tendencja do grupowania (primary clustering) zajętych pozycji.
Funkcja haszowania:
h(x, i)=(h1(x) +i h2(x)) mod m, dla i=0, 1, 2, ..., m-1
h1, h2 - pomocnicze funkcje haszujące.
_ Warunki:
1. m - potęga dwojki
h2 - zwraca tylko wartości nieparzyste
2. m - liczba pierwsza
h2 - zwraca liczby mniejsze od m (np. m-1, m-2)
_ Przykładowe funkcje haszujące:
h1(x) = x mod m
h2(x) = 1 + (x mod m'),
Algorytmy tekstowe
Pojęcia i oznaczenia.
• Σ - alfabet skończony zbior symboli (np. Σ ={0,1} lub Σ={a,b, n, z}
• Tekst (słowo) - ciąg symboli alfabetu Σ
• Długość tekstu - liczba jego symboli
• T[1 .. n]- tekst, n-elementowa tablica T (Text)
• P[l .. m] - wzorzec, m-elementowa tablica P (Pattern)
• Reprezentacje tekstow: listowa, tablicowa
Dla dowolnego słowa X:
X[i .. j] = X[i] [i+1]n X[j], gdzie i ≤ j.
Wzorzec P występuje w tekście T na pozycji i (wzorzec pasuje do tekstu
począwszy od i-tej pozycji) gdy:
T[i .. i+ m-1] = P[l .. m]
T[i + j -1] = P[j] dla 1≤ j ≤ m
Algorytm N „Naiwny” (algorytm typu Brute-force).
Dla każdej z n-m+1 możliwych wartości i algorytm znajduje wszystkie wystąpienia
wzorca. W pętli sprawdzany jest warunek:
T[i .. i+m-1] = P[l .. m]
P p1 p2 n pk n pm
1 i n-m+1
t1 t2 ti n tn-m tn-m+1 n tn T n
Złożoność obliczeniowa algorytmu O((n-m+1)m).
Algorytm KR (Karpa R. i Rabina M.)
1. Wzorzec P[1 .. m] o długości m znakow interpretowany jest jako liczbę m
cyfrową w systemie o zadanej podstawie r. Wyznaczana jest wartość funkcji
haszującej hP=h(P[1 .. m]).
2. Dla tekstu wejściowego T[i .. i+m-1] wyznaczana jest funkcja haszująca
hT=h(T[I .. i+m-1]).
3. Sprawdzenie zgodności wzorca z aktualnie badanym fragmentem tekstu
sprowadza się do sprawdzania warunku hP=hT.
Dla tekstu T[i .. i+m-1] definiowana jest wartość:
Ti = T[i] rm-1 + T[i+1] rm-2 + n+T[i+m-1]
Dla tekstu T[i+1 .. i+m] otrzymujemy:
Ti+1 = T[i+1] rm-1 + T[i+] rm-2 + n +T[i+m-1]*r +T[i+m]
Zależność Ti+1 od Ti:
Ti * r = T[i] rm-1
*r + T[i+1] rm-2
*r + n+T[i+m-1]*r + T[i+m] - T[i+m] =
T[i] rm-1
*r + Ti+1 - T[i+m]
Ti+1 = (Ti - T[i] rm-1) r +T[i+m]
Wobec tego:
Funkcja haszująca:
h(Ti) = Ti mod q
gdzie: q jest dużą liczbą pierwszą.
Złożoność obliczeniowa algorytmów
1. Porownanie rożnych algorytmow rozwiązujących te same problemy,
2. Przewidywanie wydajności algorytmow w nowym środowisku,
3. Określenie wartości parametrow algorytmow.
Podstawowe rodzaje złożoności:
_ Złożoność czasowa (Time complexity analysis),
_ Złożoność pamięciową (Space complexity analysis).
Rodzaje czasowej złożoności obliczeniowej:
1. Złożoność pesymistyczna (Worst-case complexity),
2. Złożoność oczekiwana (Average-case complexity),
3. Złożoność optymistyczna (Best-case complexity),
Dn - zbior możliwych zestawow (instancji) danych o rozmiarze n,
In - zestaw danych o rozmiarze n (In ∈ Dn),
t(In) - liczba operacji podstawowych dla zestawu In,
p(In) - prawdopodobieństwo wystąpienia zestawu In,
Xn(In) - zmienna losowa o wartości t(In) i rozkładzie prawdopodobieństawa
p(In).
Złożoność pesymistyczna:
W(n) = sup { t(In): In ∈ Dn}.
2. Złożoność oczekiwana:
3. Złożoność optymistyczna:
B(n) = inf { t(In): In ∈ Dn }
A(n) = Σ
In∈Dn
p(In) t (In)
4. Wrażliwość pesymistyczna (worst- case sensitivity):
_ (n) = W(n) - B(n) = max { t(In
1) - t(In
2): In
1, In
2∈Dn },
5. Wrażliwość oczekiwana (average- case sensitivity):
δ(n) = dev(Xn) = √ Var(Xn)
gdzie: dev(Xn) - standardowe odchylenie zmiennej Xn,
Var(Xn) - wariancja zmiennej losowej Xn,
Search (A, n, x) // A-tablica indeksowana od 1 do n
{
ind := 1;
DOPOKI ( ind ≤ n and A[ind] ≠ x) {
ind := ind + 1
}
JEZELI (ind > n) {
ind :=0
}
ZWROC(ind)
}
_ Analiza najgorszego przypadku:
- x zajmuje ostatnią pozycję,
- x nie występuje w tablicy
W(n) = n.
Analiza średniego przypadku:
1. Założenia:
- wszystkie elementy tablicy są rożne,
- x na pewno należy do A,
- x może być na każdej pozycji z jednakowym prawdopodobieństwem.
2. Założenia:
Ii - reprezentuje przypadek, gdy x jest na i-tej pozycji,
In+1 - reprezentuje przypadek, gdy x nie ma w tablicy,
q - oznacza prawdopodobieństwo, że x jest w tablicy,
Dla 1 ≤ i ≤ n: p(Ii)=q/n, p(In+1)=1-q, t(Ii)=i, t(In+1)=n.
A(n) = p(Ii) t (Ii) = Σi
Dla q=1: A(n) = (n+1)/2,
Dla q=1/2: A(n) = (n+1)/4 +n/2
Złożoność obliczeniowa w każdym przypadku (Every-case time complexity):
SORT(n) // n-rozmiar problemu
}
DLA i:=1, 2, ...,n-1 {
DLA j:= i+1, ...,n {
Operacja podstawowa
}
}
}
A(n) = W(n) = (n-1) + (n-2) + ...+ 2 +1 = . (n (n-1)) = . (n2 - n)
TEC(n) = n → sumowanie elementow tablicy,
TEC(n) = n3 → mnożenie tablic dwuwymiarowych,
TEC(n) = (n-1)n/2 → sortowanie select_sort.