Formalne metode izračunljivosti

Nastavni program:

• Skupovi, relacije, jezici; Konačna reprezentacija jezika;
• Konačni automati; Regularni izrazi; Algoritamski aspekti konačnih automata;
• Konteksno slobodne (context-free) gramatike; Pushdown automati;
• Definicija Turing-ove mašine; računanje sa Turing-ovom mašinom; Turing-ova mašina sa direktnim pristupom, Nedeterministička Turing-ova mašina;
• Church-Turingov princip;
• Problem zaustavljanja; Nerješivi problemi Turing-ovom mašinom;
• Rekurzivni jezici;
• Problemi iz klase P; Primjeri problema iz klase P;
• Problemi iz klase NP; Problem Boolean satisfiability; Cook-ov teorem:
• Polinomijalna redukcija problema; Primjeri redukcije;
• NPC (NP-complete) problemi; Primjeri NPC problema;
• Rješavanje NPC; Analiza podproblema; Aproksimacije; Kvalitet aproksimacija;
• Garancija kvalitete; garancija kvalitete u praksi;
• Metaheuristike; Taboo; Simulated anealing; Primjeri strategija za NPC probleme;

Literatura:

• Hary Lewis, Christos Papadimitriou: Elements of the Theory of Computation
• Michael Garey, David Johnson: Computers and Intractability, A Guide to the Theory of NP-Completness
• Thomas Corman, Charles Leirserson, Ronald Rivest: Introduction to Algorithms
• Robert Sedgewick: Algorithms in C/C++, Addison-Wesley, 1999.
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network algorithms, Prentice-Hall, New Jersey, 1993.
• D. Gustfield: Algorithms on Strings, Trees, & Sequences, Cambridge University Press, 1997.