Algoritmi

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.

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.

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.