Ćwiczenia 1: poprawność i złożność algorytmu

Zadanie 1 (Potęgowanie binarne)

Zaprojektuj algorytm, który dla danych nieujemnej liczby całkowitej \( \displaystyle n \) i liczby całkowitej \( \displaystyle a \), policzy wartość \( \displaystyle a^n \). Przyjmij za operację dominującą mnożenie dwóch liczb całkowitych i w tym modelu:

  1. zaproponuj algorytm działający w czasie \( \displaystyle O(\log n) \),
  2. udowodnij poprawność swojego algorytmu metodą niezmienników.

Zadanie 2 (Liczby Fibonacciego)

Liczby Fibonacciego definiuje się jak następuje:
\( \displaystyle F_0 = 0, F_1 = 1 \),
\( \displaystyle F_n = F_{n-2} + F_{n-1} \), dla \( \displaystyle n > 1 \).
Dla danej nieujemnej liczby całkowitej \( \displaystyle n \), należy policzyć liczbę \( \displaystyle F_n \). Za operacje dominujące przyjmujemy operacje arytmetyczne - dodawanie, odejmowanie lub mnożenie dwóch liczb całkowitych.

  1. Ile dodawań wykonamy obliczając \( \displaystyle F_n \) rekurencyjnie?
  2. Zastosuj metodę programowania dynamicznego (tablicowania wcześniej policzonych wyników) do policzenia \( \displaystyle F_n \) w czasie \( \displaystyle O(n) \).
  3. Wiadomo, że

    4. \[
    \left[ \begin{array}{c}
    F_{n+1}\\
    F_n
    \end{array} \right]
    =
    \left[ \begin{array}{cc}
    1 & 1\\
    1 & 0 \end{array} \right]
    \left[ \begin{array}{c}
    F_n\\
    F_{n-1}
    \end{array} \right].
    \]
    Wykorzystaj powyższy fakt do zaproponowania algorytmu obliczania \( \displaystyle F_n \) w czasie \( \displaystyle O(\log n) \).

Zadanie 3 (Pary liczb)

Dana jest dodatnia liczba całkowita \( \displaystyle n \), uporządkowana niemalejąco tablica dodatnich liczb całkowitych \( \displaystyle A[0..n-1] \) oraz dodatnia liczba całkowita \( \displaystyle C \). Zaprojektuj efektywny algorytm wyznaczenia najliczniejszego zbioru rozłącznych par elementów tablicy \( \displaystyle A \) takich, że suma elementów w każdej parze jest nie większa niż \( \displaystyle C \). Uzasadnij poprawność swojego algorytmu i dokonaj analizy jego złożoności obliczeniowej.

Zadanie 4 (Inwersje I)

Niech \( \displaystyle A[0..n-1] \) będzie tablicą (ciągiem) liczb całkowitych. Parę indeksów \( \displaystyle (i,j) \), \( \displaystyle 0 \le i < j < n \), nazwiemy inwersją tablicy \( \displaystyle A \) wtedy i tylko wtedy, gdy \( \displaystyle A[i] > A[j]. \)

  1. Jaka może być najmniejsza, a jaka największa liczba inwersji w tablicy \( \displaystyle A \)?.
  2. Przy założeniu, że w tablicy \( \displaystyle A \) zapisano permutację liczb od \( \displaystyle 0, 1, \ldots, n-1 \), zaproponuj algorytm typu "dziel i rządź" wyznaczający liczbę inwersji w \( \displaystyle A \) w czasie \( \displaystyle O(n\log n) \). Uzasadnij poprawność i dononaj analizy złożoności obliczeniowej zaproponowanego algorytmu.
  3. Zaproponuj algorytm programowania dynamicznego, który dla danych liczb całkowitych \( \displaystyle k, n \) takich, że \( \displaystyle n > 0, 0 \le k \le \frac{n(n-1)}{2} \), obliczy liczbę permutacji liczb \( \displaystyle 0, 1, \ldots, n-1 \), które zawierają dokładnie \( \displaystyle k \) inwersji.

Zadanie 5 (Inwersje II)

Niech \( \displaystyle A[0..n-1] \) będzie \( \displaystyle n\)-elementowym ciągiem liczbowym. Wektorem inwersji dla ciągu \( \displaystyle A \) nazywamy tablicę \( \displaystyle B[0..n-1] \) taką, że \( \displaystyle B[j] = |\{0 \le i < j: B[i] > B[j]\}| \).

  1. Udowodnij, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami \( \displaystyle A[0..n-1] \) liczb \( \displaystyle 0, 1, \ldots, n-1 \), a wektorami \( \displaystyle B[0..n-1] \) takimi, że \( \displaystyle 0 \le B[j] < j+1 \), dla \( \displaystyle j = 0, 1, \ldots, n-1 \).
  2. Dane są, dodatnia liczba całkowita \( \displaystyle n \) oraz wektor (inwersji) \( \displaystyle B[0..n-1] \), \( \displaystyle 0 \le B[j] < j+1 \), dla \( \displaystyle j = 0, 1, \ldots, n-1 \). Zaprojektuj algorytm, który w czasie \( \displaystyle O(n\log n) \) znajdzie permutację \( \displaystyle A[0..n-1] \) liczb \( \displaystyle 0, 1, \ldots, n-1 \), dla której wektorem inwersji jest \( \displaystyle B \).