MATEMATICA DISCRETA II 2007
Condiciones de regularidad:
Deberan aprobar dos parciales, con al menos 4 cada uno.
Ademas deberan presentar y aprobar un proyecto de programacion, que sera dado a conocer mas tarde.
Para promocionar: deben aprobar el proyecto y ademas deben aprobar cada uno de los parciales con
al menos 9. Ademas, deben inscribirse en alguna de las fechas de Junio-Julio-Agosto y VENIR el dia del examen, para el examen oral.
Fechas tentativas de los parciales: (depende de las otras materias de computacion)
24 de Abril, 2007 (DE 10:00 a 13:00)
7 de junio, 2007 (OJO: la fecha ha sido cambiada para el 12 de Junio, por compatibilidad con las otras materias) (el examen sera de 900 a 1300)
Bibliografia
Biggs: ``Matematica Discreta''
En la parte de flujo tiene basicamente solo
Edmonds-Karp, pero no lo llama asi, ni da pruebas de la complejidad.
Roberts, ``Applied Combinatorics''
Buen libro, aunque no tiene pruebas de la complejidad.
Tarjan: ``Data Structures and Network Flows''
Tiene Wave y tambien tiene una explicacion de MKM.
El Tarjan tambien tiene otro metodo, de mejor complejidad, pero
usa estrucutras de datos no triviales, y no lo veremos en clase.
Algunos .pdf de algunas clases
- El Teorema de Brooks (66K)
- En la primera clase de flujos vimos desde las definiciones basicas hasta el teorema de que existe un flujo maximal, pasando por el teorema que dice que si el valor de un flujo es igual a la capacidad de un corte, entonces el flujo es maximal.
Esa clase esta resumida AQUI (67 KB)
- Ejemplo de que FF puede no terminar nunca (32 KB)
- La prueba de la complejidad de Edmonds-Karp (46KB)
- Definicion de layered neworks, etc, y forma general de los algoritmos de tipo Dinic (39K)
- Dinic, versiones GOTO y GOTOless (21KB)
- Complejidad de Dinic (21KB)
- Descripcion de MKM (34KB)
- Ejemplo de MKM (28KB)
- Complejidad de MKM (23KB)
- Descripcion de Wave (32K)
- Un ejemplo de Wave (25K)
- Complejidad de Wave (23K)
- Algoritmo hungaro, explicacion y Teorema de complejidad (55KB)
- Algoritmo hungaro: detalles de la codificacion (68KB)
- Codificacion completa del algoritmo en C (20KB).
Es un archivo .c, con muchos muchos comentarios, espero que para
que se pueda entender mejor.
No esta bien programado, lo hice algunos anhos, las variables son todas globales por ejemplo, etc.
pero muestra bien todo lo que hablamos en clase. (al menos no tiene gotos :))
Ejercicio: hacerlo bien, como Dios (i.e. Javier) manda.
- PNP(141K) (esta escrito como lo di el anho pasado. La prueba de que 3-color es NP completo que di este anho me parece que es un poco mas legible, pero no tenia ganas de tipearla de vuelta. :)
- Teorema de Hall (NUEVO)
- Teoricos sobre la matriz de chequeo (NUEVO)
- Codigos Ciclicos(NUEVO)
- Cuerpos Finitos (pero sin Reed-Solomon) (NUEVO)
Practicos
PROYECTO
El proyecto debe ser presentado antes o durante la semana del 15 de Mayo. (en C).
Pueden hacer equipos de hasta 5 personas. Deberan implementar Dinic, ademas de un programa que
genere networks al azar, y un programa que use estos dos programas para testear la velocidad
de su programa (o la velocidad del programa de algun otro equipo).
Luego hare una competencia entre los distintos equipos que hayan aprobado el proyecto.
Los miembros del equipo con el programa mas rapido tendran un punto extra en el final.
Aqui (23 KB) pueden ver las especificaciones del proyecto.
CLASES DE CONSULTA
Primera clase: viernes 22 de junio, a las 1100.
Pasar por mi oficina y buscamos algun aula libre.
Segunda Clase:
Lunes 2 de Julio, de 1200 a 1430, en el aula 10.
Si no veo a nadie, me voy a mi oficina, busquenme alli.
TERCERA CLASE
Miercoles 25 de Julio, de 1400 a 1600.
AULA 26