nechodím na prednáškyAlgoritmy a dátové štruktúry prednáška 05
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 dátovú štruktúru vektor a predstavuje obojsmernú frontu (deque, dvojkoncovú frontu) implementovanú pomocou cyklického poľa, ktorá umožňuje vkladanie a vyberanie prvkov na oboch koncoch aj indexovanie v amortizovanom konštantnom čase. Prednáška vysvetľuje, prečo sa deque v bežnej praxi používa len zriedka, keďže väčšine programov stačí obyčajný vektor, a uvádza príklad použitia pri prehľadávaní grafu s hranami dĺžky 0 a 1. Druhá časť prednášky zavádza prioritnú frontu ako abstraktnú dátovú štruktúru a rozoberá dva neefektívne spôsoby jej implementácie - neusporiadané pole (rýchle vkladanie, pomalé vyberanie maxima lineárnym prehľadaním) a usporiadané pole (pomalé vkladanie posúvaním prvkov, rýchle vyberanie). Ako kompromis medzi nimi sa predstavuje bloková štruktúra ('halda chudobného muža') s optimálnou veľkosťou bloku rádovo odmocnina z n. Na záver sa zavádza pojem haldy (heap) a podmienka haldy ako základ pre ešte efektívnejšie riešenie, ktoré sa rozoberie v ďalšej prednáške.
- Obojsmerná fronta (deque) implementovaná v cyklickom poli
- Amortizovaná konštantná časová zložitosť operácií deque
- Prioritná fronta ako abstraktná dátová štruktúra
- Neusporiadané pole - rýchle vkladanie, pomalé vyberanie maxima
- Usporiadané pole - pomalé vkladanie, rýchle vyberanie
- Bloková štruktúra ("halda chudobného muža") a optimálna veľkosť bloku
- Úvod do haldy (heap) a podmienky haldy
Zhrnutie pripravené s pomocou AI z prepisu videa.
