Logo UAB
2021/2022

Matemática Discreta

Código: 102772 Créditos ECTS: 6
Titulación Tipo Curso Semestre
2502441 Ingeniería Informática FB 1 2
La metodología docente y la evaluación propuestas en la guía pueden experimentar alguna modificación en función de las restricciones a la presencialidad que impongan las autoridades sanitarias.

Contacto

Nombre:
Mercè Villanueva Gay
Correo electrónico:
Merce.Villanueva@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

Equipo docente

Joaquim Borges Ayats
Joan Bartrina Rapesta
Mercè Villanueva Gay
Bernat Gaston Braso

Prerequisitos

No hay requisitos previos. En cualquier caso es recomendable que el estudiante domine los temas más básicos del álgebra fundamental como la teoría de conjuntos y aplicaciones.

Objetivos y contextualización

La Matemática Discreta es el área de las matemáticas dedicada al estudio de objetos discretos. Algunos de los temas que aborda son: combinatoria, teoría de grafos, diseño y análisis de algoritmos relacionados con estos problemas, criptografía, teoría de códigos correctores de errores, optimización, etcétera. De todos estos temas, nos centraremos en: teoría básica de grafos, optimización de recorridos, algoritmos sobre grafos y complejidad de algoritmos y problemas.

Competencias

  • Adquirir hábitos de pensamiento.
  • Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.
  • Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.

Resultados de aprendizaje

  1. Calcular la complejidad computacional de los algoritmos en grafos.
  2. Comprender las propiedades básicas de los grafos dirigidos y no dirigidos.
  3. Comprender y dominar la matemática discreta, la lógica y la complejidad, desde un punto de vista matemático.
  4. Conocer y aplicar los métodos matemáticos de deducción y demostración.
  5. Demostrar la capacidad de aplicación de la optimización de recorridos en grafos.
  6. Desarrollar un pensamiento y un razonamiento crítico.
  7. Identificar y reconocer los algoritmos básicos de recorridos de grafos.
  8. Reconocer e identificar los modelos matemáticos de un problema de ingeniería.

Contenido

1. Conceptos previos: conjuntos, funciones y complejidad de algoritmos

         1.1. Conjuntos y operaciones con conjuntos

         1.2. Producto cartesiano y relaciones binarias

         1.3. Elementos de combinatoria

         1.4. Conjuntos finitos, infinitos y numerables

         1.5. Complejidad de algoritmos y problemas

         1.6. Funciones de complejidad. Complejidad polinómica y no polinómica

2.    Fundamentos de grafos

         2.1. Definiciones. Variantes de grafos

         2.2. Caminos, circuitos y distancias

         2.3. Grados y lema de los grados

         2.4. Subgrafos y tipos importantes de grafos

         2.5. Secuencias gráficas (Havel-Hakimi)

         2.6. Representación de grafos

3.    Rutas, caminos y árboles generadores óptimos

         3.1. Exploración de grafos (DFS y BFS)

         3.2. Camino de costo mínimo (Dijkstra, Floyd)

         3.3. Caracterización de árboles

         3.4. Árboles generadores óptimos (Kruskal)

4.    Planaridad y coloración

         4.1. Resultados básicos

         4.2. Caracterización de grafos planarios

         4.3. Coloración de grafos planarios

         4.4. Anexo: el polinomio cromático

5.    Grafos eulerianos y grafos hamiltonianos

         5.1. Caminos y circuitos eulerianos

         5.2. Método de Fleury (o Hierholzer)

         5.3. El problema del cartero chino

         5.4. Caminos y circuitos hamiltonianos

         5.5. El problema del viajante de comercio

6.    Complejidad computacional

          6.1. Problemas de decisión, cálculo y optimización

          6.2. Problemas resolubles e irresolubles

          6.3. Clases de complejidad. Problemas NP-completos

          6.4. Otros problemas intractables

Metodología

Las clases de teoría se basarán en clases magistrales, aunque se tratará de promover la participación del estudiante en la resolución de cálculos complejos, ejemplos, etcétera. En las clases de problemas, se seguirá una lista de ejercicios. Se promueve que los estudiantes intenten solucionar los ejercicios antes. Se promoverá también la exposición de la resolución de los problemas por parte de los estudiantes. En los seminarios se abordarán temas en profundidad: posición de casos reales, será un proyecto de grupo que relaciona páginas web y teoría de grafos. Se utilizará el Campus Virtual como medio de comunicación entre el profesorado y los estudiantes (material, actualizaciones, noticias, etc.)

Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.

Actividades

Título Horas ECTS Resultados de aprendizaje
Tipo: Dirigidas      
Clases de ejercicios 15 0,6 3, 2, 4, 5, 7, 8
Clases de teoría 30 1,2 1, 3, 2, 4, 5, 7, 8
Seminarios 5 0,2 3, 2, 6, 7, 8
Tipo: Supervisadas      
Preparación de ejercicios y seminarios 12,5 0,5 1, 3, 2, 4, 5, 6, 7, 8
Tutorías y consultas 5 0,2 1, 3, 2, 4, 5, 6, 7, 8
Tipo: Autónomas      
Preparación del examen final 25 1 1, 3, 2, 4, 5, 7, 8
Trabajo personal 50 2 1, 3, 2, 4, 5, 7, 8

