Computer science | ELEMENTS OF COMPUTATION THEORY
Computer science ELEMENTS OF COMPUTATION THEORY
cod. 0512100018
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 | |
|---|---|---|---|---|
| INF/01 | 9 | 72 | LESSONS |
| 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. |
| More Information | |
|---|---|
| A DETAILED PROGRAM WITH FURTHER INFORMATION MAY BE FOUND AT HTTP://WWW.UNISA.IT/DIPARTIMENTI/DIP_INFORMATICA/DIDATTICA/DOCENTI/DEFELICE/INDEX |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2016-09-30]
