Algoritmi

Osnovno znanje algoritmov in podatkovnih struktur.

Vsebina predmeta:
1. Računska zahtevnost za algoritme tipa deli in vladaj.
2. Randomizirani algoritmi in verjetnostna analiza algoritmov.
3. Amortizirana analiza algoritmov.
4. Iskanje v večdimenzionalnih prostorih: k-d drevesa, R drevesa, lokalno občutljivo razprševanje.
5. Sortiranje s predpostavkami: s štetjem, korensko urejanje, sektorsko urejanje.
6. Iskanje s predpostavkami: drevesa van Emde Boats.
7. Razpršene tabele: funkcije razprševanja, univerzalno razprševanje, popolno razprševanje, Bloomovi filtri.
8. Hevristične metode reševanja problemov: lokalne metode.
9. Metahevristike pri optimizaciji.
10. Biološko navdahnjene metode: genetski algoritmi, diferencialna evolucija in metode roja.
11. Računska geometrija: lastnosti daljic, konveksna ovojnica, par najbližjih točk.
12. Večnitni in porazdeljeni algoritmi.
13. Avtomati in gramatike.
Študenti, ki na prvi stopnji še niso osvojili osnovnih algoritmov in podatkovnih struktur, bodo pod mentorstvom izvajalcev v obliki seminarjev in domačih nalog sproti obdelali še manjkajoče predznanje.

1) T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009.
2) K.A.Berman, J.L. Paul: Algorithms: Sequential, Parallel, and Distributed. Thomson, 2005.
3) J. Kleinberg, E. Tardos: Algorithm Design. Pearson Education, 2006.

Cilj predmeta je nadgraditi znanje s področja načrtovanja in analize algoritmov in podatkovnih struktur. Študenti bodo dosegli nivo, ko znajo analizirati večino algoritmov in si razširili orodjarno znanih algoritmov in tehnik za njihov razvoj.
Splošne kompetence:

• sposobnost kritičnega razmišljanja,
• razvoj spretnosti kritičnega, analitičnega in sintetičnega razmišljanja,
• sposobnost razumevanja in reševanja profesionalnih izzivov,

• sposobnost nadgradnje pridobljenega znanja.
  Predmetno-specifične kompetence:

• poznavanje mojstrove metode in metode Akra-Bazzi za analizo algoritmov tipa deli in vladaj,

• randomizacija algoritmov
• verjetnostna analiza algoritmov,
• amortizirana analiza algoritmov,
• poznavanje razredov formalnih jezikov in zapis regularnih izrazov ter kontekstno neodvisnih gramatik,
• poznavanje vloge predpostavk pri razvoju učinkovitih algoritmov,
• učinkovito iskanje prostorskih podatkov,
• uporaba razpršenih tabel, sestava razprševalne funkcije,
• priprava optimizacijskega problema za reševanje z lokalnimi metodami,
• uporaba meta-hevristik v lokalnih metodah: spremenljive okolice, vodeno lokalno iskanje, tabu preiskovanje,
• priprava problema za reševanje z biološko navdahnjenimi metodami: genetskimi algoritmi, metodo rojev, diferencialno evolucijo in kolonijo mravelj,
• uporaba tehnik računske geometrije in poznavanje učinkovitih algoritmov za konveksno ovojnico,
• analiza večnitnih algoritmov, paralelna pohitritev,
• spreminjanje enonitnih v večnitne algoritme,
• poznavanje razvoja porazdeljenih algoritmov.

Po uspešnem zaključku tega predmeta bo študent:

• znal opredeliti razliko med težkim in lahkim problemom ter med dobrim in slabim algoritmom,
• razumel delovanje izbranih algoritmov in jih znal implementirati v izbranem programskem jeziku,
• sposoben izkazati algoritmični način razmišljanja in reševanja problemov,
• sposoben samostojno razviti nov algoritem za izbrane probleme,
• znal raziskati problem, določiti način reševanja in poiskati ali razviti algoritem,
• sposoben ovrednotiti kakovost algoritma za reševanje izbranega problema.

Predavanja, laboratorijske vaje in domače naloge, pomembno je sprotno oddajanje domačih nalog.
Študenti s šibkim obstoječim znanjem bodo manjkajoče znanje pridobili z dodatnimi individualnimi seminarskimi nalogami in programerskimi projekti.

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

Pet najpomembnejših del/ Five most important works:
KLOBOVES, Klemen, MIHELIČ, Jurij, BULIĆ, Patricio DOBRAVEC, Tomaž. FPGA-Based SIC/XE Processor and Supporting Toolchain. International Journal of Engineering Education, 2017, vol. 33, no. 6(A), pp. 1927–1939
MIHELIČ, Jurij, DOBRAVEC, Tomaž. SicSim: a simulator of the educational SIC/XE computer for a system-software course. Computer applications in engineering education, ISSN 1061-3773, 2015, vol. 23, no. 1, pp. 137-146
ČEŠNOVAR, Rok, RISOJEVIĆ, Vladimir, BABIĆ, Zdenka, DOBRAVEC, Tomaž, BULIĆ, Patricio. A GPU implementation of a structural-similarity-based aerial-image classification. The journal of supercomputing, ISSN 0920-8542, 2013, vol. 65, no. 2, pp. 978-996
BULIĆ, Patricio, DOBRAVEC, Tomaž. An approximate method for filtering out data dependencies with a sufficiently large distance between memory references. The journal of supercomputing, ISSN 0920-8542, 2011, vol. 56, no. 2, pp. 226-244
DOBRAVEC, Tomaž, ROBIČ, Borut. Restricted shortest paths in 2-circulant graphs. Comput. commun.. [Print ed.], March 2009, vol. 32, no. 4, str. 685-690
Celotna bibliografija je dostopna na SICRISu:
http://sicris.izum.si/search/rsr.aspx?lang=slv&,id=10416.