DESCRIPTION: The goal of Computer Science is to develop "intelligent systems" that are able to perform an automatized treatment of information. But some difficulties have arisen: problems for which there is no known solution and problems for which there is a solution but the solution is not efficient and therefore the solution is useless from a practical point of view (it needs too much time or too much space or memory).

As a consequence of those difficulties, two theoretical fields have been developped:

(1) Computability Theory: the aim is to study what is computable and what is not.

(2) Computational Complexity Theory: the aim is to study which computable functions are efficiently solvable and which are not. The complexity theory classifies solvable problems in tractable problems (those who admit an efficient solution) and intractable problems (those who do not admit efficient solutions). Besides, different degrees of tractability and intractability are also given in some cases.



In order to study the computability and the computational complexity of computational problems, different computational models have been defined: Turing machines, Lambda calculus, Recursion theory, First-order predicate calculus, etc.). In this subject, computability and complexity are studied by using the computational model based on Turing machines. This computational model is strongly associated with the study of formal languages (seen as sets of strings). The languages are classified by taking into account the properties required by the Turing machines in order to deal with such languages. Different restrictions put on Turing machines, produce different kinds of machines and each of them gives rise to a kind of language: regular languages, context-free languages, context-dependent languages and more can be identified.



Each computational model gives rise to a programming paradigm. For example, the model based on Turing machines gives rise to the imperative programming paradigm (ADA, Java, C, etc). The computational model based on the Lambda calculus gives rise to the functional programming paradigm (Haskell, etc.).



We will use the computational model based on Turing machines in order to present the theoretical results about computability and complexity. On the other hand, we will use the language Haskell to work on program dessign. In this way we will work on two computational models.



CONTEXTUALISATION: Before this subject (first semester of the second term) the students have taken some other subjects that deal with different issues related to program dessign. Once that the basic skills for dessigning programs that perform computational tasks have been adquired, it is the right moment to present the limits of computation. By means of this subject, the student becomes aware of the limits of the computation processes (computability in general and computational complexity and tractability in particular), and the student can go on perfectioning and deepening on program dessign for automatised information treatment, but now with a broader perspective.

COMPETENCIES WORKED ON THE SUBJECT:

- To identify and resolve problems that can be approached using restricted computational models (automata) or alternative computational models (intelligent systems).

- To use automata, grammars and regular expressions in order to define formal languages.

- To use pattern recognizing and processing software.

- To be aware of the existence of intrinsic limits in the computational processes and of their consequences.

- To know and to use different programming paradigms and alternative computation models.

- To use verbal, mathematical and graphic languages in order to work on and to analyze problems and their computational solutions.

BRIEF DESCRIPTION OF CONTENTS:

Automata, grammars, formal languages, computability, complexity, programming paradigms, intelligent systems.



CONTENTS:

- Computation without memory. Finite automata and transducers. Regular languages and regular expressions. Applications: lexical analysis.

- Restricted memory. Pushdown automata. Context-free languages and grammars. Linear bounded automata. Applications: syntactic analysis.

- General model of a computer and its limitations. Turing Machines. Computational universality and the Church-Turing thesis. Uncomputability. Introduction to computational complexity. Applications: cryptography with public key.

- Alternatives to the computational model. Machine models. Programming paradigms. Circuits and real machines. Imperative, functional and logic programming. Applications: automated reasoning.

- Alternatives to the problem model. Non-functional specifications. Decision trees. Classifiers. Probabilistic programming. Applications: systems that learn.

In the lectures, the theoretical contents will be presented together with relevant examples that illustrate the application of the theory to real problems. Students will have to deal with exercices to master the presented techniques.



ONLINE TEACHING (EXCEPTIONAL SITUATIONS)

If face-to-face (or in-person) classes are not possible, the teaching activities and continuous evaluation activities will be reorganised and adapted to distance (or online) teaching. In order to achieve that goal, available resources will be used (eGela etc.). Students will be properly informed by means of eGela.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Written test to be taken (%): 90
  • Realization of Practical Work (exercises, cases or problems) (%): 10

Two evaluation methods:

- Final evaluation: written examination about the whole subject at the end of the semester. Different exercices to work on the main contents of the subject. Only passed exercices will be taken into account to calculate the final punctuation.

