Získať prehľad o základných pojmoch a výsledkoch vo výpočtovej zložitosti a teórii vypočítateľnosti.

RAM a jeho varianty, registrové a Turingove stroje, rekurzívne funkcie, výpočty a ekvivalencia vypočítateľnosti na jednotlivých modeloch. Churchova téza, existencia nerozhodnuteľných problémov. Základné zložitostné triedy a vzťahy medzi nimi, existencia ťažkých problémov. NP-úplnosť, Cookova veta a niektoré ďalšie (aj pre prax dôležité) NP-úplné problémy, vzťah rozhodovacích a optimalizačných problémov. Dôležité polynomiálne riešiteľné problémy. Vzťah P a NP, rôzne prístupy k vymedzeniu efektívnej riešiteľnosti(aproximačné a pravdepodobnostné algoritmy). PSPACE-úplné problémy.

Cormen T.H., Leiserson C.E., Rivest R.L.: Introduction to Algorithms, MIT Press, 1990.
Aho A.V., Hopcroft J.E., Ullman J.D.: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1976.
Brassard G., Bratley P.: Fundamentals of Algorithmics, Prentice-Hall, 1996.
Korec: Úvod do teórie algoritmov, skriptá MFF UK, Bratislava, 1981.
Ch.H.Papadimitriou: Computational Complexity, Addison-Wesley Publishing Company, 1994.