Matemática Discreta y Algorítmica
Código: 107928Créditos: 6
| Titulación | Tipo | Curso |
|---|---|---|
| Matemáticas | OB | 2 |
Profesor/a de contacto
- Nombre :
- Joaquim Roé Vellvé
- Correo electrónico :
- joaquim.roe@uab.cat
Equipo docente
- Laura Brustenga Moncusi
- Guillem Quingles Daví
Idiomas de los grupos
Puede consultar esta información al final del documento.
Prerrequisitos
Àlgebra Lineal I y II y Fonaments de les Matemàtiques I y II.
Objetivos
La Matemática Discreta es la rama de las matemáticas dedicada al estudio de estructuras finitas. Entre los temas de que se ocupa se encuentran la combinatoria, la teoría de grafos, la criptografía y la teoría de códigos, los diseños combinatorios, y el diseño y análisis de algoritmos para resolver problemas en estos ámbitos. La mayor parte de estos temas ha experimentado un desarrollo relativamente reciente, impulsado principalmente por problemas surgidos en la informática y la optimización. Se trata de áreas en gran medida independientes entre sí y, en un curso introductorio, sólo requieren como conocimientos previos álgebra lineal, aritmética modular, combinatoria básica y, sobre todo, el dominio del lenguaje y del razonamiento matemáticos.
El curso comienza con el estudio de funciones generadoras y relaciones de recurrencia. Este tema constituye una continuación natural de contenidos introducidos en las asignaturas de Fundamentos de las Matemáticas de primer curso y permite desarrollar la capacidad de traducir enunciados de problemas al lenguaje matemático y algorítmico. A continuación, se introduce la teoría de grafos, una herramienta fundamental para modelizar y resolver problemas en ámbitos muy diversos, desde las matemáticas más abstractas hasta la investigación operativa. En muchos casos, la simple traducción de un problema al lenguaje de los grafos proporciona una comprensión más clara del mismo y conduce a estrategias de resolución muy eficaces. No obstante, en esta asignatura solo se realizará una introducción a esta materia.
La tercera parte del curso está dedicada a la optimización combinatoria, disciplina que aborda problemas combinatorios en los que el objetivo no es contar objetos de un determinado tipo, sino identificar aquellos que son óptimos según un criterio establecido. En este contexto, las respuestas no consisten en fórmulas cerradas, sino en algoritmos capaces de encontrar o aproximar soluciones óptimas. Las principales herramientas matemáticas empleadas serán el álgebra lineal y la teoría de matroides.
A lo largo del curso se presentarán diversos ejemplos de aplicaciones de las matemáticas en los que, mediante herramientas relativamente sencillas y una considerable dosis de ingenio matemático, se resuelven problemas interesantes y complejos. Asimismo, a través de los ejercicios de combinatoria y optimización, el estudiantado desarrollará una de las competencias fundamentales de la modelización matemática: comprender un problema y traducirlo a un lenguaje matemático adecuado para su resolución.
Resultados de aprendizaje
- CM14 (Reformular problemas reales como problemas de programación matemática.) Reformular problemas reales como problemas de programación matemática.
- CM15 (Plantear problemas de ordenación y enumeración, utilizando técnicas eficientes pera su resolución.) Plantear problemas de ordenación y enumeración, utilizando técnicas eficientes pera su resolución.
- KM22 (Identificar los resultados básicos de teoría combinatoria.) Identificar los resultados básicos de teoría combinatoria.
- KM23 (Identificar algoritmos elementales de resolución de problemas en grafos.) Identificar algoritmos elementales de resolución de problemas en grafos.
- KM24 (Identificar los algoritmos elementales de la programación lineal.) Identificar los algoritmos elementales de la programación lineal.
- SM18 (Resolver problemas de programación lineal, mediante los principales métodos de resolución (método simplex, método de las dos fases, método de puntos interiores).) Resolver problemas de programación lineal, mediante los principales métodos de resolución (método simplex, método de las dos fases, método de puntos interiores).
- SM19 (Utilizar técnicas computacionales en la resolución de problemas de optimización. (método del simplex, método del gradiente, etc.)) Utilizar técnicas computacionales en la resolución de problemas de optimización. (método del simplex, método del gradiente, etc.)
Contenidos
- Funciones generadoras y successiones recurrentes.
- Definición de función generadora. Técnicas de cálculo. Resolución de problemas combinatorios con funciones generadoras.
- Successiones recurrentes. Resolución de relaciones de recurrencia con funciones generadoras.
- Algoritmos y complejidad.
- Grafos.
- Definición. Algunos modelos matemáticos con grafos.
- Terminologia básica. Invariantes e isomorfismos de grafos.
- Caminos, circuitos y árboles.
- Optimitzación combinatoria.
- Algoritmos de búsqueda y ordenación
- Matroides
- Optimitzación en grafos.
Actividades formativas y Metodología
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Clases de teoría | 26 | 1,04 | CM14, CM15, KM22, KM23, KM24, SM18 |
| Resolución autónoma de problemas | 26,25 | 1,05 | CM14, CM15, KM22, KM23, KM24, SM18, SM19 |
| Estudio de la teoría | 31,25 | 1,25 | CM14, CM15, KM22, KM23, KM24 |
| Seminarios | 16 | 0,64 | CM14, CM15, KM22, KM23, KM24, SM18, SM19 |
| Prácticas de ordenador | 8 | 0,32 | CM15, KM23, KM24, SM18, SM19 |
| Preparación de la presentación oral | 31,25 | 1,25 | CM14, CM15, KM22, KM23, KM24, SM18 |
El trabajo presencial constará de:
- Teoria. El profesor expondrá los fundamentos teóricos y algunas demostraciones del curso. La exposición de algunos temas concretos o aplicaciones de la teoría correrán a cargo del alumnado: en una sesión de teoría se propondrán varios temas. En equipos de tres o cuatro estudiantes se escogerá un tema a estudiar de forma autónoma. El resultado del estudio se presentará por escrito y también oralmente a la clase.
- Seminarios. Se dispondrá de listas de problemas que el estudiantado debe trabajar antes de las sesiones de clase para sacar provecho de la discusión.
- Prácticas de ordenador con el software SageMath. Las tres primeras sessiones corresponderán a los tres temas. La quarta sesión incluirá ejercicios de los tres temas y será evaluable.
Nota: se reservarán 15 minutos de una clase, dentro del calendario establecido por el centro/titulació, para rellenar las encuestas de avaluación de la actuación del profesorado y de evaluación de la asignatura.
Evaluación
Actividades de evaluación continuada
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Práctica evaluable | 0.2 | 2 | 0,08 | CM14, KM23, KM24, SM18, SM19 |
| Presentación oral | 0.2 | 0,25 | 0,01 | CM14, CM15, KM22, KM23, KM24 |
| Examen parcial | 0.25 | 3 | 0,12 | CM14, CM15, KM22 |
| Examen final | 0.35 | 3 | 0,12 | CM14, CM15, KM22, KM23, KM24, SM18 |
| Examen de recuperación | 0.6 | 3 | 0,12 | CM14, CM15, KM22, KM23, KM24 |
Hay cuatro actividades evaluables: un examen parcial, una presentación oral, una práctica evaluable y un examen final. La evaluación de la asignatura se realizará según la siguiente fórmula: 0,25 × nota del examen parcial + 0,20 × nota de la presentación oral + 0,20 × nota de la práctica evaluable + 0,35 × nota del examen final.
Evaluación recuperable: se realizará una recuperación de los dos exámenes (60 %). Para poder presentarse a la recuperación será necesario haber participado en tres de las cuatro actividades evaluables del curso.
La calificación de «No evaluable» se asignará cuando un estudiante haya participado en dos o menos actividades evaluables y ninguna de ellas sea el examen final.
Tras el examen final se otorgarán las matrículas de honor que se consideren claramente justificadas. Estas matrículas serán definitivas. Si no se hubiera alcanzado el número máximo de matrículas de honor permitido, se reconsiderará la posibilidad de conceder más tras el examen de recuperación, al que los estudiantes podrán presentarse para mejorar su calificación de la asignatura.
Para la evaluación de esta asignatura, se permite el uso de tecnologías de "Inteligencia Artificial" (IA) exclusivamente en la preparación de la presentación oral, como herramienta de apoyo para tareas tales como la búsqueda bibliográfica o de información, la corrección de textos o las traducciones. El estudiantado deberá identificar claramente qué partes han sido generadas con esta tecnología, especificar las herramientas utilizadas e incluir una reflexión crítica sobre cómo estas han influido en el proceso y en el resultado final de la actividad. La falta de transparencia en el uso de la IA en esta actividad evaluable se considerará una falta de honestidad académica y podrá conllevar una penalización parcial o total en la calificación de la actividad, o sanciones de mayor entidad en los casos de mayor gravedad. En las actividades de evaluación presencial no se permite el uso de ninguna ayuda externa, ya sea basada en IA o de cualquier otro tipo.
Bibliografía
Bibliografia general:
- Basart, J.M, Rifà, J i 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.
- Lawler, Eugene. "Combinatorial Optimization: Networks and Matroids". Dover. ISBN 0-486-41453-1. (2001)
Grafos:
- Bondy, J.A. i Murty, U.S.R. "Graph Theory". Springer. 2008.
- Wilson, R.J. i Watkins, J. "Graphs: an introductory approach: a first course in discrete mathematics". Wiley, cop. New York. 1990.
Optimización:
- Alabert, A i Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
- Cormen, Thomas H.; Leiserson, Charles Eric.; Rivest, Ronald L., "Introduction to algorithms", Cambridge Mass. etc. : MIT Press cop. 1990
- Gordon, Gary.; McNulty, Jennifer, "Matroids : a geometric introduction", Cambridge University Press, 2012
Software
Python, SageMath.
Grupos e idiomas de la asignatura
La información proporcionada es provisional hasta el 30 de noviembre. A partir de esta fecha, podrá consultar el idioma de cada grupo a través de este enlace. Para acceder a la información, será necesario introducir el CÓDIGO de la asignatura
| Tipo de docencia | Grupo | Idioma | Semestre | Turno |
|---|---|---|---|---|
| (TE) Teoría | 1 | Catalán | primer cuatrimestre | manaña-mixto |
| (PLAB) Prácticas de laboratorio | 1 | Catalán | primer cuatrimestre | manaña-mixto |
| (SEM) Seminarios | 1 | Catalán | primer cuatrimestre | manaña-mixto |
| (PLAB) Prácticas de laboratorio | 2 | Catalán | primer cuatrimestre | manaña-mixto |
| (SEM) Seminarios | 2 | Catalán | primer cuatrimestre | manaña-mixto |
| (PLAB) Prácticas de laboratorio | 3 | Catalán | primer cuatrimestre | manaña-mixto |