Algoritmi in podatkovne strukture 2

Predavanja:
1. Računska zahtevnost algoritmov: motivacija, asimptotična notacija z definicijami in primeri.
2. Deli in vladaj: krovni izrek z dokazom, algoritem za hitro iskanje k-tega najmanjšega elementa (quickselect), Karacubov algoritem za hitro množenje, Strassenovo množenje matrik.
3. Dinamično programiranje: ponovitev osnovnih pristopov, primeri s kompleksnejšim opisom stanja (problem trgovskega potnika, barvanje grafov), primeri z zahtevnejšim računanjem (delnih) rezultatov (najdaljše naraščajoče podzaporedje, spuščanje jajc).
4. Problem maksimalnega pretoka: definicija, Ford-Fulkersonova metoda, Edmonds-Karpov algoritem, uporaba (npr. pri problemu prirejanja v dvodelnih grafih).
5. Iskanje po znakovnih zaporedjih: naivna metoda, Rabin-Karpov algoritem, Knuth-Morris-Prattov algoritem.
6. Metode za indeksiranje besedila: drevo trie, priponska tabela, priponsko drevo.
7. Računska geometrija: osnovni geometrijski objekti (točke, premice, večkotniki ...), razdalje, presečišča, ploščine, konveksna ovojnica, geometrijske podatkovne strukture (npr. k-d-drevesa).
8. Linearno programiranje: formulacija s sistemom linearnih neenačb, predstavitev optimizacijskih problemov z linearnimi programi, simpleksni algoritem.

Vaje: Na vajah bodo študentje utrjevali snov, podano na predavanjih. Snov bodo uporabili za reševanje praktičnih problemov.

Domače naloge:
V okviru sprotnih (tedenskih) domačih nalog bodo študentje reševali programerske probleme, povezane s snovjo predavanj in vaj. Oddaje se bodo preverjale s pomočjo testnih primerov. Pri točkovanju bo poleg pravilnosti štelo tudi spoštovanje časovnih in prostorskih omejitev.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022.

Dodatna literatura:
Adam Jones. Advanced Techniques in Dynamic Programming: A Comprehensive Guide for Java Developers. 2024.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry: Algorithms and Applications, 3rd Edition. Springer, 2008.
Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.

Študentje bodo pridobili poglobljeno znanje s področij načrtovanja algoritmov, analize algoritmov, uporabe podatkovnih struktur ter izbranih problemov in algoritmov, obenem pa bodo utrjevali in poglabljali svoje znanje programiranja.

Študentje bodo po opravljenem predmetu:

• znali ocenjevati računsko zahtevnost algoritmov;
• znali reševati probleme z metodo deli in vladaj in ocenjevati računsko zahtevnost pripadajočih algoritmov;
• znali uporabljati zahtevnejše prijeme pri načrtovanju algoritmov z metodo dinamičnega programiranja;
• poznali učinkovite algoritme za reševanje problema maksimalnega pretoka in znali prepoznati realne probleme, ki jih je mogoče reševati na tak način;
• poznali učinkovite algoritme za iskanje po znakovnih zaporedjih;
• poznali učinkovite algoritme za indeksiranje besedila;
• obvladali osnovne koncepte ter izbrane algoritme in podatkovne strukture na področju računske geometrije;
• poznali koncept linearnega programiranja in znali formulirati relevantne optimizacijske probleme kot linearne programe.

Uporaba:
Uporaba naučenih principov pri načrtovanju algoritmov in njihovem programiranju.

Refleksija:
Razumevanje osnovnih principov načrtovanja algoritmov in njihove vloge pri reševanju računskih problemov.

Prenosljive spretnosti:
Zmožnost načrtovanja primerne in učinkovite algoritmične rešitve različnih problemov ter zmožnost implementacije razvitih algoritmov ne glede na izbrani programski jezik.

Predavanja, vaje, domače naloge.

Sprotno preverjanje: domače naloge
Končno preverjanje: pisni in ustni izpit
ocene: 5 (negativno), 6-10 (pozitivno), (ob upoštevanju Statuta UL)

ČIBEJ, U., FÜRST, L., MIHELIČ, J. A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms. Symmetry, 11(10): 1–26, 2019.
FÜRST, L. Neighborhood-based pseudo-canonical representation of graphs. The IPSI BgD Transactions on Internet Research, 15(2): 59–68, 2019.
FÜRST, L., ČIBEJ, U., MIHELIČ, J. Maximum ex'ploratory equivalence in trees. V: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems (FedCSIS 2015), Łódź, Poljska, str. 507–518, 2015.
MIHELIČ, J, FÜRST, L., ČIBEJ, U. Exploratory equivalence in graphs: definition and algorithms. V: Proceedings of the 2014 Federated Conference on Computer Science and Information Systems (FedCSIS 2014), Varšava, Poljska, str. 447–456, 2014.
MIHELIČ, J., ČIBEJ, U., FÜRST, L. A backtracking algorithmic toolbox for solving the subgraph isomorphism problem. V: Handbook of research on methodologies and applications of supercomputing, IGI Global, str. 208–246, 2021.

Celotna bibliografija je dostopna v sistemu Cobiss.