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.

Obavijesti (zimski semestar, akad. god. 2019/20)

• Semestar je gotov — datoteke s osobnim podacima više nisu dostupne.
• Završni rezultati (bodovi/ocjene).
• Rezultati popravnog kolokvija.
  Uvidi: petak, 14.2., u 12 sati (konzultacije, ured 227).
• Zadnji rok za predaju zadaća: petak, 14. veljače 2020., od 12 do 14 sati. Koga nema do 14 sati, zakasnio je!
• Rezultati 2. kolokvija.
  Uvidi, može predavanje zadaća nakon uvida:   petak, 7.2., u 12:15 (konzultacije, ured 227).
      Studenti s barem 45 bodova na kolokvijima ne moraju predati zadaću, ako su zadovoljni ocjenom iz trenutnih bodova.
      Studenti s 30–44 bodova na kolokvijima moraju predati zadaću za prolaznu ocjenu.
• Objavljene su seminarske teme.
• Rezultati 1. kolokvija.   Ispričavam se za kašnjenje.
  Uvidi: ponedjeljak, 2.12., od 12:15 do 14 sati (ured 227);   utorak, 3.12., u pauzi i iza nastave.
      Diskusija rješenja na nastavi 3.12.
• Domaće zadaće (prošireni popis).
• Termini svih kolokvija (razred B1):
      1. kolokvij: srijeda, 20.11.2019., u 9 sati,
      2. kolokvij: srijeda, 29.1.2020., u 9 sati,
      Popravni kolokvij: srijeda, 12.2.2020., u 9 sati.

Način polaganja

Službena pravila polaganja i ocjenivanja (ili ovdje). Dodatne informacije su na prvom predavanju.

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.