Algorytmy probabilistyczne 1000-MS1-AlgProbab
1. Algorytmy randomizowane a algorytmy probabilistyczne.
1.1.Quicksort jako przykład algorytmu randomizowanego.
1.2 Nierówności Chernoffa i pogłębiona analiza Quicksortu.
2..Algorytmy Monte Carlo.
2.1 Prosta metoda Monte Carlo. Generatory liczb losowych.
2.2 Metoda odwracania dystrybuanty.
2.3 Specjalne metody Monte Carlo.
2.4 Metoda eliminacji i jej warianty.
2.5 Próbkowanie ważone.
2.6 Metody redukcji wariancji.
3. Dynamiczne metody Monte Carlo (MCMC).
3.1 Łańcuchy Markowa z dyskretną przestrzenią stanów.
3.2 Rozkłady stacjonarne. Równania równowagi szczegółowej.
3.3 Klasyfikacja stanów łańcucha Markowa.
3.4 Twierdzenie ergodyczne dla łańcuchów Markowa.
3.5 Algorytm Metropolisa-Hastingsa.
3.6 Pola Gibbsa i metoda symulowanego wyżarzania.
3.7 Łańcuchy Markowa z przeliczalną przestrzenią stanów.
Całkowity nakład pracy studenta
Efekty uczenia się - wiedza
Efekty uczenia się - umiejętności
Efekty uczenia się - kompetencje społeczne
Metody dydaktyczne
Metody dydaktyczne eksponujące
Metody dydaktyczne podające
- wykład informacyjny (konwencjonalny)
Metody dydaktyczne poszukujące
- laboratoryjna
- ćwiczeniowa
Metody dydaktyczne w kształceniu online
Wymagania wstępne
Koordynatorzy przedmiotu
Kryteria oceniania
Ćwiczenia kończą się zaliczeniem na ocenę na podstawie sprawdzianów pisemnych – U2, W2, W4, K1
Laboratoria kończą się zaliczeniem U1, U2, U3, K1,
Wykład kończy się egzaminem ustnym – W1, W2, W3, K1, K2
Praktyki zawodowe
Nie dotyczy
Literatura
1. O. Häggström, „Finite Markov chains and algorithmic applications”, Cambridge University Press, Cambridge 2002.
2. M. Harchol-Balter, „Introduction to Probability for Computing”, Cambridge University Press, Cambridge 2024.
3. M. Romaniuk, „Metody Monte Carlo”, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa 2019.
4. R. Wieczorkowski i R. Zielinski, „Komputerowe generatory liczb losowych”, Wydawnictwo Naukowo-Techniczne, Warszawa 1997.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: