Temari

1.- Conceptes

     1.1. Alfabets, mots i llenguatges

     1.2. Aparionament entre conjunts numerables

1.2.1. Numerabilitat

     1.4. Operacions sobre llenguatges

1.4.1. Operacions booleanes
1.4.2. Altres operacions
1.4.3. Morfismes

     2.1. Autòmats finits deterministes i indeterministes

2.1.1. Autòmats finits deterministes
2.1.2. Autòmats finits indeterministes
2.1.3. Determinització d'autòmats finits deterministes

     2.3. Operacions amb autòmats finits deterministes

2.3.1. Unió
2.3.2. Intersecció
2.3.3. Complementari
2.3.4. Concatenació
2.3.5. Estrella de kleene

     2.5. Llenguatges no regulars. Lema de bombament

3.- Llenguatges incontextuals

     3.1. Definicions

     3.2. Arbres de derivació

     3.3. Ambigüitat

     3.4. Simplificació de gramàtiques

3.4.1. Eliminació de produccions buides
3.4.2. Eliminació de produccions unàries
3.4.3. Eliminació de símbols inútils

3.5.1. Forma normal de Chomsky
3.5.2. Forma normal de Greibach

     3.7. Autòmats amb pila

3.7.1. Autòmats amb pila deterministes
3.7.2. Autòmats amb pila indeterministes

     4.1. La jerarquia de Chomsky

5.- Llenguatges recursivament enumerables

     5.1. Màquina de Turing

5.1.1. La màquina de Turing
5.1.2. Llenguatges recursivament enumerables
5.1.3. La màquina de Turing com a computadora de funcions

5.2.1. La màquina de Turing amb una cinta infinita en ambdós sentits
5.2.2. Màquines de Turing amb diverses cintes
5.2.3. Màquines de Turing no deterministes
5.2.4. Altres màquines de Turing

     5.4. Codificació. Godelització

     5.5. Funcions recursives i conjunts recursius

5.5.1. Caracterització i propietats
5.5.2. El problema de la parada
5.5.3. Reductibilitat

     6.1. Màquina de Turing universal

     6.2. Problemes indecidibles

6.2.1. El teorema de Rice

     6.4. Decidibilitat dels llenguatges incontextuals

7.- Introducció a la complexitat

     7.1. El problema de la complexitat

     7.2. Xarxes neuronals
 
 

Bibliografia general

E. Golobardes i Ribé, Teoria d'Autòmats, Publicacions d'Enginyeria i Arquitectura La Salle, 2000/2001 (nova edició)

E. Golobardes i Ribé, Col·lecció de problemes de Teoria d'Autòmats, Publicacions d'Enginyeria i Arquitectura La Salle

John E. Hopcroft; Jeffrey D. Ullman, Introduction to automata theory, languages, and
computation, Addison-Wesley Publishing Company, 1979.

John E. Hopcroft; Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y
computación, CECSA, 1993.

Harry R. Lewis; Christos H. Papadimitriou, Elements of the theory of computation, Prentice-Hall
Inc., 1981.

Michael A. Harrison, Introduction to formal language theory, Addison-Wesley Publishing
Company, 1978.

D. Wood, Theory of computation, Harper and Row, N.Y., 1987.

M.D. Davis; R. Sigal; E.J. Weyuker, Computability, Complexity, and Languages, Academic
Press, 1994.

J.G. Brookshear, Teoria de la computación, Addison-Wesley Iberoamericana, 1993.

J.C. Ferrando; V. Gregorio, Matematica Discreta, Editorial Reverte, S.A., 1994.
 
 

Distribució dels temes

•  1r trimestre: 1, 2
•  2n trimestre: 3, 4, 5
•  3r trimestre: 5, 6, 7