Analiza algoritmov in hevristično reševanje problemov

Poznavanje osnovnih algoritmov in podatkovnih struktur.

Vsebina predmeta:

Analiza rekurzivnih algoritmov: substitucijska metoda, rešitev za algoritme deli in vladaj, metoda Akra-Bazzi.

Verjetnostna analiza: definicija, analiza stohastičnih algoritmov.

Randomizacija algoritmov.

Amortizirana analiza kompleksnosti algoritmov.

Reševanje linearnih rekurzivnih enačb.

Analiza večnitnih in vzporednih algoritmov.

Aproksimacijski algoritmi.

Kombinatorična optimizacija, lokalno preiskovanje, simulirano ohlajanje.

Linearno programiranje za reševanje problemov.

Metahevristike in stohastično preiskovanje: vodeno lokalno preiskovanje, preiskovanje s spremenljivo soseščino, tabu preiskovanje.

Populacijske metode: genetski algoritmi, optimizacija z rojem delcev, diferencialna evolucija.

Strojno učenje v kombinatorični optimizaciji.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 4th edition. MIT Press, 2022

R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms. Addison-Wesley, 1995

M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, 2nd Edition. Springer, 2010.

Dodatna literatura je na razpolago v obliki znanstvenih člankov.

Additional literature is available in the form of scientific papers.

Cilj predmeta je študente seznaniti z analizo algoritmov, računsko zahtevnostjo in učinkovitim reševanjem zahtevnih problemov, ki potrebujejo posebne pristope in optimizacijske tehnike.

Splošne kompetence:

sposobnost kritičnega razmišljanja,

sposobnost definiranja, razumevanja in reševanja ustvarjalnih profesionalnih izzivov,

sposobnost prenosa znanja in pisne komunikacije v domačem in tujem jeziku.

Predmetno-specifične kompetence:

uporaba metod za analizo rekurzivnih algoritmov: substitucijska metoda, drevesna metoda.

metode za analizo algoritmov deli in vladaj: mojstrska metoda in metoda Akra-Bazzi

verjetnostna analiza algoritmov,

uporaba amortizirane analize algoritmov,

poznavanje ideje aproksimacijskih tehnik,

poznavanje hevrističnih pristopov in meta-hevristik za reševanje težkih problemov,

uporaba populacijskih optimizacijskih metod in principov evolucijskega računanja

Po koncu predmeta bodo študente znali analizirati algoritme in njihovo računsko zahtevnost. Sposobni bodo ovrednotiti delovanje hevrističnih metod za reševanje zahtevnih problemov in bodo takšno analizo izvedli na realnem problemu. Konkretno bodo
uporabljali splošne metode za analizo rekurzivnih algoritmov:

substitucijsko metodo in drevesno metodo,
uporabljali metode za analizo algoritmov deli in vladaj: mojstrsko metodo in metodo Akra-Bazzi

verjetnostno analizirali programe

uporabljali amortizirano analizo algoritmov,

poznali ideje aproksimacijskih tehnik,

uporabljali, razlikovali in vrednotili hevristične pristope in meta-hevristik za reševanje težkih problemov,

uporabljali in primerjali populacijske optimizacijske metode in principe evolucijskega računanja.

Predavanja, naloge s pisnimi poročili in z ustnimi nastopi in predstavitvami, seminarski način dela in domače naloge, ki stimulirajo sproten študij. Študenti bodo v manjših skupinah samostojno reševali in analizirali zahtevne optimizacijske probleme. Skupine bodo svoje naloge, analize in rešitve opisale v pisnem poročilu in predstavile ostalim v obliki kratke predstavitve, ki se ocenjuje skupaj s poročilom.

Način: pisni in ustni izpit, domače naloge, predstavitev projekta, projekt.

Sprotno preverjanje: domače naloge, projektno delo.
Končno preverjanje: pisni in ustni izpit.
Ocene: 6-10 pozitivno, 5 negativno
(v skladu s Statutom UL).

1. VREŠ, Domen, ROBNIK ŠIKONJA, Marko. Preventing deception with explanation methods using focused sampling. Data mining and knowledge discovery. 2023, vol. , no. , str. 1-46
2. MIOK, Kristian, ŠKRLJ, Blaž, ZAHARIE, Daniela, ROBNIK ŠIKONJA, Marko. To BAN or not to BAN: Bayesian attention networks for reliable hate speech detection. Cognitive computation.  Jan. 2022, vol. 14, iss. 1, str. 353-371
3. LAVRAČ, Nada, ŠKRLJ, Blaž, ROBNIK ŠIKONJA, Marko. Propositionalization and embeddings: two sides of the same coin. Machine learning. 2020, vol. 109, no. 7, str. 1465-1507.
4. KRANJC Janez, ORAČ, Roman, PODPEČAN, Vid, LAVRAČ, Nada, ROBNIK ŠIKONJA, Marko. ClowdFlows: online workflows for distributed big data mining. FGCS, 2017, vol. 68, pp. 38-58
5. ROBNIK ŠIKONJA, Marko. Data generators for learning systems based on RBF networks. IEEE transactions on neural networks and learning systems. May 2016, vol. 27, no. 5, str. 926-938

Celotna bibliografija je dostopna na SICRISu https://cris.cobiss.net/ecris/si/sl/researcher/8741

Complete bibliography is available in SICRIS: https://cris.cobiss.net/ecris/si/en/researcher/8741