Podatkovne strukture in algoritmi 2

Opravljen predmet Podatkovne strukture in algoritmi 1.

• Požrešna metoda: Huffmanovo kodiranje, pokritje množice, itd.
• Amortizirana časovna zahtevnost. Disjunktne množice.
• Minimalna vpeta drevesa. Boruvkav, Primov in Kruskalov algoritem.
• Iskalna in uravnotežena drevesa.
• Naključnostna iskalna drevesa. Preskakovalni seznami.
• Zgoščanje.
• Hitra Fouriereva transformacija.
• Primeri NP-težkih problemov. Splošne metode za težke probleme.
• Drugi izbrani algoritmi.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 2. izdaja, MIT Press, Cambridge, 2001.
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: Algorithms, McGraw-Hill, 2008.
J. Erickson: Zapiski za Undergraduate Algorithms, 2012.
J. Kleinberg, E. Tardos: Algorithm design, Pearson/Addison-Wesley, 2005.
J. Kozak: Podatkovne strukture in algoritmi, DMFA-založništvo, Ljubljana, 1997.

Študent nadgradi poznavanje osnovnih podatkovnih struktur in z njimi povezanih algoritmov, ki se uporabljajo pri programiranju. Seznani se z matematično analizo pravilnosti ter časovne in prostorske zahtevnosti algoritmov.

Znanje in razumevanje: Poznavanje osnovnih podatkovnih struktur in algoritmov ter praktičnih problemov, pri katerih se jih lahko smiselno uporabi. Poznavanje osnov teorije računske zahtevnosti in razumevanje njenega pomena v praksi.
Uporaba: Snovanje učinkovitih računalniških programov in napovedovanje njihovega obnašanja s pomočjo matematičnih metod.
Refleksija: Povezanost med teoretičnimi napovedmi o obnašanju računalniških programov in dejanskim obnašanjem.
Prenosljive spretnosti – niso vezane le na en predmet: Pomen matematične analize računskih postopkov in njena praktična uporabnost. Ločevanje med računsko obvladljivimi in neobvladljivimi problemi.

Predavanja, vaje, domače naloge, konzultacije

Način (pisni izpit, ustno izpraševanje, naloge, projekt):

Domače naloge z zagovorom;
kolokvija namesto izpita iz vaj, izpit iz vaj

ocene: 5 (negativno), 6-10 (pozitivno) (po Statutu UL)

CABELLO, Sergio. Finding shortest contractible and shortest separating cycles in embedded graphs. V: 20th Annual ACM-SIAM Symposium on Discrete Algorithms, January 4-6, New York. SODA 2009 : special issue, (ACM transactions on algorithms, ISSN 1549-6325, Vol. 6, iss. 2). New York: Association for Computing Machinery, 2010, article No.: 24 (18 str.). [COBISS-SI-ID 15572057]
CABELLO, Sergio, KNAUER, Christian. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational geometry, ISSN 0925-7721. [Print ed.], 2009, vol. 42, iss. 9, str. 815-824. [COBISS-SI-ID 15160409]
CABELLO, Sergio, HAVERKORT, Herman Johannes, KREVELD, Marc van, SPECKMANN, Bettina. Algorithmic aspects of proportional symbol maps. Algorithmica, ISSN 0178-4617, 2010, vol. 58, no. 3, str. 543-565. [COBISS-SI-ID 15151193]
PERME, Tomaž, NOVAK, Matjaž, STRAŠEK, Rok, KAVKLER, Iztok, ORBANIĆ, Alen. A model for technical optimisation of the distribution centre, 2011, Acta technica corviniensis, tome 4, fasc. 2, str. 39-43. [COBISS-SI-ID 4154583]
ORBANIĆ, Alen. F -actions and parallel-product decomposition of reflexible maps. Journal of algebraic combinatorics, ISSN 0925-9899, 2007, issue 4, vol. 26, str. 507-527. [COBISS-SI-ID 14429529]
ORBANIĆ, Alen, BOBEN, Marko, JAKLIČ, Gašper, PISANSKI, Tomaž. Algorithms for drawing polyhedra from 3-connected planar graphs. Informatica, ISSN 0350-5596, 2004, vol. 28, no. 3, str. 239-243. [COBISS-SI-ID 13285977]