Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Matematicas
Área: Matematicas
(Programa del año 2014)
I - Oferta Académica
Materia Carrera Plan Año Periodo
MATEMATICA DISCRETA ING. EN COMPUT. 28/12 2014 2° cuatrimestre
MATEMATICA DISCRETA ING. INFORM. 026/12 2014 2° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
JAUME, DANIEL ALEJANDRO Prof. Responsable P.Adj Exc 40 Hs
SOTA, RODRIGO ARIEL Responsable de Práctico A.1ra Simp 10 Hs
LOPEZ ORTIZ, JUAN IGNACIO Auxiliar de Práctico A.2da Simp 10 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total C - Teoria con prácticas de aula Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
 Hs. 3 Hs. 3 Hs.  Hs. 6 Hs. 2º Cuatrimestre 19/08/2014 21/11/2014 15 90
IV - Fundamentación
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
V - Objetivos
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.
VI - Contenidos
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.

VII - Plan de Trabajos Prácticos
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.
VIII - Regimen de Aprobación
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).
IX - Bibliografía Básica
[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
X - Bibliografia Complementaria
[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.
XI - Resumen de Objetivos
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.
XII - Resumen 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.

XIII - Imprevistos