nechodím na prednáškyAlgoritmy a dátové štruktúry prednáška 17
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 pokračuje v téme dynamického programovania a venuje sa úlohe hľadania najdlhšej spoločnej podpostupnosti (LCS) dvoch reťazcov. Najprv sa ukazuje neefektívne riešenie hrubou silou s exponenciálnou zložitosťou, potom rekurzívne riešenie, ktoré postupne redukuje problém na prefixy oboch reťazcov. Zavádza sa memoizácia a následne iteratívna verzia s dvojrozmernou tabuľkou, v ktorej sa počíta dĺžka najdlhšej spoločnej podpostupnosti pre všetky dvojice prefixov. Ukazuje sa, ako pomocou šípok v tabuľke spätne zrekonštruovať jedno konkrétne optimálne riešenie, a diskutuje sa aj o hľadaní či počítaní všetkých optimálnych riešení na príklade najdlhšej rastúcej podpostupnosti. Na záver je spomenuté efektívnejšie riešenie najdlhšej rastúcej podpostupnosti v čase O(n log n).
- Najdlhšia spoločná podpostupnosť dvoch reťazcov
- Hrubá sila skúšajúca všetky podreťazce
- Rekurzívne riešenie a memoizácia
- Iteratívne vypĺňanie DP tabuľky best[i][j]
- Rekonštrukcia riešenia pomocou šípok v tabuľke
- Počítanie a generovanie všetkých optimálnych riešení
- Najdlhšia rastúca podpostupnosť ako ďalší príklad
- Efektívnejšie riešenie LIS v čase O(n log n)
Zhrnutie pripravené s pomocou AI z prepisu videa.
