algorytmy-mini, POLITECHNIKA wydział E kierunek I, ALGORYTMY I ZLOZONOSC, ROZNE JAKIES TAM


1. Modele w informatyce a).Cel: -Opis rzeczywistości -Uzasadnienie zjawisk w rzeczywistości -Retrospekcja -Przekształcenie rzeczywistości -Przewidywanie; b).Środki -Otoczenie, w tym ludzie-Sprzęt-Oprogramowanie

2. Geneza -Pierwszy znany: Euklides (III w p Ch) -największy wspólny podzielnik -Nazwa: Al-Khowârizmî(Persja, VIII-IX w)

3.budowa algorytmu a)..Założenia-Co jest przedmiotem algorytmu?-Jaki jest model użytkownika?-Jak określone jest otoczenie?-Przesłanki technologiczne; b)..Poziom abstrakcji -podstawowe działania (dalej nie definiowane); c)..Kolejnośćdziałania d)Czas działania e).Szeregowośći równoległośćw działaniu f).Pętle g).Algorytmy składowe h).Rekursywność i)..Uniwersalność

4. Złożoność obliczeniowa algorytmów..Problem -Czy to da siępoliczyć?-Jakie zasoby potrzebne sądo wykonania algorytm?..Złożonośćobliczeniowa algorytmów-Ilośćzasobów niezbędnych do wykonania algorytmu?-Jak zachowuje sięalgorytm wraz ze zwiększeniem sięwymiaru problemu?..Czy algorytm jest rozstrzygalny -daje stan końcowy w

skończonej liczbie operacji

