Ćwiczenia 5: zadania powtórkowe, część I

Poniżej zamieszczono zadania z pierwszych klasówek z ASD w latach 2007-2009. Niektóre zadania zawierają treści jeszcze nie poruszane na wykładzie i ćwiczeniach, ale dla pełności obrazu zawarto te klasówki w całości.

Zadanie 1 [8 punktów]

Dana jest tablica \(n \times n\), \(n > 1\), w której w każde pole wpisano liczbę całkowitą. Chcemy przejść z dolnego lewego rogu (z \( (1,1) \) ) do górnego prawego rogu (do \( (n,n) \) ) i wrócić, idąc w drodze z \( (1,1) \) zawsze w prawo lub w górę, a z powrotem - w lewo lub w dół. Z danego pola można przejść tylko na pola sąsiednie (współrzędne różnią się o 1 na dokładnie jednej pozycji). Żadne pole nie może się pojawić na całej trasie (czyli tam i z powrotem) więcej niż raz, poza polem (1,1), które pojawia się na początku i na końcu trasy. Zaprojektuj algorytm znajdowania najtańszej trasy, czyli takiej, na której suma wartości pól jest najmniejsza.

Zadanie 2 [7 punktów]

Niech \( n \) będzie liczbą całkowitą większą od 1, a \( X = \{ (x,y): x = 0, 1, \ldots, n-1, y = 0, 1, 2, 3, 4 \}\) zbiorem punktów na płaszczyźnie. Danych jest \( n \) różnych prostych, z których każda przechodzi przez dwa różne punkty ze zbioru \( X \), różniące się zawsze pierwszą współrzędną. Każda prosta zadana jest przez parę punktów \( [(x1,y1),(x2,y2)] \), \( x1 < x2 \). Zaprojektuj algorytm, który w czasie liniowym posortuje wszystkie proste niemalejąco względem ich kątów nachylenia do osi OX.

Zadanie 3 [5 punktów]

Podaj permutację liczb \( 1, 2, \ldots, 7 \), dla której algorytm HeapSort wykona największą liczbę porównań. Uwaga: należy wziąć pod uwagę obie fazy algorytmu – budowę kopca i właściwe sortowanie; poprawianie kopca odbywa się zawsze przez przesiewanie stosownego elementu w dół kopca; sortujemy rosnąco.

Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.

Zadanie 1 [5 punktów]

Oto możliwa implementacji procedury Partition w algorytmie QuickSort:

procedure Partition(le,pr: integer);
{ 1<=le<=pr<=n; a[pr+1] >= max(a[le..pr]) }
var
   i, j, s, v: integer;
begin
   if le < pr then
   begin
      s := (le + pr) div 2; v := a[s]; a[s] := a[le];
      i := le; j := pr+1;
      repeat
         repeat i := i+1 until a[i] >= v;
         repeat j := j -1 until a[j] <= v;
         if i < j then a[i] :=: a[j]; {zamiana wartości zmiennych}
     until j <= i;
     a[le] := a[j]; a[j] := v
  end
end;

a) Podaj zawartość tablicy \( a[1..n] \) dla \( n = 7 \) - permutację liczb \(1, 2, \ldots, n \), dla której algorytm QuickSort z powyższą procedurą Partition wykona:

1. najmniejszą liczbę porównań [1 punkt]
2. największą liczbę porównań [2 punkty]

b) Podaj zawartość tablicy \( a[1..n] \) dla \( n = 15 \) - permutację liczb \( 1, 2, \ldots, n \), dla której algorytm HeapSort buduje kopiec (pierwsza faza algorytmu) za pomocą

1. najmniejszej liczby porównań [1 punkt]
2. największej liczby porównań [1 punkt]

Odpowiedzi uzasadnij.
Uwaga: porównania dotyczą elementów tablicy \( a\), interesuje nas sortowanie w porządku niemalejącym.

Zadanie 2 [8 punktów]

Zaproponuj wzbogacenie kopca zupełnego w taki sposób, żeby efektywnie w czasie zamortyzowanym wykonywane były operacje: Min, DeleteMin, Insert, CountMin. Ostatnia operacja polega na podaniu aktualnej liczby elementów w kopcu o wartości równej Min. Przeprowadź analizę kosztu (zamortyzowanego) wykonania poszczególnych operacji.

Zadanie 3 [7 punktów]

Zaproponuj sposób wykonania operacji Inc(L) dla licznika Fibonacciego L w taki sposób, żeby po wykonaniu \(n\)-tej operacji wartość liczby \( n \) zapisanej w liczniku wynosiła \( L[0]*F_0 + L[1]*F_1 + L[2]*F_2 + \ldots \), gdzie \( L[i] \) to wartość \(i\)-tego bitu w liczniku, \( F_i \), to \( i \)-ta liczba Fibonacciego (\( F_0 = 0, F_1 = 1 \)). Operacje elementarne w rozwiązaniu, to zmiana wartości jednego bitu i odczytanie wartości jednego bitu. Zaproponuj rozwiązanie z jak najmniejszym kosztem zamortyzowanym. Dokonaj analizy kosztu zamortyzowanego metodą funkcji potencjału. Możesz założyć, że licznik jest początkowo wyzerowany.

Zadanie 1 [5 punktów]

Opracuj strukturę danych, która pozwala wykonywać następujące operacje:

• Ini(\(k\)):: inicjacja struktury danych i ustalenie długości krotek liczb całkowitych na \( k \)
• Insert(\( < a_1, a_2, \ldots, a_k > )\):: dodaje do struktury krotkę \( < a_1, a_2, \ldots, a_k > \)
• Min:: podaje najmniejszą leksykograficznie krotkę w strukturze
• ExtractMin:: usuwa najmniejszą leksykograficznie krotkę ze struktury

W Twoim rozwiązaniu operacje Insert i ExtractMin powinny by wykonywane w czasie \( O(\log n + k)\).

Zadanie 2 [5 punktów]

Udowodnij, że jeśli algorytm sortujący tablicę \( A[1..n] \) porównuje i zamienia wyłącznie elementy odległe co najwyżej o 2007 (tzn. jeśli porównuje \( A[i] \) z \( A[j] \), to \(|i-j| \le 2007\)), to jego pesymistyczny czas działania jest co najmniej kwadratowy.

Zadanie 3 [5 punktów]

Zaproponuj implementację następujących operacji na tablicy liczb naturalnych \(T[0..n+1]\), początkowo wypełnionej zerami, w taki sposób, żeby ich koszt zamortyzowany był stały.

• Inc(\(i\)):: \( T[i] := T[i] + 1 \) // zawsze \( 0 < i < n+1 \)
• BlockDec(\( i \)):: Jeśli \(T[i]=0\) nic nie rób. W przeciwnym przypadku znajdź najbliższy indeks \(j\) taki, że \(T[i] \ne T[j]\) (jeśli są dwa takie indeksy wybieramy mniejszy z nich). Dla każdego \(k\) pomiędzy \(i\) oraz \(j\) wykonaj \(T[k] := T[k] – 1\)

Zadanie 4 [5 punktów]

Udowodnij, że dla każdego naturalnego \( n \) istnieje drzewo czerwono-czarne o co najmniej \( n \) wierzchołkach, które nie jest AVL-drzewem.