Theory of Computation
Professor: Natasha Sharygina
Assistant: Simone Fulvio Rollini
Tipo di corso: Lecture
Valore in crediti ECTS: 6
Riferimenti bibliografici sul sito della biblioteca (CoRe)
Academic year 2012/2013 - Third year - Fall semester
Prerequisites: Automata and Formal Languages
Objectives
The class introduces the fundamental mathematical properties of computer hardware, software, and certain applications thereof. It explores what can and cannot be solved on a computer, how quickly, with how much memory,
and on which type of computational model. The class is divided into two major parts: computability theory and complexity theory. Computability theory deals primarily with the question of whether a problem is solvable at all on
a computer. Complexity theory considers how efficiently the problem can be solved. Two major aspects are considered: time complexity and space complexity, which respectively address a problem of how many steps does it take to perform a computation, and how much memory is required to perform that computation. The subjects have strong connections with engineering practice.
Practical exercises will involve experimentation with various tools.
Contents
The specific topics include, but are not limited to, the following:
Computability:
- Turing machines
- Decidability
- Undecidability
- Reducibility Complexity
- Complexity measures
- Time and space hierarchies
- P and NP
- NP-completeness
- Applications of intractability
Goals
After completing this course, students will have: Thorough understanding of several models of computation, their purpose, and their use in formal arguments. Exposure to fundamental results in complexity theory and building of
intuition regarding limitations of computing. Skills at manipulating formal systems as used in CS theory, particularly in developing and writing up proofs.
Prerequisite
The course assumes a previous course in CS theory covering at least finite state automata, and context-free grammars (a class on Automata and Formal Languages).
Teaching methodology and course structure
The class contains lectures and practical sessions. The grade will be a combination of exams, homework assignments, and a project.
References
Introduction to the Theory of Computation, by Michael Sipser, 2006, second edition (Required)