Posledna prednaska + VYSVETLENIE SKUSKY - Vypoctova zlozitost algoritmov 14.12.2020 9:15

Zhrnutie prednášky

Posledná prednáška z výpočtovej zložitosti algoritmov je venovaná randomizovaným algoritmom, v ktorých je do výpočtu zakomponovaná náhodná voľba. Úvodom sa prednášajúca venuje filozofickému pozadiu determinizmu (Demokritos, Einstein) a nedeterminizmu (Epikuros) a náhodu vymedzuje ako axiómu, teda jav, ktorý nevieme predvídať. Zopakuje rozdiel medzi deterministickým algoritmom, ktorý pre rovnaký vstup vždy vygeneruje rovnakú postupnosť krokov, a nedeterministickým, ktorý sa môže rozvetvovať. Randomizovaný algoritmus potom simuluje nedeterministické rozhodovanie náhodným výberom z viacerých možností a ako príklad uvádza randomizovaný quicksort, kde sa pivot volí náhodne, pretože ideálny pivot (medián) nie je dopredu známy. Na začiatku zaznejú aj organizačné pokyny, že skúškové obdobie bude podľa rektora prebiehať dištančne.

• - Randomizovaný algoritmus obsahuje náhodnú voľbu a umožňuje efektívnejšie riešiť ťažké problémy zo tried NP.
• - Determinizmus vychádza z kauzality, nedeterminizmus pripúšťa existenciu náhody; spor pretrváva dodnes.
• - Náhoda sa berie ako axióma: jav, ktorý nevieme predvídať, bez ohľadu na to, či príčinu nepoznáme alebo neexistuje.
• - Deterministický algoritmus generuje pre rovnaký vstup vždy rovnakú postupnosť krokov a rovnaký výstup.
• - Nedeterministické rozvetvenie sa v počítači realizuje náhodným výberom jednej z možností.
• - Randomizovaný quicksort volí pivota náhodne, lebo optimálny pivot (medián) by dal rozdelenie na rovnaké polovice.
• - Skúškové obdobie bude podľa rektorovho prípisu prebiehať distančne.

Zhrnutie pripravené s pomocou AI z prepisu videa.