5. O(f(N)-rząd złożoności...O(1)-złożonośćrzędu 1 -liczba operacji jest w przybliżeniu

niezależna od rozmiaru problemu -Bez względu na wielkośćprzetwarzanych obiektów algorytm trwa tak samo długo lub krótko -Nie rozróżniamy złożoności a O(1)od złożoności b O(1), nawet jeżeli a ob (dotyczy to wszystkich rzędów złożoności) -Niska złożonośćmoże oznaczaćbardzo długie wykonywanie algorytmu -bardzo długie bez względu na rozmiar problemu (tak samo długo dla populacji 30 i 30 milionów osób)

-Rząd złożoności pozostaje ten sam mimo, że:..Zamieniamy stomatologa na szybszego lub wolniejszego..Wszyscy pacjenci mająbardzo pracochłonne zabiegi lub wszyscy mająnajkrótsze porady

6. Operacje związane z listami..Czytanie pierwszego elementu z listy front (q) = q (1)

..Wstawianie elementu x na początek listy push(q,x) = [x] & q;..Usuwanie jednego elementu z początku listy pop (q) = q (2 .. |q|);..Czytanie ostatniego elementu z listy read(q) = q (|n|);

..Wstawianie elementu x na koniec listy inject(q,x) = q & [x] ;.Usuwanie jednego elementu z końca listy eject(q) = q(1 .. (|q|-1))

Jeżeli możliwe jest wykonanie wszystkich operacji, to listęnazywamy kolejką dwustronną

7. Stos..Lista z możliwościąwykonania tylko operacji -Czytanie pierwszego elementu z listy

-Wstawianie elementu x na początek listy;Usuwanie jednego elementu z początku listy= dostęp tylko do początku listy LIFO -last in first out

8.Kolejka ..Lista z możliwościąwykonania tylko operacji -Czytanie pierwszego elementu z listy-Usuwanie jednego elementu z początku listy-Wstawianie elementu x na koniec listy= organizacja..Czytanie tylko z początku listy ..Wstawianie na koniec listy FIFO -first in first out

9. Kolejka priorytetowa..Celem jest czytanie (i ewentualne usuwanie) każdorazowo

największego elementu (lub najmniejszego)..Podejścia-Kolejka priorytetowa przygotowana

..Każdorazowo nowy element wstawiany jest na miejsce w kolejce wynikające z jego porządku według relacji większości (mniejszości)

10. Algorytmy rekurencyjne Fraktale..Struktura rekurencyjna..W każdej skali ma nie banalnąstrukturę..Wymiar Hausdorffajest większy niżjego wymiar topologiczny..Najczęściej ma wygląd nawiązujący do struktur z natury

Zastosowanie ..Rozwiązanie problemu o rozmiarze danych wejściowych n daje sięrozwiązaćprzez rozwiązanie tego samego problemu o mniejszym rozmiarze danych

wejściowych ..

Założenia-Można określićproblem o mniejszym rozmiarze -Jego rozwiązanie jest łatwiejsze

-Na podstawie rozwiązania problemu o mniejszym rozmiarze można rozwiązaćproblem o większym rozmiarze

11.Poprawność algorytmów rekurencyjnych ..Nawiązuje do metody dowodzenia indukcyjnego w matematyce..Algorytmy-Udowodnić, że rozwiązanie algorytmu o najmniejszej złożoności jest poprawne-Udowodnić, że problem jest rekurencyjny

-Udowodnić, że założenie poprawności algorytmu o najmniejszej złożoności prowadzi do poprawności algorytmu o większej złożoności

Implementacja..Przez umieszczanie zadania bardziej złożonego na stos i pobieranie go, kiedy zadania mniej skomplikowane zostaną rozwiązane ..Niebezpieczeństwa -Przepełnienie stosu -brak pamięci-Brak spełnienia warunku stop -złe zaprojektowanie algorytmu

12. Zastosowania al. rekurencyjnych ..Metoda dziel i zwyciężaj (divide and conquer)

-Top down-Dzielenie problemu na problemy o mniejszym wymiarze

..Metoda programowania dynamicznego (dynamic programming) -Bottom up -Wstępujące rozwiązanie -po rozwiązaniu problemu mniej złożonego -rozwiązanie problemu bardziej złożonego

..Zalety -Łatwośćzrozumienia-Mała złożoność;..Wady-Duże zapotrzebowanie na

pamięć

13. Wyszukiwanie naiwne ..Cel: wyszukaj element xo typie zgodnym z elementami tablicy

functionWyszukaj (x, tablica [1..n])

begin

for i:=1 to n do

iftablica [i] = x return i;

od

return w tablicy nie ma elementu x

end

..Złożoność-Algorytmu O(n)-kiedy? -W średnim przypadku O (log (n+1)/2) = O(n)-dlaczego? -W najlepszym przypadku O (1)-kiedy?

14. Wyszukiwanie binarne..Założenie: dana jest uporządkowana tablica-

kryterium porządku (liczbowy, alfabetyczny, chronologiczny …) ..Cel: wyszukaj element xo typie zgodnym z elementami tablicy..Uwaga: w przykładowym algorytmie tablica uporządkowana jest rosnąco

functionWyszukaj Binarnie (x, tablica [1..n])

begin

i = 1 (*dolna granica przeszukiwania*)

j = n (*górna granica przeszukiwania*)

whilei .j do begin

m = (i + j) / 2

if(tablica [m] < x)

theni = m + 1

elseiftablica [m] > x

thenj = m -1

elsereturn m; end

return w tablicy nie ma elementu x end;

.Złożoność O (log n)

15.Algorytm SF (straight forward)..Pierwszy znak z łańcucha poszukiwany wyszukiwany

jest w łańcuchu przeszukiwany ..Jeżeli jest znaleziony na pozycji i łańcucha

przeszukiwany, to porównywane sąposzukiwany [j] z [i + j] dla j = (2 …|poszukiwany|) -

kiedy?..Jeżeli poszukiwany [j] .przeszukiwany[i + j], to porównujemy [1] z [i + j]

..Złożonośćobliczeniowa O (|poszukiwany| x | przeszukiwany|)

poszukiwany = array [1…|poszukiwany|] of char;

przeszukiwany= array [1..| przeszukiwany|] of char;

function SF(vart: przeszukiwany; varm: poszukiwany): integer;

var j, k: integer;

begin j := 1;k := 1;

repeat

if t[k] <> m[j] then begin

if j>1 then k := k -j + 1;

j := 0 end;

j := j + 1;k := k + 1;

until (k> | przeszukiwany|) or (j> |poszukiwany|);

if j> |poszukiwany| then SF:= k -|poszukiwany|elseSF:= 0 end

16. Automaty skończone nazywamy uporządkowaną piątkę (Q, ., A, ., q0)gdzie

-Q-skończony zbiór stanów automatu -E(suma)-skończony zbiór stanowiący alfabet automatu -A-zbiór akceptowanych stanów automatu AfQ

-fi.-funkcja przejścia automatu .: Q x -›Q

-q00Q-stan początkowy automatu q00Q

17. Algorytm Aho-Corasik..Dane-.skończony alfabet -x0.*skończony łańcuch tekstowy

-Zbiór słów kluczowych

K = {y1, y2, …yk} | yi0.*

..Zlokalizować wszystkie wystąpienia słów kluczowych w x..Podejścia

-Wielokrotne czytanie dla znalezienia każdego słowa kluczowego osobno

-Jednokrotne czytanie dla znalezienia wszystkich słów kluczowych

18. Słownik -implementacja zbioru.. Słownik to struktura danych A pozwalająca na:

-Stworzenie słownika Constract(A)A = .

-Wstawianie elementu do słownika (możliwe na zbiorach) Insert (a, A)A = A c{a}

-Usuwanie elementu ze słownika (możliwe na zbiorach)Delete(a, A)A = A -{a}

-Podanie pozycji elementu w słowniku (nie możliwe na zbiorach)Search (a, A) Position(a, A)

IF a óA THEN Position(a, A) = NUL

19.Odwołanie do elementu słownika..Przez wartośćelementu, a nie przez pozycję(jak ma to miejsce w listach lub tablicach) -.Słowniki sąjednak implementowane przez uporządkowane lub nieuporządkowane listy lub tablice; -.Szczególnie interesujące listy lub tablice rekordów -dostęp do elementu słownika przez wartośćjednego z pól znanego kluczem

..Klucz musi pozwalaćokreślićrelacjęporządku -w konsekwencji możliwe jest określenie wartości funkcji

-Minimum (A) -zwraca pozycjęelementu o najmniejszej wartości klucza

-Maximum(A) -zwraca pozycjęelementu o największej wartośćklucza

-Successor(A, a) -zwraca pozycjęelementu następującego po a

-Predecessor(A, a) -zwraca pozycjęelementu poprzedzającego a

20. Grafem nazywamy G = (W, I) Gdzie -Zbiór W nazywamy zbiorem wierzchołków (węzłów)-Zbiór I nazywamy zbiorem krawędzi (powiązań, incydencji) I = {(x, y): x, y 0W vx .y}

..Rozmiar grafu n = |W| m = |I|

21. Graf skierowany (x, y) 0I ›(y, x) óI

..Obraz graficzny -Linia łącząca węzły zakończona strzałką -Pomiędzy dwoma węzłami mogąbyćpoprowadzone co najwyżej dwie linie (o strzałkach skierowanych w przeciwnych kierunkach) ..Maksymalna liczba krawędzi mmax= |W|2

22. Graf nieskierowany (x, y) 0I ›(y, x) 0I ..Obraz graficzny: -Linia łącząca węzły

-Pomiędzy dwoma węzłami może byćpoprowadzona co najwyżej jedna linia

..Maksymalna liczba krawędzi mmax= 0.5(|W| -1) |W|

23..Graf nazywamy planarnym, gdy można go narysowaćna płaszczyźnie bez

przecinania się krawędzi ..Graf pełny m = mmax ..Graf rzadki m nmmax

24. Cykle w grafach..Jeżeli istnieje p (wp,wk), to węzełwknazywamy

osiągalnym z węzła wp ..Cyklem nazywamy ścieżkęp (wp, wp)

.Jeżeli graf nie zawiera żadnego cyklu, to nazywamy go acyklicznym

.Cykl prowadzący przez każdy węzełnazywamy cyklem Hamilton'a

.Cykl, do którego należy każde połączenie, nazywamy cyklem Euler'a

25. Spójność grafów..Graf nazywamy spójnym, jeżeli pomiędzy dowolnymi

dwoma węzłami istnieje ścieżka..Graf skierowany nazywamy silne spójnym, jeżeli

pomiędzy dwoma dowolnymi węzłami u i v istnieją p (u,v) vp (v,u)

26. Stopnie grafów ..Stopniem węzła grafu nieskierowanegonazywamy

liczbępowiązańz nim związanych ..Stopniem węzła grafu skierowanego nazywamy liczbępowiązańdochodzących do niego..Grafem regularnym nazywamy graf, którego węzły

mająten sam stopień

27. Opisywanie grafów ..Powiązaniom mogąbyćprzypisane atrybuty -Najczęściej liczby zwane wagami-Interpretacja: koszt, odległość..Węzłom mogąbyćprzyporządkowane etykiety

-Unikalna nazwa, identyfikator -odróżnienie od innych węzłów..Problem: sprawdzenie izomorfizmu = sprawdzenie, czy przy pominięciu wag i etykiet grafy sąidentyczne

28. Implementacja grafów -macierz sąsiedztwa

A[x,y] = 1 jeżeli (x,y) 0I

A[x,y] = 0 jeżeli (x,y) óI

Uwaga: etykiety węzłów i powiązań, na przykład numery lub oznaczenia literowe nie sązwiązane z definicjągrafu, mogąbyćzwiązane z jego implementacją

29..Drzewem nazywamy dowolny graf spójny i acykliczny..Każdy węzeł, który ma przynajmniej jednego potomka, nazywamy węzłem wewnętrznym drzewa

..Każdy węzeł, który nie ma potomka, nazywamy liściem drzewa

30..Lasem nazywamy zbiór rozłącznych drzew (w lesie istniejąprzynajmniej dwa węzły, pomiędzy którymi nie można wyznaczyćścieżki)

31. Drzewem rozpinające grafu G = (W, I) nazywamy graf G'= (W, I') będący

