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.

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.

Obavijesti (zimski semestar, akad. god. 2018/19)

  • Rezultati 1. kolokvija.
    Uvidi: petak, 30.11., u 12:15 (konzultacije, ured 227);   utorak, 4.12., u pauzi i iza nastave.
        Diskusija rješenja na nastavi 4.12.
  • Objavljene su domaće zadaće.
  • Termini svih kolokvija (razred B1):
        1. kolokvij: srijeda, 21.11.2018., u 9 sati,
        2. kolokvij: srijeda, 30.1.2019., u 9 sati,
        Popravni kolokvij: srijeda, 13.2.2019., 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.
  • R. Johnsonbaugh, M. Schaefer, Algorithms, Pearson Education International, Upper Saddle River, New Jersey, 2004.

Dodatna literatura


Zadnja promjena: 29.11.2018.