9.11.2006

Informatyka w I-szej A
Lista nr 3

Zadania obowiązkowe 
1.	Zapisz w kodzie maszynie RAM schemat blokowy szybkiego potęgowania, który opracowaliśmy na lekcji.
2.	Porównaj szybkości działania programów obliczających potęgę liczb metodą naiwną i metodą szybką. Przypominam, że program używający metody naiwnej napisaliśmy na zajęciach 25.10. Porównania dokonaj uruchamiając te programy na takich samych zestawach danych i odczytując koszt czasowy, zarówno jednorodny jak i logarytmiczny (zakładka „Complexity Report”  w maszynie RAM).
3.	Napisz program, który dla danych liczb naturalnych a i q (takich, że q jest liczbą pierwszą oraz a<q) oblicza najmniejsze k większe od 0, takie, że ak ≡1 mod q (zapis ten oznacza, że ak  daje resztę 1 z dzielenia przez q). 
Uwagi:
•	Twój program nie musi być super szybki, tzn. nie wymagam, byś wymyślił jakiś extra oryginalny algorytm.

Termin nadsyłania rozwiązań: 13.11.06; godz. 23.59.
	
Uwagi:
•	jeśli potrzebujesz wskazówek do któregoś zadania, napisz do mnie.
•	Jako rozwiązania zadań 1 i 3  prześlij napisane programy.
•	Jako rozwiązanie zadania 2 prześlij tabelę postaci:
•	Nie przesadzaj z liczbą testów. Zwróć uwagę na dobór podstawy  i wykładnika taki, by zestawienie dobrze ilustrowało różnicę w szybkości działania algorytmów.

podstawa	wykładnik	Koszt jednorodny	Koszt logarytmiczny	
		Algorytm naiwny	Algorytm szybki	Algorytm naiwny	Algorytm szybki	

						

Zadania nadobowiązkowe
4.	Rozważ  problem z zadania 3.
a.	Udowodnij, że dla każdej pary liczb a, q naturalnych (q – pierwsza) wynik jest dobrze określony (czyli, że szukane k istnieje).
b.	Dla przykładowych wartości q (powiedzmy 17, 19,…) stablicuj wartości k dla wszystkich a z przedziału [1,q-1]. Postaraj się wykryć jakieś własności liczb k.
5.	Wymyśl strategię wygrywającą dla gry NIM2. Różni się ona tym od podstawowej wersji NIM, że zawodnik doprowadzający do opróżnienia ostatniego z niepustych stosów przegrywa.
6.	Zastanów się nad uogólnieniem gier NIM i NIM2 na większą liczbę stosów.

Krzysztof Loryś