Logo UAB
2022/2023

Grafos, Topología y Geometría Discreta

Código: 104349 Créditos ECTS: 6
Titulación Tipo Curso Semestre
2503758 Ingeniería de Datos OB 1 2

Contacto

Nombre:
César Pablo Corcoles Briongos
Correo electrónico:
cesar.corcoles@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:
No
Algún grupo íntegramente en español:
No

Equipo docente

Joan Serra Sagristà
Miguel Hernández Cabronero
David Marín Pérez

Prerequisitos

No hay requisitos previos. Es aconsejable dominio de nociones básicas de programación, álgebra y de teoría de conjuntos fundamentales, así como haber cursado las asignaturas Fundamentos de Matemáticas y Fundamentos de Programación.

Objetivos y contextualización

Se tratarán temas del área de la matemática discreta, incluyendo teoría de grafos, optimización de caminos, y otros algoritmos en grafos, así como nociones de complejidad de algoritmos. Se tratarán asimismo conceptos básicos de topología discreta y geometría sobre curvas y superficies.

Competencias

  • Buscar, seleccionar y gestionar de manera responsable la información y el conocimiento.
  • Desarrollar un pensamiento y un razonamiento crítico y saber comunicarlo de manera efectiva, tanto en las lenguas propias como en inglés.
  • Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
  • Representar los datos de forma adecuada, tanto desde el punto de vista computacional como el matemático.
  • Trabajar cooperativamente, en entornos complejos o inciertos y con recursos limitados, en un contexto multidisciplinar, asumiendo y respetando el rol de los diferentes miembros del equipo.

Resultados de aprendizaje

  1. Buscar, seleccionar y gestionar de manera responsable la información y el conocimiento.
  2. Desarrollar un pensamiento y un razonamiento crítico y saber comunicarlo de manera efectiva, tanto en las lenguas propias como en inglés.
  3. Identificar e interpretar los descriptores y propiedades fundamentales de las representaciones basadas en la geometría de los datos.
  4. Identificar i reconocer los algoritmos básicos de recorrido de grafos y demostrar la capacidad de aplicar su optimización.
  5. Interpretar y aplicar las propiedades básicas de los grafos dirigidos y no dirigidos.
  6. Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
  7. Trabajar cooperativamente, en entornos complejos o inciertos y con recursos limitados, en un contexto multidisciplinar, asumiendo y respetando el rol de los diferentes miembros del equipo.

Contenido

Parte I

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

    1. Conjuntos y operaciones con conjuntos

    2. Producto cartesiano y relaciones binarias

    3. Combinatoria

    4. Conjuntos finitos, infinitos y numerables

    5. Complejidad de algoritmos y problemas

    6. Complejidad de funciones. Complejidad polinomial y no polinomial.

  2. Fundamentos de grafos

    1. Definiciones y variantes

    2. Caminos, circuitos y distancias

    3. Grado y lema del saludo

    4. Subgrafos y tipos importantes de grafo

    5. Secuencias gráficas (Havel-Hakimi)

    6. Representación de grafos

  1. Caminos, recorridos y árboles generadores óptimos

    1. Exploración de grafos (búsquedas en profundidad y en anchura)

    2. Caminos de coste mínimo (Dijkstra, Floyd)

    3. Caracterización de árboles

    4. Árboles generadores óptimos (Kruskal)

  1. Planaridad y coloración

    1. Resultados básicos

    2. Caracterización de grafos planos

    3. Coloración de grafos planos

Parte II

  1. Topología

    1. Espacio topológico y propiedades básicas

    2. Isomorfismos

    3. Simplex, redes y grafos como codificadores de topologías discretas

  1. Geometría  de curvas y superficies

    1. Curvas paramétricas

    2. Parámetros angulares, parametrización implícita y curvas de nivel

    3. Descriptores básicos de curvas en el espacio: Triedro de Frenet, torsión y curvatura

  2. Geometría de superficies

  1. Superficies paramétricas

  2. Espacio tangente

  3. Primera y segunda formas fundamentales

  4. Difeomorfismos

  5. Geodésicas y caminos de coste mínimo

Metodología

Se discutirán los conceptos teóricos del currículum en clases. Será necesario Trabajo Personal Independiente para maximizar el aprendizaje durante las clases. Estas no se basarán en la lectura de una selección de materiales obligatorios y disponibles en el Campus Virtual, sino en el aprovechamiento de estos.

En las clases de problemas se trabajarán problemas de entre una selección. Como en la parte de teoría, será necesario trabajo personal independiente para maximizar el aprendizaje en estas sesiones. En particular, habrá una lista de problemas seleccionados que deberán trabajarse antes de cada sesión, y cuyas soluciones se discutirán conjuntamente.

En las sesiones de prácticas, se asistirá a la obtención de experiencia práctica con temas relacionados mediante microproyectos. Se definirá una lista de entregables obligatorios, a trabajar como parte del trabajo personal, con asistencia a las sesiones de prácticas.

