Algorytmy probabilistyczne

Podstawowe umiejętności w zakresie analizy matematycznej. Kurs rachunku prawdopodobieństwa.

udział w wykładach - 15 godzin

- udział w ćwiczeniach - 15 godzin

- udział w laboratorium - 15 godzin

- przygotowanie do zaliczenia ćwiczeń - 30 godzin

- przygotowanie do zaliczenia egzaminu - 30 godzin

- lektura literatury - 15 godzin

Łącznie 120 godzin. (4 ECTS)

W1. Student rozumie różnicę między algorytmem randomizowanym a algorytmem probabilistycznym.

W2. Zna podstawowe metody Monte Carlo.

W3. Rozumie metody obliczeń oparte na łańcuchach Markowa.

W4. Zna najważniejsze zastosowania dynamicznych metod Monte Carlo.

U1. Student potrafi napisać i zaimplementować prosty algorytm Monte Carlo U2. Umie symulować najważniejsze rozkłady prawdopodobieństwa.

U3. Potrafi empirycznie ocenić jakość prowadzonych symulacji.

K1. Student ma świadomość powszechności metod probabilistycznych i statystycznych w funkcjonowaniu współczesnych społeczeństw

(K_K02)

K2. Student zna niebezpieczeństwa związane z manipulacją danymi (K_K01)

Wykład konwencjonalny wspomagany komputerowo

Ćwiczenia rachunkowe

Samodzielne programowanie.

- pokaz

- wykład informacyjny (konwencjonalny)
- wykład problemowy

- ćwiczeniowa
- klasyczna metoda problemowa
- laboratoryjna

- metody służące prezentacji treści

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