Algoritmi

Opis predmeta

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.

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

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.