Předmět Pravděpodobnostní analýza algoritmů (NTIN018)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN018 - Pravděpodobnostní analýza algoritmů, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
Časová složitost algoritmu v nejhorším a průměrném případě. Metody pro určení očekávané doby výpočtu deterministického algoritmu při známém rozložení vstupních dat (přímý výpočet, využití vytvořujících funkcí, rekurentní vztahy). Vyšší momenty doby výpočtu, rozptyl. Markovova a Čebyševova nerovnost a jejich význam pro odhad pravděpodobnosti velkých odchylek skutečné doby výpočtu od očekávaného průměru. Reprezentace algoritmu Markovovým řetězcem, pravděpodobnosti přechodu mezi stavy výpočtu, očekávaný počet průchodů jednotlivými stavy. Princip randomizovaných (pravděpodobnostních) algoritmů a jejich význam. Výpočet očekávané časové složitosti, odhad pravděpodobnosti chyby. Konkrétní příklady pravděpodobnostní analýzy algoritmů: jednoduché počítání na Turingově stroji, hledání maximálního prvku v posloupnosti, třídicí algoritmy (SelectionSort, QuickSort, InsertSort, ShellSort), grafové algoritmy (barvení grafu, tranzitivní uzávěr, náhodné procházky na grafech), pravděpodobnostní testování prvočíselnosti, randomizovaný SAT a případně další.
Literatura
Feller, W.: An introduction to probability theory and its applications.Wiley, New York,1970. Hofri, M.: Probabilistic analysis of algorithms. Springer-Verlag, 1987. Sedgewick, R., Flajolet, P.: An introduction to the analysis of algorithms. Addison-Wesley, 1996.
Garant
RNDr. Alena Koubková, CSc.