Curso CC3101 Secciones 1 y 2 (Primavera 2021)

Matemáticas Discretas para la Computación, Semestre Primavera 2021
Profesores Federico Olmedo y Alejandro Hevia

(Ver log de cambios al final)

Objetivos del curso

El curso tiene como propósito que los y las estudiantes identifiquen y utilicen herramientas matemáticas formales necesarias para analizar y resolver problemas que involucren elementos discretos. Dichas herramientas incluyen trabajar con el lenguaje de la lógica formal, con demostraciones, combinatoria y estructuras discretas como relaciones y grafos.

Al finalizar el curso, los y las estudiantes serán capaces de utilizar dichas herramientas para modelar y resolver, de forma precisa y rigurosa, una amplia variedad de problemas computacionales.

Programa del curso: Se recomienda revisar el programa oficial del curso.

Estrategia de enseñanza y aprendizaje

La metodología de enseñanza-aprendizaje del curso es activo–participativa y considera las siguientes estrategias:

• Clases expositivas: se presentan los conceptos fundamentales de cada unidad y los y las estudiantes analizan ejemplos y trabajan en problemas y ejemplos fundamentales para las matemáticas discretas, así como con modelos y técnicas para abordarlos.
• Resolución de problemas: los y las estudiantes resuelven problemas donde modelan dichos problemas y utilizan técnicas, métodos, herramientas matemáticas asociados para decidir metodológicamente cómo abordar en forma rigurosa cada problema y demostrar formalmente que utiliza lenguaje de matemática discreta, en particular, de lógica, combinatoria y grafos.

Metodología de trabajo

El contenido del curso se trabaja en tres formatos complementarios que los alumnos deben ver y desarrollar: videos, trabajo individual y trabajo grupal.

1. Clases en formato Videos: Cada clase está grabada en una serie de videos cortos de publicación semanal, (puedes encontrar la playlist completa acá).
2. Quizzes (individuales): Cada estudiante debe desarrollar (individualmente) una evaluación corta (denominado "quiz") de no más de 5 minutos al final de cada cátedra. Los quizzes es una evaluación formativa (opcionales), se realizan en forma individual y online y su contenido cubre el contenido de la clase correspondiente.
3. Trabajo grupal: Cada estudiante deberá realizar tres actividades o trabajos grupales, uno por macro unidad, esto es, un total de 3 actividades. Los detalles están más abajo.

Los contenidos del curso están divididos en tres macro unidades:

• macro unidad I: unidades 1 (Lógica) y 2 (Técnicas de Demostración),
• macro unidad II: unidades 3 (Relaciones), 4 (Combinatoria) y 5 (Recurrencias), y
• macro unidad III: unidades 6 (Teoría de Grafos).

Reglas del curso y evaluación

• NF (nota final): 2/3 NC + 1/3 NE (NC>=4 y NE>=4).
• NC (nota trabajos grupales): promedio de las notas para los 3 trabajos grupales (1 trabajo por cada macro unidad).
• NE (nota ejercicios): promedio ejercicios (1 ejercicio x semana, ver calendario) a lo cual se agrega el bonus BonusQ, esto es, NE = (Promedio Ejercicios) + BonusQ.
• NQ (nota quizzes): promedio quizzes (1 quiz x clase de cátedra). Si bien los quizzes son optativos, todos son corregidos y su resultado comunicado. Si entrega al menos 20 de ellos (son 25) y el promedio NQ >=5.5 entonces obtiene BonusQ = 0.5. Si no, BonusQ=0.

Trabajos grupales y ejericios individuales deben aprobarse por separado .

Quizzes (evaluaciones por clase, opcionales)

