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: