Turingin kone, laskennallisten ongelmien ratkeavuus sekä laskennan vaativuusteoria. Esitiedot: Ohjelmoinnin ja laskennan perusmallit, Tietorakenteet sekä matematiikan opintoja. Suositeltava kurssikirja: Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation (2nd ed.), Addison-Wesley, 2001.