Cada Martes y Jueves, al final del horario de cátedra, se dejará disponible un mini test o quiz de carácter formativo (optativo), el cual estará disponible en ucursos/tests y deberá ser respondido individualmente. Cada quiz tendrá unas pocas preguntas (típicamente 4) y estará diseñado para ser respondido en menos de 5-10 minutos. Si bien el plazo para entregar el quiz es todo el día, hasta las 23:59hrs, se recomienda contestarlo inmediatamente al finalizar de ver los videos asociados a la cátedra correspondiente. El quiz busca medir (y dar retroalimentación de) la comprensión de la materia vista en la clase respectiva.

Si bien el carácter del quiz es formativo (concretamente, para que el/la estudiante reciba retroalimentación de los conceptos vistos), si el promedio de todos los quizzes es mayor o igual a 5.5 entonces el/la estudiante obtendrá un bonus (BonusQ) de +0.5 puntos que puede agregar a su promedio de ejercicios (NE).

Ejercicios (evaluaciones semanales)

Se realizarán ejercicios con nota semanales, en cada clase auxiliar virtual, los cuales deben ser enviados vía u-cursos. Esta actividad consiste el desarrollo individual de un problema asociado a la materia cubierta en la semana previa, con el objetivo reforzar y comprobar el aprendizaje. El enunciado se entregará durante la clase auxiliar y se espera que su resolución se realice durante la misma clase (aunque el plazo de entrega podrá extenderse hasta el fin del mismo día). Para ello, lxs estudiantes contarán con el apoyo de lxs auxiliares durante la clase vía preguntas y respuestas. Es muy importante realizar todos los ejercicios ya que permite a los profesores tener retroalimentación sobre lo que se enseña.

Se eliminará 1 ejercicio en cada macro unidad siempre que se hicieren al menos 3 ejercicios en la macro unidad. Nota: Tal como está el calendario, se eliminará 1 ejercicio de las macro unidades 1 y 2, pero no en la 3 pues en esta última hay sólo 2.

Trabajos Grupales (evaluaciones de macro unidades)

Al final de cada macro unidad, los estudiantes deberán realizar un trabajo grupal tipo tarea o mini proyecto cuyo objetivo es resolver, estudiar, y explorar un problema asociado al contenido visto en la macro unidad. La entrega/presentación de este trabajo ocurrirá en una semana de presentaciones (o presentation fest) y estará explícitamente anunciada en el calendario. Para este trabajo, entre 10 y 7 días antes de la fecha de entrega/presentación, se publicará el tema específico del trabajo grupal. Este tema podrá considerar variantes (o casos particulares) asociados a cada grupo.

En cada trabajo grupal, cada grupo será evaluado en base a 2 entregables:

1. Un breve reporte en PDF, con la solución del trabajo grupal.
2. Una presentación (video) de no más de 15 min, más 5 minutos para preguntas.

Tanto el reporte como la presentación son evaluados por el miembro del equipo docente (profesor o auxiliar) presente, con nota NDPTG (Nota del Docente de la Presentación Trabajo Grupal). El resto de sus compañeros en la misma sesión deben evaluar el trabajo de los otros grupos, asignándole una nota a cada grupo. El promedio de dichas notas (eliminando outliers) será la nota denominada NPPTG (Nota de Pares de la Presentación del Trabajo Grupal) asociada a cada grupo.

Co-evaluación dentro del grupo: Cada grupo debe co-evaluarse internamente, lo cual se traducirá en un ponderador PP (ponderador de pares), un número entre 0 y 1.

La nota de cada trabajo grupal (NTG) será calculada como

(Trabajo Grupal 1:) NTG = 0.25 x NITG + 0.5 x ((NDPTG-1.0)x PP + 1.0 + BonusP) + 0.25 x NPPTG.

(Trabajo Grupal 2 y 3:) NTG = 0.80 x ((NDPTG + BonusE - 1.0)x PP + 1.0 + BonusP) + 0.20 x ((NPPTG-1.0)*PP + 1.0),

La nota BonusP depende de la participación en la misma sesión es explicada más abajo.

Los grupos deben ser de no más de 3 personas. Todas las presentaciones tendrán lugar durante la clase auxiliar del Lunes y durante la clase de cátedra del Martes durante la semana de presentation fest.

