Universidad de Oviedo Oferta formativa Página oficial  
   Uniovi Directo   Alumnos   Profesores, PDI   P.A.S.   Oferta Formativa   
Español

Course information
Academic year: 2017/2018

Timetable (only in Spanish) Exams (only in Spanish)

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, Non-deterministic and with lamda-moves. 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. Push-Down Automata. 2.8. Properties of Context Free Languages.
3:COMPUTATION MODELS: 3.1. intuitive concept of algorithm. 3.2. While-Programs, URM., Turing Machines 3.3. while-computable Functions. 3.4. Church Thesis.
4: ENUMERATION OF THE ALGORITHMS: 4.1. Enumeration of the While-Programs.
4.2. Universality theorem. 4.3. s-m-n 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 NP-complete 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. Prentice-Hall, 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. Addison-Wesley, 2001.
4.- Kfoury, A. J., Moll, R. N., Arbib, M. A., A Programming Approach to Computability. Springer-Verlag, 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. Prentice-Hall, 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:
E-LSUD-4-MATH-407-CT
ECTS credits:
7.2
Theoretical:
4.8
Practical:
2.4
Teaching method:
Lectures
Course practicum
In-class assignments
Assessment system:
Written exam
Continuous assessment

©2002 Universidad de Oviedo