Clases
Lunes 4:00-6:00 pm y viernes 6:00-8: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 (30%)
Habrá dos parciales. La fecha de estos se avisará con al menos una semana de anticipación.Final (30%)
Habrá un exámen final sobre todo el contenido del programa por un valor del 30%.Tareas y quizzes (40%)
Habrá conjuntos de problemas que se asignarán aproximadamente cada semana y que deberán ser entregados a la semana siguiente. 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 15% en el primer corte, 15% en el segundo corte, y 10% 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 01/22 | Introducción. ¿Qué es la combinatoria? |
| Vie 01/26 | Principios básicos de conteo. Permutaciones y factoriales |
| Lun 01/29 | Combinaciones y selecciones |
| Vie 02/02 | Combinaciones y selecciones |
| Lun 02/05 | Coeficientes binomiales y el triángulo de Pascal |
| Vie 02/09 | Selecciones con repeticiones y composiciones |
| Lun 02/12 | Selecciones con repeticiones y composiciones |
| Vie 02/16 | Un teorema de inversión matricial |
| Lun 02/19 | Recurrencias |
| Vie 02/23 | Método de la ecuación auxiliar |
| Lun 02/26 | Método de la ecuación auxiliar |
| Vie 03/02 | Primer Parcial |
| Lun 03/05 | Funciones generatrices |
| Vie 03/09 | Funciones generatrices |
| Lun 03/12 | Desarreglos. Algoritmos de ordenamiento |
| Vie 03/16 | Números de Catalan |
| Vie 03/23 | Grafos |
| Lun 04/02 | Caminos y árboles |
| Vie 04/06 | Árboles de expansión |
| Lun 04/09 | Árboles de expansión |
| Vie 04/13 | Grafos bipartitos. Planaridad |
| Lun 04/16 | Poliedros |
| Vie 04/20 | Segundo Parcial |
| Lun 04/23 | Grafos Hamiltonianos |
| Vie 04/27 | Problema del agente viajero |
| Lun 04/30 | Grafos Eulerianos |
| Vie 05/04 | Particiones |
| Lun 05/07 | Particiones |
| Vie 05/11 | Coloraciones de grafos y el polinomio cromático |
| Vie 05/18 | Principio de Inclusión-Exclusión (PIE) |