Algorismia y Combinatoria en Grafos. Métodos Heurísticos
Código: 104388 Créditos ECTS: 6| Titulación | Tipo | Curso |
|---|---|---|
| 2503740 Matemática Computacional y Analítica de Datos | FB | 1 |
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.
[Traducido de la versión catalana por Google translator]
Objetivos y contextualización
- 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 su complejidad.
[Traducido de la versión catalana por Google translator]
Resultados de aprendizaje
- KM02 (Conocimiento) Distinguir los objetos propios del cálculo con funciones y de sus propiedades y utilidades.
- KM05 (Conocimiento) Describir los conceptos y objetos matemáticos propios de la teoría de grafos.
- SM05 (Habilidad) Desarrollar estrategias autónomas para la resolución de problemas propios del cálculo numérico, la probabilidad y la teoría de grafos.
Contenido
- Algoritmos combinatorios para grafos.
- Grafos combinatorios y búsquedas en grafía.
- Teoría de grafos: introducción.
- Buscar 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
[Traducido de la versión catalana por Google translator]
Actividades formativas y Metodología
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Tipo: Dirigidas | |||
| Asistir a las clases teóricas y prácticas | 49 | 1,96 | |
| Tipo: Supervisadas | |||
| Realización de las prácticas | 62 | 2,48 | |
| Tipo: Autónomas | |||
| Resolución de ejercicios complementarios | 30 | 1,2 |
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.
[Traducido de la versión catalana por Google translator]
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 |
|---|---|---|---|---|
| Entrega de ejercicios prácticos | 25% | 0 | 0 | KM02, KM05, SM05 |
| Examen final | 40% | 4 | 0,16 | KM02, KM05, SM05 |
| Trabajo pràctico individual | 35% | 5 | 0,2 | 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, durante las sesiones prácticas, 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 mínima en cada una de las tres actividades de evaluación para poder aprobar la asignatura es de 3,5 puntos sobre 10.
Aquellos estudiantes que, después de evaluarse de las tres partes, no superen la asignatura, podran presnetarse a una recuperación del examen final i el trabajo práctico individual.
[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. Avantatgews inconvenients de cada una de les opcions: Wikipedia i notes del curs
- ACà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
Lista de idiomas
| Nombre | Grupo | Idioma | Semestre | Turno |
|---|---|---|---|---|
| (PLAB) Prácticas de laboratorio | 1 | Catalán | segundo cuatrimestre | manaña-mixto |
| (SEM) Seminarios | 1 | Catalán | segundo cuatrimestre | manaña-mixto |
| (TE) Teoría | 1 | Catalán | segundo cuatrimestre | manaña-mixto |