[Home]   [Program i literatura]   [Ispitni zadaci]

I152: ANALIZA ALGORITAMA

Program predmeta

0. Uvod

  • (Intuitivni) pojam algoritma i njegov istorijat
  • Reči, jezici, prirodni brojevi
  • Formalizacija pojma algoritamskog problema, Čerčova teza
1. Rekurzivne funcije i skupovi
  • Prosto rekurzivne funkcije, teoreme o zbiru i proizodu
  • Operator minimalizacije i teorema o majoraciji
  • Rekurzije višeg reda
  • Akermanova funkcija
  • Rekurzivni i rekurzivno naborjivi skupovi
2. Tjuringove mašine
  • Osnovni model TM
  • Mašine za izračunavanje funkcija u unarnom ("recka") sistemu
  • Vremenska i prostorna složenost TM
  • Višetračne TM
  • Univerzalna TM i neodlučivi problemi
  • RAM mašine
3. Osnovi teorije vremenske složenosti algoritama
  • Primeri polinomnih algoritama: Euklidov algoritam, množenje matrica, problem HORNSAT
  • Polinomni algoritmi na grafovima: pretraživanje grafa u širinu, Dajkstrin algoritam, minimalna razapinjuća stabla
  • Nedeterminističke TM i nedeterministička složenost
  • Klasa NP
  • Redukcije i kompletnost, NP-kompletnost
  • Primeri NP-kompletnih problema: SAT, klike u grafovima, varijante problema SAT, celobrojno programiranje

Celine 1 i 2 će biti predmet provere znanja na prvom, a celina 3 na drugom kolokvijumu.

Literatura

Udžbenik za ovaj predmet je:

Udžbenik se nalazi u prodaji u Skriptarnici PMF-a.

Koristan podsetnik predstavlja sledeći skeniran rukopis sa skicama Tjuringovih mašina koje se koriste za izračunavanje rekurzivnih funkcija u azbuci Σ={ | }:

tm-recka.pdf

Sledeća zbirka može poslužiti za uvežbavanje jednostavnijih zadataka iz oblasti rekurzivnih funkcija i Tjuringovih mašina:

  • R.Tošić, S.Crvenković, Zbirka zadataka iz teorije algoritama, Institut za matematiku, Novi Sad, 1980.

Od strane literature, zainteresovanim studentima naročito preporučujem naslove:

  • M.Sipser, Introduction to the Theory of Computation, PWS, Boston, 1997.

  • Ch.Papadimitriou, Computational Complexity, Addison-Wesley, Reading, 1994.

  • D.C.Kozen, The Design and Analysis of Algorithms, Springer-Verlag, New York, 1992.

[Home]   [Program i literatura]   [Ispitni zadaci]