1. Klasówka 2004/05#
Zadanie 1#
Podaj dokładne oszacowanie na liczbę liści (odpowiedzi) w drzewie decyzyjnym wyznaczającym najmniejszy element spośród elementów \(a[1], \cdots, a[n]\)? Odpowiedź uzasadnij.
Zadanie 2#
Podaj permutację liczb \(1, 2, \cdots, n\), dla której podczas wykonywania algorytmu \(MergeSort\) (rekurencyjnie, z pomocniczą tablicą do scalania) element \(n\) jest porównywany z innymi największą liczbę razy. Ile wynosi taka liczba porównań? Odpowiedź uzasadnij. Możesz przyjąć, że \(n\) jest potęgą \(2\).
Podpowiedź
Zauważmy, że element n jest porównywany przy scalaniu uporządkowanych ciągów L i \(R=r_1,\ldots,r_{k},n\) dokładnie \(\alpha=| \{ x\in L : x > r_k \}|\) razy. Stąd najlepszy wynik otrzymujemy gdy \(\alpha=|L|\) (czyli \(min(L) > r_k\)). Dla n=8 najlepszy ciąg to [4, 5, 6, 7, 2, 3, 1, 8].
def gen(n, last=None):
assert n == 1 or n % 2 == 0
if n == 1:
return [last or n]
else:
return list(range(n // 2, n)) + gen(n // 2, last=last or n)
Zadanie 3#
Rozważamy dynamiczny graf \(G\) o \(n\) wierzchołkach, na którym wykonywane są następujące operacje:
dodanie nowej krawędzi (możesz założyć, że nigdy nie powstaną krawędzie równoległe);
utożsamienie dwóch wierzchołków
Operacja utożsamienie dwóch wierzchołków polega na połączeniu ich w nowy wierzchołek (nowy wierzchołek może być reprezentowany przez jeden z wierzchołków utożsamianych), którego sąsiadami w grafie są wszyscy sąsiedzi łączonych wierzchołków. Zakładamy, że nigdy nie utożsamiamy wierzchołków pomiędzy którymi istnieje ścieżka długości \(2\).
Przed pierwszą operacją i po ostatniej operacji grafu \(G\) nie zawiera krawędzi. Graf \(G\) reprezentowany jest w pamięci komputera za pomocą list sąsiedztwa. Zaprojektuj algorytm wstawiania krawędzi i utożsamiania wierzchołków tak, aby zamortyzowany czas ich wykonania był jak najlepszy. W celu uzyskania efektywnych algorytmów możesz wzbogacić strukturę list sąsiedztwa o dodatkowe informacje. Podaj zamortyzowany i pesymistyczny czas zaprojektowanych algorytmów.
Zadanie 4#
Spróbuj zaprojektować kolejkę priorytetową, której podstawą są drzewa lewicowe (kolejka może być lasem drzew lewicowych), umożliwiającą wykonywanie operacji \(Insert\), \(Min\) w stałym czasie i \(DeleteMin\) w czasie zamortyzowanym \(O(\log n)\). Uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoności.