Materia	Carrera	Plan	Año	Periodo
MATEMATICA DISCRETA	PROF.MATEM.	010/09	2011	2° cuatrimestre

Docente	Función	Cargo	Dedicación
JAUME, DANIEL ALEJANDRO	Prof. Responsable	P.Adj Exc	40 Hs
CANCELA, ELIAS DAMIAN	Auxiliar de Práctico	A.2da Simp	10 Hs
VIDELA GUZMAN, DENIS EDUARDO	Auxiliar de Práctico	A.2da Simp	10 Hs

Una de las principales razones para el estudio de los temas que conforman esta asignatura es la abundancia de aplicaciones que se encuentran en Ciencias de la Computación y en Matemáticas, en particular en las áreas de estructuras de datos, la teoría de lenguajes de computación y el análisis de algoritmos. Matemática Discreta es una asignatura que contiene temas de álgebra, combinatoria, teoría elemental de grafos, y teoría elemental de números que son necesarios para posteriores estudios en ambas carreras

Uno de los objetivos principales es que el alumno se familiarice con la forma de trabajo en matemáticas y alcance cierta experiencia en los distintos métodos de demostración y las técnicas de los métodos discretos. Se espera que, finalizado el curso, además de las habilidades técnicas el alumno haya adquirido los conocimientos básicos de cada uno de los temas del programa, los cuales se han planificado en el nivel más adecuado para su mejor aprovechamiento teniendo en cuenta que el estudio de la Matemática Discreta requiere cada vez mayor nivel de madurez matemática.

Unidad Nº 1: Congruencias
Buen orden. Teorema de la División. Bases. Máximo común divisor. Algoritmo de Euclides. Identidad de Bezout. Teorema fundamental de la aritmética. Notación exponencial. Ecuaciones Diofánticas lineales. Congruencias módulo m: propiedades, criterios de divisibilidad. Teorema de Wilson.

Unidad Nº 2:Permutaciones y combinaciones
Principio de la adición. Principio de la multiplicación. Principio de la división. Pruebas biyectivas. Principio de promedio. Conteo doble: lema de los saludos. Permutaciones. Permutaciones circulares. Combinaciones. Multiconjuntos. Permutaciones y combinaciones sobre multiconjuntos.

Unidad Nº 3: Principios de palomar y coeficientes binomiales.
Forma débil del principio del palomar. Teorema de Erdös-Zsekeres. Teorema Chino del Resto. Forma fuerte del principio del palomar. Aplicaciones del principio del palomar. Coeficientes binomiales. Fórmula de Pascal. Triángulo de Pascal. Simetría de los coeficientes de binomiales. Teorema del Binomio. Identidades. Teorema multinomial. Teorema binomial de Newton.

Unidad Nº 4: Principio de Exclusión-inclusión y Recursividad
Principio de inclusión-exclusión. Combinaciones con repetición. Desarreglos. Permutaciones con posiciones prohibidas. Sucesiones especiales. Recursiones lineales homogéneas. Recursiones lineales no-homogéneas. Funciones generatrices. Aplicaciones.

Unidad Nº 5: Grafos
Grafos. Propiedades básicas: orden, tamaño, grado. Caminatas, senderos y caminos. Ciclos. Estructura: cortes por vértices, por lados. Bloques. Árboles: caracterizaciones propiedades básicas. Menores y contracciones.

Unidad Nº 6: Conectividad
Conectividad. Conectividad por lados. 2 y 3 conectividad. Teorema de Menger. Teorema de Mader. Vulnerabilidad de grafos: dureza, integridad, grado de ruptura, número de dispersión y tenacidad.

Unidad Nº 7: Eulerianidad, Hamiltonicidad y Planaridad
Grafos y dígrafos Eulerianos. Subeulerianidad. Supereulerianidad. Grafos y dígrafos Hamiltonianos. Hamiltonicidad y dureza, conjetura de Chvátal. Condiciones tipo Ore. Resultados tipo Dirac. Hamiltonicidad y sucesiones de grados. Grafos de Línea. Grafos Potencias. Fórmula de Euler. Caracterización de Grafos Planares. Hamiltonicidad y planaridad. Número de cruce. Genus de un grafo. Máximo genus de un grafo.

