Guía docente de la asignatura
(6093) GRAFOS Y OPTIMIZACIÓN DISCRETA

Curso académico 2024/2025

  1. Identificación

    1. De la asignatura

      2. Curso Académico
      2024/2025
      Titulación
      GRADO EN MATEMÁTICAS
      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECÍFICO DE GRADO EN MATEMÁTICAS Y GRADO EN FÍSICA
      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECÍFICO DE GRADO EN MATEMÁTICAS Y GRADO EN INGENIERÍA INFORMÁTICA
      Nombre de la asignatura
      GRAFOS Y OPTIMIZACIÓN DISCRETA
      Código
      6093
      Curso
      TERCERO
      QUINTO
      CUARTO
      Carácter
      OBLIGATORIA
      Número de grupos
      3
      Créditos ECTS
      6.0
      Estimación del volumen de trabajo
      150.0
      150.0
      150.0
      Organización temporal
      2º Cuatrimestre
      2º Cuatrimestre
      2º Cuatrimestre
      Idiomas en que se imparte
      Español
      Curso Académico 2024/2025
      Titulación

      GRADO EN MATEMÁTICAS,

      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECÍFICO DE GRADO EN MATEMÁTICAS Y GRADO EN FÍSICA,

      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECÍFICO DE GRADO EN MATEMÁTICAS Y GRADO EN INGENIERÍA INFORMÁTICA
      Nombre de la asignatura GRAFOS Y OPTIMIZACIÓN DISCRETA
      Código 6093
      Curso TERCERO QUINTO CUARTO
      Carácter OBLIGATORIA
      Número de grupos 3
      Créditos ECTS 6.0
      Estimación del volumen de trabajo 150.0 150.0 150.0
      Organización temporal 2º Cuatrimestre 2º Cuatrimestre 2º Cuatrimestre
      Idiomas en que se imparte Español

    2. Del profesorado: Equipo docente

      • MARIN PEREZ, ALFREDO N. Docente: GRUPO 1, GRUPO PCEO MATE+INFORM Coordinación de los grupos: PCEO MATEMÁTICAS+FÍSICA GRUPO 1, GRUPO PCEO MATE+INFORM, Coordinador de la asignatura

        Categoría

        CATEDRATICOS DE UNIVERSIDAD

        Área

        ESTADÍSTICA E INVESTIGACIÓN OPERATIVA

        Departamento

        ESTADÍSTICA E INVESTIGACIÓN OPERATIVA

        Correo electrónico / Página web / Tutoría electrónica

        amarin@um.es http://www.um.es/or Tutoría electrónica: No

        Teléfono, horario y lugar de atención al alumnado

        Duración:
        C1         		Día:
        Viernes         		Horario:
        08:00-14:00         		Lugar:
        868883627, Facultad de Matemáticas y Aulario General B1.2.009 (DESPACHO PROF. ALFREDO MARÍN PÉREZ)
        Observaciones:
        Pedir cita por correo
        Duración:
        C2         		Día:
        Lunes         		Horario:
        17:00-19:00         		Lugar:
        868883627, Facultad de Matemáticas y Aulario General B1.2.009 (DESPACHO PROF. ALFREDO MARÍN PÉREZ)
        Observaciones:
        Pedir cita por correo
        Duración:
        C2         		Día:
        Viernes         		Horario:
        10:00-14:00         		Lugar:
        868883627, Facultad de Matemáticas y Aulario General B1.2.009 (DESPACHO PROF. ALFREDO MARÍN PÉREZ)
        Observaciones:
        Pedir cita por correo

  2. Presentación

    3. Los grafos resumen la información de un conjunto de objetos que se relacionan, o no, entre sí Si además se añade una medida de esta relación, el concepto de grafo se extiende al de red Puede modelarse mediante un grafo un mapa de carreteras o metro, una red de comunicaciones, de tendidos eléctricos, gasísticos, etcétera Pero también pueden usarse los grafos en otros casos menos obvios, como la modelización de la incompatibilidad (países con fronteras comunes no pueden colorearse de la misma forma en un mapa), del movimiento de una ficha en un juego, incluso veremos apliaciones en química y biología La Teoría de Grafos es muy extensa, y contempla muchos puntos de vista distintos En esta asignatura intentaremos, en lo posible, que el alumno tenga una visión amplia de la materia y unos conocimientos básicos suficientes que le sirvan de base para hipotéticas ampliaciones de conocimientos

    Entre los problemas más interesantes que se presentan sobre estructuras modelizables como grafos, están los de optimización discreta Estudiaremos la forma de formularlos y resolverlos como problemas de programación lineal entera y nos introduciremos en las principales técnicas subyacentes en los algoritmos utilizados comúnmente por el software específico del campo

  3. Condiciones de acceso a la asignatura

    1. Incompatibilidades

      2. No constan

    2. Requisitos

      3. No constan

    3. Recomendaciones

      4. Es recomendable haber superado la asignatura de Optimización Lineal

  4. Competencias

    1. Competencias básicas

      • CB1: Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio
      • CB2: Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio
      • CB5: Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía

    2. Competencias de la titulación

      • CG1: Ser capaz de expresarse correctamente en español en el ámbito de la Matemática.
      • CG2: Comprender y expresarse en un idioma extranjero en el ámbito de la Matemática, particularmente en inglés.
      • CG3: Ser capaz de gestionar la información y el conocimiento en el ámbito de la Matemática, incluyendo saber utilizar como usuario las herramientas básicas en TIC.
      • CG4: Considerar la ética y la integridad intelectual como valores esenciales de la práctica profesional.
      • CG6: Ser capaz de trabajar en equipo y relacionarse con otras personas del ámbito de la Matemática o cualquier otro ámbito.
      • CG7: Desarrollar habilidades de iniciación a la investigación.
      • CG8: Comprender y utilizar el lenguaje matemático. Adquirir la capacidad para enunciar proposiciones en distintos campos de la Matemática, para construir demostraciones y para transmitir los conocimientos matemáticos adquiridos.
      • CG9: Conocer demostraciones rigurosas de algunos teoremas clásicos en distintas áreas de la Matemática.
      • CG10: Asimilar la definición de un nuevo objeto matemático, en términos de otros ya conocidos, y ser capaz de utilizar este objeto en diferentes contextos.
      • CG11: Saber abstraer las propiedades estructurales (de objetos matemáticos, de la realidad observada, y de otros ámbitos) distinguiéndolas de aquellas puramente ocasionales y poder comprobarlas con demostraciones o refutarlas con contraejemplos, así como identificar errores en razonamientos incorrectos.
      • CG12: Capacitar para el aprendizaje autónomo de nuevos conocimientos y técnicas.
      • CE1: Resolver problemas de Matemáticas, mediante habilidades de cálculo básico y otras técnicas, planificando su resolución en función de las herramientas de que se disponga y de las restricciones de tiempo y recursos.
      • CE2: Proponer, analizar, validar e interpretar modelos de situaciones reales sencillas, utilizando las herramientas matemáticas más adecuadas a los fines que se persigan.
      • CE3: Utilizar aplicaciones informáticas de análisis estadístico, cálculo numérico y simbólico, visualización gráfica, optimización u otras para experimentar en Matemáticas y resolver problemas.
      • CE5: Utilizar herramientas de búsqueda de recursos bibliográficos.
      • CE6: Comunicar, tanto por escrito como de forma oral, conocimientos, procedimientos, resultados e ideas matemáticas

    3. Competencias transversales y de materia

      • Conocer y caracterizar los distintos tipos de grafos y redes
      • Resolver el problema de la conexión de un grafo, y conocer sus aplicaciones
      • Saber obtener árboles, caminos y otras subestructuras óptimas sobre redes
      • Formular problemas de optimización combinatoria de forma eficiente
      • Resolver problemas de optimización discreta mediante algoritmos de ramificación y acotación
      • Resolver problemas de optimización discreta mediante algoritmosbasados en hiperplanos de corte
      • Saber utilizar paquetes informáticos para resolver problemas sobre grafos y de optimización combinatoria

  5. Contenidos

    1. Teoría

      2. Bloque 1: Teoría de Grafos

      Tema 1: Conceptos básicos en Teoría de Grafos

      Definiciones y ejemplo Primero resultados Ejercicios

      Tema 2: Conexión

      Conexión y componentes conexas Algunos resultados sobre conexión k-conexión Ejercicios

      Tema 3: ÿrboles

      Introducción y árboles con raíz Árboles binarios Árboles generadores de peso mínimo Algoritmos de Kruskal y Prim Ejercicios

      Tema 4: Camino más corto. Recorridos por aristas y vértices

      Caminos más cortos Algoritmo de Dijkstra Grafos eulerianos Algoritmo de Dantzig Grafos hamiltonianos El problema del viajante de comercio Ejercicios

      Tema 5: Grafos planos. Coloración de grafos

      Coloración Teorema fundamental de reducción Planaridad Coloreado de grafos planares Ejercicios

      Bloque 2: Optimización Discreta

      Tema 1: Modelo de programación entera

      Repaso de Optimización Lineal Algoritmo dual Modelo de Programación Entera Formulación de problemas de optimización sobre grafos Indicaciones para formular Ejercicios

      Tema 2: Ramificación y acotación. Hiperplanos de corte

      Algoritmo de ramificación y acotación Hiperplano de corte todo entero Hiperplano de corte mixtoEjercicios

    2. Prácticas

      • Práctica 1: Resolución de problemas de Optimización Discreta

        Las prácticas se llevarán a cabo en un aula de ordenadores con el software xpress para Optimización Discreta, siguiendo un cuadernillo preparado al efecto

        Relacionado con:
        • Tema 1: Conceptos básicos en Teoría de Grafos
        • Tema 2: Conexión
        • Tema 3: ÿrboles
        • Tema 4: Camino más corto. Recorridos por aristas y vértices
        • Tema 5: Grafos planos. Coloración de grafos
        • Tema 1: Modelo de programación entera
        • Tema 2: Ramificación y acotación. Hiperplanos de corte

  6. Actividades Formativas

    7. Actividad Formativa Metodología Horas Presencialidad
    AF1: Exposición teórica-práctica / Clase magistral de teoría-problemas 30.0 100.0
    AF2: Tutoría ECTS o trabajos dirigidos 2.0 100.0
    AF3: Resolución de problemas / Seminarios / Exposición y discusión de trabajos 30.0 100.0
    AF4: Prácticas con ordenadores 8.0 100.0
    AF5: Trabajo autónomo del estudiante 80.0 0.0
    Totales 150,00

  7. Horario de la asignatura

    8. https://www.um.es/web/estudios/grados/matematicas/2024-25#horarios

  8. Sistemas de Evaluación

    9. Identificador Denominación del instrumento de evaluación Criterios de Valoración Ponderación
    SE1 Exámenes (escritos u orales)

    El examen de prácticas puntuará un 5%

    Se responderá preguntas de teoría (enunciados, demostraciones y cuestiones teóricas sobre los resultados centrales de la asignatura) contando un 45% de la calificación

    El 50% restante consistirá en la resolución por escrito de cuestiones prácticas, ejercicios y problemas

    		 90.0
    SE2 Informes escritos, trabajos y proyectos

    La calificación de este apartado se sumará a la nota del examen Se podrá conseguir hasta 15 puntos adicionales mediante la resolución de problemas en un control, la resolución de tareas propuestas por el profesor, la resolución del examen de prácticas de ordenador, etc

    		 5.0
    SE3 Presentación de trabajos

    La participación en clase podrá aportar medio punto más a la nota de la asignatura

    		 5.0

  9. Fechas de exámenes

    10. https://www.um.es/web/estudios/grados/matematicas/2024-25#examenes

  10. Resultados del Aprendizaje

    • Conocer y manejar nociones de combinatoria y métodos de enumeración
    • Conocer y caracterizar los distintos tipos de grafos y redes
    • Resolver el problema de la conexión de un grafo, y conocer sus aplicaciones
    • Saber obtener árboles, caminos y otras subestructuras óptimas sobre redes
    • Formular problemas de optimización combinatoria de forma eficiente
    • Resolver problemas de optimización discreta mediante algoritmos de ramificación y acotación
    • Resolver problemas de optimización discreta mediante algoritmosbasados en hiperplanos de corte
    • Saber utilizar paquetes informáticos para resolver problemas sobre grafos y de optimización lineal y combinatoria

  11. Bibliografía

    12. Bibliografía complementaria

    No constan

  12. Observaciones

    13. El plagio y/o copia en cualquier proceso de la evaluación de la asignatura es un comportamiento poco ético y tendrá como consecuencia, de forma automática, el suspenso en la actividad evaluada

    Aquellos estudiantes con discapacidad o necesidades educativas especiales pueden dirigirse al Servicio de Atención a la Diversidad y Voluntariado (ADYV; http://wwwumes/adyv/) para recibir la orientación o asesoramiento oportunos para un mejor aprovechamiento de su proceso formativo El tratamiento de la información sobre este alumnado es de estricta confidencialidad

    Esta asignatura no se encuentra vinculada de forma directa con los Objetivos de Desarrollo Sostenible

    La evaluación de las convocatorias extraordinarias se llevará a cabo mediante examen de teoría y problemas al 50%

    NECESIDADES EDUCATIVAS ESPECIALES

    Aquellos estudiantes con discapacidad o necesidades educativas especiales podrán dirigirse al Servicio de Atención a la Diversidad y Voluntariado (ADYV - https://www.um.es/adyv) para recibir orientación sobre un mejor aprovechamiento de su proceso formativo y, en su caso, la adopción de medidas de equiparación y de mejora para la inclusión, en virtud de la Resolución Rectoral R-358/2016. El tratamiento de la información sobre este alumnado, en cumplimiento con la LOPD, es de estricta confidencialidad.

    REGLAMENTO DE EVALUACIÓN DE ESTUDIANTES

    El artículo 8.6 del Reglamento de Evaluación de Estudiantes (REVA) prevé que "salvo en el caso de actividades definidas como obligatorias en la guía docente, si el o la estudiante no puede seguir el proceso de evaluación continua por circunstancias sobrevenidas debidamente justificadas, tendrá derecho a realizar una prueba global".

    Se recuerda asimismo que el artículo 22.1 del Reglamento de Evaluación de Estudiantes (REVA) estipula que "el o la estudiante que se valga de conductas fraudulentas, incluida la indebida atribución de identidad o autoría, o esté en posesión de medios o instrumentos que faciliten dichas conductas, obtendrá la calificación de cero en el procedimiento de evaluación y, en su caso, podrá ser objeto de sanción, previa apertura de expediente disciplinario".