Informatyka MIMUW

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

$$\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$.