Posledne cvicenie; Otazky na skuske - Vyp. zloz. algoritmov 16.12.2020 13:00

Zhrnutie prednášky

Posledné cvičenie z Výpočtovej zložitosti algoritmov slúžilo na dohodnutie technickej stránky online skúšky a na ukážkový príklad. Vyučujúca so študentmi skúšala odovzdávanie ručne písaných riešení: vkladanie obrázkov priamo do testu nefunguje, funkčné je zdieľanie odkazu na obrázok z cloudu alebo odovzdanie súboru ako prílohy v samostatnom zadaní. Ručne písané riešenia (na papieri, tablete či grafickom tablete) vyžaduje, aby bolo vidieť autentický postup výpočtu zložitosti. Následne spoločne riešili úlohu s vnorenými cyklami, kde zápisom cez sumy vyšlo T(n) = n² + n, teda asymptoticky n². Na záver začali dokazovať hornú asymptotickú hranicu O(n²) z definície.

• - Skúška bude kombinovať testové otázky (výber odpovede, krátka odpoveď) s úlohami s ručne písaným riešením.
• - Vkladanie obrázkov priamo do testu nefunguje; Ctrl+C/Ctrl+V tiež nie.
• - Funkčné možnosti odovzdania: odkaz na zdieľaný obrázok alebo príloha v samostatnom zadaní na nahrávanie súborov.
• - Riešenia treba označiť číslom úlohy a pri viacerých úlohách odovzdať jeden spoločný dokument.
• - Zložitosť cyklov sa vyjadrí ako vnorená suma: súčet od i=1 po n z (n−i) + i + 1 dáva n·(n+1) = n² + n.
• - Asymptoticky je zložitosť Θ(n²), teda aj O(n²).
• - Pri dôkaze hornej hranice O(n²) treba z definície ukázať, že výraz je ohraničený zhora c·n² od istého n₀.

Zhrnutie pripravené s pomocou AI z prepisu videa.