1. Klasówka 2001/02 (2001-11-28)#
Zadanie 1 (8 punktów)#
Rozważmy następujący algorytm sortowania
krok:=0
for i:=1 to n-1 do
for j:=i+1 to n do
begin
krok:=krok+1;
if a[j-1] > a[j] then
a[j-1] :=: a[j] {zamiana}
end;
Niech początkową wartością a[i] będzie \(x_i\)
- Zaproponuj efektywny algorytm, który dla każdego \(x_i\) oblicza krok, w którym
\(x_i\) jest zamieniany pierwszy raz (0, gdy nie dzieje się to w żadnym kroku)
- Oblicz, ile średnio zamian jest wykonywanych w powyższym algorytmie w modelu
losowej permutacji
Zadanie 2 (6 punktów)#
Wiadomo, że każdą nieujemną liczbę całkowitą można przedstawić jako sumę różnych liczb Fibonacciego, z których żadne dwie nie są kolejne. Taką reprezentację nazwiemy znormalizowaną reprezentacją Fibonacciego. Niech L[0..k] będzie licznikiem, w którym liczby są zapisywane w znormalizowanej reprezentacji Fibonacciego (liczba zapisana w liczniku jest równa \(\sum_{i=0}^k L[i]\cdot F_i\), gdzie k jest pozycją najbardziej znaczącej jedynki). Na początku L[i]=0, dla każdego i, a \(k=0\). Opisz operację dodawania 1 do licznika L i zanalizuj koszt zamortyzowany wykonania takiej operacji.
Zadanie 3 (3 punkty)#
Pokaż, że każde drzewo wyszukiwań binarnych można przekształcić na AVL-drzewo za pomocą pojedynczych rotacji.
Podpowiedź
Każde drzewo można za pomocą rotacji przekształcić na listę (oraz listę na dowolne drzewo).
Zadanie 4 (3 punkty)#
Udowodnij, że każdy algorytm scalający uporządkowany ciąg n-elementowy z uporządkowaną parą elementów wymaga w pesymistycznym przypadku \(2\log(n+1)\) porównań.