Celem przedmiotu jest zapoznanie studentów z podstawowymi techniki
probabilistycznymi używanymi w projektowaniu i analizie zrandomizowanych
algorytmów i struktur danych ioraz przedstawia ich zastosowanie do
rozwiązywania klasycznych zagadnień algorytmicznych. W przypadku prowadzenia zajęć w formie zdalnej, wykłady będą w formie wideokonferencji, a na ćwiczeniach będą rozwiązywane listy zadań. Deklaracje, zgłaszanie rozwiązań wybranego przeze mnie zadania i punktowe oceny będą realizowane w SKOS-ie.
**Program:**
1. Podstawowe pojęcia probabilistyki, klasy obliczeń i problemów losowych.
2. Zrandomizowane struktury danych,
3. Metoda probabilistyczna.
4. Łańcuchy Markowa i błądzenie losowe.
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.
