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.

Podać strukturę węzła B-drzewa.

Narysować optymalne B-drzewo rzędu 5, zawierające wartości 12-stu kluczy.

Pokazać jak przebiega usunięcie jednego klucza z korzenia tego drzewa i podać koszt tej operacji.

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;

Temat 3.

Narysować nietrywialny kopiec Fibonacciego mający 31 węzłów.

Narysować nietrywialny kopiec dwumianowy mający 31 węzłów.

Omówić mechanizm zmiany wartości klucza położonego na najdalszym poziomie w narysowanym kopcu dwumianowym

Podać koszt tej operacji.

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.

Kiedy rotacje: ROTPrawa() lub ROTLewa() mogą być wykonane? Kiedy to ma sens praktyczny?

Podać pełny koszt wykonania rotacji ROTPrawa().

Omówić różnice i podobieństwa pomiędzy drzewami typu Splay a drzewami AVL.

Omówić mechanizmy stosowane w obsłudze tych drzew i zilustrować ich działanie przykładami.

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.

Kosztem wykonania rotacji ROTPrawa() jest wykonanie czterech przypisań:

wrk = D->Prawy
D->Prawy = O->Lewy
O->Lewy = S->
PrawyS->Prawy = wrk

Temat 5.

Problem minimalnego drzewa rozpinającego dla ważonego grafu nieskierowanego, można rozwiązać dwoma wersjami algorytmu Kruskala. (?!)

Wyjaśnić dlaczego dostępne są dwie wersje. (?!)

Zilustrować działanie algorytmu na przykładzie nietrywialnego grafu spójnego.

Na początek należy posortować wszystkie krawędzie w porządku niemalejącym. Po tej czynności można przystąpić do tworzenia drzewa. Proces ten nazywa się rozrastaniem lasu drzew. Wybieramy krawędzie o najmniejszej wadze i jeśli wybrana krawędź należy do dwóch różnych drzew należy je scalić (dodać do lasu). Krawędzie wybieramy tak długo, aż wszystkie wierzchołki nie będą należały do jednego drzewa.

Po posortowaniu krawędzi wg. wag otrzymamy:

1. Krawędź ae=1

2. Krawędź af=2

3. Krawędź bc=2

4. Krawędź be=2

5. Krawędź de=3

6. Krawędź ab=4

7. Krawędź fd=6

8. Krawędź ef=7

9. Krawędź cd=8

Przykład algorytmu zachłannego, który dokonuje najlepszego wyboru w danej chwili.

Temat 6.

Omówić struktury danych wykorzystywane w problemie 8 Hetmanów.

Podać algorytm rozwiązujący problem 8 Hetmanów, który wykorzystuje te struktury.

Przedstawić wartości tych struktur dla przykładowego ustawienia Hetmana.

Przedyskutować złożoność obliczeniową algorytmu.

Problem hetmanów. Należy ustawić na szachownicy 8 hetmanów tak aby żaden z nich nie szachował innych. Umieszczamy pierwszego hetmana na szachownicy, potem 2-go tak aby nie sza-chował 1-ego, potem 3-ego itd. Niech i-ty hetman nie da się ustawić bez kolizji. Wówczas zmieniamy pozycję poprzedniego tj. i-1 tak długo aż uda się umieścić i-tego bezkolizyjnie. Jeśli to nie pomaga wra-camy do i-2, i-3 i rozpoczynamy od nowa. Rekurencyjnie problem można zapisać w postaci algorytmu:

Hetman(row)

for każda pozycja col w rzędzie row

if pozycja col nie jest szachowana then

{ umieść kolejnego hetmana na col

if row<8 Hetman(row+1)

else Drukuj_Wynik }

else Usuń_Hetmana z pozycji col