Cvicenie - Vypoctova zlozitost algoritmov 21.10.2020 13:00

Zhrnutie prednášky

Cvičenie začína stručným zopakovaním asymptotickej výpočtovej zložitosti: horná hranica sa značí O, dolná Ω a najlepšie je ohraničenie zhora aj zdola rovnakou funkciou (Θ), pričom konštanty sa zanedbávajú a stačí, aby nerovnosť platila od nejakej hranice n₀. Hlavnou témou je určovanie časovej zložitosti rekurzívnych algoritmov na príklade hlavolamu Hanojské veže. Po vyskúšaní hlavolamu v interaktívnej simulácii je algoritmus sformulovaný metódou rozdeľuj a panuj: n−1 kotúčov sa presunie na pomocnú tyč, najväčší kotúč na cieľovú tyč a potom sa n−1 kotúčov presunie na cieľ. Následne je navrhnutá rekurzívna procedúra Hanoj(n, odkiaľ, kam, cez), kde triviálny prípad n = 1 vypíše jediný presun a netriviálny prípad volá seba samu dvakrát s n−1.

• - Asymptotická horná hranica sa značí O, dolná Ω; najlepšie je ohraničenie zhora aj zdola tou istou funkciou.
• - Pri asymptotickej zložitosti sa zanedbávajú multiplikatívne konštanty a nerovnosť stačí, ak platí od istého n₀.
• - Hanojské veže: presúvať možno len jeden kotúč naraz, s využitím pomocnej tyče a nikdy väčší kotúč na menší.
• - Riešenie využíva metódu rozdeľuj a panuj: problém s n kotúčmi sa rozloží na problémy s n−1 kotúčmi.
• - Rekurzívna procedúra Hanoj(n, odkiaľ, kam, cez) má triviálny prípad pri n = 1, kde sa len vypíše presun kotúča.
• - Netriviálny prípad: presun n−1 kotúčov na pomocnú tyč, presun najväčšieho kotúča na cieľ a opäť n−1 kotúčov na cieľovú tyč.
• - Cieľom cvičenia je následne určiť časovú zložitosť tohto rekurzívneho algoritmu pomocou rekurentného vzťahu.

Zhrnutie pripravené s pomocou AI z prepisu videa.