Unidad Nº 8: Coloreo y Matching
Coloreo de vértices. Número cromático. Teorema de Nordhaus-Gaddum. Coloreo de lados. Teorema de Vizing. Teorema de Berge-Fournier. Matchings. Conjuntos independientes de vértices. Número de independencia. Matching in grafos bipartitos. Propiedades de grafos bipartitos. Teorema de Hall. Sistema de distintos representantes. Empaquetamientos y cubrimientos.

Unidad Nº 9: Posets y Lattices.
Relaciones. Relaciones de Equivalencia. Ordenes. Dualidad. Ordenes lineales. Posets. Teorema de Dilworth. Unimodalidad. Teorema de Sperner. Sistemas independientes. Lattices.

Resolver problemas de aplicación de cada unidad. Se pretende que el alumno use el conocimiento adquirido y sea capaz de:
- Describir e interpretar la situación estableciendo relaciones entre los datos del problema
- Seleccionar y aplicar algún método, propiedad, técnica, etc.
- Obtener las conclusiones que se piden en el problema.
- Comunicar las soluciones de forma oral y escrita.

Habrá dos parciales, calificados de 0 a 10. Con sendos recuperatorios y un recuperatorio general (en el que sólo se puede recuperar uno de los parciales).
La materia es por promoción sin examen. Para acceder a la misma se debe aprobar los parciales de primera instancia o en el primer recuperatorio con 7 (siete o más). El uso del recuperatorio general automáticamente excluye la posibilidad de promoción. Para acceder a la condición de regular y tener derecho a rendir un examen final de carácter teórico en las mesas que para tal fin disponga la Facultad el alumno debe obtener 6 (seis) en cada parcial, en cualquiera de sus instancias. Cabe destacar que la nota que vale es la de la última instancia, i.e., si un alumno saca 6,50 (seis cincuenta) de primera instancia, y luego saca 5,50 en el recuperatorio correspondiente y finalmente 4 (cuatro) en el general, la nota final asociada al parcial correspondiente es 4 (cuatro).

[1] 1. Chartrand & Lesniak. Graphs & Digraphs. 3rd ed. Chapman & Hall. 1996.
[2] 2. Diestel. Graph Theory. 3rd. Ed. Springer-Verlag. 2006.
[3] 3. Bollobás. Modern Graph theory. Springer-Verlag. 1998.N
[4] 4. Brualdi, R. Introductory Combinatorics. 3th Edition. Prentice Hall.
[5] 5. Jukna, Stasys. Extremal Combinatorics, with applications in computer science. Springer. 2001

[1] 1. Bollobás. Extremal Graph Theory. Dover. Reprint 2004.
[2] 2. Asratian, Denley y Häggkvist. Bipartite Graphs and their Applications. Cambridge University Press 1998.

Uno de los objetivos principales es que el alumno se familiarice con la forma de trabajo en matemáticas y alcance cierta experiencia en los distintos métodos de demostración y las técnicas de los métodos discretos. Se espera que, finalizado el curso, además de las habilidades técnicas el alumno haya adquirido los conocimientos básicos de cada uno de los temas del programa.

Unidad Nº 1: Congruencias

Unidad Nº 2:Permutaciones y combinaciones

Unidad Nº 3: Principios de palomar y coeficientes binomiales.

Unidad Nº 4: Principio de Exclusión-inclusión y Recursividad

Unidad Nº 5: Grafos

Unidad Nº 6: Conectividad

Unidad Nº 7: Eulerianidad, Hamiltonicidad y Planaridad

Unidad Nº 8: Coloreo y Matching

Unidad Nº 9: Posets y Lattices.