Temas de los trabajos grupales:

1. Macro Unidad I: 27 y 28 de Septiembre 2021.
2. Macro Unidad II: 8 y 9 de Noviembre 2021.
3. Macro Unidad III: 29 y 30 de Noviembre 2021.

Participación en Clases y Bonus

Se espera que cada estudiante también participe durante la presentaciones de los otros grupos en la presentation fest. Hay dos tipos de participaciones posibles:

1. Publicando preguntas vía el mecanismo online provisto durante cada uno de los días de la presentation fest.
2. Evaluando (con nota) a los otros grupos que presentan en la misma sesión que le corresponde presentar a su grupo.

Cada estudiante podrá acceder a dos bonus por participación (el valor inicial del bonus para cada estudiante es BonusP = 0):

1. Si durante la presentación de alguno de los otros grupos, su pregunta es seleccionada por el miembro del equipo docente que modera la sesión: BonusP += 0.2
2. Si la nota asignada por el/la estudiante a alguno de los otros grupos que presentan en la misma sesión coincide con la nota asignada por el miembro del equipo docente (en un rango +/-0.2 décimas): BonusP += 0.3.

Nota: Este bonus sólo se aplica para preguntas y evaluaciones realizada en la misma sesión donde presenta la persona que puede recibir el bonus.

Bonus por eficiencia

En los trabajos grupales que incluyan implementación, se podrá tener un bonus por eficiencia si es que el enunciado lo indica. En este tipo de bonus, se evaluará la eficiencia (rapidez) de la solución en varios casos (metodología a publicar) y el grupo con la solución más rápida (eficiente) tendrá un bonus BonusE=+0.5.

Compromiso ético y política de colaboración durante el curso

Se asume que todos los alumnos que participan del curso cumplirán con un compromiso ético en el desarrollo de su trabajo. Este compromiso implica realizar los ejercicios, quizzes y trabajo personal de manera responsable y honesta, sin incurrir en plagio, copia, o suplantación de identidad. Los ejercicios son trabajos de carácter individual pero pueden ser discutidos siguiendo la política de colaboración Whiteboard Policy indicada a continuación en este documento. Los quizzes son trabajos de carácter individual y no pueden ser discutidos. Los trabajos grupales sólo pueden discutirse entre los miembros del grupo. El no cumplir con estos compromisos de cualquier manera es considerado una violación del reglamento y puede implicar el inicio de un sumario. Por favor, no se arriesguen.

Para los ejercicios sí está permitido (y es altamente recomendado) discutir estrategias para la solución de problemas entre estudiates como parte de la reflexión y el aprendizaje del curso, pero siempre debe hacerse en el marco de la política de colaboración detallada a continuación.

Detalles: ¿Qué tipo de colaboración entre estudiantes se permite y qué no?: en el curso siguiremos la Whiteboard Policy (o Política de Pizarrón Blanco) la cual está detallada acá. En resumen, dos personas pueden discutir una tarea en un pizarrón (virtual o real, o pantalla de computador) siempre que no tomen notas individuales, ni se grabe o fotografíe el pizarrón o pantalla. Luego, al terminar, se cierra todo, y a partir de su memoria cada uno puede hacer su ejercicio. Lo más importante de la política es que no debe haber transpaso de trozos explícitos de soluciones (texto o desarrollo de fórmulas) entre las dos personas. Si cumplen esa regla, no tendrán ningún problema de copia. Así que anímense a colaborar!

Material del curso

• Videos de las clases de cátedra,
• Material adicional (opcional) en la forma de apuntes por clases con soluciones o ejemplos asociados a las cátedras o clases auxiliares,
• Capítulos de libros, y
• Material online (opcional) referenciado en las clases.

Este material aparecerá referenciado explícitamente en la sección Enlaces de ucursos.

Se dejará un post en el Blog del curso con detalles sobre el material en caso que sea necesario.

Calendario y Contenidos Publicados por Semana

