Analiza algoritmov in hevristično reševanje

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.
Razreda P in NP: definicija, NP-polnost, standardni NP-polni problemi.
Prevedljivost in reševanje NP-polnih problemov.
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, umetni imunski sistemi.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009
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: mojstrova metoda in metoda Akra-Bazzi
verjetnostna analiza algoritmov,
uporaba amortizirane analize algoritmov,
prevedba nekaterih NP-polnih problemov,
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.

Znanje in razumevanje:
Poznavanje ozadja računalniške grafike in računalniških iger.
Uporaba:
Razvoj interaktivnih 3D vizualizacij in računalniških iger.
Refleksija:
Spoznavanje in razumevanje uglašenosti med teorijo in njeno aplikacijo na konkretnih primerih s področja računalniške grafike in iger.
Prenosljive spretnosti - niso vezane le na en
predmet:
Razvoj grafičnih vizualizacij na različnih strokovnih področjih.

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.

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

ROBNIK ŠIKONJA, Marko, KONONENKO, Igor. Theoretical and empirical analysis of ReliefF and RReliefF. Machine learning, ISSN 0885-6125. [Print ed.], 2003, vol. 53, str. 23-69, graf. prikazi. [COBISS-SI-ID 3813460]
ROBNIK ŠIKONJA, Marko, KONONENKO, Igor. Explaining classifications for individual instances. IEEE transactions on knowledge and data engineering, ISSN 1041-4347. [Print ed.], May 2008, vol. 20, no. 5, str. 589-600, ilustr. [COBISS-SI-ID 6528340]
PIČULIN, Matej, ROBNIK ŠIKONJA, Marko. Handling numeric attributes with ant colony based classifier for medical decision making. Expert systems with applications, ISSN 0957-4174. [Print ed.], Nov. 2014, vol. 41, no. 16, str. 7524-7535, graf. prikazi. [COBISS-SI-ID 10715732]
ROBNIK ŠIKONJA, Marko. Data generators for learning systems based on RBF networks. IEEE transactions on neural networks and learning systems, ISSN 2162-237X. [Print ed.], May 2016, vol. 27, no. 5, str. 926-938, ilustr. [COBISS-SI-ID 1536875203]
KRANJC, Janez, ORAČ, Roman, PODPEČAN, Vid, LAVRAČ, Nada, ROBNIK ŠIKONJA, Marko. ClowdFlows : online workflows for distributed big data mining. FGCS, ISSN 0167-739X. [Print ed.], 2017, vol. 68, str. 38-58. [COBISS-SI-ID 29851943]