Práce je kompilačního charakteru, úkolem studenta/tky je s pomocí doporučené literatury podat přehled některých z níže zmíněných aplikací a ukázat, jak se při řešení algoritmických problémů využívají Markovské řetězce. Vlastní příspěvek studenta bude spočívat v přehledném zpracování představené problematiky (v češtině nebo slovenštině), rozpracování příkladů, doplnění podrobností v některých důkazech a vypracování vybraných cvičení z Haggstromovy knihy.
Pro úspěšné vypracování práce je vhodné absolvovat předměty NSTP238 a NSTP050.
Seznam odborné literatury
O Haggstrom (2002): Finite Markov Chains and Algorithmic Applications. Cambridge University Press, Cambridge.
Předběžná náplň práce
V posledních 20 letech se velmi rozšířila oblast uplatnění Markovských řetězců i do oblastí mimo pravděpodobnost a statistiku. Nejvýznamější z těchto aplikací lze najít v informatice, v algoritmických aplikacích jako je počítaní (tj. dostatečně přesný odhad počtu) nebo generování vzorků nějakých složitých kombinatorických objektů. Pomocí metod Markov chain Monte Carlo a Markovských řetězců s diskrétním časem a konečným stavovým prostorem je možné najít odpovědi na velmi složité algoritmické problémy.
Předběžná náplň práce v anglickém jazyce
The range of applications of Markov chains was enlarged a lot during the last 20 years, also to areas outside of probability and statistics. We can find the most important of these applications in computer science, in algoritmic applications like counting (i.e. sufficiently accurate estimate of the number of some objects) or generating samples of some complicated combinatorial objects. By means of the Markov chain Monte Carlo methods and Markov chains with discrete time and finite statespace it is possible to find answers to quite comlicated algoritmic problems.
- zadáno a potvrzeno stud. odd.