1. Klasówka 2016/17 (17.11.2016)#

Zadanie 1 (7 punktów)#

Słowa kluczowe: optymalne porównania

W tym zadaniu interesują nas optymalne algorytmy wyznaczania z pomocą porównań dwóch największych elementów z 4 różnych liczb. Uwaga: nie żadamy ustalenia porządku pomiędzy dwoma największymi elementami

  1. (5 punktów) Udowodnij, że każy algorytm wyznaczający dwa największe elementy wykonuje w pesymistycznym przyopadku co najmniej 4 porównania.

  2. (2 punkty) Zaproponuj optymalny ze względu na porównania algorytm wyznaczania dwóch największych elementów spośród czterech

Zadanie 2 (13 punktów)#

Słowa kluczowe: sortowanie

Niech n będzie dodatnią liczbą całkowitą. Dla dodanie liczby całkowitej k powiemy, że ciąg liczb \(a[1],\ldots,a[n]\) jest k-dobry, jeżeli każda inwersja (i,j): \(1 \le i \le j \le n\), spełnia \(j \le i + k\).

  1. (8 punktów) Zaproponuj asymptotycznie optymalny ze względu na porównania algorytm sortujący ciągi k-dobre. Uzasadnij astymptotyczną optymalność swojego algorytmu. Uwaga: w tym zadaniu argumentami funkcji złożoności są k i n.

  2. (5 punktów) Zaproponuj efektywny czasowo i pamięciowo algorytm, który sprawdza, czy dany ciąg liczb \(a[1],\ldots,a[n]\), dla zadanie dodatniej liczby całkowitej k, jest k-dobry. Uzasadnij poprawność swojego algorytmu i dokonaj jego analizy czasowej i pamięciowej.

Każde zadanie na oddzielnej kartce, czas trwania kolokwium: 14:00-15:45 (dokładnie).

Podpowiedź

Algorytm dla punktu a)

Utwórz kopiec H (typu MIN) z pierwszych k-elementów
foreach i in k+1..n:
   wypisz ExtractMin(H)
   Push(H, a[i])
while !empty(H)
   wypisz ExtractMin(H)

Dowód dolnej granicy, zauważmy, że liczba ciągów $k-dobrych* jest większa niż \((k!)^\frac{n}{k}\):

  • wystarczy że rozważamy permutacje w których pierwsze k-elementów to liczby z zakresu \({1,\ldots,k}\), kolejne k-elementów to liczby z zakresu \({1+k,\ldots,2k}\), itd.

  • w każdym bloku (niezależnie) możemy wybrać dowolną permutację

  • wszystkie tego typu ciągi są k-dobre

Algorytm dla punktu b)

Niech \(LMax[i]=\max\{a[j] : 1 \le j \le i\}\). Łatwo obliczyć LMax w czasie \(O(n)\).

Ciąg jest k-dobry jeśli dla każdego \(k< i \le n\) mamy \(LMax[i-k-1] \le a[i]\).