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

Anotace

čeština

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)

angličtina

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.

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

čeština

Č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)

angličtina

The worst case and average case time complexity of algorithms. Methods for computing of the expected running time of deterministic algorithms under known distribution of input data (straight computing, using generating functions, recurrences).

Higher order moments of running time, the variance. Markov's inequality, Chebyshev's inequality, their importance for estimation of probability of large deviations from the expected running time.

The representation of an algorithm by a Markov chain, transition probabilities between the states of computing, the expected number of passes through given states.

The principle and importance of randomized (probabilistic) algorithms. Computing of their expected time complexity, estimation of the error probability.

Examples of probabilistic analysis of algorithms: simple counting on the Turing machine, finding the largest term in a sequence, sorting algorithms (Selectionsort, Quicksort, Insertinsort, Shellsort), graph algorithms (graph coloring, transitive closure, random walks on graphs), probabilistic primality testing, randomized SAT and others.

Poslední úprava: T_KSI (24.05.2002)