Prezentacia - Vypoctova zlozitost algoritmov 9.11.2020 9:15

Zhrnutie prednášky

Prednáška zopakovala metódu rozdeľuj a panuj, pri ktorej sa problém rekurzívne delí na menšie podproblémy až po triviálne prípady a riešenie sa potom skladá späť. Na príkladoch sa ukázalo, že pri hľadaní maxima nepriniesla zlepšenie, pri druhom maxime znížila konštantu z 2n na 3n/2 a pri triedení (quicksort, mergesort) zlepšila zložitosť z O(n²) na O(n log n). Hlavnou témou bolo násobenie matíc: klasický algoritmus vyžaduje O(n³) násobení aj sčítaní. Strassenov algoritmus (70. roky) pre matice 2×2 používa sedem násobení namiesto ôsmich, no až 18 sčítaní a odčítaní namiesto štyroch, takže pre malé matice sa neoplatí. Pri rekurzívnom použití na bloky matíc rozmeru 2^k sa ušetrené násobenie výrazne prejaví. Ako ďalšia univerzálna metóda sa avizuje dynamické programovanie, ktoré rieši prípady, keď nesprávne použité rozdeľuj a panuj zhorší zložitosť.

• - Rozdeľuj a panuj delí problém na menšie podproblémy, rieši triviálne prípady a skladá výsledné riešenie.
• - Pri hľadaní maxima metóda nezlepšuje zložitosť a pridáva réžiu rekurzie.
• - Pri druhom maxime sa konštanta znížila z 2n na 3n/2, rád O(n) zostal.
• - Quicksort a mergesort zlepšujú zložitosť z O(n²) na O(n log n).
• - Klasické násobenie matíc n×n má zložitosť O(n³): n³ násobení a n²(n−1) sčítaní.
• - Strassenov algoritmus robí pre 2×2 sedem násobení namiesto ôsmich, ale 18 sčítaní namiesto štyroch.
• - Strassenov algoritmus sa uplatní rekurzívne na podmatice veľkosti 2^k a oplatí sa až pri veľkých maticiach.
• - Ďalšou metódou bude dynamické programovanie ako riešenie pri nevhodnom použití rozdeľuj a panuj.

Zhrnutie pripravené s pomocou AI z prepisu videa.