Preskoči na glavno vsebino

Podatkovne strukture in algoritmi 2

2026/2027
Program:
Univerzitetni študijski program 1. stopnje Matematika
Letnik:
3 letnik
Semester:
drugi
Vrsta:
izbirni
ECTS:
5
Jezik:
slovenski
Nosilec 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
  1. T. H. Cormen ... [et al.]: Introduction to Algorithms, 2nd ed. - Cambridge (Mass.) : MIT Press ; Boston : McGraw-Hill, cop. 200
  2. S. Dasgupta, C. Papadimitriou, U. Vazirani: Algorithms, Boston : McGraw-Hill, cop. 2008.
  3. J. Erickson: Algorithms, [S. l.] : J. Erickson, cop. 2019.
  4. J. Kleinberg, E. Tardos: Algorithm design, Boston : Pearson/Addison-Wesley, cop. 2006.
  5. J. Kozak: Podatkovne strukture in algoritmi, 2. natis. - Ljubljana : Društvo matematikov, fizikov in astronomov Slovenije, 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

Domače naloge z zagovorom;
kolokvija namesto izpita iz vaj, izpit iz vaj
5 - 10, pri čemer velja, da je pozitivna ocena od 6 - 10

Reference nosilca

Sergio Cabello Justo:
– 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]
– 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. 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]