Profesores:	Dr. Juan Carlos Augusto
	Dr. Alejandro J. García
Código	1671
Créditos	20

Objetivos: Brindar nociones básicas sobre distintos formalismos que desempeñan un rol importante en la teoría de las ciencias de la computación y sus diversas aplicaciones en la resolución de problemas computacionales. El curso estará orientado especialmente a personas que comienzan un postgrado en ciencias de la computación y desean obtener conocimientos en los aspectos fundamentales de la ciencia.
 

Prerequisitos: nociones básicas de matemática y aprobación del profesor.
 

Detalle del contenido del curso:

1. Teorías Formales: Axiomas, reglas de inferencia, deducción, teoremas, consistencia, sensatez y decidibilidad
2. Calculo Proposicional: lenguaje, interpretación, deducción y computación. Completitud.
3. Calculo de Predicados: lenguaje, interpretación, deducción y computación.
4. Programación en Lógica: lenguaje, semántica y negación. Prolog.
5. Lógicas Modales: Lenguaje, axiomatizaciones, semántica.
6. Lenguajes, Nociones Preliminares: cadena, lenguaje, gramática, Jerarquía de Chomsky.
7. Lenguajes Regulares y Autómatas Finitos: Definiciones básicas, expresiones regulares, teorema de Kleene, automatas de Mealy y Moore, aplicaciones en casos practicos.
8. Lenguajes Libres del Contexto y Autómatas a Pila: Definiciones basicas, relación entre dichos conceptos, aplicaciones en casos prácticos.
9. Lenguajes Sensibles al Contexto y Autómatas Acotados Linealmente: Definiciones basicas, aplicaciones en casos prácticos.
10. Lenguajes estructurados por frases y Máquinas de Turing: Definiciones básicas, aplicaciones en casos practicos.
11. Computabilidad y Tesis de Turing - Church: Procedimiento Efectivo, problemas solubles e insolubles, aplicación en casos prácticos, Tesis de Turing, Tesis de Church, Funciones Recursivas Parciales, Teorema de Kleene, otros formalismos expresivamente equivalentes.