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 (zimski semestar, akad. god. 2017/18)

  • Rezultati popravnog kolokvija (akad. god. 2017/18).
    Uvidi i upis ocjena: petak, 16.2., u 12 sati (konzultacije, ured 227);   ponedjeljak, 19.2., u 11:30 (ured 227).
  • Trenutni rezultati (bodovi/ocjene) (K1, K2/seminari, popravni, zadaće). Ako uočite neku grešku, javite mi odmah.
        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.
  • Raspored studenata po predavaonicama za popravni kolokvij, u srijedu, 14.2.2018., u 9 sati.
  • Rezultati 2. kolokvija (akad. god. 2017/18).
    Uvidi, upis ocjena, može predavanje zadaća nakon uvida: ponedjeljak, 5.2., u 12 sati (ured 227);   petak, 9.2., u 12:15 (konzultacije, ured 227).
  • Raspored studenata po predavaonicama za 2. kolokvij, u srijedu, 31.1.2018., u 9 sati.
  • Objavljene su seminarske teme.
  • Rezultati 1. kolokvija (akad. god. 2017/18).
    Uvidi: ponedjeljak, 27.11., u 12 sati (ured 227);   petak, 1.12., u 12:15 (konzultacije, ured 227);   utorak, 5.12., u pauzi i iza nastave.
        Diskusija rješenja na nastavi 5.12.
  • Raspored studenata po predavaonicama za 1. kolokvij, u srijedu, 22.11.2017., u 9 sati.
  • Objavljene su domaće zadaće.
  • Termini svih kolokvija (razred B1):
        1. kolokvij: srijeda, 22.11.2017., u 9 sati,
        2. kolokvij: srijeda, 31.1.2018., u 9 sati,
        Popravni kolokvij: srijeda, 14.2.2018., u 9 sati.
  • Konačno je osvježena 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: 15.02.2018.