topleft topright
topleft

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.

Obavijesti

  • Rezultati popravnog kolokvija (akad. god. 2016/17).
    Uvidi i upis ocjena: petak, 17.2., u 12 sati (konzultacije, ured 227);   ponedjeljak, 20.2., u 11:30 (ured 227).
  • Rezultati 2. kolokvija (akad. god. 2016/17).
    Uvidi i upis ocjena: ponedjeljak, 6.2., u 12 sati (ured 227);   srijeda, 8.2., od 11:45 do 12:15 (ured 227);   petak, 10.2., u 12:15 (konzultacije, ured 227).
    Predaja zadaća: ponedjeljak, 6.2., iza uvida;   petak, 10.2., u 12:15 (konzultacije);   utorak, 14.2., od 12 do 14 sati (zadnji termin).
  • Rezultati 1. kolokvija (akad. god. 2016/17).
    Uvidi: ponedjeljak, 28.11., u 12 sati (ured 227);   petak, 2.12., u 12:15 (konzultacije, ured 227);   utorak, 6.12., u pauzi i iza nastave.
        Diskusija rješenja na nastavi 6.12.
  • Konačno je oživila i službena web-stranica kolegija :-)
    Za ostale stvari pogledajte ovdje.

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.
  • R. Johnsonbaugh, M. Schaefer, Algorithms, Pearson Education International, Upper Saddle River, New Jersey, 2004.

Dodatna literatura


Zadnja promjena: 16.02.2017.