Las clases tendrán lugar predominantemente en inglés.

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 teoría 26 1,04 1, 2, 3, 4, 5, 6
Prácticas 12 0,48 1, 2, 3, 4, 5, 6, 7
Sesiones de problemas 12 0,48 1, 2, 3, 4, 5, 6
Tipo: Supervisadas      
Preparación de problemas y entregas de prácticas 12,5 0,5 1, 2, 3, 4, 5, 6, 7
Tutorías 5 0,2 1, 2, 3, 4, 5, 6
Tipo: Autónomas      
Preparación para el examen final 25 1 1, 2, 3, 4, 5, 6
Trabajo personal 50 2 1, 2, 3, 4, 5, 6

Evaluación

Todas las fechas de evaluación continua, así como posibles cambios, serán publicadas en el Campus Virtual.

Las fechas de la evaluación continua (y cualesquiera cambios que pudiese haber) se publicarán en el Campus Virtual.

La evaluación de la asignatura (sobre 10 puntos) se realizará de la siguiente manera:

Teoría (6 puntos):

Dos pruebas parciales, 6 puntos (3 cada una). La primera prueba parcial se realizará al final de los primeros tres temas. La segunda, al concluir el curso. Las pruebas individuales consistirán mayoritariamente en problemas como los trabajados durante el curso, y una parte menor dedicada a conceptos teóricos.

Examen final, 6 puntos. Aquellas personas que no hayan aprobado la asignatura mediante las pruebas parciales, tendrán la opción de hacer un examen final como nota de recuperación. No hay recuperación separada para las pruebas parciales, el examen final cubre todo el temario tratado en la asignatura. El formato será similar al de las pruebas parciales.

Resolución de ejercicios (1.5 puntos):

Como parte de la evaluación continua, se resolverán ejercicios aplicando los algoritmos estudiados (mediante, por ejemplo, tests online). La parte presencial de estos ejercicios tendrá lugar durante las propias sesiones de problemas.

Prácticas (2.5 puntos):

Habrá una serie de entregables obligatorios, anunciados pertinentemente en el CV. La nota final de las prácticas será el promedio de la nota de estos. 1.8 puntos corresponden a la primera part del curso, los 0.7 puntos restantes a la segunda.

Se requerirá una nota global de 5 para aprobar. Una nota de "no evaluable" no podrá ser otorgada cuando se haya tomado parte en cualquiera de las pruebas individuales parciales o finales. No se dará trato preferencial a estudiantes repetidores, si bien la nota de seminarios/prácticas de años anteriores podrá ser convalidada en caso de ser solicitado. Para obtener matrícula de honor, será imprescindible una nota final de 9.0 o superior. Se otorgará como máximo un 5% de matrículas de honor a las mejores calificaciones, teniendo en cuenta las pruebas parciales en caso de empate.

No se permitirán actividades de evaluación fuera delas fechas establecidas para todo el alumnado, a no ser sean justificadas y notificadas con suficiente antelación al equipo docente.

En el caso de la resolución de problemas, se podrá solicitar revisión de las actividades de evaluación el mismo día de la actividad, o fecha de cierre en el caso de tests online. Para cada una de las demás actividades de evaluación, todos los detalles de una actividad de revisión (incluyendo lugar, fecha y hora) serán comunicados al alumnado empleando el canal habitual. Únicamente se podrá solicitar la revisión de notas durante esta actividad.

Plagio y otras irregularidades académicas

Sin detrimento de otras medidas disciplinarias, y de acuerdo con la legislación vigente, todas las actividades de evaluación conllevarán un cero en caso de que el o la estudiante cometa irregularidades académicas, y no podrá ser reevaluado. Si el aprobado de dichas actividades es obligatorio para aprobar la asignatura, se suspenderá asimismo directamente la asignatura, sin oportunidad de reevaluación durante el mismo año académico.

Entre otras, se contemplan las siguientes irregularidades: copia total o parcial de cualquier actividad de evaluación; compartición de soluciones para su presentación (irregular) como copia; presentación de trabajo de grupo que no haya sido desarrollado enteramente por los miembros del grupo; presentación de trabajo de terceros como propio, incluyendo derivaciones y adaptaciones; posesión de dispositivos de comunicación (móviles, ordenadores, smartwatches, etc) durante las actividades de evaluación individual.

Para más información sobre regulación académica aprobada en Consejo de Gobierno de la UAB: http://webs2002.uab.es/afers_academics/info_ac/0041.htm.

Actividades de evaluación

Título Peso Horas ECTS Resultados de aprendizaje
Dos exámenes parciales 60% 3 0,12 1, 3, 4, 5, 6
Envío de entragles de prácticas 25% 3 0,12 1, 2, 3, 4, 5, 6, 7
Pruebas de problemas basado en ejercicios de la clase de problemas 15% 1,5 0,06 1, 2, 3, 4, 5

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.
  • 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.
  • F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
  • M. P. do Carmo. Geometría diferencial de curvas y superficies. Alianza Editorial, 1995.
  • J. R. Munkres, Topología, Prentice-Hall, 2a edición, 2002.
  • M. Spivak. Cálculo en variedades. Editorial Reverté, 2a edición, 1970.
  • W. A. Sutherland, Introduction to metric and topological spaces, 2nd edition, Oxford University Press, 2009.

Software

Las prácticas de la asignatura se harán en Python.