Programovanie, 8. týždeň

Zhrnutie prednášky

Prednáška nadväzuje na minulotýždňovú tému jednosmerných spájaných zoznamov, ktorých nevýhodou ostáva lineárna zložitosť operácií. Predstavuje obojsmerný spájaný zoznam, kde každý uzol ukazuje na nasledujúci aj predchádzajúci prvok, a jeho použitie pri histórii prehliadača či prehrávaní videa. Ďalej opisuje kruhový spájaný zoznam, v ktorom je posledný prvok prepojený s prvým, a jeho využitie v doskových hrách (poradie hráčov) a v plánovači procesov operačného systému. Úvahou o ukazovaní do stredu zoznamu, ktoré zníži zložitosť len na polovicu, prednáška motivuje prechod k stromu ako hierarchickému abstraktnému údajovému typu, a tým aj k binárnemu vyhľadávaciemu stromu. Neskôr sa spomínajú aj únie a príklad vyústený do jednoduchej počítačovej hry.

• - Jednosmerný spájaný zoznam má stále lineárnu zložitosť operácií, rovnako ako pole.
• - Obojsmerný spájaný zoznam obsahuje v uzle ukazovateľ na nasledujúci aj predchádzajúci prvok.
• - Obojsmerný zoznam umožňuje prechod oboma smermi, napr. história prehliadača alebo prehrávanie videa.
• - Kruhový spájaný zoznam prepája posledný prvok s prvým; využíva sa v doskových hrách a plánovači procesov.
• - Ukazovanie do stredu zoznamu zníži zložitosť iba na O(n/2), čo je stále lineárne.
• - Opakovaním delenia na ľavú a pravú časť vzniká strom, hierarchický abstraktný údajový typ.
• - Prednáška smeruje k binárnemu vyhľadávaciemu stromu a k únii v záverečnom príklade hry.

Zhrnutie pripravené s pomocou AI z prepisu videa.