Podatkovne strukture in algoritmi 1

Pogojev za vključitev v delo ni.

• Algoritmi, podatkovne strukture, časovna zahtevnost.
• Tabela, sklad, vrsta, seznam.
• Deli in vladaj: binarno iskanje, urejanje z zlivanjem, Strassenov algoritem, rešitev rekurzivnih enačb, hitro urejanje, mediana, itd.
• Sestopanje.
• Dinamično programiranje: najdaljše naraščajoče podzaporedje, Levenshteinova razdalja, množenje več matrik, 0/1-nahrbtnik, problem trgovskega potnika, itd.
• Predstavitve grafov in omrežij. Osnovni algoritmi na grafih: pregledi, topološko urejanje, Floyd-Warshallov algoritem, Dijkstrov algoritem (kopice), Bellman-Fordov algoritem, itd.

1. T. H. Cormen ... [et al.]: Introduction to Algorithms, 2nd ed. - Cambridge (Mass.) : MIT Press ; Boston : McGraw-Hill, cop. 2001.
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.

Študent spozna osnovne podatkovne strukture in z njimi povezane algoritme, ki se uporabljajo pri programiranju. Seznani se z matematično analizo pravilnosti ter časovne in prostorske zahtevnosti algoritmov.

Znanje in razumevanje: Poznavanje nekaterih osnovnih podatkovnih struktur in algoritmov ter praktičnih problemov, pri katerih se jih lahko smiselno uporabi. Ugotavljanje pravilnosti računskih postopkov.
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 njihovim dejanskim obnašanjem.
Prenosljive spretnosti – niso vezane le na en predmet: Pomen matematične analize računskih postopkov in njena praktična uporabnost

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)

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

Sandi Klavžar:
KLAVŽAR, Sandi, MOLLARD, Michel. Cube polynomial of Fibonacci and Lucas cubes. Acta applicandae mathematicae, ISSN 0167-8019, 2012, vol. 117, no. 1, str. 93-105. [COBISS-SI-ID 16191833]
ILIĆ, Aleksandar, KLAVŽAR, Sandi, RHO, Yoomi. Generalized Lucas cubes. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2012, vol. 6, no. 1, str. 82-94. [COBISS-SI-ID 16242265]
BATAGELJ, Vladimir, KORENJAK-ČERNE, Simona, KLAVŽAR, Sandi. Dynamic programming and convex clustering. Algorithmica, ISSN 0178-4617, 1994, let. 11, št. 2, str. 93-103. [COBISS-SI-ID 6799364]
KLAVŽAR, Sandi, LOKAR, Matija, PETKOVŠEK, Marko, PISANSKI, Tomaž. Izbrana poglavja iz računalništva. Del 2, Diskretna optimizacija, (Matematični rokopisi, 15). Ljubljana: Društvo matematikov, fizikov in astronomov SRS, 1986. 128 str. [COBISS-SI-ID 13496065]