1. Klasówka 2017/18 (17.11.2017)#
Zadanie 1 (11 punktów)#
W liczbowym, różnowartościowym ciągu \(<a_1,a_2,\ldots,a_n>\), \(n>2\), element \(a_i\), \(1 < i < n\), nazywamy lokalnym ekstremum gdy jest mniejszy lub większy od obu sąsiadów, tzn.
albo \(a_{i-1} > a_i < a_{i+1}\), albo \(a_{i-1} < a_i > a_{i+1}\)
(3 punkty) Udowodnij, że każdy algorytm sortujący przez porównania 4-elementowe ciągi z co najwyżej jednym lokalnym ekstremum wymaga wykonania w pesymistycznym przypadku co najmniej 4 porównań.
(4 punkty) Zaproponuj algorytm sortowania 4-elementowych ciągów z co najwyżej 1 lokalnym ekstremum za pomocą co najwyżej 4 porównań
(4 punkty) Zaproponuj algorytm, asymptotycznie optymalny ze względu na liczbę porównań, sortujący ciągi o co najwyżej k lokalnych ekstremach dla zadanego k, \(0 < k < n\). Dowiedź optymalności swojego rozwiązania.
Zadanie 2 (9 punktów)#
W tym zadaniu rozważamy algorytm InsertionSort dla tablicy a[1..n], n>0, zawierającej permutację liczb 1,2,…,n. Dokonaj analizy pesymistycznej złożoności obliczeniowej tego algorytmu dla następujących przypadków.
(2 punkty) \(|a[i]-a[j]|<2017\), dla każdej pary \(1 \le i, j, \le n\) takiej, że \(|i-j|<2017\),
(3 punkty) \(|i-a[i]|<2017\), dla każdego \(1 \le i \le n\),
(4 punkty) dla co najwyżej 2017 elementów zachodzi \(i\not=a[i]\) \(1 \le i \le n\).
Podpowiedź
\(O(n^2)\) ponieważ ciąg odwrotnie posortowany spełnia warunki.
\(O(n)\) ponieważ ciąg a posiada \(\le 2\cdot 2017n\) inwersji (dowolne elementy odległe o więcej niż \(2\cdot 2017\) są już uporządkowane)
\(O(n)\) ponieważ ciąg a posiada \(\le 2017n\) inwersji (jeśli para (i,j) stanowi inwersję to \(i\not=a[i]\) lub \(j\not=a[j]\))
Prosimy o zapisywanie rozwiązań każdego zadania (podpunktu) na oddzielnej, podpisanej kartce.