Asignatura:

Modelos Discretos

 

Unidad 1:

LÓGICA PROPOSICIONAL
Lógica proposicional. Proposiciones simples y compuestas. Valor de verdad. Conectivos. Siste-mas adecuados de conectivos. Leyes lógicas. Razonamientos. Inferencia. Métodos para deter-minar validez. Noción de sistema axiomático.

Unidad 2:

LÓGICA DE PREDICADOS DE PRIMER ORDEN
Cuantificadores. Predicados. Dominio de referencia. Variables libres y ligadas. Alcance de los cuantificadores. Razonamientos.

Unidad 3:

ÁLGEBRAS DE BOOLE
Álgebras de Boole. Circuitos de compuertas. Simplificación de funciones booleanas. Método de Karnaugh.

Unidad 4:

OTRAS LÓGICAS
Lógica modal. Lógica temporal. Lógicas plurivalentes. Distintas lógicas trivalentes: comparacio-nes. Lógica difusa. Lógicas no monotónicas.

Unidad 5:

TEORÍA DE GRAFOS
Grafos. Definiciones relativas a grafos orientados y no orientados. Representaciones compu-tacionales. Matrices de incidencia, adyacencia y latina. Aplicaciones. Problemas de accesibilidad, detección de circuitos. Conexión. Cadenas y ciclos de Euler y de Hamilton. Caminos mínimos en un grafo. Algoritmos BFS, de Dijkstra y de Ford.
Árboles y arborescencias. Representaciones de árboles binarios y no binarios. Árboles genera-dores mínimos. Algoritmos de Prim y Kruskal.
Coloreo de grafos y mapas. Teorema de los cuatro colores.

Unidad 6:

LENGUAJES REGULARES
Lenguajes. Alfabetos. Palabras. Operaciones entre sartas y entre conjuntos de sartas. Jerarquía de Chomsky. Autómatas finitos con salida y sin salida. Concepto de determinismo. Autómatas determinísticos y no determinísticos. Autómatas mínimos equivalentes. Lenguajes regulares. Expresiones regulares. Autómatas finitos como aceptores. Gramáticas regulares.

Unidad 7:

LENGUAJES LIBRES DE CONTEXTO
Lenguajes libres de contexto. Autómatas de pila. Gramáticas libres de contexto. Derivación. Am-bigüedad. Lenguajes inherentemente ambiguos.

Unidad 8:

LENGUAJES GENERALES
Lenguajes sensibles al contexto. Lenguajes generales. Máquinas de Turing. Máquinas de Turing Universales.

Unidad 9:

COMPUTABILIDAD Y COMPLEJIDAD ALGORÍTMICA
Concepto de computabilidad. Tesis de Church. Funciones computables.
Nociones de complejidad algorítmica. Complejidad de un problema. Funciones computables en tiempo real. Problemas P, NP y NP-completos. Aplicaciones.

Bibliografía

Alfonseca, M.; Sancho, J.; Martínez Orga, M. (1990). Teoría de Lenguajes, Gramáticas y Autó-matas. Madrid: Ed. Universidad y Cultura.
Brookshear, J. (1989). Teoría de la Computación. California: Addison-Wesley Iberoamericana.
Cuena, J. (1985). Lógica informática. Madrid, Ed. Alianza.
Christophides, N. (1975). Graph Theory. Londres, Academic Press.
Davis, M. D.; Weyuker, E. J. (1983). Computability, Complexity and Languages. Londres, Aca-demic Press.
Even, S. (1980). Graph Algorithms. EEUU, Computer Science Press.
Fernández, G.; Saez Vacas, F. (1987). Fundamentos de Informática. Madrid, Ed. Alianza.
García Valle, L. (1990). Matemáticas especiales para Computación. Madrid, Mc. Graw Hill.
Grimaldi, R. (1997). Matemáticas Discreta y Combinatoria. Wilmington, Addison-Wesley Iberoamericana.