nechodím na prednáškyAlgoritmy a dátové štruktúry prednáška 20
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
Záverečná prednáška sa vracia k viacerým úlohám riešiteľným dynamickým programovaním. Najprv sa podrobne rieši problém vydávania mincí najmenším počtom platidiel pomocou rekurzie s memoizáciou, pričom sa diskutuje pseudopolynomiálna časová zložitosť a spôsob overenia korektnosti pažravého algoritmu pre danú sústavu mincí. Ďalej sa rieši problém batohu technikou meet in the middle pre malý počet predmetov a následne dynamickým programovaním pre celočíselné hmotnosti s pseudopolynomiálnou zložitosťou O(n krát W). Na záver sa prednáška vracia k problému rozmiestnenia autobusových zastávok v dedine, kde sa ukazuje, že medián minimalizuje súčet vzdialeností a aritmetický priemer minimalizuje súčet štvorcov vzdialeností, a celá úloha sa rieši kombináciou pažravého odhadu počtu zastávok, prefixových súčtov a dynamického programovania.
- Problém vydávania mincí najmenším počtom platidiel
- Rekurzia s memoizáciou a pseudopolynomiálna časová zložitosť
- Overenie korektnosti pažravého algoritmu pre sústavu mincí
- Problém batohu a technika meet in the middle
- Dynamické programovanie pre batoh s celočíselnými hmotnosťami
- Medián ako optimálne riešenie pre súčet vzdialeností
- Aritmetický priemer ako optimum pre súčet štvorcov vzdialeností
- Rozmiestnenie autobusových zastávok pomocou DP a prefixových súčtov
Zhrnutie pripravené s pomocou AI z prepisu videa.
