Konstrukcija i analiza algoritama (R smer)

Asistent:
Način polaganja ispita:
Da bi se polozio ispit potrebno je osvojiti bar 25 poena na prakticnom delu ispita, bar 20 poena na usmenom ispitu i u zbiru osvojiti barem 51 poen.
Obavestenja:
Predavanja:
  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: