http://www.inf.unibz.it/~calvanese/teaching/17-18-tc/

Free University of Bozen-Bolzano
Faculty of Computer Science
Master of Science in Computer Science
European Master in Computational Logic

Home page of the course
Theory of Computing

A.Y. 2017/2018

Prof. Diego Calvanese


News


Course description

Objectives. The objective of the Theory of Computing course is to introduce and study abstract, mathematical models of computation (such as Turing machines, formal grammars, recursive functions), and to use the abstract computation models to study the ability to solve computational problems, by identifying both the intrinsic limitations of computing devices, and the practical limitations due to limited availability of resources (time and space). A second objective is to show how to reason and prove properties about computations in a precise, formal, abstract way.

Prerequisites. There are no prerequisites in terms of courses to attend. Students should be familiar with notions of mathematics and set theory, and with basic proof techniques, as taught in the mathematics courses of a bachelor in computer science.

Teaching material
[M1] Introduction to Automata Theory, Languages, and Computation (3rd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.
[M2] Lecture Notes for Theory of Computing. Diego Calvanese. 2013. Available as scanned pages in pdf.
[M3] Languages and Machines (3rd edition). Thomas A. Sudkamp. Addison Wesley, 2005. Only Chapter 13.
[M4] The Convenience of Tilings. Peter van Emde Boas. In Complexity, Logic, and Recursion Theory, volume 187 of Lecture Notes in Pure and Applied Mathematics, pages 331-363, 1997.
[M5] Exercises on Theory of Computing. Available as scanned pages in pdf.
Additional reading material Further interesting and fun material


Back to teaching page of Diego Calvanese
Last modified: Wednesday, 11-Oct-2017 19:00:40 CEST