Konstrukcija i analiza algoritama (R smer)

Asistent:
Način polaganja ispita:
Obavestenja za skolsku 2022/23:
Predavanja u skolskoj 2022/23:
  1. Uvod. Korektnost algoritma i veza sa induktivno/rekurzivnom konstrukcijom. Dokaz korektnosti rekurzivnih i iterativnih funkcija (pdf)
    Simulacija algoritma Trobojka izvrsavanjem korak po korak (aplet)
  2. Slozenost algoritama. Merenje vremena izvrsavanja. Asimptotska analiza slozenosti. Slozenost nekih cestih oblika petlji. Matematicke osnove. Rekurentne jednacine (pdf)
  3. Tehnike za poboljsanje slozenosti algoritama. Zamena iteracije formulom. Odsecanje. Inkrementalnost. Zbirovi prefiksa i razlike susednih elemenata niza (pdf)
  4. Sortiranje. Binarna pretraga. Tehnika dva pokazivaca (pdf)
  5. Induktivno-rekurzivna konstrukcija: zvezda, apsolutni pobenik na glasanju, broj rastucih segmenata. Ojacavanje induktivne hipoteze: faktori ravnoteze binarnog drveta, dijametar binarnog drveta (pdf)
  6. Strukture podataka - koriscenje: skup, multiskup, mapa, stek, red (pdf)
  7. Strukture podataka - implementacija (pdf)
  8. Grafovi: reprezentacija, pretraga u dubinu, pretraga u sirinu (pdf)
  9. Grafovi: topolosko sortiranje (pdf)
  10. Grafovi: najkraci putevi iz zadatog cvora, minimalno povezujuce drvo (pdf)
  11. Dekompozicija (pdf)
  12. Pretraga, gruba sila, backtracking (pdf)
  13. Dinamicko programiranje (pdf)
Literatura: