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.

Sesión 1:
Técnicas básicas de pruebas:
 Principio de Inducción Matemática: Inducción simple, fuerte y principio de buen orden.
 Métodos de demostración: Prueba directa, contrapositiva y contradicción.
•
Sesión 2:
Relaciones y funciones:
 Conjuntos.
 Relaciones y Funciones.
 Principio de inclusión – exclusión.
 Principio del Palomar.

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

Sesión 4:
 Homomorfismo, encajes e isomorfismos de CPO’s,
 Retículos y subretículos.
 Retículo complementado.
 Retículo distributivo.

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

Sesión 6
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.

Sesión 7:
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.

Sesión 8:
 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.

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

Sesión 10:
 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.

Sesión 11:
Árboles:
 Definición y caracterización de un árbol.
 Isomorfismo de árboles.
 Automorfismo de un árbol.
 Codificación de un árbol.

Sesión 12:
 Árbol recubridor: Formula de Cayley.
 Algoritmo de Kruskal.
 Algoritmo de Dijkstra.

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

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

Sesiones 15, 16: Parcial

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

Sesión 18:
 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.

Sesión 19:
 Teorema fundamental de la Aritmética.
 MCD y MCM.

Sesión 20:
 Teorema chino del resto.
 Aritmética modular.

Sesión 21:
 Pequeño teorema de Fermat.
 Teorema de Wilson.
 Teorema de Euler.

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

Sesión 23:
 Grafo de Cayley.
 Raíces primitivas.

Sesión 24:
 Logaritmo discreto.

Sesión 25:
 Residuos cuadráticos (Símbolo de Legendre).

Sesión 26:
 Ley de reciprocidad cuadrática.
UNIDAD 4: CRIPTOGRAFÍA.

Sesión 27:
 Código BCD, ASCII y UNICODE.
 Cifrado Cesar.
 Códigos poligráficos (el código Vigenére).

Sesión 28:
 Cifrado Hill.
 Códigos de Flujo (El código Vernam).

Sesión 29:
 Cifrado Diffie-Hellman.

Sesión 30:
 Cifrado RSA.
------------------