Evaluación

Las fechas para la avaluación continuada se publicarán en el Campus Virtual. Si se produce algún cambio de programación en las fechas, éste será comunicado a los estudiantes a través del Campus Virtual (CV), puesto que se entiende que el CV es el mecanismo habitual de comunicación entre el profesorado y los estudiantes.    

La evaluación del curso, de 10 puntos, será de la siguiente forma:

  • Dos exámenes parciales durante el curso (3+3), 6 puntos. Como parte de la avaluación continuada, el primer parcial se realizará durante las clases; y el segundo será en la fecha especificada por el coordinador. El primer parcial será al final de los tres primeros temas, y el segundo al final de curso. Estas pruebas individuales consistirán en mayor parte en ejercicios del estilo de los que se han realizado durante el curso. Una parte más pequeña constará de cuestiones teóricas.
  • Pruebas basadas en ejercicios en las clases de problemas, 1,5 puntos. Como parte de la avaluación continuada, se tratará de solucionar cuestionarios (pueden ser online) y problemas mediante la aplicación de algoritmos vistos. Las actividades o ejercicios que no sean online se realizaran durante las clases de problemas.
  • Evaluación continua de seminarios, 2.5 puntos. Se tratará de evaluar las actividades desarrolladas de forma tutorizada en estos seminarios. Los alumnos deberán presentar los ejercicios realizados en grupo durante las sesiones. Además, habrá una entrega individual.
  • Examen final, 6 puntos. Aquellos estudiantes que no hayan superado la asignatura a través de los dos exámenes parciales, tendrán la opción de realizar un examen final de recuperación. No existe la posibilidad de recuperar los exámenes parciales por separado, el examen final cubre todos los temasdel curso. Consistirá en mayor parte en ejercicios del estilo de los que se han realizado durante el curso; y una parte más pequeña constará de cuestiones teóricas.

Sin perjuicio de otras medidas disciplinarias oportunas y de acuerdo con la normativa académica vigente, las irregularidades cometidas por un estudiante que puedan conducir a una variación de la calificación se calificarán con un cero (0). Las actividades de evaluación calificadas de esta forma y por este procedimiento no serán recuperables. Si es necesario superar cualquiera de estas actividades de evaluación para superar la materia, este curso se suspenderá directamente, sin oportunidad de recuperar en el mismo curso. Las irregularidades contempladas incluyen, entre otras:

  1. la copia parcial o total de cualquier actividad de evaluación;
  2. permitir a otros copiar;
  3. presentar un trabajo en grupo que no haya sido realizado enteramente por los miembros del grupo;
  4. presentar cualquier material preparado por otra persona como si fuera propio, incluso si estos materiales son traducciones o adaptaciones, incluyendo trabajos que no son originales o exclusivos del estudiante;
  5. disponer de dispositivos de comunicación (como por ejemplo teléfonos móviles, relojes inteligentes, etc.) accesibles durante la realización de los exámenes individuales teóricos o prácticos.   

Para superar la asignatura se requiere una puntuación de como mínimo 5 puntos. Si un estudiante se presenta a cualquiera de las pruebas parciales ya no puede ser considerado como "no evaluable". Si un estudiante se presenta al examen final tampoco puede ser considerado como “no evaluable”. No habrá ningún tratamiento especial para los estudiantes repetidores, salvo que la nota de los seminarios podrá ser convalidada del año anterior. Se otorgará la calificación "matrícula de honor" a todos aquellos estudiantes que tienen un excelente y entren dentro del porcentaje de la normativa para las mejores notas, con prioridad para aquellos que no hacen el examen de recuperación.

En el caso de las pruebas basadas en resoluciones de ejercicios, se puede solicitar una revisión después de la fecha de la actividad o la fecha de cierre de la prueba. Para todas las demás actividades de evaluación, se indicará el lugar, la fecha y la hora de la revisión, lo que permitirá a los estudiantes revisar la actividad. Si los estudiantes no participan en esta revisión, no habrá más oportunidades disponibles.

Normativa de evaluación de la UAB, aprobada por el Consejo de administración de la Universidad Autónoma de BARCELONA (30/09/2010): http://webs2002.uab.es/afers_academics/info_ac/0041.htm

Actividades de evaluación

Título Peso Horas ECTS Resultados de aprendizaje
Dos pruebas parciales 60% 3 0,12 1, 3, 2, 4, 5, 7, 8
Pruebas basadas en ejercicios en la classe de problemas 15% 0,5 0,02 3, 2, 4, 5, 7, 8
Pruebas en grupo en seminarios 25% 4 0,16 3, 2, 6, 7, 8

Bibliografía

  • J.M. Basart. Grafs: fonaments i algorismes. Manuals de la UAB, 13. Servei de publicacions de la UAB, 1994.
  • C. Berge. Graphs. North-Holland, 1991.
  • N.L. Biggs. Matemàtica discreta. Vicens-Vives, 1994.
  • N. Christofides. Graph theory, an algorithmic approach. Academic Press, 1975.
  • M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-Completeness. W.H. Freeman, 1979.
  • F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
  • J. Gimbert, R. Moreno, J.M. Ribó, M. Valls. Apropament a la teoria de grafs i als seus algorismes. Eines 23, edicions de la UdL, 1998.

Software

No se utiliza ninún software.