Matemáticas Discretas y Algoritmos

Esta es la página del curso Matemáticas Discretas y algoritmos que imparto en la Licenciatura en Ciencia de Datos de la UNAM. En este curso cubrimos el temario oficial de la materia viendo varios problemas y ejemplos en el camino. El material consiste en fuertes componentes teóricos y de programación.

Organización del curso

El curso está dividido en cuatro unidades temáticas.

  • Unidad 1: Inducción, recursión e introducción a teoría de gráficas
  • Unidad 2: Análisis de algoritmos
  • Unidad 3: Tipos de algoritmos
  • Unidad 4: Más algoritmos en teoría de gráficas

Notas del curso

A continuación están las entradas de blog con el contenido del curso. Se irán llenando los enlaces poco a poco, conforme el material esté disponible.

Unidad 1: Inducción, recursión e introducción a teoría de gráficas

  • Introducción a teoría de gráficas, grados, vecindades
  • Caminos, trayectorias y ciclos
  • Conexidad y distancia en gráficas
  • Árboles y bosques
  • Gráficas bipartitas, emparejamientos y el teorema de Hall
  • Independientes y coloraciones de vértices y de aristas
  • Introducción a principio de las casillas
  • El teorema de Ramsey
  • Gráficas planas y en teorema de Kuratowski
  • Gráficas que vienen de contextos geométricos

Unidad 2: Análisis de algoritmos

  • Algoritmos correctos
  • Introducción a eficiencia de algoritmos: tiempo y espacio
  • Paréntesis sobre modelos computacionales y máquinas de Turing
  • Análisis de complejidad asintótica
  • Análisis de espacio asintótico

Unidad 3: Tipos de algoritmos

  • Algoritmos recursivos y árboles de recursión
  • Algoritmos iterativos
  • Algoritmos voraces
  • Algoritmos divide y vencerás
  • Algoritmos de programación dinámica

Unidad 4: Algoritmos fundamentales en teoría de gráficas

  • Emparejamientos máximos
  • Algoritmo de Ford-Fulkerson
  • Algoritmo de Floyd-Warshall
  • Colorear es NP-completo

Videos del curso

Por el momento no hay videos disponibles para este curso.

Moodle del curso

Además de las notas y videos del curso, se cuenta con un curso en Moodle en donde hay mucho más material:

  • Foros de discusión divididos por cada unidad temática
  • Cuestionarios de opción múltiple y respuesta numérica para verificar el entendimiento de cada uno de los temas que cubrimos en el curso
  • Tareas y exámenes de versiones anteriores del curso

Para tener acceso a este material, es necesario tener una cuenta en el portal NekoMath Learn y pedir en un correo la inscripción al curso en línea.

Evaluación

La forma específica de evaluar depende de cada vez que se imparte el curso. Hay variantes entre la modalidad en línea y la modalidad presencial.

Bibliografía

En esta página se pueden encontrar las notas que usamos para llevar el curso.

Créditos

Las siguientes personas me han ayudado a impartir este curso en la Licenciatura en Ciencia de Datos de la UNAM.

Semestre 2021-1: Victor Hugo Almendra Hernández