nechodím na prednáškyADŠ prednáška 02: Motivácia k časovej zložitosti
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška otvára analýzu algoritmov a časovú zložitosť otázkou, či sú efektívne algoritmy potrebné, keď výkon počítačov exponenciálne rastie podľa Mooreovho zákona. Ten platí dodnes, no už najmä vďaka viacjadrovým procesorom a GPU, čo prináša problémy s paralelizáciou. Efektívne algoritmy zostávajú dôležité, pretože sa kapacity vždy využijú naplno a objem dát, napríklad na internete, rastie rýchlejšie než výkon strojov, takže hrubá sila pri vyhľadávaní nestačí. Ďalším príkladom sú hry dvoch hráčov, najmä šach, kde algoritmus minimax prehľadáva strom ťahov so zhruba desiatimi možnosťami na každej úrovni a hĺbka predvídania rozhoduje o kvalite hry.
- - Mooreov zákon: výpočtová sila exponenciálne rastie, dnes najmä cez viacjadrové procesory a GPU.
- - Paralelizácia prináša nové problémy, lebo nie všetky úlohy sa dajú dobre paralelizovať.
- - Dostupné kapacity sa vždy plne využijú, preto rýchlejší hardvér nenahrádza efektívne algoritmy.
- - Objem dát na internete rastie rýchlejšie ako rýchlosť počítačov, hrubá sila vo vyhľadávaní nestačí.
- - Aj bez veľkých dát sú potrebné efektívne algoritmy, napríklad v hrách dvoch hráčov ako šach.
- - Minimax prehľadáva strom možných ťahov: za seba volí maximum, za súpera minimum.
- - Čím viac polťahov dopredu program vidí, tým lepšie hrá, no počet pozícií rastie exponenciálne.
Zhrnutie pripravené s pomocou AI z prepisu videa.