drzewem, gdzie I'fI (kiedy I'dI?)

32. Binarne drzewa wyszukiwawcze..Wyróżniamy lewego i prawego potomka węzła

..Węzłom przyporządkowujemy wartości..Na wartościach węzłów określona jest relacja porządku..Binarnym drzewem wyszukiwawczym nazywamy drzewo binarne, gdzie dla każdego węzła spełnione sąwarunki: -Lewy potomek oraz wszystkie węzły poddrzewa, którego jest on korzeniem, mająmniejsząwartośćniżwartośćwęzła -Prawy potomek oraz wszystkie węzły poddrzewa, którego jest on korzeniem, mająwiększąwartośćniżwartośćwęzła

33.Szukanie węzła o zadanej wartości wartość

function SzukanyWęzeł(varwartość:węzeł): węzeł;

VarBieżącyWęzeł: węzeł Begin

BieżącyWęzeł:= root

repeat

ifBieżącyWęzeł= wartośćthenSzukanyWęzeł:= BieżącyWęzeł

ifBieżącyWęzeł> wartość

thenBieżącyWęzeł:= LewySyn

elseBieżącyWęzeł:= PrawySyn

UntilBieżącyWęzeł= NILEnd

34. Wstawianie węzła - algorytm

function WstawWęzeł(varwartość:węzeł): węzeł;

