Prednaska - Vypoctova zlozitost algoritmov 30.11.2020 9:15

Zhrnutie prednášky

Prednáška opakuje látku z minulej hodiny o pažravých algoritmoch a backtrackingu a pripravuje pôdu na zavedenie tried zložitosti problémov, vrátane triedy súvisiacej s nedeterministickými algoritmami. Pažravá stratégia pri optimalizačnom probléme vyberá lokálne najlepšiu možnosť, no nie vždy vedie k optimálnemu riešeniu: pri vyplácaní mincami funguje len pre určité nominálne hodnoty (1, 2, 5, 10, 20, 50), funguje aj pri hľadaní minimálnej kostry grafu. Backtracking systematicky prehľadáva nedeterministický výpočtový strom do hĺbky a má exponenciálnu zložitosť c^n, kde c je stupeň nedeterminizmu a n hĺbka stromu. Na príklade skákania šachovým koňom po šachovnici sa vysvetľuje, že cesta od koreňa k listu zodpovedá jednému nedeterministickému výpočtu, hĺbka stromu je 64 a stupeň nedeterminizmu najviac 8.

• - Pažravá stratégia vyberá v každom kroku lokálne najlepšiu možnosť, ale nie vždy dá optimálne riešenie.
• - Mincovka pažravo funguje len pre vhodné nominály (1, 2, 5, 10, 20, 50); minimálna kostra grafu je ďalší klasický príklad, kde pažravosť funguje.
• - Nedeterministický algoritmus môže v niektorých krokoch pokračovať rôznymi spôsobmi, jeho výpočet tvorí strom, deterministický výpočet je lineárna postupnosť krokov.
• - Backtracking (prehľadávanie s návratom) deterministicky prehľadáva celý výpočtový strom do hĺbky.
• - Zložitosť backtrackingu je exponenciálna, c^n, kde c je stupeň nedeterminizmu a n dĺžka (hĺbka) výpočtu.
• - Pri probléme šachového koňa je hĺbka stromu 64 (počet políčok), stupeň nedeterminizmu najviac 8 a riešením sú len cesty dĺžky 64.
• - Pojem nedeterministického algoritmu je dôležitý pre triedy zložitosti, ktoré sa zavádzajú na tejto hodine.

Zhrnutie pripravené s pomocou AI z prepisu videa.