
Course information

Academic year: 2017/2018

Local code:

936 
Course:

COMPUTABILITY THEORY 
Syllabus:


Centre:


Course type:

Elective

Total credits:

9 
Theoretical:

6 
Practical:

3 
Cycle:

2nd 
Year:


Terms:

ANNUAL 
Lecturers:


Goals:

1.  To dominate the classes of formal languages: scope, relations and their respective generating devices. 2.  To understand the algorithm concept and to know techniques to try to find out what is and what is not computable. 3.  To understand the underlying philosophy in the concept of Computation Model, as well as in the Thesis of Church; and the equivalence between the different models. 4.  To know how to use of suitable form the results of Universality, Parameterization and Recursion. 5.  To understand the importance of the Algorithmic Complexity in the tasks of theoretical verification of efficiency and comparison of algorithms.
Transversal capacities 1. Oral expresion 2. Analysis and synthesis 3. Resolution of problems 4. Intuition

Content:

1: AUTOMATA And LANGUAGES: 1.1. Introduction. 1.2. Deterministic, Nondeterministic and with lamdamoves. 1.3. Regular Expressions. 1.4. Minimization of Finite Automata. 1.5. Properties of Regular Languages. 1.6. Applications of Automata. 2: GRAMMARS And CONTEXT FREE LANGUAGES: 2.1. Introduction. 2.2. Definition of Grammar and Context Free Language. 2.3. Derivation Trees. 2.4. Ambiguity. 2.5. Regular Grammars. 2.6. Normal forms of Chomsky and Greibach. 2.7. PushDown Automata. 2.8. Properties of Context Free Languages. 3:COMPUTATION MODELS: 3.1. intuitive concept of algorithm. 3.2. WhilePrograms, URM., Turing Machines 3.3. whilecomputable Functions. 3.4. Church Thesis. 4: ENUMERATION OF THE ALGORITHMS: 4.1. Enumeration of the WhilePrograms. 4.2. Universality theorem. 4.3. smn theorem. 4.4. Recursion theorem. 5: ALGORITHMIC SOLVABILITY AND UNSOLVABILITY 5.1. Solvable and unsolvable problems. 5.2. Method of Diagonalization: Totality problem. 5.3. Reductions. 5.4. Rice theorem: problems of the Totality and Equivalence. 5.5 Recursive and Recursively enumerable sets. 6: ALGORITHMIC COMPLEXITY: 6.1. Complexity and complexity measures 6.2. Complexity classes: P and NP. 6.3. Complete problems 6.4. Some NPcomplete problems.

Bibliography:

1. Brookshear, J. G., Teoría de la Computación. Addison Wesley Iberoamericana, 1993. 2. Dean, K., Automata and Formal Languages. An Introduction. Ed. PrenticeHall, 1995 3.Hopcroft, J.E.; Motwanni, R.; Ullman, J.D., Introducción a la Teoría de Autómatas, Lenguajes y Computación. Segunda edición, Ed. AddisonWesley, 2001. 4. Kfoury, A. J., Moll, R. N., Arbib, M. A., A Programming Approach to Computability. SpringerVerlag, 1982. 5. Kozen, D. C., Automata and Computability. Ed. Springer, 1997. 6. Martin, J. C., Introduction to Languajes and the Theory of Computation. Ed. McGraw Hill 1991. 7. McNaughton, R., Elementary Computability, Formal Languages, and Automata. PrenticeHall, 1982. 8. Moret, B. M., The Theory of Computation. Ed. Addison Wesley, 1998. 9. Sudkamp, T. A., Languajes and Machines. Ed. Addison Wesley 1997 (second edition).

Metodology and Assessment system:

The evaluation will be made by means of two partial examinations with a weight of 50% each one, and final examinations corresponding to June September and February. Occasionally, the evaluation could be made by means of other type of tests like the accomplishment and later exhibition of works.

ECTS information 
ECTS code:

ELSUD4MATH407CT

ECTS credits:

7.2 
Theoretical:

4.8 
Practical:

2.4 
Teaching method:

Lectures Course practicum Inclass assignments 
Assessment system:

Written exam Continuous assessment 

