Matemáticas discretas

Incluye contenido

1. Lógica y demostraciones. Proposiciones. Proposiciones condicionales y equivalencia lógica. Cuantificadores. Demostraciones. Demostraciones por resolución. Inducción matemática, rincón de solución de problemas: inducción matemática, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 2. El lenguaje de las matemáticas. Conjuntos. Sucesiones y cadenas. Sistemas numéricos. Relaciones, rincón de solución de problemas: relaciones. Relaciones de equivalencia, rincón de solución de problemas: relaciones de equivalencia. Matrices de relaciones. Bases de datos relacionales. Funciones, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 3. Algoritmos. Introducción. Notación para los algoritmos. El algoritmo de Euclides. Algoritmos recursivos. Complejidad de los algoritmos, rincón de solución de problemas: diseño y análisis de un algoritmo. Análisis del algoritmo de Euclides. El sistema criptográfico con clave pública, RSA, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 4. Métodos de conteo y el principio de la pichonera. Principios básicos, rincón de solución de problemas: conteo. Permutaciones y combinaciones, rincón de solución de problemas: combinaciones. Algoritmos para generar permutaciones y combinaciones. Permutaciones y combinaciones generalizadas. Coeficiente binomial e identidades combinatorias. El principio de la pichonera, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 5. Relaciones de recurrencia. Introducción. Solución de relaciones de recurrencia, rincón de solución de problemas: relaciones de recurrencia. Aplicaciones al análisis de algoritmos, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 6. Teoría de gráficas. Introducción. Caminos y ciclos, rincón de solución de problemas: gráficas. Ciclos hamiltonianos y el problema del agente de ventas viajeros. Un algoritmo para la ruta más corta. Representaciones de gráficas. Isomorfismo de gráficas. Gráficas planas. Locura instantánea, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 7. Árboles. Introducción. Terminología y caracterizaciones de los árboles, rincón de solución de problemas: árboles. Árboles de expansión. Árboles de expansión mínimos. Árboles binarios. Recorridos de un árbol. Árboles de decisión y el tiempo mínimo para el ordenamiento. Isomorfismo de árboles. Árboles de juegos, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 8. Modelo de redes y redes de petri. Modelos de redes. Un algoritmo de flujo máximo. El teorema de flujo máximo y corte mínimo. Acoplamiento, rincón de solución de problemas: acoplamiento. Redes de petri, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 9. Álgebras booleanas y circuitos combinatorios. Circuitos combinatorios. Propiedades de circuitos combinatorios. Álgebras booleanas, rincón de solución de problemas: álgebras booleanas. Funciones booleanas y simplificación de circuitos. Aplicaciones, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 10. Autómatas, gramáticas y lenguas. Circuitos secuenciales y máquinas de estado finito. Automatas de estado finito. Lenguajes y gramática. Automatas de estado finito no determinista. Relaciones entre lenguajes y autómatas, notas, conceptos básicos del capítulo, autoevaluación del capítulo.-- 11. Geometría computacional. El problema del par más cercano. Una cota inferior para el problema del par más cercano. Un algoritmo para calcular la cubierta convexa, notas, conceptos básicos del capítulo, autoevaluación del capítulo.