Metody stochastyczne w analizie algorytmów

Co łączy PageRank Google’a, symulowane wyżarzanie, part-of-speech tagging, szyfry strumieniowe, kody splotowe? Analizę każdego z wymienionych algorytmów/protokołów/gier można przeprowadzić poprzez badanie własności odpowiadających im procesów Markowa (Łańcuch Markowa jest ciągiem zdarzeń losowych, w którym kolejny stan zależy tylko od stanu obecnego).

Celem wykładu jest zapoznanie studentów z zagadnieniami łańcuchów Markowa z dyskretnym czasem, na przestrzeeniach skończonych.

Pojęcia, techniki:

• procesy Markowa, rozkłady stacjonarne, szybka zbieżność
• coupling, path coupling,
• strong stationary times,
• Hidden Markov Model (Viterbi, Baum-Welch)
• martyngały.

Poruszane zagadnienia:

• kolorowanie grafów (zliczanie kolorowań, samplowanie kolorowań),
• symulowane wyżarzanie,
• analiza anonimowości (transakcje blockchainowe, sieci miksujące),
• bezpieczeństwo generatorów pseudolosowych i szyfrów strumieniowych,
• Risk Limiting Audits,
• Gambler’s ruin problem, independent chip model.