Výpočtová zložitosť algoritmov

Tento kurz ťa naučí analyzovať efektivitu algoritmov z pohľadu výpočtovej zložitosti a porozumieť rôznym metódam riešenia algoritmických problémov.

Začneš s pojmom časovej a pamäťovej zložitosti, určíš najhorší a priemerný prípad, a naučíš sa, ako sa počíta asymptotická horná a dolná hranica zložitosti.

Postupne prejdeš najznámejšie triediace algoritmy ako bubblesort, quicksort, mergesort, heapsort či insertsort – a porovnáš ich výpočtové vlastnosti. Spoznáš rozdiel medzi zložitosťou algoritmu a problému.

V druhej časti kurzu sa naučíš kľúčové strategické prístupy k riešeniu problémov: Rozdeľ a panuj (napr. Strassenov algoritmus), Dynamické programovanie (batoh, najkratšia cesta), Backtracking a vetvy a medze, Greedy algoritmy (napr. problém mincí, minimálna kostra).

Následne sa zameriaš na teoretickú informatiku – triedy zložitosti P, NP, NPC, ich hierarchiu a čo znamená, že problém je algoritmicky neriešiteľný.

V závere kurzu preskúmaš aj pokročilé a pravdepodobnostné metódy, ako sú Monte Carlo, Las Vegas algoritmy či genetické algoritmy na riešenie ťažkých úloh.

Celé štúdium je podopreté riešením praktických úloh, testami a záverečnou skúškou.