1. Klasówka 2018/19 (22.11.2018)#

Zadanie 1 (7 punktów)#

Słowa kluczowe: sortowanie

Niech n będzie dodatnią liczbą całkowitą większą od 1. Dla dodatniej liczby całkowitej k < n powiemy, że ciąg liczb a[1],…,a[n] jest k-dobry, jeżeli dla każdej pary (i,j) takiej, że \(1 \le i < j \le n\) oraz a[i] > a[j], mamy \(j \le i + k\). Sortowaniem k-dobrym nazywamy takie porządkowanie elementów danego ciągu, w wyniku którego uzyskujemy ciąg k-dobry.

Zaproponuj algorytm sortowania k-dobrego działający w czasie \(O(n \log (n/k))\).

Podpowiedź

Chcemy uprządkować ciąg do sekwencji bloków \(B_1,\ldots,B_p\), takich, że:

  • bloki zawierają wszystkie elementy ciągu a,

  • \(|B_i| \le k\)

  • bloki są względem siebie uporządkowane, tzn. \(\max(B_i) \le \min(B_{i+1})\)

Takie uporządkowanie możemy otrzymać stosując algorytm QuickSort z następującymi modyfikacjami:

  • jeśli sortowany obszar ma długość \(\le k\), to przerywamy sortowanie (zostawiamy ten kawałek ciągu nieuporządkowany)

  • do wyboru elementu dzielącego używamy algorytmu magicznych piątek (i wybieramy medianę)

Ponieważ zatrzymujemy rekurencję na poziomie k, stąd złożoność takiego algorytmu to \(O(n \log (n/k))\).

Zadanie 2 (4 punkty)#

Słowa kluczowe: optymalne porównania

Wiadomo, że każdy algorytm wyznaczający przez porównania dwa elementy - największy i najmniejszy - w ciągu długości n = 2k, wykonuje w pesymistycznym przypadku co najmniej 3k - 2 porównania. Udowodnij powyższe dla n = 4 i zaproponuj optymalny algorytm w tym przypadku.

Podpowiedź

Dla n=4 istnieje \(4\cdot 3=12\) możliwych odpowiedzi, stąd dolne ograniczenie na liczbę porównań w modelu drzew decyzyjnych to \(\lceil \log 12 \rceil=4\).

def min_max(a, b, c, d):
    min_1, max_1 = (a, b) if a < b else (b, a)
    min_2, max_2 = (c, d) if c < d else (d, c)
    min_ = min(min_1, min_2)
    max_ = max(max_1, max_2)
    return (min_, max_)

Zadanie 3 (6 punktów)#

Słowa kluczowe: kopiec

Elementy w tablicy a[1..n], n > 0, są rozmieszczone w porządku kopcowym typu MIN. Dla k > 0 tablicę a rozszerzono o k elementów a[n+1], …, a[n+k]. Zaproponuj algorytm, który w czasie \(O(k + \log^2 n)\) zbuduje kopiec typu MIN na całej tablicy a[1..n+k].

Uwaga: rozpocznij swoje rozważania przy założeniu, że \(n = 2^{h-1}\), dla pewnego h > 0.

Podpowiedź

  • Jeśli \(k=O(n)\) to po prostu budujemy kopiec od nowa, co zajmuje \(O(k)\).

  • Jeśli \(k<n/2\) i \(n = 2^{h-1}-1\) to dopisujemy nowe elementy na koniec kopca, po czy wykonujemy operację DownHeap dla wszystkich węzłów oryginalnego kopca, które w swoim poddrzewie mają nowe elementy. Niech A to będą węzły oryginalnego kopca, które mają w obu swoich poddrzewach nowe elementy. Natomiast B to węzły, które mają w jednym poddrzewie nowe elementy. Obsługa operacji DownHeap dla węzłów typu A zajmuje \(O(|A|)\) czasu (przypomina tworzenie kopca w czasie liniowym). Natomiast zbiór B jest dosyć mały tzn. \(|B|=O(\log n)\) stąd wszystkie operacje DownHeap dla B zajmują \(O(\log^2 n)\).

  • Jeśli \(k<n/2\) i \(n \not= 2^{h-1}-1\) to dzielimy dodawanie na dwa etapy po \(k=k_1+k_2\) (najpierw uzupełniamy ostatni poziom kopca przez \(k_1\) elementów, a następnie dodajemy kolejne \(k_2\) elementów do następnego poziomu).

Zadanie 4 (3 punkty)#

Słowa kluczowe: sortowanie

W tablicy a[1..n] dany jest ciąg jednocześnie 7- i 11-uporządkowany. Udowodnij, że algorytm InsertionSort sortuje a w czasie liniowym.

Uwaga: powiemy, że ciąg a jest k-uporządkowany, k > 0, gdy dla każdego i = 1, 2, …, n - k, \(a[i] \le a[i+k]\).

Uzasadnij poprawność swoich rozwiązań i przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów.

Podpowiedź

Możemy pokazać, że dla ciąg a ma \(O(n)\) inwersji: dla dowolnych i, j, dla których \(1 \le i < i+77 \le j \le n\), mamy \(a[i] \le a[j]\).

Bonusy:

  1. Udowodnij, że algorytm z zadania 1 jest optymalny.

  2. W zadaniu 3 podaj algorytm działający w czasie \(O(k + \log n)\).