Algoritmi in podatkovne strukture 2
Section outline
-
V skladu z dogovorom vas vabimo, da pri predmetu APS 2 izvedete tudi domače programerske naloge
preko e-učilnice v pod-sistemu CodeRunner.Pozor:
Pri kodiranju programerskih nalog uporabljajte le osnovne, built-in, programerske strukture (kazalec, tabela)
in ne kakšnih pomožnih iz java.util paketa!
Do konca semestra bo zaporedoma na dva (2) tedna objavljenih pet (5) nalog.Prva in zadnja naloga bosta predvidoma vredni 5 točk, ostale tri naloge pa 10 točk.Skupno torej lahko preko domačih programerskih nalog zberete 40 točk (tukaj naj vas spomnim, da je
minimum za opravljene vaje postavljen na doseženih 50% uspešnosti, torej 20 točk). -
-
Pregled vsebin avditornih vaj pri predmetu APS 2. Opis predvidenih aktivnosti in študentskih obveznosti, ter organizacije izvajanja.
Določanje časovnih zahtevnosti algoritmov z uporabo asimptotskih simbolov O, Omega, Theta.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Pregled različnih pristopov reševanja problema največjega podzaporedja v zaporedju števil. Ocenjevanje časovne zahtevnosti omenjenih pristopov.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Pregled določanja časovne zahtevnosti algoritmov s postopkom amortizirane analize.
Določanje amortizirane časovne zahtevnosti algoritmov po metodi vsote in po metodi kopičenja.
-
-
Pregled nekaterih pogosto uporabljenih podatkovnih struktur v Javi.
-
-
Pregled podatkovnih struktur seznam, urejen seznam in preskočni seznam.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Urejena dvojiška drevesa, rotacije in B drevesa.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Pregled AVL in Rdeče-črnih dreves.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Bloom filtri, zgoščevalne funkcije, veriženje, odprto naslavljanje.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
P-NP problemi, pokritje povezav (vertex cover), problem klike (clique problem)
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Dinamično programiranje: množenje matrik, razdalja med nizi
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-
-
Dinamično programiranje: problem 0/1 nahrbtnika, problem rezanja palice.
Priporočljivo je, da si pripravite zapiske predavanj, ter pisalo in papir.
-