Podatkovne strukture in algoritmi 3

2022/2023
Program:
Magistrski študijski program 2. stopnje Matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
izbirni
Skupina:
R1
ECTS:
6
Jezik:
slovenski, angleški
Nosilci predmeta:
Ure na teden – 1. ali 2. semester:
Predavanja
2
Seminar
1
Vaje
2
Laboratorij
0
Vsebina

Predavatelj izbere teme iz naslednjega seznama:
Uravnotežena iskalna drevesa.
Zgoščene tabele.
Binomske in Fibonaccijeve kopice.
Vodenje disjunktnih množic.
Algoritmi na nizih (Rabina in Karpa, Knutha, Morrisa in Pratta, Boyerja in Moora).
Računanje konveksne ovojnice.
Voronojev diagram in Delauneyeva triangulacija.
Iskanje maksimalnega pretoka s predtokom.
Iskanje največjega (uteženega) prirejanja v splošnem grafu.
Algoritem alpha-beta.
Algoritmi za ravninske grafe.
Algoritmi za zunanji pomnilnik.
Vztrajne podatkovne strukture.
Podatkovne strukture za cela števila.
Enostavni vzporedni algoritmi.
Dinamična drevesa.

Temeljni literatura in viri

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 2. izdaja, MIT Press, 2001.
D. C. Kozen: The Design and Analysis of Algorithms, Springer, 1991.
D. E. Knuth: Selected Papers on Analysis of Algorithms, Cambridge University Press, 2000.
S. Even, G. Even: Graph Algorithms, 2. izdaja, Cambridge University Press, 2011.
Znanstveni članki.

Cilji in kompetence

Študent nadgradi poznavanje podatkovnih struktur in z njimi povezanih algoritmov, ki se uporabljajo pri načrtovanju učinkovitih algoritmov. Ob tem poglobi znanje o matematični analizi pravilnosti ter časovne in prostorske zahtevnosti algoritmov.

Predvideni študijski rezultati

Znanje in razumevanje: Poznavanje zahtevnejših podatkovnih struktur in algoritmov, praktičnih in teoretičnih problemov, pri katerih se jih lahko smiselno uporabi, ter poznavanje osnov teorije računske zahtevnosti.
Uporaba: Snovanje učinkovitih računalniških programov in napovedovanje njihovega obnašanja v praksi 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 zahtevnimi in manj zahtevnimi problemi.

Metode poučevanja in učenja

predavanja, seminar, vaje, domače naloge, konzultacije in samostojno delo študentov

Načini ocenjevanja

Izpit iz vaj (2 kolokvija ali pisni izpit) ali domače naloge
Ustni izpit
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Reference nosilca

Sergio Cabello:
CABELLO, Sergio, COLIN DE VERDIÈRE, Éric, LAZARUS, Francis. Algorithms for the edge-width of an embedded graph. V: 26th Annual Symposium on Computational Geometry, June 13th-16th, 2010, Snowbird, Utah. 26th Annual Symposium on Computation Geometry at Snowbird, Utah, USA : Special issue, (Computational geometry, ISSN 0925-7721, Vol. 45, iss. 5-6, 2012). Amsterdam: Elsevier, 2012, str. 215-224. [COBISS-SI-ID 16093017]
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. Many distances in planar graphs. Algorithmica, ISSN 0178-4617, 2012, vol. 62, no. 1-2, str. 361-381. [COBISS-SI-ID 15702873]