Podatkovne strukture in algoritmi 2

2020/2021
Program:
Univerzitetni študijski program 1. stopnje Finančna matematika
Letnik:
3 letnik
Semester:
drugi
Vrsta:
izbirni
Skupina:
B2
ECTS:
5
Jezik:
slovenski
Nosilci predmeta:
Ure na teden – 2. semester:
Predavanja
2
Seminar
0
Vaje
1
Laboratorij
1
Pogoji za vključitev v delo oz. za opravljanje študijskih obveznosti

Opravljen predmet Podatkovne strukture in algoritmi 1.

Vsebina

• 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.

Temeljni literatura in viri

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.

Cilji in kompetence

Š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.

Predvideni študijski rezultati

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.

Metode poučevanja in učenja

Predavanja, vaje, domače naloge, konzultacije

Načini ocenjevanja

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)

Reference nosilca

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]