nechodím na prednáškyADŠ prednáška 14: Pažravé algoritmy 2 - voľba optimálneho poradia.
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 nadväzuje na pažravé algoritmy a prechádza od úloh, kde nezáležalo na poradí, k úlohám, v ktorých treba zvoliť optimálne poradie činností. Ako úvodný príklad slúži studňa, pri ktorej si viacerí ľudia naberajú vodu a minimalizuje sa súčet (ekvivalentne priemer) časov čakania. Pomocou časovej osi sa ukazuje, že prerušovanie naberania nemá zmysel: ak ľudí zoradíme podľa okamihu skončenia a každý si naberie naraz, nikomu sa čas nezhorší. Spojitá úloha sa tak zmení na diskrétnu s n! možnými poradiami, ktorú možno riešiť hrubou silou, no lepšie je použiť elegantnejší argument o výmene susedných prvkov v rozvrhu. Spomenutý je aj problém obchodného cestujúceho, pre ktorý pažravé riešenie optimum nenájde.
- - Druhá trieda pažravých úloh: záleží na poradí, v akom sa činnosti vykonajú.
- - Problém obchodného cestujúceho: pažravý postup (najlacnejší ďalší lístok) nedáva optimum a vhodné pažravé riešenie nepoznáme.
- - Minimalizácia súčtu a priemeru časov čakania je to isté, lebo počet ľudí je pevný.
- - Prerušovanie činností nemá zmysel: zoradením podľa času skončenia sa nikomu čas nezhorší.
- - Spojitú úlohu tak prevedieme na diskrétnu s n! možnými poradiami, ktorú vieme riešiť aj hrubou silou.
- - Elegantnejší dôkaz optimality vychádza z výmeny susedných prvkov v ľubovoľnom rozvrhu.
Zhrnutie pripravené s pomocou AI z prepisu videa.
