MATEMÁTICAS DISCRETAS
1. Introducción
En la primera parte de este material, exploramos los fundamentos de las
Matemáticas Discretas, incluyendo conceptos básicos de teoría de grafos,
combinatoria, lógica y teoría de números. En esta segunda parte,
profundizaremos en temas avanzados que son esenciales para
aplicaciones en informática, optimización y ciencias de la computación.
Objetivos:
• Comprender conceptos avanzados de teoría de grafos, como grafos
dirigidos, algoritmos de recorrido y caminos mínimos.
• Explorar principios combinatorios avanzados, como el principio de
inclusión-exclusión y el Teorema de Ramsey.
• Analizar la aritmética modular y su aplicación en criptografía.
• Introducir autómatas y lenguajes formales, así como su relación con
la computabilidad.
• Discutir aplicaciones prácticas de la geometría discreta y la lógica
matemática.
2. Teoría de Grafos Avanzada
2.1 Grafos Dirigidos y No Dirigidos
• Definiciones:
o Un grafo no dirigido es un conjunto de vértices conectados
por aristas sin dirección.
o Un grafo dirigido es un conjunto de vértices conectados por
aristas con dirección (flechas).
• Ejemplos prácticos:
o Grafos no dirigidos: Redes sociales (amistades
bidireccionales).
o Grafos dirigidos: Diagramas de flujo de trabajo (tareas con
dependencias).
• Pregunta de reflexión: ¿En qué situaciones reales se utilizan los
grafos dirigidos y no dirigidos?
2.2 Algoritmos de Recorrido: DFS y BFS
• Búsqueda en Profundidad (DFS):
o Recorre un grafo profundamente antes de expandirse.
o Pseudocódigo:
Pseudocódigo hecho
en Python:
DFS(grafo, nodo):
visitar(nodo)
para cada vecino en
grafo[nodo]:
si vecino no
visitado:
DFS(grafo,
vecino)
• Búsqueda en Anchura (BFS):
o Recorre un grafo nivel por nivel.
Pseudocódigo hecho en Python:
BFS(grafo, inicio):
cola = [inicio]
mientras cola no esté vacía:
nodo = cola.pop(0)
visitar(nodo)
para cada vecino en grafo[nodo]:
si vecino no visitado: cola.append(vecino)
2.3 Grafos Ponderados y Algoritmos de Caminos Mínimos
• Algoritmo Caminos:
o Encuentra el camino más
corto desde un nodo inicial a
todos los demás.
o Ejemplo: Optimización de
rutas en GPS.
o Problema
práctico: Encuentra el camino
más corto en un grafo ponderado
utilizando el algoritmo de
Dijkstra.
2.4 Aplicaciones en Redes y Optimización
• Estudio de casos:
o Optimización de redes de comunicación.
o Diseño de circuitos electrónicos.
• Pregunta de reflexión: ¿Cómo podría aplicarse la teoría de grafos
en el diseño de circuitos electrónicos?
3. Combinatoria Avanzada
3.1 Principio de Inclusión-
Exclusión
• Desarrollo:
o Permite contar
elementos en la
unión de conjuntos
considerando sus
intersecciones.
o Fórmula: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣∣A∪B∣=∣A∣+∣B∣−∣A∩B∣.
• Ejemplo resuelto: Contar estudiantes que toman al menos una de
dos materias.
• Problema práctico: Aplica el principio de inclusión -exclusión para
contar el número de estudiantes que toman al menos una de dos
materias.
3.2 Teorema de Ramsey
• Introducción:
o Establece que en cualquier grafo
suficientemente grande, siempre habrá
subestructuras ordenadas.
o Aplicación en redes sociales:
Detección de comunidades.
• Pregunta de reflexión: ¿Cómo se podría
utilizar el Teorema de Ramsey en redes
sociales?
4. Teoría de Números en Matemáticas Discretas
• Definición: Es una rama de la matemática que se centra en el
estudio de propiedades y relaciones de los números enteros.
Explora patrones, distribuciones y propiedades los números primos,
enteros y fraccionarios. Problemas clásicos incluyen la conjetura de
Goldbach, la hipótesis de Riemann y conjetura de Collatz.
La teoría de números tiene aplicaciones en criptografía, codificación, y
otras disciplinas. Ademas, contribuye a la compresión fundamental de la
estructura y comportamiento de los números en diversas áreas
matemáticas y científicas.
4.1 Congruencias y Aritmética Modular
• Definiciones:
o a≡b (mod m) a≡b (mod m) si mm divide a a−ba−b.
o Aplicaciones en criptografía
• Problema práctico: Resuelve la congruencia x≡3 (mod 7)
4.2 Teorema de los Restos Chinos
Explicación:
o Permite resolver sistemas de congruencias simultáneas.
o Ejemplo: x≡2 (mod 3), x≡3 (mod 5)
• Pregunta de reflexión: ¿Por qué es útil este teorema en la
informática?
Teorema del Resto Chino.
5. Lógica Matemática y Teoría de la Computabilidad
5.1 Lógica Proposicional y de Predicados
• Fundamentos:
o Tablas de verdad y
cuantificadores
(∀∀, ∃∃).
o Ejemplo: Verificar la
validez de una
proposición.
• Problema práctico: Verifica la
validez de la siguiente
proposición usando tablas de
verdad.
6. Geometría Discreta
6.1 Teorema de los Cuatro Colores
• Análisis:
o En cualquier mapa plano, cuatro colores son suficientes para
colorear las regiones sin que dos adyacentes tengan el mismo
color.
o
• Problema práctico:
Dibuja un mapa simple y coloréalo con el menor número de colores
posible.
7. Conclusión
En este documento, hemos explorado temas avanzados de Matemáticas
Discretas, desde teoría de grafos hasta lógica y geometría discreta. Estos
conceptos son fundamentales en áreas como la informática, la
optimización y la inteligencia artificial.
Pregunta de cierre: ¿Cómo crees que la Matemática Discreta influye en
el desarrollo de la inteligencia artificial?
8. Referencias
• Rosen, K. H. (2018). Matemáticas Discretas y sus Aplicaciones. McGraw-
Hill.
• Cormen, T. H. (2009). Introduction to Algorithms. MIT Press.
• Grimaldi, R. P. (2018). Matemáticas Discretas y Combinatorias.
Pearson.
