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.
Predmet učimo na programih
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.
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.