Logo UAB

Matemática Discreta

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

Contacto

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

Equipo docente

Joaquin Borges Ayats
Joan Bartrina Rapesta
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.


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


Actividades formativas y Metodología

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

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 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

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. 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. 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 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. 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.

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.

Software

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


Lista de idiomas

Nombre Grupo Idioma Semestre Turno
(PAUL) Prácticas de aula 411 Catalán segundo cuatrimestre manaña-mixto
(PAUL) Prácticas de aula 412 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
(SEM) Seminarios 411 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 431 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 432 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 433 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 434 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 451 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 452 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 453 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 471 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 472 Catalán segundo cuatrimestre manaña-mixto
(SEM) Seminarios 473 Catalán segundo cuatrimestre manaña-mixto
(TE) Teoría 41 Catalán 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