Basic Information

An illustration of using probabilistic methods in analysis of the expected running time of deterministic algorithms (e.g. sorting, graphs algorithms) and in the construction and analysis of randomized algorithms. Basic knowledge of statistics is required.

Time and Location	Tue 10:40 - 12:10 in S301
Winter Term	2/0 Zk
Information in SIS:	NTIN018

News

work in progress...

Aktuální obsah přednášky a požadavky ke zkoušce

Příklad analýzy jednoduchého algoritmu – přičítání jedničky k binárnímu číslu

Realizace algoritmu na Turingově stroji, odvození pravděpodobnostního rozdělení doby výpočtu. Výpočet očekávané doby výpočtu z definice, pomocí vytvořující funkce, aplikací geometrického rozdělení. Pravděpodobnosti velkých odchylek – Markovova a Čebyševova nerovnost. Další charakteristiky doby výpočtu – modus, medián. Popis algoritmu Markovovým řetězcem.

Další použití Markovových řetězců v analýze algoritmů

Ramdomizovaný 2-SAT, náhodná procházka na grafech. Výpočet očekávaného počtu průchodů daným stavem algoritmu. Odhad velikosti dynamických datových struktur (Markovovy procesy se spojitým časem, základy teorie front) – nezkouší se.

Algoritmy nad permutacemi

Pomocný matematický aparát

Počítání s binomickými koeficienty, Stirlingova čísla 1. a 2. druhu a jejich použití. Vytvořující funkce náhodných veličin a jejich použití.

Hledání maxima v permutaci

Analýza počtu nalezených průběžných maxim (rekordů): Odvození rekurentního vztahu pro pravděpodobnosti, jeho řešení pomocí vytvořující funkce, výpočet hledaných pravděpodobností z vytvořující funkce, přímý výpočet očekavané hodnoty z definice (nezkouší se). Odvození (a řešení) rekurentních vztahů pro střední hodnotu a rozptyl z rekurze pro vytvořující funkce. Aplikace výsledků při analýze algortimu třídění exktrakcí maxima (Selectionsort) a cyklů v permutaci.

Inverze v permutaci

Inverzní tabulka permutace, pravděpodobnostní rozdělení jejích prvků. Výpočet očekávaného počtu nul v inverzní tabulce, aplikace při analýze počtu rekordů. Očekávaný počet inverzí, aplikace při analýze Insertionsortu. Zobecnění Insertionsortu – algoritmus Shellsort. Odvození očekávaného složitosti dvoustupňového Shellsortu s přírůstky 1, 2 a 1, h (zkouší se jen odvození základního výrazu pro očekávaný počet inverzí, ne jeho další úpravy).

Quicksort

Klasická analýza očekávané složitosti Quicksortu. Řešení rekurentního vztahu pro očekávanou dobu výpočtu pomocí vytvořující funkce (nezkouší se). Analogicky - řešení rekurentního vztahu pro očekávanou dobu výpočtu Mergesortu pomocí vytvořující funkce. Ananlýza randomizovaného Quicksortu – odhad počtu porovnání prvků pomocí náhodného binárního vyhledávacího stromu generovaného algoritmem.

Grafové algoritmy

Barvení grafu

Výpočet obarvení metodou backtracking, odhad očekávaného počtu vrcholů v prohledávacím stromě. Důkaz, že očekávaný čas algoritmu je O(1).

Tranzitivní uzávěr

Topologické uspořádání acyklického orientovaného grafu, tranzitivní uzávěr, tranzitivní redukt. Náhodný graf. Dva způsoby analýzy algoritmu pro výpočet tranzitivního uzávěru (a tranzitivního reduktu) acyklického grafu – odhad očekávané doby výpočtu O(n5/2) a O(n2log n) – druhá analýza se nezkouší. Násobení řídkých matic.

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