El calendario del semestre está resumido en este PDF.

Semana	Tema	Videos	Referencias (libros)	Material extra
1	Clase 1: Introducción a la Lógica proposicional	Parte 1: Introducción a la lógica Parte 2: Sintaxis de la lógica proposicional Parte 3: Introducción a la deducción natural Parte 4: Introducción a la deducción natural continuación		Diapositivas
1	Clase 2: Pruebas por deducción natural	Parte 1: Resumen clase anterior Parte 2: Reglas de Inferencia Parte 3: Ejemplo de aplicación y notación Parte 4: El asistente de prueba Lean Parte 5: Demo de Lean Parte 6: Demo de Lean continuación		Diapositivas LeanTactics Código demo en Lean
2	Clase 3: Semántica de la lógica proposicional	Parte 1: Interpretación de fórmulas Parte 2: Satisfactibilidad, tautología y consecuencia lógica Parte 3: Conexión entre enfoques deductivo y semántico		Diapositivas
2	Clase 4: Lógica proposicional: Razonamiento ecuacional	Parte 1: Equivalencia de fórmulas Parte 2: Razonamiento ecuacional Parte 3: Expresividad de conectivos Parte 4: Aplicaciones - Semáforo Parte 5: Aplicaciones - Caballeros y canallas Parte 6: Aplicaciones - Personalización de autos		Diapositivas
3	Clase 5: Lógica de predicados	Parte 1: Conceptos básicos Parte 2: Conceptos básicos - continuación Parte 3: Deducción natural - 1 de 3 Parte 4: Deducción natural - 2 de 3 Parte 5: Deducción natural - 3 de 3 Parte 6: Equivalencia		Diapositivas
3	Clase 6: Técnicas de demostración	Parte 1: Conceptos básicos Parte 2: Demostración directa Parte 3: Demostración por contraposición Parte 4: Demostración por análisis de casos Parte 5: Demostración por contradicción		Diapositivas
4	Clase 7: Principios de prueba sobre los naturales	Parte 1: Principio de Inducción débil - 1 de 2 Parte 2: Principio de inducción débil - 2 de 2 Parte 3: Principio de inducción fuerte Parte 4: Principio del buen orden Parte 5: Principio de inducción con múltiples casos bases		Diapositivas
4	Clase 8: Inducción estructural y Recursión	Parte 1: Conceptos Básicos Parte 2: Inducción Estructural Parte 3: Funciones Recursivas Parte 4: Aplicaciones (Listas) Parte 5: Aplicaciones (Árboles Binarios)		Diapositivas
5	Clase 9: Derivaciones estructuradas	Parte 1: Introducción Parte 2: Ejemplo ilustrativo Parte 3: Nivel de detalle Parte 4: Justifiaciones y premisas Parte 5: Anidando derivaciones Parte 6: Incorporando métodos de prueba		Diapositivas
5	Clase 10: Relaciones y funciones	Parte 1: Definiciones y ejemplos Parte 2: Propiedades de las relaciones Parte 3: Ejemplos Parte 4: Relaciones de orden y de equivalencia Parte 5: Clases de equivalencia		Diapositivas
6	Clase 11: Relaciones y funciones continuación	Parte 1: Operaciones sobre relaciones Parte 2: Clausura Parte 3: Funciones como relaciones		Diapositivas
7	Clase 12: Conteo Básico	Parte 1: Introducción Parte 2: Regla del producto, ejemplos y aplicaciones Parte 3: Regla del producto - Requisito, ejercicios y alternativa Parte 4: Regla de la suma Parte 5: Principio de inclusión-exclusión, generalización y aplicación Parte 6: Principio de inclusión-exclusión - Ejercicio 1 Parte 7: Principio de inclusión-exclusión - Ejercicio 2 y 3 Parte 8: Principio de inclusión-exclusión - Ejercicio 4		Diapositivas
7	Clase 13: Combinatoria y principio del palomar	Parte 1: Permutaciones (definición) Parte 2: Permutaciones (aplicaciones) Parte 3: Combinaciones (definición) Parte 4: Combinaciones (aplicaciones) Parte 5: Pruebas combinatoriales Parte 6: Principio del palomar		Diapositivas
8	Clase 14: Relaciones de Recurrencia	Parte 1: Introducción y definición Parte 2: Aplicaciones a problemas de conteo Parte 3: Aplicaciones - Ejemplo 2 Parte 4: Aplicaciones - Ejemplo 3 y ejercicio propuesto Parte 5: Sistemas de relaciones de recurrencias		Diapositivas
9	Clase 15: Técnicas básicas para resolver recurrencias	Parte 1: Introducción Parte 2: Forma cerrada de una recurrencia Parte 3: Solución via inferencia Parte 4: Solución via transformaciones Parte 5: Ejemplos Parte 6: Observaciones		Diapositivas
9	Clase 16: Funciones Generadoras, Parte 1	Parte 1: Motivación y definiciones Parte 2: Ejemplos de funciones generadoras Parte 3: Resolviendo recurrencias con funciones generadoras Parte 4: Receta básica Parte 5: Datos útiles sobre funciones generadoras Parte 6: Ejemplo Final		Diapositivas
10	Clase 17: Teorema del Binomio Extendido	Parte 1: Introducción Parte 2: Coeficiente Binomial Extendido Parte 3: Datos útiles del CBE Parte 4: Teorema del Binomio Extendido Parte 5: Aplicaciones en funciones generadoras Parte 6: Aplicación de funciones generadoras para demostrar identidades Parte 7: Aplicación - Números de Catalan		Diapositivas
10	Clase 18: Funciones Generadoras y conteo	Parte 1: Introducción Parte 2: Conteo con funciones generadoras Parte 3: Generalizando el enfoque Parte 4: Un problema simple de conteo Parte 5: Formas de pagar con monedas Parte 6: Formas de pagar con monedas cuando el orden NO importa Parte 7: Formas de pagar con monedas cuando el orden SI importa Parte 8: Aplicación - usando f.g. para calcular r-combinaciones directamente Parte 9: Número de multiconjuntos Parte 10: Contando selección de objetos de distinto tipo		Diapositivas
10	Clase 19: Conceptos básicos sobre grafos	Parte 1: Introducción Parte 2: Aplicaciones Parte 3: Teorema de los saludos Parte 4: Familia de grafos relevantes		Diapositivas
11	Clase 20: Representación, subgrafos, isomorfismo y conectividad de grafos	Parte 1: Representación de grafos Parte 2: Subgrafos Parte 3: Isomorfismos Parte 4: Caminos Parte 5: Conectividad de grafos no dirigidos Parte 6: Conectividad de grafos dirigidos Parte 7: Caminos, Isomorfismos e invariantes Parte 8: Ejercicios propuestos		Diapositivas
12	Clase 21: Caminos y circuitos Eulerianos	Parte 1: Introducción a circuitos Eulerianos Parte 2: Caracterización Parte 3: Aplicación de la caracterización Parte 4: Generalización a caminos Eulerianos y grafos dirigidos		Diapositivas
12	Clase 22: Caminos más cortos y colorabilidad	Parte 1: Introducción a caminos más cortos Parte 2: Algoritmo de Dijkstra, informal Parte 3: Dijkstra, precisiones y descripción formal Parte 4: Dijkstra en grafos dirigidos/multigrafos. Simulador online Parte 5: Colorabilidad en grafos, definición y ejercicios Parte 6: Aplicaciones de colorabilidad Parte 7: El problema de los 4 colores		Diapositivas
13	Clase 23: Introducción a Árboles	Parte 1: Aplicaciones Parte 2: Definición Parte 3: Caracterizaciones alternativas Parte 4: Árboles con raíz		Diapositivas
13	Clase 24: Árboles generadores	Parte 1: Árboles generadores, conceptos básicos Parte 2: Cuándo existe árbol generador Parte 3: Algoritmos para árboles generadores: DFS Parte 4: Algoritmos para árboles generadores: BFS Parte 5: Ejercicios DFS, BFS y relación entre árboles generadores Parte 6: Árboles generadores de costo mínimo. Algoritmo de Prim Parte 7: Árboles generadores de costo mínimo. Algoritmo de Kruskal Parte 8: Correctitud y eficiencia de Prim y Kruskal		Diapositivas

