Wykład omawia podstawowe techniki probabilistyczne i przedstawia ich
zastosowanie do rozwiązywania klasycznych zagadnień algorytmicznych.
**Program:**
1. Podstawowe pojęcia probabilistyki, klasy obliczeń i problemow losowych.
2. Metoda probabilistyczna.
3. Łańcuchy Markowa i błądzenie losowe.
4. Techniki algebraiczne w problemach weryfikacji i dowodach interakcyjnych.
5. Zastosowanie losowości w algorytmach grafowych, programowaniu liniowym, geometrii obliczeniowej, algorytmach teorio-liczbowych, itp.
**Wymagania:** Algorytmy i struktury danych, Matematyka dyskretna Rachunek
prawdopodobieństwa
**Literatura:**
1. R. Motvani, P. Raghavan, Randomized Algorithms,Cambridge University Press, 1995.
2. Minzermacher Michael, Upfal Eli, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press 2005 _lub polskie wydanie_ Metody probabilistyczne i obliczenia. Algorytmy randomizowane i analiza probabilistyczna, WNT 2009.
