Pravděpodobnostní analýza algoritmů

Upozornění

Úmluva na výběrovou přednášku proběhne e-mailem. Prosím zájemce, aby mě kontaktovali nejpozději do středy 4. října 2023.

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ší.

Slidy k přednášce

• Úvod a literatura
• Příklad analýzy jednoduchého algoritmu – přičítání jedničky k binárnímu číslu
• Další použití Markovových řetězců v analýze algoritmů

Algoritmy nad permutacemi

1. Pomocný matematický aparát
2. Hledání maxima v permutaci
3. Inverze v permutaci
4. Quicksort

Grafové algoritmy

1. Barvení grafu
2. Tranzitivní uzávěr

• Analýza hašování s lineárním přidáváním

Zkouška

Zkouška má pouze ústní část. Požadavky odpovídají sylabu předmětu, detaily budou upřesněny na přednášce.