1.notacja O(f(n)),Ɵ(f(n)),Ω(f(n)) def:

T(n)=O(f(n)) istnieje takie stałe c>0, n₀ >0, że T(n)<=c*f(n) dla n>=n₀

T(n)=Ω(f(n)) istnieje takie stałe c>0, n₀ >0, że T(n)>=c*f(n) dla n>=n₀

T(n)=Ɵ(f(n)) istnieje takie stałe c₁,c₂>0, n₀ >0, że c₁*f(n)<=T(n)<=c₂*f(n) dla n>=n₀

oszacować złożoność:

for i<-- 1 to n do P(i)

gdzie P(i) jest Ɵ(n) dla każdego i

T- pesymistyczna złożoność algorytmu

T(n)=Ɵ(n²) bo i <-- 1 to n jest Ɵ(n) czyli n*n=n²

2.Kopce binarne

Def: Pełne drzewo binarne gdzie wszystko jest równomierne zapełnione oprócz liści drzewa.

Ojciec>= syn bo są elementy uporządkowane

8 /\ 6 7 /\ /\ 3 2 1 4

Reprezentacja tablicowa 8 6 7 3 2 Lewy syn i-tego jest na pozycji 2*i a prawy 2*i+1. A ojciec ˻ i/2 ˼

Związek wysokości kopca z ilością elementów

H= ˻ lg n ˼ lub h=O(lg n) lub h=Ɵ(lg n)

3. Jakie są typowe operacje na kopcach binarnych i ich złożoność:

1. Wstawianie - Insert - Ɵ(lg n)

2. usunięcie maxymalnego - extract-max - Ɵ(lg n)

3. podanie wartosci ele. Max. - Maximum - Ɵ(1)

4. budowa kopca - build-heap - Ɵ(n)

wysokość kopca jest niewiększa niż lg n, a wstawienie polega na przejściu z góry kopca w dół ścieżką od korzenia do liścia, a wysokość jest logarytmiczna

zastosowanie: implementacja kolejek priorytetowych

4.oszacowanie górne i dolne zło pes Heap sort

heap-sort Ɵ(n* lg n)

uzasadnienie build heap

czas pesymistyczny T(n)<={Ɵ(n)} +{ n*0(n*lg n)}

pętla sortująca, bierzemy ostatni element i wstawiamy na górę n razy operacji kopcowania, gdzie wysokość kopca<= lg n

5.Kolejki piorytetowe: Typowe operacje:

a) dla list uporzadkowanych

1. Insert Ɵ(n)

2. extract-max Ɵ(1)

3. maximum Ω(1)

b) dla list nie uporząttkowanych

1. Insert Ɵ(1)

2. extract-max Ɵ(n)

3. maximum Ω(n)

6.Quick sort:

zło pes: Ɵ(n²)

czas podziału Patrition

T(n)>=n+(n-1)+(n-2)+...+2=Ω(n²)

Drzewo rekursji

Czas<=n*Ɵ(n)=O(n²)

Czas oczekiwany dla wersji probabilistycznej

T(n) = O(n*lg n)

n

T(n)<={Ɵ(n)}+{1/n(Σ (T(i) +T(n-i) + T(n-1)+ T(1))}

i=1

7.Dolne oszacowanie zło pes alg sort przez porównania

Ω(n*lg n)

T(n)>=c*n*lg n

uzasa: Algorytm sortujący przez porównania reprezentujemy jak drzewo decyzyjne, które musi mieć co najmniej n! liści, a z tego wynika że ma wysokość h>=lg n! czyli Ω(n*lg n), czyli złożoność pesymistyczna>= wysokości drzewa decyzyjnego Ω(n*lg n)

Drzewo decyzyjne:

Def: pełne drzewo binarne, które przedstawia porównywanie wykonywane przez algo sort.

8.Sortowanie w czasie liniowym algorytm, znane algorytmy:

1. sortowanie przez zliczanie-Counting-Sort - złożoność O(n+k) k- zakres wartości czyli O(n) gdy k jest stałe, k jest O(n);

ograniczenia: k zawsze jest do jakieś wartości

2. Sortowanie przez pozycyjne (Rodix-sort)- złożoność O(d(n+k)), każda pozycja sortowana przez zliczanie; d- ilość pozycji;O(n) gdy k,d są stałe;

ograniczenia: ze względu na ilość pozycji

9.Elementarne struktury danych, typowe operacje, zło na na stosach, kolejkach i listach:

Zło: wszystkie maja Ɵ(1)

Wyjątek - szukanie na n elementowych listach Ɵ(n)

Operacje: stosy- PUSH, POP, kolejki- ENQUEUE, DEQUEUE, listy-

10.Tab hasz

Np. h(k)=k mod m Cechy: - łatwa do liczenia Ɵ(1) - równomiernie rozrzuca klucze po pozycjach 0... m-1

11.tab hasz Łańcuchowa metoda

Pes zło:1.wstaw Ɵ(1), 2. szukaj Ɵ(n)

Oczekiwana zło O(1+α) α=n/m m- współczynnik wypełnienia n- ilość kluczy w tablicy

Założenie o równomiernym hasz: Dla losowego wybranego klucza k h(k) przyjmuje 1...m-1 z jednakowym rozmiar tablicy prawdopodobieństwem.

Porażka:Średni czas wyszukiwania klucza k zakończonego porażką jest równy średniemu czasowi przejścia do końca listy. Średnia długość takiej listy jest równa współczynnikowi zapełnienia tab. Stąd oczekiwana liczba ele. sprawdzonych w czasie wyszukiwania zak. Porażką jest równa alfa, a całkowity czas wynosi O(1+α)

12.Metoda adresowania otwartego:

H(k,0) jeśli zajęte to H(k,1) jeśli zajęte to H(k,2) itd.

H(k,i)= (h(k)+i) mod m wzór liniowego

H(k,i)=( h(k)+c₁*i+c₂*i²)mod m wzór kwadratowego

H(k,i)=( h₁(k)+i*h₂(k))mod m wzór dwukrotnego

Czas pesymistyczny dla szukaj, wstawiaj Ɵ(n)

Czas oczekiwany: O(1/(1-alfa) lub O(1) gdy alfa jest ograniczony przez stała alfa<=c<1

13.Drzewa poszukiwań binarnych

Def: drzewo binarne realizowane za pomocą struktyury danyh z dowiązaniami, w której każdy węzeł jest obiektem. Na lewo większe, na prawo mniejsze.

Czas pes: wstaw, szukaj, usuń: Ɵ(n) lub Ɵ(h) n- ilość kluczy, h- wysokość drzewa

Uzasadnienie:

Średnia wysokość drzew dla losowo skonstruowanego BST

Losowo skonstruowane BST - uzyskane w wyniku wykonania pewnej ilości wstawień do początkowo pustego drzewa; każda permutacja jednakowo prawdopodobna.

Średnia wysokość O(lg n) = oczekiwana złożoność szukania i wstawiania

15.Drzewo cz-cz

Definicja: drzewo BST które spełnia warunki:

1. węzeł jest czerwony albo czarny

2. korzeń jest czarny

3. każdy liść NIL jest czarny

4. jeśli węzeł jest czerwony obaj jego synowie są czarni

5. każda ścieżka z korzenia do liścia ma tyle samo arnych węzłów

Wysokość w zależności od ilości węzłów

H<=2 lg (n+1)

Zło pes: O(lg n) n-ilość kluczy

Uzasadnienie: Bo h=O(lg n) bo algorytm jest przejście od korzenia do liścia i zmiana kolorów i że wykonujemy w jedną i drugą daną ilość operacji

16.Jaka własność może być zakłócona w cz-cz

Wstawianie:

- wstawiamy czerwony do czerwonego ojca

- usuwanie jak wywalimy czarny to za mało będzie

- jak skasujemy czarny to czerwony będzie przy czerwonym

17.Sposoby organizacji efektywności algorytmów

1. dziel i zwycieżaj: podzielenia problemu rekurencyjnie na mniejsze problemy, które rozwiązuje się nie żależnie - Quick-sort

2. programowanie dynamiczne: podzielenie problemu na podproblemy względem kilku parametrów. - najdłuższy wspólny podciąg

3. strategia zachłanna: algorytm zachłany wykonuje zawsze działanie, które wydaje się w danej chwili najkorzystniejsze - algorytm Huffmana

18.Algorytm Huffmana -kod prefiksowy

Reprezentacja drzewowa

Koszt drzewa: B(T) = Σ f[c]*d_T(c)

cεC

f(c) - ilość wystąpień

d_T(c) - głębokość gdzie występują

b(T) - liczba bitów potrzebnych do zakodowania pliku

19. B-drzewo def: drzewo ukorzenione o strukturze:

- wszystkie liście są na tym samym poziomie

-ograniczenie ilości kluczy w wężle: w korzeniu 1..2t-1, a w pozostałych węzłach t-1..2t-1

20. związek B drzewa wysokość do ilości kluczy

h<= log_t((n+1)/2) t- stopień drzewa

22. operacje

1. wstawianie

2. usuwanie

Złożoności: -Dyskowe

ad1. Ɵ(h)=Ɵ(lg _t n)

- wszystkie

ad1 i 2. O(th) = O(t lg _t n)

1.notacja O(f(n)),Ɵ(f(n)),Ω(f(n)) def: T(n)=O(f(n)) istnieje takie stałe c>0, n0 >0, że T(n)<=c*f(n) dla n>=n0 T(n)=Ω(f(n)) istnieje takie stałe c>0, n0 >0, że T(n)>=c*f(n) dla n>=n0 T(n)=Ɵ(f(n)) istnieje takie stałe c1,c2>0, n0 >0, że c1*f(n)<=T(n)<=c2*f(n) dla n>=n0 oszacować złożoność: for i<-- 1 to n do P(i) gdzie P(i) jest Ɵ(n) dla każdego i T- pesymistyczna złożoność algorytmu T(n)=Ɵ(n^2) bo i <-- 1 to n jest Ɵ(n) czyli n*n=n^2	8.Sortowanie w czasie liniowym algorytm, znane algorytmy: sortowanie przez zliczanie-Counting-Sort - złożoność O(n+k) k- zakres wartości czyli O(n) gdy k jest stałe, k jest O(n); ograniczenia: k zawsze jest do jakieś wartości Sortowanie przez pozycyjne (Rodix-sort)- złożoność O(d(n+k)), każda pozycja sortowana przez zliczanie; d- ilość pozycji;O(n) gdy k,d są stałe; ograniczenia: ze względu na ilość pozycji
2.Kopce binarne Def: Pełne drzewo binarne gdzie wszystko jest równomierne zapełnione oprócz liści drzewa. Ojciec>= syn bo są elementy uporządkowane 8 /\ 6 7 /\ /\ 3 2 1 4 Reprezentacja tablicowa 8 6 7 3 2 Lewy syn i-tego jest na pozycji 2*i a prawy 2*i+1. A ojciec ˻ i/2 ˼ Związek wysokości kopca z ilością elementów H= ˻ lg n ˼ lub h=O(lg n) lub h=Ɵ(lg n)	9.Elementarne struktury danych, typowe operacje, zło na na stosach, kolejkach i listach: Zło: wszystkie maja Ɵ(1) Wyjątek - szukanie na n elementowych listach Ɵ(n) Operacje: stosy- PUSH, POP, kolejki- ENQUEUE, DEQUEUE, listy- 10.Tab hasz Np. h(k)=k mod m Cechy: - łatwa do liczenia Ɵ(1) - równomiernie rozrzuca klucze po pozycjach 0... m-1
3. Jakie są typowe operacje na kopcach binarnych i ich złożoność: Wstawianie - Insert - Ɵ(lg n) usunięcie maxymalnego - extract-max - Ɵ(lg n) podanie wartosci ele. Max. - Maximum - Ɵ(1) budowa kopca - build-heap - Ɵ(n) wysokość kopca jest niewiększa niż lg n, a wstawienie polega na przejściu z góry kopca w dół ścieżką od korzenia do liścia, a wysokość jest logarytmiczna zastosowanie: implementacja kolejek priorytetowych	11.tab hasz Łańcuchowa metoda Pes zło:1.wstaw Ɵ(1), 2. szukaj Ɵ(n) Oczekiwana zło O(1+α) α=n/m m- współczynnik wypełnienia n- ilość kluczy w tablicy Założenie o równomiernym hasz: Dla losowego wybranego klucza k h(k) przyjmuje 1...m-1 z jednakowym rozmiar tablicy prawdopodobieństwem. Porażka:Średni czas wyszukiwania klucza k zakończonego porażką jest równy średniemu czasowi przejścia do końca listy. Średnia długość takiej listy jest równa współczynnikowi zapełnienia tab. Stąd oczekiwana liczba ele. sprawdzonych w czasie wyszukiwania zak. Porażką jest równa alfa, a całkowity czas wynosi O(1+α)
4.oszacowanie górne i dolne zło pes Heap sort heap-sort Ɵ(n* lg n) uzasadnienie build heap czas pesymistyczny T(n)<={Ɵ(n)} +{ n*0(n*lg n)} pętla sortująca, bierzemy ostatni element i wstawiamy na górę n razy operacji kopcowania, gdzie wysokość kopca<= lg n	12.Metoda adresowania otwartego: H(k,0) jeśli zajęte to H(k,1) jeśli zajęte to H(k,2) itd. H(k,i)= (h(k)+i) mod m wzór liniowego H(k,i)=( h(k)+c1*i+c2*i^2)mod m wzór kwadratowego H(k,i)=( h1(k)+i*h2(k))mod m wzór dwukrotnego Czas pesymistyczny dla szukaj, wstawiaj Ɵ(n) Czas oczekiwany: O(1/(1-alfa) lub O(1) gdy alfa jest ograniczony przez stała alfa<=c<1
5.Kolejki piorytetowe: Typowe operacje: a) dla list uporzadkowanych Insert Ɵ(n) extract-max Ɵ(1) maximum Ω(1) b) dla list nie uporząttkowanych Insert Ɵ(1) extract-max Ɵ(n) maximum Ω(n)	19. B-drzewo def: drzewo ukorzenione o strukturze: - wszystkie liście są na tym samym poziomie -ograniczenie ilości kluczy w wężle: w korzeniu 1..2t-1, a w pozostałych węzłach t-1..2t-1 20. związek B drzewa wysokość do ilości kluczy h<= logt((n+1)/2) t- stopień drzewa 22. operacje wstawianie usuwanie Złożoności: -Dyskowe ad1. Ɵ(h)=Ɵ(lg t n) - wszystkie ad1 i 2. O(th) = O(t lg t n)
6.Quick sort: zło pes: Ɵ(n^2) czas podziału Patrition T(n)>=n+(n-1)+(n-2)+...+2=Ω(n^2) Drzewo rekursji Czas<=n*Ɵ(n)=O(n^2) Czas oczekiwany dla wersji probabilistycznej T(n) = O(n*lg n) n T(n)<={Ɵ(n)}+{1/n(Σ (T(i) +T(n-i) + T(n-1)+ T(1))} i=1	7.Dolne oszacowanie zło pes alg sort przez porównania Ω(n*lg n) T(n)>=c*n*lg n uzasa: Algorytm sortujący przez porównania reprezentujemy jak drzewo decyzyjne, które musi mieć co najmniej n! liści, a z tego wynika że ma wysokość h>=lg n! czyli Ω(n*lg n), czyli złożoność pesymistyczna>= wysokości drzewa decyzyjnego Ω(n*lg n) Drzewo decyzyjne: Def: pełne drzewo binarne, które przedstawia porównywanie wykonywane przez algo sort.
13.Drzewa poszukiwań binarnych Def: drzewo binarne realizowane za pomocą struktyury danyh z dowiązaniami, w której każdy węzeł jest obiektem. Na lewo większe, na prawo mniejsze. Czas pes: wstaw, szukaj, usuń: Ɵ(n) lub Ɵ(h) n- ilość kluczy, h- wysokość drzewa Uzasadnienie: Średnia wysokość drzew dla losowo skonstruowanego BST Losowo skonstruowane BST - uzyskane w wyniku wykonania pewnej ilości wstawień do początkowo pustego drzewa; każda permutacja jednakowo prawdopodobna. Średnia wysokość O(lg n) = oczekiwana złożoność szukania i wstawiania	18.Algorytm Huffmana -kod prefiksowy Reprezentacja drzewowa Koszt drzewa: B(T) = Σ f[c]*dT(c) cεC f(c) - ilość wystąpień dT(c) - głębokość gdzie występują b(T) - liczba bitów potrzebnych do zakodowania pliku
17.Sposoby organizacji efektywności algorytmów dziel i zwycieżaj: podzielenia problemu rekurencyjnie na mniejsze problemy, które rozwiązuje się nie żależnie - Quick-sort programowanie dynamiczne: podzielenie problemu na podproblemy względem kilku parametrów. - najdłuższy wspólny podciąg strategia zachłanna: algorytm zachłany wykonuje zawsze działanie, które wydaje się w danej chwili najkorzystniejsze - algorytm Huffmana	15.Drzewo cz-cz Definicja: drzewo BST które spełnia warunki: węzeł jest czerwony albo czarny korzeń jest czarny każdy liść NIL jest czarny jeśli węzeł jest czerwony obaj jego synowie są czarni każda ścieżka z korzenia do liścia ma tyle samo arnych węzłów Wysokość w zależności od ilości węzłów H<=2 lg (n+1) Zło pes: O(lg n) n-ilość kluczy Uzasadnienie: Bo h=O(lg n) bo algorytm jest przejście od korzenia do liścia i zmiana kolorów i że wykonujemy w jedną i drugą daną ilość operacji 16.Jaka własność może być zakłócona w cz-cz Wstawianie: - wstawiamy czerwony do czerwonego ojca - usuwanie jak wywalimy czarny to za mało będzie - jak skasujemy czarny to czerwony będzie przy czerwonym

n

{}Czas procedury patrition

{}Średni czas wszystkich możliwych podziałów tablicy

N

T

T

N

b>c

a>b

a

H=n-1

e

c

d

0

1

b

n

{}Średni czas wszystkich możliwych podziałów tablicy

{}Czas procedury patrition

N

b>c

a>b

T

T

N

H=n-1

1

0

e

c

d

b

a

---