Clases Auxiliares

Semana	Tema	Video	Enunciado	Pauta	Enunciado Ejercicio	Pauta Ejercicio
2	Clase Auxiliar 1: Demostraciones en Lean	Auxiliar 1	Auxiliar 1 - Lean	Auxiliar 1 - Lean	Ejercicio 1 - Lean	Ejercicio 1 - Lean
3	Clase Auxiliar 2: Lógica proposicional	Auxiliar 2	Auxiliar 2 - PDF	Auxiliar 2 - PDF	Ejercicio 2 - PDF	Ejercicio 2 - PDF
4	Clase Auxiliar 3: Técnicas de demostración	Auxiliar 3	Auxiliar 3 - PDF	Auxiliar 3 - PDF	Ejercicio 3 - PDF	Ejercicio 3 - PDF
5	No hay clase auxiliar	--	--	--	--	--
6	No hay clase auxiliar	--	--	--	--	--
7	Clase Auxiliar 4: Inducción y Relaciones	Auxiliar 4	Auxiliar 4 - PDF	Auxiliar 4 - PDF	Ejercicio 4 - PDF	Ejercicio 4 - PDF
8	Clase Auxiliar 5: Conteo y Principio del palomar	Auxiliar 5	Auxiliar 5 - PDF	Auxiliar 5 - PDF	Ejercicio 5 - PDF	Ejercicio 5 - PDF
9	No hay clase auxiliar	--	--	--	--	--
10	Clase Auxiliar 6: Recurrencias	Auxiliar 6	Auxiliar 6 - PDF	Auxiliar 6 - PDF	Ejercicio 6 - PDF	Ejercicio 6 - PDF
11	No hay clase auxiliar	--	--	--	--	--
12	Clase Auxiliar 7: Grafos	Auxiliar 7	Auxiliar 7 - PDF	Auxiliar 7 - PDF	Ejercicio 7 - PDF	Ejercicio 7 - PDF
13	Clase Auxiliar 8: Colorabilidad y Caminos Eulerianos	Auxiliar 8	Auxiliar 8 - PDF	Auxiliar 8 - PDF	Ejercicio 8 - PDF	Ejercicio 8 - PDF

Ver el Google Calendar actualizado de las clases

Discord del curso

Para unirse al discord del curso, hagan click aquí. En él podrán realizar consultas sobre cualquier cosa del curso :D.

Bibliografía

• [1] Rosen, K.H. (2011). “Discrete Mathematics and Applications”. McGraw-Hill: 7th Ed.
• [2] Back, R-J. (2016). “Introduction to Structured Derivations”. Four Ferries Publishing.
• [3] Graham, R.L., Knuth, D.E., Patashnik, O. (1994) “Concrete Mathematics - A Foundation for Computer Science”. Addison-Wesley: 2nd Ed.
• [4] Apunte del Curso Matemáticas Discretas para la Computación. Disponible en "Material U- Cursos".
• [5] Avigad, J., Lewis, R.Y. y Van Doorn, F. (2017). "Logic and Proof”. Disponible en https://leanprover.github.io/logic_and_proof/.

Log de Cambios

2021-08-19 (por AH): Corrección menor en cálculo de nota de presentaciones de trabajo grupal para considerar punto base, y clarificación de la entrega del reporte el día Lunes de las semana de presentaciones. 2021-10-21 (por AH): Se actualizaron las reglas del trabajo grupal (para que sean coherentes con lo indicado en el blog).