Sadržaj predavanja

• Uvod
  Pojam algoritma. Pregled standardnih metoda izgradnje algoritama. Ocjene složenosti algoritama.
• Teorija automata
  Konačni automat i regularni izrazi. Potisni automati i kontekstno slobodne gramatike. Turingovi strojevi
• Aproksimacijski algoritmi
  Heuristike (genetički algoritmi, sumulated anealling), aproksimacijske sheme. Primjeri aproksimacijksih algoritama (TSP, k-rez, problem ranca)
• Teorija složenosti algoritama
  Turingov stroj. Izračunljivost. Klase kompleksnosti: P i NP. NP-potpuni problemi. NP i coNP. Klasifikacija unutar klase P. Algoritmi iznad NP.
• Heuristike
  Genetski algoritmi. Algoritmi temeljeni na metodi simuliranog hlađenja.
• Randomizirani algoritmi
  Metode izgradnje randomiziranih algoritama (temeljene na teoriji igara, vjerojatnosna metoda, algebarske tehnike), Randomizirane strukture podataka, randomizirano linearno programiranje, randomizirani algoritmi na grafovima.
• Paralelni algoritmi
  Principi izgradnje paralelnih algoritama. Paralelizam temeljen na prosljeđivanju poruka. Paralelizam temeljen na dijeljenju memorije. Primjeri paralelnih algoritama (matrični algoritmi, sortiranje, algoritmi na grafovima, dinamičko programiranje)

Osnovna literatura

• S. Dagupta, C. Papadimitriu, U. Vazirani: Algorithms, Mc Graw-Hill ,2008
• M. Mozgovoy: Algorithms, Languages, Automata, and Compilers, Jones and Bartlett, 2010.
• C.H. Papadimitriou: Computational Complexity, Addison-Welsey, 1994.
• V.V. Vazirani: Approximation Algorithms, Springer-Verlag, 2003.
• R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge Universitay Press, 1995.
• A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to Parallel Computing, 2nd ed., Addison-Wesley, 2003.
• L. Fortnow: The Golden Ticket, P, NP, and the Search for the Impossible, Princenton University, 2013

Dopunska literatura

• R.M. Garey, D.S. Johnson: Computers and Intractability: A Guoide to the Theory of NP-Completeness, Freemanand, Co., 1979.
• R. Sedgewick: Algorithms in C++, parts 1-4. Addison-Wesley, 1998.
• R. Sedgewick: Algorithms in C++, part 5. Addison-Wesley, 2002.
• A. Aho, J. Hopcroft, J.D. Ullman: Data Structures and Algorithms, Addison-Wesley, 1987
• Atallah, M.J. ed.: Algorithms and Theory of Complexity Handbook, CRC Press, 1999.
• D.E. Knuth: The Art of Computer Programming: Fundamental Algorithms, Addison-Wesley, 1968.
• D.E. Knuth: The Art of Computer Programming: Seminumerical Algorithms, Addison-Wesley, 1969.
• D.E. Knuth: The Art of Computer Programming:Searching and Sorting, Addison-Wesley, 1973.
• E. Horowitz, S. Sahni: Fundamental of Computer Algorithms, Computer Science Press, 1978.
• D.E. Knuth: Selected Papers on Analysis of Algorithms, CSLI, 2000.
• J. van Leeuwen (ed.): Handbook of Theoretical computer Science, Volume A: Algorithms and Complexity, MIT Press, 1990
• J. van Leeuwen (ed.): Handbook of Theoretical computer Science, Volume B: Formal Models and Semnatics, MIT Press, 1990
• L.A. Hemaspaandra, M. Ogihara: The Complexity Theory Companion, Springer-Verlag, 2002.

Slični predmeti

• RWTH Aachen, http://www-mgi.informatik.rwth-aachen.de/Teaching/KT-WS01/
• Universität Trier, http://eccc.uni-trier.de/eccc-local/ECCC-LectureNotes/IntroComplTh/cc-pre.html
• Princeton University, http://www.cs.princeton.edu/courses/archive/spring03/cs423/
• Berkeley, http://www.cs.berkeley.edu/~luca/cs278/
• M.I.T., http://theory.lcs.mit.edu/~madhu/ST02/
• London School of Economics and Political Science, http://www.maths.lse.ac.uk/Courses/ma314.html
• San Diego State University, http://www.eli.sdsu.edu/courses/spring95/cs662/