# Computer science | ELEMENTS OF COMPUTATION THEORY

## Computer science ELEMENTS OF COMPUTATION THEORY

 0512100018 DIPARTIMENTO DI INFORMATICA COMPUTER SCIENCE 2013/2014

 OBBLIGATORIO YEAR OF COURSE 3 YEAR OF DIDACTIC SYSTEM 2008 SECONDO SEMESTRE
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY INF/01 9 72 LESSONS COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

 CLELIA DE FELICE T
Objectives
KNOWLEDGE OF BASIC NOTIONS IN COMPUTATION THEORY (ABSTRACT COMPUTING DEVICES AND THEIR COMPUTATIONAL POWER, PROBLEMS THAT ARE SOLVABLE AND PROBLEMS THAT ARE UNSOLVABLE)). KNOWLEDGE OF BASIC NOTIONS IN COMPLEXITY THEORY (PROBLEMS COMPUTATIONALLY EASY AND PROBLEMS COMPUTATIONALLY HARD).
Prerequisites
KNOWLEDGE OF DISCRETE MATHEMATICS, LOGIC, AND ALGORITHMS.
Contents
COMPUTATIONAL MODELS: FINITE AUTOMATA, REGULAR LANGUAGES, TURING MACHINES. COMPUTABILITY THEORY: DECIDABLE AND UNDECIDABLE LANGUAGES, MAPPING REDUCIBILITY, RICE THEOREM. COMPLEXITY THEORY: THE CLASSES P AND NP, NP-COMPLETENESS, POLYNOMIAL TIME REDUCIBILITY. EXAMPLES OF NP-COMPLETE LANGUAGES.
Teaching Methods
CLASS LECTURES WITH SOME PRACTICE LESSONS
Verification of learning
WRITTEN TEST AND ORAL EXAMINATION
Texts
1.M. SIPSER, INTRODUCTION TO THE THEORY OF COMPUTATION, COURSE TECHNOLOGY, SECOND EDITION, 2005.
2. J. HOPCROFT, R. MOTWANI, J. ULLMAN , AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009.