Seminario de matemática discreta
Código: 100098 Créditos ECTS: 6| Titulación | Tipo | Curso | Semestre |
|---|---|---|---|
| 2500149 Matemáticas | OB | 2 | 1 |
Contacto
- Nombre:
- Salvador Comalada Clara
- Correo electrónico:
- Salvador.Comalada@uab.cat
Uso de idiomas
- Lengua vehicular mayoritaria:
- catalán (cat)
- Algún grupo íntegramente en inglés:
- No
- Algún grupo íntegramente en catalán:
- Sí
- Algún grupo íntegramente en español:
- No
Prerequisitos
Álgebra Lineal y Fundamentos de las Matemáticas, del primer curso del Grado de Matemáticas.
Objetivos y contextualización
La matemática discreta es el área de las matemáticas dedicada al estudio de objetos finitos. Se ocupa de temas como combinatoria, grafos, criptografía, códigos correctores de errores, diseños combinatorios, teoria de juegos, lógica, optimización o diseño y análisis de algoritmos para resolver problemas en cada uno de aquellos ámbitos. La mayor parte de la matemática discreta se ha desarrollado hace relativamente poco tiempo a raíz de problemas relacionados sobretodo con la informática y la optimización. Los temas de este curso introductorio son bastante independientes entre sí y requieren solamente conocimientos de álgebra lineal, aritmética modular, combinatoria básica y, fundamentalmente, lenguaje y razonamiento matemáticos.
El curso empieza con las funciones generadoras y las sucesiones recurrentes. Se trata de una continuación natural de la combinatoria estudiada en la asignatura de primer curso Fundamentos de las Matemáticas. Los problemas de este tema requieren una vez más el ejercicio de traducir un enunciado al lenguaje matemático. Los grafos son una herramienta básica para resolver problemas de origen muy diverso, que va desde la matemática más abstracta hasta la investigación operativa. En algunos casos, la simple traducción del problema al lenguaje de los grafos ya resulta esclarecedora y muy eficaz.
El tercer tema del curso es la programación lineal, que se ocupa de optimizar funciones lineals de varias variables sujetas a restricciones lineales. En cierto sentido, no pertenece estrictamente a la matemática discreta, sin embargo es habitual que forme parte de los cursos de dicha materia. La teoría usa solamente álgebra lineal, aunque los métodos explicados seaplican a la resolución de problemas de planteo, algunos de los cuales, entre los más interesantes, requieren variables con valores enteros o binarios.
Así pues, a lo largo del curso se presentaran diferentes ejemplos de aplicaciones de las matemáticas en los que, usando herramientas relativamente simples y una buena dosis de ingenio, se resolveran problemas interesantes y difíciles. A su vez, los estudiantes podran practicar, por medio de los ejercicios de combinatoria y de optimización, la primera fase en modelización matemática: entender un problema y traducirlo al lenguaje matemático adecuado para su resolución.
Competencias
- Ante situaciones reales con un nivel medio de complejidad, recabar y analizar datos e información relevantes, proponer y validar modelos utilizando herramientas matemáticas adecuadas para, finalmente, obtener conclusiones.
- Aplicar el espíritu crítico y el rigor para validar o refutar argumentos tanto propios como de otros.
- Demostrar de forma activa una elevada preocupación por la calidad en el momento de argumentar o hacer públicas las conclusiones de sus trabajos.
- Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
- Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.
- Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
- Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
- Utilizar aplicaciones informáticas de análisis estadístico, cálculo numérico y simbólico, visualización gráfica, optimización u otras para experimentar en Matemáticas y resolver problemas.
- Utilizar eficazmente bibliografía y recursos electrónicos para obtener información.
Resultados de aprendizaje
- Aplicar el espíritu crítico y el rigor para validar o refutar argumentos tanto propios como de otros.
- Conocer el lenguaje y las aplicaciones más elementales de la teoría de grafos, así como algoritmos de resolución de problemas en grafos.
- Demostrar de forma activa una elevada preocupación por la calidad en el momento de argumentar o hacer públicas las conclusiones de sus trabajos.
- Plantear problemas de ordenación y enumeración y utilizar técnicas eficientes para su resolución.
- Plantear problemas reales como problemas de programación matemática.
- Plantear y resolver problemas de programación lineal.
- Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
- Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.
- Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
- Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
- Utilizar eficazmente bibliografía y recursos electrónicos para obtener información.
- Utilizar técnicas computacionales para resolver problemas de optimización.
Contenido
1. Funciones generadoras y sucesiones recurrentes.
- Definición de función generadora. Técnicas de cálculo. Resolución de problemas combinatorios con funciones generadoras.
- Sucesiones recurrentes. Recurrencias lineales de primer y de segundo orden.
- Resolución de relaciones de recurrencia usando funciones generadoras.
2. Grafos.
- Definición y algunos modelos matemáticos con grafos.
- Terminología básica y algunos tipos de grafos.
- Representación de grafos, isomorfismos de grafos.
- Caminos y circuitos.
- Árboles.
3. Programación lineal.
- Introducción. Ejemplos.
- El modelo. Terminología. Resultados.
- El método del simplex.
4. Seminarios de introducción muy breve a otros temas de Matemática Discreta.
- Diseños combinatorios.
- Criptografía.
- Grafos planos.
- Grafos hamiltonianos.
- Grafos aleatorios.
- Teoría de códigos.
- Teoría de Ramsey.
- Teoría de juegos.
Metodología
El trabajo presencial variará a lo largo del curso:
- Para los temas 1 y 2 constará de teoría y problemas. En las clases de problemas, los estudiantes habrán trabajado previamente las listas de problemas del curso, con el fin de poder aprovechar su discusión y resolución en clase.
- Para el tema 3 consistirá en teoría, problemas y prácticas de ordenador. En dichas prácticas se resolverán problemas de programación lineal usando el kit de programación lineal GLPK, en donde los problemas se pueden modelar en lenguaje GNU MathProg, el cual comparte muchas características con AMPL.
- Después de un mes de haber iniciado el curso, los estudiantes empezarán a trabajar en sus presentaciones. Se formarán equipos de cuatro estudiantes y cada equipo escogerá un tema acordado con el profesor. El equipo trabajará de forma autónoma, elaborando una guía de estudio del tema que contenga un índice, las definiciones y los resultados más relevantes y una bibliografía. Las dos o tres últimas semanas de clase se dedicarán a las presentaciones orales que habrán preparado los diferentes equipos.
Actividades
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Tipo: Dirigidas | |||
| Clases de teoría | 28 | 1,12 | |
| Prácticas con ordenador | 8 | 0,32 | |
| Sesiones de problemas | 16 | 0,64 | 10 |
| Tipo: Supervisadas | |||
| Entrevista sobre la preparación del tema del seminario | 1 | 0,04 | 7, 8, 9 |
| Tipo: Autónomas | |||
| Estudio personal de teoría | 26 | 1,04 | 7, 8, 10 |
| Estudio y preparación en grupo del tema que se va a presentar en el Seminario | 14 | 0,56 | 7, 8, 9 |
| Hacer problemas | 36 | 1,44 | 10 |
| Práctica autónoma con el software de programación lineal | 8 | 0,32 | 10 |
Evaluación
Hay cuatro actividades evaluables: un examen parcial, un examen de prácticas, un trabajo de seminario y un examen final.
La nota de la asignatura se calcula según la fórmula siguiente:
0.15 nota del examen parcial + 0.2 nota del examen de prácticas + 0.15 nota trabajo seminario + 0.5 nota del examen final
La prueba parcial no eliminará materia. En el caso de que un estudiante no la pueda realizar por causas médicas o de otra índole, deberá presentar una justificación válida para poder acordar otro día.
Evaluación recuperable: se recuperará solamente el examen final (50%). Para poder presentarse a la recuperación es necesario haber participado, al menos, en tres de las cuatro actividades evaluables del curso.
Se otorgará la calificación de "no presentado" a aquel estudiante que haya participado en un máximo de dos actividades evaluables, no siendo ninguna de ellas el examen final.
Después del examen final se concederán las matrículas de honor que se consideren claras. Dicha decisión será firme. Tras el examen de recuperación, donde los estudiantes pueden presentarse para mejorar nota, se reconsiderará la posibilidad de otorgar el resto de matrículas.
Actividades de evaluación
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Evaluación de la presentación oral y escrita del trabajo de seminario | 0.15 | 1 | 0,04 | 1, 3, 7, 8, 9, 10, 11 |
| Examen de prácticas | 0.2 | 2 | 0,08 | 6, 4, 12 |
| Examen de recuperación | 0.5 | 4 | 0,16 | 2, 6, 4, 5 |
| Examen final | 0.5 | 4 | 0,16 | 2, 6, 4, 5 |
| Examen parcial | 0.15 | 2 | 0,08 | 2, 6, 4, 5, 10 |
Bibliografía
Bibliografía general (excepto programación lineal):
Basart, J.M., Rifà, J., Villanueva, M. "Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica". Col. Materials de la UAB, n. 36. 1997.
Graham, R.L., Knuth, D. E., Patashnik, O. "Concrete mathematics: a foundation for computer science". Addison-Wesley. 1990.
Grimaldi, Ralph P. "Discrete and combinatorial mathematics: an applied introduction". 5th ed. Pearson.Addison-Wesley. 2004.
Rosen, Kenneth H. "Discrete mathematics and its applications", 6th ed. McGraw-Hill. 2007.
Grafos:
Bondy, J.A., Murty, U.S.R. "Graph Theory". Springer. 2008.
Wilson, R.J., Watkins, J. "Graphs: an introductory approach: a first course in discrete mathematics". Wiley, cop. New York. 1990.
Programación lineal:
Alabert, A., Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
Basart, J.M. "Programació lineal". Col. Materials de la UAB, n. 58.. 1998.
Luenberger, D. "Programación lineal y no lineal". Addison-Wesley iberoamericana. 1989.