Kolegij je obavezan za studente prve godine diplomskog sveučilišnog studija Računarstvo i matematika. Nastava se održava u zimskom semestru, a sastoji se od tri sata predavanja svakog tjedna.

Skraćeni naziv kolegija je OAA (koristi se na ostalim stranicama).

Napomena: Za pristup datotekama koje sadrže osobne podatke studenata (rezultati kolokvija, rasporedi za kolokvij, zadaće), potrebna je autorizacija AAI@EduHr korisničkim imenom i lozinkom. Takve datoteke dostupne su samo do kraja semestra u kojem ide nastava iz kolegija.

Način polaganja

Službena pravila polaganja i ocjenivanja (str. 110).

Sadržaj kolegija

• Uvod u složenost. Pojam složenosti algoritma (vremenska, prostorna, paralelna). Asimptotsko ponašanje funkcija. Red veličine. Zapis složenosti algoritma. Složenost iterativnih algoritama i brojanje operacija. Ocjena sume integralom. Praktično mjerenje vremenske složenosti na jednostavnim algoritmima (sume alternirajućeg reda, zbrajanje i množenje matrica). Interpretacija rezultata i poboljšanje algoritama (ubrzanje konvergencije, blokovski algoritmi).
• Rekurzivni algoritmi. Rekurzivne jednadžbe. Rekurzivni algoritmi tipa ''smanji, pa vladaj'' i njihova složenost (Hanojski tornjevi). Rekurzivni algoritmi tipa ''podijeli, pa vladaj'' i njihova složenost (binarno traženje, Mergesort). Proširenje uvjetne složenosti na bezuvjetnu. Brzo množenje matrica (Strassenov algoritam i poboljšanja), brzo množenje velikih brojeva (Karatsubin algoritam, generalizacije). Binarno potenciranje, brzo računanje n-tog člana rekurzije, Fibonaccijevi brojevi.
• Sortiranje. Jednostavni postupci za sortiranje uspoređivanjem. Složeniji algoritmi: Quicksort, Heapsort, Mergesort i njihove efikasne implementacije. Praktična analiza složenosti opisanih algoritama. Donja ograda za složenost sortiranja uspoređivanjem. Prosječna složenost Quicksort-a.
• Oblikovanje efikasnih algoritama. Kratki pregled metoda za oblikovanje algoritama. Pohlepni algoritmi, problemi najkraćih puteva, razapinjućih stabala i komponenti povezanosti. Efikasna realizacija putem strukture disjunktnih skupova i složenost raznih implementacija ove strukture. Stabilno sparivanje, Gale-Shapley algoritam i primjene.
• Brza Fourierova transformacija (FFT). Definicija diskretne Fourierove transformacije i inverzne transformacije (interpolacija i izvrednjavanje u n-tim korijenima iz jedinice). Brza implementacija kad je n potencija od 2, sekvencijalna i paralelna složenost FFT-a. Primjena na brzo množenje polinoma.
• Studentski seminari. Pregled ostalih metoda za oblikovanje algoritama i algoritama za pojedine probleme (dinamičko programiranje, pretraživanje teksta i sl.).

Literatura

• S. Singer, Nastavni materijali, PMF–Matematički odsjek, Zagreb, od 1991. do danas.
• J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, Inc., Boston, Massachusetts, 2006.
• M. T. Goodrich, R. Tamassia, Algorithm Design and Applications, Wiley, 2015.
• R. Johnsonbaugh, M. Schaefer, Algorithms, Pearson Education International, Upper Saddle River, New Jersey, 2004.

Dodatna literatura

• G. Brassard, P. Bratley, Algorithmics, Prentice–Hall International, Englewood Cliffs, New Jersey, 1988.
• H. S. Wilf, Algorithms and Complexity, Internet Edition, Summer, 1994.
• D. M. Mount, Design and Analysis of Computer Algorithms, CMSC 451, University of Maryland, 2015.