VarBieżącyWęzeł: węzeł Begin

BieżącyWęzeł:= root

repeat

ifBieżącyWęzeł= wartośćthenSzukanyWęzeł:= BieżącyWęzeł

ifBieżącyWęzeł> wartość

thenBieżącyWęzeł:= LewySyn

elseBieżącyWęzeł:= PrawySyn

ifBieżącyWęzeł= NIL thenWstawWęzełWNIL(wartość)

UntilBieżącyWęzeł= NILend

35. Usuwanie węzła o zadanej wartości 1.Jest liściem -usuwamy 2.Posiada jednego potomka (obojętnie lewego czy prawego) -usuwamy węzeł, a potomek zajmuje jego miejsce

3.Posiada dwóch potomków -zastępowany jest następnikiem, a dalej punkt 1. lub 2.

36. Trawersowanie drzew..Problem: należy odwiedzićwszystkie węzły - dokonując na nich dokładnie raz określonąoperację..

37. Trawersowanie drzewa in order-Trawersuj lewe poddrzewo od węzła X in order

-Dokonaj operacji na węźle X -Trawersuj prawe poddrzewo od węzła X in order

38. Trawersowanie drzewa preorder..Algorytm -Dokonaj operacji na węźle X

-Trawersuj lewe poddrzewo od węzła X preorder -Trawersuj prawe poddrzewo od węzła X preorder

39. Przeszukiwanie grafu wszerz..Rozpoczynamy od węzła początkowego ..Badamy wszystkie węzły o najkrótszej drodze kod węzła początkowego

40. Algorytm inicjujący

..Graf G = (W, I) reprezentowany jest przez listy sąsiedztwa każdego węzła:

-tablica o wymiarze |W| -Sąsiedztwo [i] = 1 jeżeli węzełi jest sąsiadem węzła, dla którego zbudowano listę-Sąsiedztwo [i] = 0 jeżeli węzełi nie jest sąsiadem węzła..Dla każdego węzła ugrafu określamy -Zmiennąkolor (zgodnie z poprzednim przykładem)

..Kolor (u) = biały (węzełnie byłjeszcze odwiedzony) ..Kolor (u) = szary (węzełjest odwiedzany) ..Kolor (u) = czerwony (węzełbyłodwiedzony)

-Zmiennąpoprzednik (jeżeli węzełnie zostałjeszcze odwiedzony, to poprzednik

(u) = 0) -Odległośćwęzła od węzła początkowego odległość(u) (jeżeli odległośćnie jest

znana, to określamy jąjako nieskończoną)

Inicjuj zmienne (G, s) (* G = (W, I), s węzełpoczątkowy *)

FOR dla każdego u 0W DO

kolor (u) := biały

poprzednik (u) := 0

odległość(u) := %

END

kolor (s) := szary

odległość(s) := 0

poprzednik (s) := 0

Q := NULL END

41. Algorytm przeszukiwania wszerz

Przeszukiwanie Wszerz (G, s) (* G = (W, I), s węzełpoczątkowy *)

Inicjuj zmienne (G, s)

EnQueue(Q, s)

WHILE Q ..DO

u := DeQueue(Q)

FOR każdego vbędącego następnikiem u DO

IF kolor (v) = biały THEN

kolor (v) := szary

odległość(v) := odległość(u) + 1

poprzednik (v) := u

EnQueue(Q, v)

END END

kolor (u) := czerwonyEND

42. Algorytm Dijkstry

Dijkstry(G: graf)

FOR każdy v 0W DO

d(v) := %;

pop(v) := NULL

END FOR

d(s) := 0; Q := W;

WHILE Q ..DO

u jest węzłem o najmniejszym d(u)

Q := Q -{u}

FOR każdy v dla którego istnieje (u,v) DO

relaksuj (u,v)

END FOR

END WHILE END


Wyszukiwarka