Capítulo 1 |
Conjuntos y Lógica |
- Sistema de numeración y aritmética binaria;
- Conjuntos;
- Proposiciones;
- Reglas de inferencia, y
- Cuantificadores.
|
Capítulo 2 |
Funciones, Secuencias y Relaciones |
- Funciones;
- Strings y Secuencias; y
- Relaciones.
|
Capítulo 3 |
Métodos de Conteo |
- Principios básicos de conteo;
- Permutaciones;
- Combinaciones;
- Permutaciones y Combinaciones generalizadas;
- Coeficientes binomiales y el principio del palomar, y
- Principio de la inducción matemática.
|
Capítulo 4 |
Grafos y Árboles |
- Conceptos básicos sobre grafos;
- Ciclos de Hamilton y el problema del vendedor;
- Tipos de grafos;
- El camino más corto de un grafo;
- Conceptos básicos sobre árboles binarios y de expansión, y
- Isomorfismo de grafos y árboles.
|
Capítulo 5 |
Autómatas finitos |
- Lenguajes formales;
- Autómatas finitos determinísticos;
- Autómatas finitos no determinísticos;
- Conversión NFA-DFA;
- Intersección de autómatas finitos;
- Autómatas finitos probabilísticos, y
- Cadenas de Markov.
|
Capítulo 6 |
Lenguajes regulares |
- Lenguajes Regulares;
- Gramáticas regulares;
- Expresiones regulares formales, y
- Expresiones regulares en lenguaje de programación (PCRE).
|
Capítulo 7 |
Lenguajes libres de contexto |
- Lenguajes libres de contexto;
- Autómatas de pila;
- Gramáticas libres de contexto, y
- Lenguajes ambiguos.
|
Capítulo 8 |
Máquinas de Turing |
- Introducción a las Máquinas de Turing;
- Máquinas de Turing como reconoceres de lenguajes;
- Máquinas de Turing como transductores;
- Complejidad de tiempo, complejidad de espacio e intractabilidad;
- Introducción a la decibilidad, y
- Introducción a la reducibilidad.
|