Esta versión de la guía docente es provisional hasta que no finalize el periodo de edición de las guías del nuevo curso.

Logo UAB

Matemática Discreta

Código: 102772 Créditos ECTS: 6
2025/2026
Titulación Tipo Curso
Ingeniería Informática FB 1

Contacto

Nombre:
Maria Merce Villanueva Gay
Correo electrónico:
merce.villanueva@uab.cat

Equipo docente

Joan Bartrina Rapesta
Miguel Hernández Cabronero
Julián Salas Piñón
Maria Merce Villanueva Gay
Bernat Gaston Braso

Idiomas de los grupos

Puede consultar esta información al final del documento.


Prerrequisitos

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.


Resultados de aprendizaje

  1. CM01 (Competencia) Utilizar los conocimientos y habilidades relacionados con la matemática discreta para la resolución de problemas con equipos multidisciplinares
  2. KM01 (Conocimiento) Explicar procedimientos algorítmicos relacionados con los grafos, los conjuntos y la combinatoria
  3. SM01 (Habilidad) Aplicar conocimientos de grafos y combinatoria en la resolución de problemas en ingeniería informática

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.   Modelado y resolución de problemas

          6.1. Abstracción y formulación de problemas con grafos

          6.2. Ejemplos de modelado y resolución de problemas reales


Actividades formativas y Metodología

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

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 tratarán temas relacionados en profundidad: se realizarán varios ejercicios sobre algoritmos explicados en teoría aplicados a casos reales y en formato práctico. 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.


Evaluación

Actividades de evaluación continuada

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

Esta asignatura no contempla el sistema de evaluación única. 

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. 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. Es necesario obtener como mínimo 1 punto (de los 3 puntos) en cada prueba parcial para poder superar la asignatura.
  • 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 teoría o 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. La superación de los seminarios requerirá aprobar las pruebas de validación individuales vinculadas a cada práctica. En estas pruebas se evaluará la asimilación tanto de los conceptos teóricos como prácticos asociados a cada actividad. Es necesario obtener como mínimo 1 punto (de los 2.5 puntos) para poder superar la asignatura.
  • 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. Es necesario obtener como mínimo 2 puntos (de los 6 puntos) para poder superar la asignatura.

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 es necesario que la evaluación de cada una de las partes supere el mínimo exigido y que la evaluación total seacomo mínimo de 5 puntos. En caso de no superar la asignatura devido a que alguna de las actividades de evaluació no llegue a la nota mínima requerida, la nota numérica del expediente será el valor menor entre 4.5 y la media ponderada de las notas. 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.

En esta asignatura se permite el uso de tecnologías de Inteligencia Artificial (IA) exclusivamente para tareas de apoyo al aprendizaje, como la búsqueda bibliográfica o de información, la corrección de textos o el estudio personal. No se permite el uso de tecnologías de IA para la resolución de actividades entregables (es decir, prácticas, ejercicios entregables o exámenes). Cualquier trabajo que incluya fragmentos generados con IA será considerado una falta de honestidad académica y podrá conllevar una penalización parcial o total en la calificación de la actividad, o sanciones mayores en casos graves.

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


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.
  • R. J. Wilson, Introduction to graph theory. 5th edition. Pearson, 2010.

Software

Se utiliza python3 y para seguir los seminarios es necesario llevar un ordenador con un navegador web.

https://docs.python.org/3/reference/index.html

https://docs.jupyter.org/en/latest/


Grupos e idiomas de la asignatura

La información proporcionada es provisional hasta el 30 de noviembre de 2025. 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

Nombre Grupo Idioma Semestre Turno
(PAUL) Prácticas de aula 411 Catalán/Español segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 412 Catalán/Español segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 431 Catalán/Español segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 432 Catalán/Español segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 451 Catalán/Español segundo cuatrimestre tarde
(PAUL) Prácticas de aula 452 Catalán/Español segundo cuatrimestre tarde
(PAUL) Prácticas de aula 471 Catalán/Español segundo cuatrimestre tarde
(SEM) Seminarios 411 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 412 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 413 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 414 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 431 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 432 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 433 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 434 Catalán/Español segundo cuatrimestre manaña-mixto
(SEM) Seminarios 451 Catalán/Español segundo cuatrimestre tarde
(SEM) Seminarios 452 Catalán/Español segundo cuatrimestre tarde
(SEM) Seminarios 453 Catalán/Español segundo cuatrimestre tarde
(SEM) Seminarios 471 Catalán/Español segundo cuatrimestre tarde
(SEM) Seminarios 472 Catalán/Español segundo cuatrimestre tarde
(SEM) Seminarios 473 Catalán/Español segundo cuatrimestre tarde
(TE) Teoría 41 Catalán/Español segundo cuatrimestre manaña-mixto
(TE) Teoría 43 Catalán/Español segundo cuatrimestre manaña-mixto
(TE) Teoría 45 Catalán/Español segundo cuatrimestre tarde
(TE) Teoría 47 Catalán/Español segundo cuatrimestre tarde