Logo

Matemática Discreta

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

Profesor/a de contacto

Nombre :
Mercè Villanueva Gay
Correo electrónico :
merce.villanueva@uab.cat

Equipo docente

Miguel Hernández Cabronero
Joan Bartrina Rapesta
Mercè 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

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

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

Contenidos

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

  1. Conjuntos y operaciones con conjuntos
  2. Producto cartesiano y relaciones binarias
  3. Elementos de combinatoria
  4. Conjuntos finitos, infinitos y numerables
  5. Complejidad de algoritmos y problemas
  6. Funciones de complejidad. Complejidad polinómica y no polinómica

2. Fundamentos de grafos

  1. Definiciones. Variantes de grafos
  2. Caminos, circuitos y distancias
  3. Grados y lema de los grados
  4. Subgrafos y tipos importantes de grafos
  5. Secuencias gráficas (Havel-Hakimi)
  6. Representación de grafos

3. Rutas, caminos y árboles generadores óptimos

  1. Exploración de grafos (DFS y BFS)
  2. Camino de costo mínimo (Dijkstra, Floyd)
  3. Caracterización de árboles
  4. Árboles generadores óptimos (Kruskal)

4. Planaridad y coloración

  1. Resultados básicos
  2. Caracterización de grafos planarios
  3. Coloración de grafos planarios
  4. Anexo: el polinomio cromático

5. Grafos eulerianos y grafos hamiltonianos

  1. Caminos y circuitos eulerianos
  2. Método de Fleury (o Hierholzer)
  3. El problema del cartero chino
  4. Caminos y circuitos hamiltonianos
  5. El problema del viajante de comercio

6. Modelado y resolución de problemas

  1. Abstracción y formulación de problemas con grafos
  2. Ejemplos de modelado y resolución de problemas reales

Actividades formativas y Metodología

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

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 será de la siguiente forma:

  • Dos exámenes parciales durante el curso (30% + 30% de la nota final). 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 un 3 sobre 10 en cada prueba parcial para poder superar la asignatura.
  • Pruebas basadas en ejercicios en las clases de problemas (15% de la nota final). Como parte de la evaluación continua, se llevarán a cabo cuestionarios (que pueden ser online) y ejercicios de resolución de problemas mediante la aplicación de los conceptos trabajados en clase. Las actividades o ejercicios que no sean online se realizaran durante las clases de teoría o problemas. Estos ejercicios no serán recuperables.
  • Evaluación continua de seminarios (25% de la nota final). Se evaluarán las actividades en grupo desarrolladas de forma tutorizada en estos seminarios (50% de la nota). La superación de los seminarios requerirá también la aprobación de las pruebas individuales realizadas durante las sesiones (50% de la nota). En estas pruebas se evaluará la asimilación tanto de los conceptos teóricos como de los prácticos asociados a cada actividad. Para superar esta parte de la asignatura, será necesario obtener al menos un 4 sobre 10 y asistir, como mínimo, al 80% de las sesiones. En caso de no superarla, deberá realizarse una prueba individual, que representará el 100% de la calificación de esta parte, en la que también deberá obtenerse un mínimo de 4 sobre 10.
  • Examen final (60% de la nota final). 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 un 3 sobre 10 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.

El protocolo de “solicitud de reprogramación de actividades de evaluación” está disponible en la web de la Escuela de Ingeniería y es aplicable en los casos descritos en los criterios e instrucciones de evaluación del centro.

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


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 41 Español segundo cuatrimestre manaña-mixto
(TE) Teoría 43 Catalán segundo cuatrimestre manaña-mixto
(TE) Teoría 45 Catalán segundo cuatrimestre tarde
(TE) Teoría 47 Catalán segundo cuatrimestre tarde
(PAUL) Prácticas de aula 411 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 411 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 412 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 412 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 413 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 414 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 415 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 416 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 417 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 418 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 419 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 420 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 421 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 422 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 423 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 424 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 425 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 431 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 432 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 451 Catalán segundo cuatrimestre tarde
(PAUL) Prácticas de aula 452 Catalán segundo cuatrimestre tarde
(PAUL) Prácticas de aula 471 Catalán segundo cuatrimestre tarde