1. Klasówka 2024/25 (22.11.2024)#
Zadanie 1 [10 punktów]#
Niech n będzie dodatnią liczbą całkowitą postaci \(2^{h+1}-1\), gdzie h jest nieujemną liczbą całkowitą.
O ciągu parami różnych liczb całkowitych \(C = <c_1, c_2, \ldots c_n>\) powiemy, że jest pełny, jeżeli po wstawieniu do początkowo pustego drzewa wyszukiwań binarnych, kolejno elementów ciągu C, dostaniemy pełne drzewo binarne.
Przykład
Ciąg <4, 6, 7, 2, 3, 5, 1> jest ciągiem pełnym, natomiast ciąg <4, 7, 6, 2, 3, 5, 1> już nie.
[4 punkty] Zaproponuj optymalny ze względu na porównania algorytm sortujący 7-elementowe ciągi pełne.
[2 punkty] Udowodnij, że każdy algorytm sortujący n-elementowe ciągi pełne wymaga w pesymistycznym przypadku \(\Omega(n \log n)\) porównań.
[4 punkty] Niech \(a[1,\ldots,n]\) będzie tablicą, w której zapisano pełny ciąg C (\(a[i] = c_i\)). Zaproponuj algorytm, który dla zadanego k, \(1 \le k \le n\), znajduje k-ty co do wielkości element w ciągu C. Twój algorytm powinien działać w miejscu i wykonywać mniej niż 2n porównań między elementami ciągu.
Podpowiedź
Dolna granica to 7 porównań, liczba możliwych kombinacji to \(\binom{6}{3} \cdot 2 \cdot 2=80\), czyli \(\lceil \log_2 80\rceil=7\). Dla n=7 mamy \(c_1=4\), robimy stabilny podział ciągu na elementy \(a_1,a_2,a_3<c_1\) oraz \(b_1,b_2,b_3>c_1\), to da się wykonać za pomocą 5 porównań (nie musimy wykonywać ostatniego porównania, bo oba ciągu mają dokładnie 3 elementy). Ciągi 3 elementowe też są pełne, więc \(a_1\) oraz \(b_1\) są medianami, musimy jednie porównać \(a_2,a_3\) oraz \(b_2,b_3\) (2 porównania)
\(T(n)=\binom{n}{n/2} \cdot T(n/2) \cdot T(n/2)\), niech \(L(n)=\log_2(T(n))\), \(L(n)=\Theta(n)+2L(n/2)=\Theta(n \log n)\).
Jeśli \(k=n/2+1\) to zwracamy \(c_1\). Zauważamy, że po zrobieniu partition (przy użyciu \(c_1\)) dostajemy dwa krótsze ciągi pełne, jeśli \(k\le n/2\) to szukamy w ciągu z mniejszymi wartościami, wpp. szukamy w ciągu z większymi wartościami.
Zadanie 2 [6 punktów]#
Dla słowa \(s = [s_1,s_2, \ldots, s_k]\) i liczby całkowitej j, \(0 \le j < k\), j-tym przesunięciem cyklicznym słowa s nazywamy słowo \({Cycl}_j(s) = [s_{j+1},s_{j+2}, \ldots, s_k, s_1, \ldots, s_j]\).
Dla dodatnich liczb całkowitych n, k danych jest n słów \(W_1, W_2, \ldots, W_n\) nad alfabetem \(\{1, 2, \ldots, n\}\), każde o długości k. Zaprojektuj algorytm, który w łącznym czasie \(O(nk)\) znajdzie dla każdego \(j = 0, 1, 2, \ldots, k-1\), najmniejsze leksykograficzne przesunięcie cykliczne wśród j-tych przesunięć słów \(W_1,W_2, \ldots, W_n\).
Podpowiedź
Posortuj słowa w czasie \(O(nk)\), co daje rangę słów dla przesunięcia j=0 (\(\mbox{Rank}_j(i)\)). Porządek dla przesunięć \(j=k-1,\ldots,1\) możemy wyznaczyć sortując pary: \((W_i[j + 1], \mbox{Rank}_{(j + 1) \mod k}(i))\), co wymaga czasu \(O(n)\).
Zadanie 3 [4 punkty]#
Na maszynie klasówkowej mamy do wykonania cztery typy zadań: A, B, C i D. Wykonanie zadań typu A, B, C, D zajmuje odpowiednio czasy a, b, c, d. Czasy wykonań zadań są dodatnimi liczbami całkowitymi.
Na maszynie mamy zarezerwowany czas t (dodatnia liczba całkowita). Przestoje na maszynie są bardzo kosztowne. Dlatego naszym celem jest minimalizacja łącznego czasu przestojów i przy minimalnym czasie przestojów wykonanie jak największej liczby zadań.
Zaprojektuj algorytm, który dla danych a, b, c, d i t policzy w czasie \(O(t)\) minimalny czas przestojów i dla tego czasu wyznaczy maksymalną liczbę zadań, które można wykonać na maszynie klasówkowej.
Podpowiedź
Policz za pomocą programowania dynamicznego wartości T[i] maksymalna liczba zadań których wykonanie zajmuje dokładnie i jednostek czasu (lub \(-\infty\) jeśli to nie jest możliwe). Wynikiem jest ostatnia wartość z \(T[0,\ldots,t]\) różna od \(-\infty\).
Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.