- On-going (or continuous) evaluation: one written examination for each main content of the subject. The exams will be held along the semester. Passed exams will liberate the corresponding content and the punctuation will be summed to calculate the final punctuation. At the end of the semester, students that have not reached 5 points will have the opportunity to repeat the non-liberated exercices in order to try to reach to 5 points.



Changing from one evaluation method to the other: students can change from one evaluation methond to the other at any time before the day of the final examination (at the end of the semester).



Anyone that has not yet 5 points and does not take the final examination, will have a "not presented" as the final result.



CONTINUOUS EVALUATION (EXCEPTIONAL SITUATIONS)

If face-to-face (or in-person) continuous evaluation is not possible, the continuous evaluation will be reorganised and adapted to distance (or online) continuous evaluation. In order to achieve that goal, available resources will be used (eGela etc.). Students will be properly informed by means of eGela.



ONLINE EVALUATION (EXCEPTIONAL SITUATIONS)

If face-to-face (or in-person) evaluation is not possible, the evaluation will be realized online. In order to achieve that goal, available resources will be used (eGela etc.). Students will be properly informed by means of eGela.

Same approach as in ordinary evaluation.



ONLINE EVALUATION (EXCEPTIONAL SITUATIONS)

If face-to-face (or in-person) evaluation is not possible, the evaluation will be realized online. In order to achieve that goal, available resources will be used (eGela etc.). Students will be properly informed by means of eGela.

Material at eGela.

Basic bibliography

- J.E. Hopcroft, R. Motwani, J.D. Ullman: "Introduction to Automata Teory, Languages and Computation". Addison-Wesley, 2001

- J.E. Hopcroft, R. Motwani, J.D. Ullman: "Teoría de Autómatas, Lenguajes y Computación" 3rd ed. Pearson educación, 2007

- R. Brena; "Autómatas y Lenguajes. Un enfoque de diseño" Tec de Monterrey, 2003. [on line] Disponible en http://lizt.mty.itesm.mx/~rbrena/AyL.html

- S. Russell, P. Norvig: "Artificial Intelligence: A Modern Approach" 3rd ed. Prentice Hall, 2009

- Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero, José E. Gallardo: "Razonando con Haskell. Curso sobre Programación Funcional". Thomson - Paraninfo, 2004

- Simon Thompson: "Haskell. The Craft of Functional Programming" Third Edition. Adison-Wesley, 2011

- Richard Bird; traducción, Ricardo Peña Marí; revisión técnica, María Alpuente Frasnedo, Salvador Lucas Alba: "Introducción a la programación funcional con Haskell" 2ª ed. Prentice Hall, 2000





J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN: "Teoría de Autómatas, Lenguajes y Computación" 3ª ed. Pearson educación, 2007

R. BRENA; "Autómatas y Lenguajes. Un enfoque de diseño¿ Tec de Monterrey, 2003. [on line] Disponible en http://lizt.mty.itesm.mx/~rbrena/AyL.html

S. RUSSELL, P. NORVIG: "Artificial Intelligence: A Modern Approach" 2ª ed. Prentice Hall, 2003

In-depth bibliography

- E. Rich; "Automata, Computability and Complexity". Pearson Education, 2008
- S.H. Rodger, T.W. Finley; "JFLAP: An Interactive Formal Languages and Automata Package". Jones and Bartlett, 2006
- D. Wood; "Theory of computation". John Wiley & Sons, 1987.
- S. Arora, B. Barak: "Computational Complexity: A Modern Approach" Cambridge University, 2009.
- T. Mitchell: "Machine Learning" McGraw Hill, 1997
- G.F. Luger, W.A. Stubblefield: "Artificial Intelligence. Structures and Strategies for Complex Problem Solving." Benjamin/Cummings Publishing Company, Inc, 1998.

Journals

None.

Web addresses

- Java Computability Tool kit (JCT): http://humboldt.sunyit.edu/jct/
- Visual and interctive tools (JFLAP): http://www.jflap.org/
- Machine Learning theory and examples: http://www.cs.cmu.edu/~avrim/ML07/index.html
- Implementación de algoritmos de IA en Java: http://code.google.com/p/aima-java/
- Tutorial de Haskell en castellano: http://aprendehaskell.es
- Tutorial de Haskell en inglés: http://learnyouahaskell.com/chapters