Yachakaj: CM2H1 MATEMÁTICA DISCRETA

(Prácticas y exámenes)
(Bibliografía)

Matemática discreta y sus aplicaciones (5ta ed.). Rosen Kenneth.

a) Preparación
Problemas ligados a la matemática discreta. Notaciones comunes. Inducción matemática. Funciones y relaciones. Relaciones de equivalencia y de orden parcial.
b) Conteo (teoría + ejercicios)
Funciones y subconjuntos. Permutaciones y factoriales. Coeficientes binomiales. Comparación asintótica de funciones: las notaciones O, o. Estimados de la función factorial y los coeficientes binomiales. El principio de inclusión-exclusión.
c) Grafos (teoría + ejercicios)
Noción de grafo; isomorfismo. Subgrafos, componentes, matriz de adyacencia. Secuencia de grados de un grafo. Grafos eulerianos. 2-conectividad.
d) Árboles
Definición y caracterizaciones. Isomorfismo de árboles. Árboles de expansión de un grafo. El problema del árbol de expansión mínima. El número de árboles de expansión mínima.
e) Graficando grafos en el plano
Graficando en el plano y otras superficies. Ciclos en grafos planares. Fórmula de Euler. Coloreando mapas: el problema de los cuatro colores.
f) Enteros, divisores, primalidad (teoría + ejercicios)
Divisibilidad de enteros. Factorización en primos. El algoritmo de Euclides. Congruencias. Aritmética modular. Elementos invertibles módulo n. El pequeño teorema de Fermat. Descubriendo números compuestos.
g) Criptografía (teoría + ejercicios)
Un método de criptografía simétrica. La propuesta de Diffie y Hellman. El método RSA. El problema del logaritmo discreto.
------------------------------------------------
UNIDAD 1: TÉCNICAS BÁSICAS DE PRUEBAS, RELACIONES Y FUNCIONES, ÁLGEBRA DE BOOLE Y MÉTODOS DE CONTEO.
Técnicas básicas de pruebas:
 Inducción simple, fuerte y principio de buen orden.
 Prueba directa, contrapositiva y contradicción.
•
Relaciones y funciones.
 Conjuntos.
 Relaciones y Funciones.
 Principio de inclusión – exclusión.
 Principio del Palomar.

 Relación de equivalencia.
 Relación de orden parcial y total (diagrama de Hasse).
 Orden sobre el producto de CPO’s.
 Orden Lexicográfico.

 Homomorfismo, encajes e isomorfismos de CPO’s,
 Retículos y subretículos.
 Retículo complementado.
 Retículo distributivo.

Álgebra de Boole:
 Álgebra de Boole.
 Funciones booleanas.
 Simplificación de expresiones booleanas (FND,FNC).
 Mapas de Karnaugh.

Métodos de conteo:
 Permutaciones y combinaciones.
 Estimaciones de la función factorial.
 Estimaciones de los coeficientes binomiales.
UNIDAD 2: TEORÍA DE GRAFOS: GRAFOS NO DIRIGIDOS Y ÁRBOLES. GRAFOS PLANARES Y COLORACIÓN.
Grafos:
 Grafos dirigidos y no dirigidos
 Tipos de grafos simples: Camino simple, Ciclo, Completo, Bipartito (caracterización), Bipartito Completo y Rueda
 Secuencia de grados de un grafo: Lema del apretón de manos, algoritmo Havel-Hakimi
 Homomorfismo e isomorfismo de grafos

 Grafo conexo
 Distancia entre dos vértices, excentricidad de un vértice, radio, diámetro y centro de un grafo
 Matriz de adyacencia, conteo de caminos de longitud k

 Tipos de trayectorias: Recorrido y Circuito
 Camino y Grafo Euleriano
 Camino y Grafo Hamiltoniano: Teorema de Ore, Dirac y Bondy– Chvátal

 Grafo de Ramanujan
 Grafos fuertemente regulares
 Operaciones: Complemento de un grafo, eliminación de un vértice y una arista, subdivisión y contracción de una arista

Arboles:
 Definición y caracterización de un árbol
 Isomorfismo de árboles
 Automorfismo de un árbol
 Codificación de un árbol

 Árbol recubridor: Formula de Cayley
 Algoritmo de Kruskal
 Algoritmo de Dijkstra

Graficando grafos en el plano:
 Grafo planar y planar maximal
 Grafos homeomorfos
 Teorema de Kuratowski
 Género de un grafo  Fórmula de Euler

 Grafo extraplanar
 Teorema de Wagner
 Coloración de un vértice (número cromático)
 Teorema de Brooks

 Polinomio cromático.
 Formula de eliminación y contracción de aristas.

 Coloración de aristas (número cromático)
 Teorema de Vizing, Ramsey, Turán y Schur
UNIDAD 3: INTRODUCCIÓN A LA TEORÍA DE NÚMEROS.
 Teorema fundamental de la Aritmética
 MCD y MCM
 Teorema chino del resto
 Aritmética modular

 Pequeño teorema de Fermat
 Teorema de Wilson
 Teorema de Euler

 Grupos: ℤ, ℤ_𝑛, GL_𝑛(ℝ) y S_3
 Orden de un grupo y un elemento
 Subgrupos
 Teorema de Lagrange

 Grafo de Cayley  Raíces primitivas

 Logaritmo discreto

 Residuos cuadráticos (Símbolo de Legendre)

 Ley de reciprocidad cuadrática
UNIDAD 4: CRIPTOGRAFÍA.
 Código BCD, ASCII y UNICODE
 Cifrado Cesar
 Códigos poligráficos (el código Vigenére)

 Cifrado Hill  Códigos de Flujo (El código Vernam)

 Cifrado Diffie-Hellman

 Cifrado RSA
------------------