Introducción a Matemática Discreta II

Breve reseña histórica de los orígenes de la Computación

Axiomatización de la Lógica
Los 20 problemas de Hilbert
La paradoja de Russel y Principia Matematica
Completitud e Incompletitud de Godel
La máquina de Turing

Resumen de los contenidos del curso

Autómatas y Computabilidad

Autómatas
- Finitos deterministas y no-deterministas
- De pila
- Máquinas de Turing
Lenguajes formales
- Gramáticas
- Jerarquía de Chomsky
- Equivalencias con autómatas
Problemas indecidibles
- Lema del bombeo
- Máquina universal de Turing
- Lenguaje universo
- Halting problem

Teoría de grafos

Definiciones, tipos de grafos
Caminos
Subgrafos, componentes conexas y fuertemente conexas
Árboles
Grafos hamiltoneanos y eulerianos
Coloreo
Grafos planares
Torneos
Cliques y conjuntos independientes
Grafos bipartitos
Emparejamientos

Sistema de evaluación

2 exámenes parciales + examen final (ambos temas hay que aprobarlos)
Ejercicios de CP (opcional)
Demostraciones adicionales (opcional)