Probabilistic algorithms

Przedmiot stanowi pomost między podstawowym kursem z rachunku prawdopodobieństwa, a zaawansowanymi metodami modelowania stochastycznego. W oparciu o znane pojęcia i fakty budowane są metody obliczeniowe (Monte Carlo, Markov Chain Monte Carlo) powszechnie używane w zastosowaniach. W tle doskonalone są techniki symulacyjne studenta.

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.

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.

Ć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

Nie dotyczy