1. Klasówka 2007/08#
Zadanie 1#
Opracuj strukturę danych, która pozwala wykonywać następujące operacje:
\(Ini(k) ::\) inicjacja struktury danych i ustalenie długości krotek liczb całkowitych na \(k\)
\(Insert(<a_1, a_2, \cdots, a_k>) ::\) dodaje do struktury krotkę \(<a_1, a_2, \cdots, a_k>\)
\(Min ::\) podaje najmniejszą leksykograficznie krotkę w strukturze
\(ExtractMin ::\) usuwa najmniejszą leksykograficznie krotkę ze struktury
W Twoim rozwiązaniu operacje Insert i ExtractMin powinny by wykonywane w czasie \(O(\log n + k)\).
Zadanie 2#
Udowodnij, że jeśli algorytm sortujący tablicę \(A[1..n]\) porównuje i zamienia wyłącznie elementy odległe co najwyżej o \(2007\) (tzn. jeśli porównuje \(A[i]\) z \(A[j]\), to \(|i-j| \leq 2007\)), to jego pesymistyczny czas działania jest co najmniej kwadratowy.
Podpowiedź
Jeśli \(|i-j| \leq 2007\) to zmiana \(A[i]\) i \(A[j]\) może usunąć co najwyżej \(O(1)\) inwersji. Stąd posortowanie ciągu odwrotnie uporządkowanego zajmie \(O(n^2)\) czasu.
Zadanie 3#
Zaproponuj implementację następujących operacji na tablicy liczb naturalnych \(T[0..n+1]\), początkowo wypełnionej zerami, w taki sposób, żeby ich koszt zamortyzowany był stały.
\(Inc(i) :: T[i] = T[i] + 1\), zawsze \(0 < i < n+1\)
\(BlockDec(i) ::\) Jeśli \(T[i] = 0\) nic nie rób. W przeciwnym przypadku znajdź najbliższy indeks \(j\) taki, że \(T[i] \neq T[j]\) (jeśli są dwa takie indeksy wybieramy mniejszy z nich). Dla każdego \(k\) pomiędzy \(i\) oraz \(j\) wykonaj \(T[k] = T[k] - 1\).
Podpowiedź
Implementujemy funkcję Inc w sposób naturalny (po prostu zmieniamy wartość tablicy). W funkcji BlockDec znajdujemy indeks j jednocześnie szukając na lewo i prawo pierwszej niezgodności.
while i-D >= 0 and i + D < n and T[i-D]==T[i] and T[i+D]==T[i]:
i++
Aby uzasadnić stały czas zamortyzowany obu operacji możemy wybrać jako funkcję potencjału: \(\Phi=3\sum_{i=0}^{n-1} T[i]\).
Zadanie 4#
Udowodnij, że dla każdego naturalnego \(n\) istnieje drzewo czerwono-czarne o co najmniej \(n\) wierzchołkach, które nie jest AVL-drzewem.