Egzamin 2 (20.06.2009r)

Temat 1.

Podać formalną definicję notacji O. Wyjaśnić różnice w interpretacji notacji O i Ω.

Podać przyczyny powstania tych notacji.

Omówić miary złożoności wykorzystujące informacje o rozkładach prawdopodobieństwa.

Niech dane będą dwie funkcje: f(n) i g(n) o wartościach dodatnich.

Funkcja f(n) jest klasy O(g(n)) jeżeli istnieją dwie stałe:

Rzeczywista c > 0 i naturalna n0,

Takie, że relacja f(n) ≤  c • g(n) zachodzi dla każdego n ≥ n0.

Funkcja f(n) jest dużym O z g(n).

Notacja O jest opisem pesymistycznego czasu działania i jest niejednoznaczna ponieważ nie ma sposobów i kryteriów wyznaczania wartości c i n0.

Temat 2.

{ Do omówienia kopiec Fibonacciego }

Postać węzła ma charakter struktury o polach:

1. liczba zmiennych w węźle

2. zmienna logiczna leaf[x] – czy węzeł jest liściem (TRUE jeśli węzeł jest liściem)

3. tablica zawierająca klucze

4. tablica zawierająca wskaźniki do poddrzew

Usuwamy klucz k=20;

Następnie przesuwamy wszystkie klucze k>20 w lewo;

Kopiec dwumianowy zawierający 31 węzłów. Składa się z drzew dwumianowych o wysokościach 0, 1, 2, 3, 4.

Mechanizm zmiany wartości klucza położonego w najniższym poziomie wygląda następująco:
Jeśli klucz zmniejszony jest mniejszy niż klucz ojca to zamieniamy miejscami, powtarzamy tą czynność aż odtworzymy własność kopca.
Jeśli zmniejszymy wartość z 44 do 43, 42 to nie zajdzie potrzeba przywracania własności kopca, jeśli wartość będzie mniejsza np. [41,37] to musimy wykonywać zamiany (nie chce mi się tego rysować).

Temat 4.

Rotacja ROTPrawa() może być wykonana jeśli w węźle istnieje lewy syn.

Wykonanie jest opłacalne gdy zależy nam na wyważeniu drzewa oraz chcemy zminimalizować wysokość drzewa co przyczynia się do zmniejszenia kosztu operacji na drzewie.