Algoritmia y Combinatoria en Grafos. Métodos Heurísticos
Código: 104388Créditos: 6
2026/2027
| Titulación | Tipo | Curso |
|---|---|---|
| Matemática Computacional y Analítica de Datos | FB | 1 |
Profesor/a de contacto
- Nombre :
- Albert Ruiz Cirera
- Correo electrónico :
- albert.ruiz@uab.cat
Equipo docente
- Albert Ruiz Cirera
Idiomas de los grupos
Puede consultar esta información al final del documento.
Prerrequisitos
Es recomendable que el estudiante haya cursado Matemáticas en los dos cursos de bachillerato y se haya examinado de esta materia en las PAU.
Objetivos
- Conocer los grafos combinatorios y su terminología.
- Conocer los diferentes algoritmos de búsqueda y movimiento en grafos.
- Conocer los tipos de datos dinámicos para representación de grafos y su implemnentació en C.
- Conocer los algoritmos básicos de búsqueda óptimas en grafos y evaluar su complejidad.
Resultados de aprendizaje
- KM02 (Distinguir los objetos propios del cálculo con funciones y de sus propiedades y utilidades.) Distinguir los objetos propios del cálculo con funciones y de sus propiedades y utilidades.
- KM05 (Describir los conceptos y objetos matemáticos propios de la teoría de grafos.) Describir los conceptos y objetos matemáticos propios de la teoría de grafos.
- SM05 (Desarrollar estrategias autónomas para la resolución de problemas propios del cálculo numérico, la probabilidad y la teoría de grafos.) Desarrollar estrategias autónomas para la resolución de problemas propios del cálculo numérico, la probabilidad y la teoría de grafos.
Contenidos
- Algoritmos combinatorios para grafos.
- Introducció a los grafos combinatorios.
- Recorrido en grafos: Depth-first and Breadth-first.
- Algoritmos Greedy.
- Recursividad.
- Tipos abstractos de datos: listas dinámicas y árboles.
- Algoritmos de representación de grafos. Ventajas e inconvenientes de cada una de las opciones.
- Tipos abstractos y dinámicos de datos para grafos y su implementación en C.
- Algoritmos básicos de búsqueda óptimas en grafos y su complejidad.
- Cálculo de distancias a partir de la latitud y la longitud.
- Algoritmo de Dijkstra para rutas óptimas en grafos.
- Algoritmo A *: búsqueda heurística para rutas óptimas en grafos.
Actividades formativas y Metodología
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Resolución de ejercicios complementarios | 30 | 1,2 | |
| Realización de las prácticas | 62 | 2,48 | |
| Asistir a las clases teóricas y prácticas | 49 | 1,96 |
Las sesiones semanales de la asignatura se dividirán, normalmente, en dos partes:
- Una parte teórica en la que el profesor introducirá los conceptos, métodos y ejemplos relativos al temario de la asignatura.
- Una parte práctica en la que se propondrá a los estudiantes una serie de problemas o ejercicios en los que se pondrá de manifiesto y se trabajará de forma concreta lo que se ha visto en la parte teórica. Cada práctica tendrá un enunciado diferente, que se publicará en el Campus Virtual e implicará la entrega de las respuestas a algunas cuestiones planteadas.
También se propondrán ejercicios complementarios como actividad autónoma para ayudar a la comprensión de la parte aplicada de la asignatura.
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 |
|---|---|---|---|---|
| Trabajo pràctico individual | 35% | 5 | 0,2 | KM02, KM05, SM05 |
| Entrega de ejercicios prácticos | 25% | 0 | 0 | KM02, KM05, SM05 |
| Examen final | 40% | 4 | 0,16 | KM02, KM05, SM05 |
La evaluación constará de las siguientes actividades:
- Un examen final, que cuenta el 40% de la nota.
- Un trabajo práctico individual con plazo de entrega donde será necesario desarrollar e implementar algoritmos, que cuenta el 35% de la nota.
- Entrega de ejercicios prácticos que se realizarán en grupos de dos. Cuentan un 25% de la nota. Esta es una actividad de evaluación continua y no es recuperable.
La nota final será:
- La media ponderada según el peso de cada parte para aquellos estudiantes que hayan sacado 3,5 o más a todas las partes.
- El mínimo entre 3,5 y la media ponderada según el peso de cada parte para aquellos estudiantes que hayan realizado alguna de las evaluaciones individuales y en alguna de las partes no lleguen al 3,5.
- No evaluable para aquellos estudiantes que no hayan realizado ninguna de las evaluaciones individuales.
Aquellos que se hayan evaluado de las tres partes (en particular, deben haber entregado el trabajo práctico individual y el examen final) y no superen la asignatura, se podrán presentar a una recuperación del examen final y el trabajo práctico individual.
En las instrucciones de cada entrega se hará explícito qué uso de la Inteligencia Artificial puede realizarse. Saltarse estas instrucciones se considerará fraude académico.
Esta asignatura no contempla el método de evaluación única.
[Traducido de la versión catalana por Google translator]
Bibliografía
- Fundamentos de programación (algoritmos, estructuras de datos y objetos), Luis Joyanes, McGraw-Hill, Madrid etc. (2003).
- Algoritmos y estructuras de datos – una perspectiva en C, Luis Joyanes y Ignacio Zahonero, McGraw-Hill, Madrid etc. (2004).
- Grafs combinatòris i cerques en gràfs:Wikipedia
- Tipus abstractes de dades i programació orientada a objectes: Llistes dinàmiques i arbres; Tipus abstractes i dinàmics de dades per a grafs i la seva implementació en C.
- Notes del curs
- Algoritmos + Estructura de datos = Programas, Niklaus Wirth, Ediciones del Castillo, Madrid (1986).
- C algoritmos, programación y estructuras de datos, Luis Joyanes Aguilar et al., McGraw-Hill, Madrid etc. (2005).
- Algorismes de representació de grafs. Avantatges inconvenients de cada una de les opcions: Wikipedia i notes del curs
- Càlcul de distàncies a partir de la latitud i la longitud: Wikipoedia i notes del curs
- Algorisme de Dijkstra per a rutes òptimes en grafs: Presentació d'Eric Demaine
- Algorisme A*: cerca heurística per a rutes òptimes en grafs
- Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
Pagines: 33 to 46, 48, 49, 64, 65, 73--85.L'exemple a les pàgines 52--54 pot ser relevant.
Software
C
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 | 1 | Catalán | segundo cuatrimestre | manaña-mixto |
| (PLAB) Prácticas de laboratorio | 1 | Catalán | segundo cuatrimestre | manaña-mixto |
| (SEM) Seminarios | 1 | Catalán | segundo cuatrimestre | manaña-mixto |