Teoría de la Computación

1.Lógica: proposiciones, proposiciones condicionales y equivalencia lógica, cuantificadores, cuantificadores anidados y sus pseudocódigos, demostraciones, inducción matemática.
2.Conjuntos: conjuntos, funciones, sucesiones y cadenas.
3.Relaciones: relaciones, relaciones de equivalencia, matrices de relaciones.
4.Algoritmos: notaciones, algoritmos recursivos.
5.Introducción a la teoría de números: divisores, máximo común divisor, mínimo común múltiplo, algoritmo de Euclides, cifrar y descifrar mensajes usando el sistema criptográfico de llave pública RSA.
6.Métodos de conteo: principios básicos, permutaciones y combinaciones, coeficientes binomiales e identidades combinatorias, permutaciones y combinaciones generalizadas, conteo de caminos en reticulados con eventuales restricciones y sus pseudocódigos, conteo de soluciones en ecuaciones diofánticas y sus pseudocódigos; enunciados y usos del principio del palomar.
7.Relaciones de Recurrencia (RR): introducción, solución de las RR, aplicaciones de las RR en el análisis de algoritmos.
8.Grafos: caminos y ciclos, ciclos eulerianos y hamiltonianos, el problema del viajante, ruta más corta mediante el algoritmo de Dijkstra, representaciones de grafos, isomorfismos de grafos, grafos planares.
9.Árboles: terminología y caracterización de árboles, árboles generadores (o de expansión) mediante búsqueda a lo ancho y en profundidad, árboles generadores mínimos a través de los algoritmos de Prim y de Kruskal, árboles binarios, recorridos de árboles, isomorfismos de árboles.
10.Autómatas, gramáticas y lenguajes: Máquinas de Estado Finito (MEF) y Autómatas de Estado Finito (AEF), lenguajes y gramáticas, AEF deterministas y AEF no-deterministas, conversión de un AEF no-determinista a un AEF equivalente, relaciones entre lenguajes y autómatas.