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.
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\).
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.
Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.