Clases
Lunes y Martes 4:00-6:00 pm.Literatura
A First Course in Discrete Mathematics. Ian Anderson.Notas de clase ( en PDF).
Contenido del curso
La combinatoria es la rama de la matemática que se encarga de la enumeración y estructura de familias de objetos discretos. Un grafo es un objeto discreto formado por un conjunto de nodos y un conjunto de aristas entre ellos. La teoría de grafos se encarga entonces de la enumeración y el estudio de las propiedades estructurales de familias de grafos. Este es principalmente un curso introductorio a la teoría de enumeración combinatoria en donde usaremos la teoría de grafos como campo de juego en donde usar herramientas combinatorias. Desde el punto de vista enumerativo se cubrirán los principios básicos de conteo; permutaciones y números factoriales; subconjuntos y coeficientes binomiales; composiciones y composiciones débiles; particiones de conjuntos y números de Stirling; números de Fibonacci y números de Catalan; recurrencias; funciones generatrices; y el principio de inclusión-exclusión (PIE). De la teoría de grafos se cubrirán las definiciones básicas de grafos; caminos, caminatas y ciclos; árboles generadores o de expansión; grafos bipartitos; planaridad y el teorema de Kuratowski; grafos Hamiltonianos y Eulerianos.; poliedros; y coloraciones de grafos y el polinomio cromático.Distribución de las notas
Parciales (60%)
Habrá tres parciales. La fecha de estos se avisará con al menos una semana de anticipación.Tareas y quizzes (40%)
Habrá tres conjuntos de problemas que se asignarán para cada corte. Trabajar en los problemas de tarea es fundamental para el entendimiento del material presentado en clase. Asegúrese de separar tiempo suficiente de cada semana para pensar y escribir sus soluciones. Se recomienda que le piense e intente cada problema por su propia cuenta antes de buscar ayuda. Se invita a los estudiantes a que discutan el material del curso con sus compañeros, sin embargo cada estudiante debe escribir sus propias soluciones y en sus propias palabras. Pueden haber algunos quizzes que no serán anunciados y también contarán hacia la nota final. La distribución de las tareas según los cortes será de 10% en el primer corte, 10% en el segundo corte, y 20% en el tercer corte.Sesiones de problemas
Habrá varias sesiones de problemas en clase durante el semestre con el objetivo de reforzar los conceptos aprendidos en cada semana. Durante las sesiones de problemas se invita a los estudiantes a que compartan lo que han aprendido y que aprendan de sus compañeros de clase.Problemas sugeridos
Habrá también algunos problemas sugeridos adicionales. Estos problemas será asignados en algunas de las clases.Programa
Este es un programa aproximado del contenido del curso:Fecha | Tema |
---|---|
Lun 07/26 | Introducción. ¿Qué es la combinatoria? |
Mar 07/27 | Principios básicos de conteo. Permutaciones y factoriales |
Lun 08/02 | Combinaciones y selecciones |
Mar 08/03 | Combinaciones y selecciones |
Lun 08/09 | Coeficientes binomiales y el triángulo de Pascal |
Mar 08/10 | Selecciones con repeticiones y composiciones |
Mar 08/17 | Un teorema de inversión matricial |
Lun 08/23 | Recurrencias |
Mar 08/24 | Método de la ecuación auxiliar |
Lun 08/30 | Método de la ecuación auxiliar |
Mar 08/31 | Primer Parcial |
Lun 09/06 | Funciones generatrices |
Mar 09/07 | Funciones generatrices |
Lun 09/13 | Desarreglos. Algoritmos de ordenamiento |
Mar 09/14 | Números de Catalan |
Lun 09/20 | Grafos |
Mar 09/21 | Caminos y árboles |
Lun 09/27 | Árboles de expansión |
Mar 09/28 | Árboles de expansión |
Lun 10/04 | Grafos bipartitos. Planaridad |
Mar 10/05 | Poliedros |
Lun 10/11 | Grafos Hamiltonianos |
Mar 10/12 | Segundo Parcial |
Lun 10/25 | Problema del agente viajero |
Mar 10/26 | Grafos Eulerianos |
Mar 11/02 | Particiones |
Lun 11/08 | Particiones |
Mar 11/09 | Coloraciones de grafos y el polinomio cromático |
Mar 11/16 | Principio de Inclusión-Exclusión (PIE) |
Mar 11/23 | Tercer Parcial |