Computer Science

General goals: The course introduces the students to some of the most important results in theoretical computer science: from the fundamental results in computability theory of the thirties, through the ones in automata theory of the fifties to the challenging open problem P versus NP, raised in the seventies. Specific goals: Students will understand that there are different models of computation and the reason for their different computational power. The students will become familiar with abstract concepts such as language classes, universal machines, reducibility and they will know that some problems are impossible to solve by computers and that others are difficult to solve, even so difficult to solve that they could be considered unsolvable. They will see today's use of some of these results. Knowledge and understanding: By the end of the course the students will get familiar with the basic methods and results of the Theory of Computability and Complexity and they will be able to apply them to evaluate the complexity of problems from various fields. In particular, they will be able to: prove the equivalence between different characterizations of regular languages prove the equivalence between different characterizations of context-free languages explain the concept of nondeterminism explain the existence of problems without algorithmic solutions or those which are intractable Applying knowledge and understanding: By the end of the course the students will be able to: build finite state automata by a formal or an informal specification of a language build stack automata by a formal or an informal specification of a language use reducibility between problems to prove either decidability or undecidability use polynomial reductions to prove the NP-hardness of problems. Critical and judgmental skills: Understand the right level of abstraction to solve problems, choose the more convenient computational model in an applicative context. Communication skills: describe problems that are undecidable, not provably intractable or intractable explain the meaning and the relevance of the question “P=NP?" Learning ability: The student will be able to learn other computational models, both really new or variations of the ones seen during the course. She/he will be able to understand new NP-completeness proofs or more generally completeness proofs for any complexity class.