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: