Algoritmi in podatkovne strukture 1
Section outline
-
Namen predmeta APS1 je naučiti udeležence algoritmičnega razmišljanja. Ukvarjali se bomo s pravilnostjo in učinkovitostjo algoritmov. Spoznali bomo več osnovnih algoritmov in z njimi povezanih podatkovnih struktur, ki bodo predstavljali našo osnovno orodjarno. Poleg tega bodo služili kot primeri, na katerih se bomo učili načrtovanja ter analiziranja algoritmov in podatkovnih struktur. S konkretnimi implementacijami zasnovanih idej pa bomo utrjevali in poglabljali znanje programiranja.
-
- Pregled predmeta in študentskih obveznosti
- C++
- osnovna urejanja
Laboratorijske vaje se začnejo drugi teden semestra. -
- računska zahtevnost
- mergesort, quicksort
- urejanje brez primerjav
- bisekcija
-
- seznam, sklad, vrsta (dinamično polje, povezan seznam)
- vrsta s prednostjo (kopica, preskočni seznam)
- množica, slovar (razpršena tabela)
-
- dvojiška, iskalna, izrazna, črkovna, ...
- statično drevo (poizvedbe na območjih)
- uravnotežena drevesa (AVL)
-
- dokazovanje pravilnosti
- primeri problemov (car fueling, interval scheduling, ...)
-
- vrste, lastnosti, predstavitev
- preiskovanja (DFS, BFS), povezanost
- topološko urejanje
-
- Dijkstra
-
- disjunktne množice
- minimalno vpeto drevo (Prim, Kruskal)
-
- opis tehnike
- master theorem
- primeri nalog
-
- opis tehnike
- primeri uporabe (rod cutting, longest common subsequence, knapsack, ...)
-
- osnovni koncepti (preseki, razdalje)
- vsebovanost, površina
- konveksna ovojnica