Opis predmeta
Vsebina predmeta:
-
Računska zahtevnost za algoritme tipa deli in vladaj.
-
Randomizirani algoritmi in verjetnostna analiza algoritmov.
-
Amortizirana analiza algoritmov.
-
Iskanje v večdimenzionalnih prostorih: k-d drevesa, R drevesa, lokalno občutljivo razprševanje.
-
Sortiranje s predpostavkami: s štetjem, korensko urejanje, sektorsko urejanje.
-
Iskanje s predpostavkami: drevesa van Emde Boats.
-
Razpršene tabele: funkcije razprševanja, univerzalno razprševanje, popolno razprševanje, Bloomovi filtri.
-
Hevristične metode reševanja problemov: lokalne metode.
-
Metahevristike pri optimizaciji.
-
Biološko navdahnjene metode: genetski algoritmi, diferencialna evolucija in metode roja.
-
Računska geometrija: lastnosti daljic, konveksna ovojnica, par najbližjih točk.
-
Večnitni in porazdeljeni algoritmi.
-
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.
Cilji in kompetence
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.
Metode poučevanja in učenja
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.
Predvideni študijski rezultati
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.
Reference nosilca
BRODNIK, Andrej, GRGUROVIČ, Marko, POŽAR, Rok. Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time. Ars mathematica contemporanea. 2022, vol. 22, no. 1, str. 1-22, ilustr. ISSN 1855-3966.
BRODNIK, Andrej, MALNIČ, Aleksander, POŽAR, Rok. A subquadratic algorithm for the simultaneous conjugacy problem. Journal of graph theory. 2022, str. 1-8. ISSN 1097-0118.
BRODNIK, Andrej, MALNIČ, Aleksander, POŽAR, Rok. The simultaneous conjugacy problem in the symmetric group. Mathematics of computation. Nov. 2021, vol. 90, no. 332, str. 2977-2995. ISSN 0025-5718.
BRODNIK, Andrej, JEKOVEC, Matevž. Sliding suffix tree. Algorithms. 2018, vol. 11, no. 8, str. 1-11. ISSN 1999-4893.
BRODNIK, Andrej, GRGUROVIČ, Marko. Parallelization of ant system for GPU under the PRAM model. Computing and informatics. 2018, vol. 37, no. 1, str. 229-243, graf. prikazi. ISSN 1335-9150.
Temeljni viri in literatura
-
T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009.
-
K.A.Berman, J.L. Paul: Algorithms: Sequential, Parallel, and Distributed. Thomson, 2005.
-
J. Kleinberg, E. Tardos: Algorithm Design. Pearson Education, 2006.