Matemáticas Discretas y Algoritmos

[latexpage]

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: Fundamentos matemáticos
  • Unidad 2: Fundamentos algorítmicos
  • Unidad 3: Tipos de algoritmos
  • Unidad 4: Algoritmos fundamentales 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: Fundamentos matemáticos

  • Introducción a teoría de gráficas
  • Grados, vecindades y teorema de Euler
  • Caminos, trayectorias y ciclos
  • Conexidad y distancia en gráficas
  • Árboles y bosques
  • Gráficas bipartitas, emparejamientos y teorema de Hall
  • Conjuntos Independientes y coloraciones
  • Gráficas planas y teorema de Kuratowski
  • Gráficas de contextos geométricos
  • Principio de las casillas
  • El teorema de Turán
  • El teorema de Ramsey

Unidad 2: Fundamentos algorítmicos

  • Problemas algorítmicos
  • Análisis de correctitud
  • Pensamiento asintótico
  • El modelo RAM
  • Análisis de complejidad asintótica en tiempo y espacio
  • Estructuras de datos
  • Árboles binarios balanceados y búsqueda binaria
  • El problema de ordenar elementos
  • Algoritmos de ordenamiento cuadráticos
  • Heaps y heap-sort
  • Quick-sort
  • Aplicaciones de ordenar

Unidad 3: Tipos de algoritmos

  • Espacios de estados y exploración exhaustiva
  • Algoritmos voraces
  • Algoritmos divide y vencerás
  • Algoritmos recursivos y el teorema maestro
  • Programación dinámica
  • Búsquedas combinatorias
  • Backtrack
  • Exploración de subconjuntos, permutaciones y combinaciones
  • Métodos heurísticos y probabilísticos

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

  • Implementaciones de gráficas, gráficas ponderadas, gráficas dirigidas y redes.
  • Búsqueda en profundidad y aplicaciones
  • Búsqueda en anchura y aplicaciones
  • Ordenamientos topológicos
  • Árboles de peso mínimo: algoritmos de Prim y Kruskal
  • Caminos de peso mínimo: algoritmos de Dijkstra y Floyd-Warshall
  • Introducción a redes y flujos
  • Teorema del flujo máximo – corte mínimo
  • Algoritmo de Ford-Fulkerson y variantes

Extra: Problemas difíciles

  • Reducciones de problemas
  • Clases P y NP
  • P vs NP
  • Problemas de gráficas NP-completos

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