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

C1Z11: ANALIZA ALGORITAMA

Program predmeta

• (Intuitivni) pojam algoritma i njegov istorijat
• Reči, jezici, prirodni brojevi
• Formalizacija pojma algoritamskog problema, Čerčova teza

• 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

• 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, 2 i 3 odgovaraju delovima gradiva koji će biti predmet provere znanja na kolokvijumima.

Literatura

Udžbenik za ovaj predmet je:

• Igor Dolinka, Kratak uvod u analizu algoritama, Univerzitet u Novom Sadu, PMF, Novi Sad, 2008.

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]