MATEMATICA DISCRETA II 2019

CLASE DE CONSULTA PARA EL PRIMER FINAL: Miercoles 3 de Julio de 2019, 1430hs, en el pasillo al lado del aula 16.

Condiciones de regularidad:
  • Deberan aprobar dos parciales, con al menos 4 cada uno. Hay recuperatorios de cada uno, los cuales se toman el mismo dia, al final del cuatrimestre.
  • Primer parcial, como dijimos en clase, es el 3 de mayo. Hora: 14hs a 18hs.
  • SE DEBE USAR LAPICERA AZUL O NEGRA o LAPIZ DE TRAZO GRUESO. Si no se puede leer, no se corrige.
  • Segundo parcial viernes 14 de junio de 14 a 18hs.
  • Entrega de notas del segundo parcial: miercoles 19 de junio, de 16 a 18hs. (antes se da el teorico)
  • Recuperatorios de los parciales: viernes 21 de junio.

    Practicos

  • El primer práctico (coloreo de grafos y repaso de DFS,BFS)
  • El Práctico 2 es el mismo que el del 2016.
  • El práctico 3 es el mismo del 2015.
  • Práctico 4 (códigos).
  • práctico 5 (matching) (es el práctico 4 del 2018 y 6 del 2016).
  • el práctico 6 (de Dinitz (Dinic-Even)) es el practico 4 del 2015.
  • El práctico 7, de códigos ciclicos. HASTA ESTE PRACTICO (incluido) LLEGA EL SEGUNDO PARCIAL.
  • práctico de Wave
  • El práctico de Genéticos es el mismo que el del 2016.

    Proyecto

  • Deberán presentar y aprobar un proyecto de programación.

    Acá esta el proyecto de este año.

    CAMBIO EN una de las condiciones del Proyecto

  • En el documento se dice que solo se podran hacer grupos individuales o de dos personas.
  • Ante algunos pedidos hemos decidido permitir grupos de tres personas BAJO CIERTAS CONDICIONES
  • Esas condiciones las detallaremos el viernes 15 de marzo, pero esencialmente:
  • Si participaron de la competencia ACM interna de Famaf del año pasado, pueden hacer grupo de 3.
  • Si no, pueden formar equipo de 3, pero pediremos algún involucramiento en la ACM. Solo pediremos que se inscriban al curso y vayan a dos clases, o bien vayan a una clase y participen de alguno de los torneitos internos que se organizan.

    Grafos de ejemplos>

    Link activado: Acá hay varios,incluyendo los de testeo obligatorio

    En http://mat.gsia.cmu.edu/COLOR/instances.html hay muchos ejemplos, pero en algunos de ellos el supuesto número de vertices es solo una cota superior del número real de vertices y en otros casos hay lados xz y lados zx. Asi que en esta pagina encontrarán copias de algunos de esos grafos, a los cuales se les ha reescrito el numero de vertices correcto o se les ha eliminado los lados repetidos.

    Teóricos para el final

    Todavia no los decidí pero si quieren ir estudiando, los que entran seguro (ademas de otros) son:
  • los teoremas de las complejidades de Edmonds-Karp, Dinic y Wave
  • 3-Color es NP completo. (este teorema se tomará en TODOS los finales)
  • Hall
  • Matrimonio
  • cota de Hamming
  • el teorema que relaciona la cantidad de columnas LD de H con delta.
  • Max Flow Min Cut.
  • El teorema sobre que un código cíclico esta formado por los múltiplos del generador (del grado adecuado) y que el grado de este es n-k.

    Link activado: Acá esta la lista completa

    NUEVO (Enero 2020)

    El teorema de Brooks para el caso G NO regular no se tomará en las fechas de Febrero. (el caso regular puede o no tomarse)