Pravděpodobnostní analýza algoritmů - NTIN018
Anglický název: Probabilistic Analysis of Algorithms
Zajišťuje: Katedra distribuovaných a spolehlivých systémů (32-KDSS)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: nevyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: http://d3s.mff.cuni.cz/teaching/ntin018
Garant: RNDr. Alena Koubková, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Ukázky použití metod teorie pravděpodobnosti při výpočtu očekávané časové složitosti deterministických algoritmů (třídění, grafové algoritmy apod.) a při konstrukci a analýze randomizovaných algoritmů. Předpokládají se základní znalosti pravděpodobnosti a matematické statistiky.
Poslední úprava: Katedry Tajemník (22.04.2010)
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.

Poslední úprava: KOUBKOVA/MFF.CUNI.CZ (15.05.2008)
Požadavky ke zkoušce

Zkouška má pouze ústní část. Požadavky odpovídají sylabu předmětu.

Poslední úprava: Koubková Alena, RNDr., CSc. (10.10.2017)
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ší.

Poslední úprava: T_KSI (24.05.2002)