Algorismia y Combinatoria en Grafos. Métodos Heurísticos
Código: 104388 Créditos ECTS: 6| Titulación | Tipo | Curso | Semestre |
|---|---|---|---|
| 2503740 Matemática Computacional y Analítica de Datos | FB | 1 | 2 |
Contacto
- Nombre:
- Lluís Alseda Soler
- Correo electrónico:
- lluis.alseda@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:
- Sí
- Algún grupo íntegramente en español:
- No
Equipo docente
- Lluís Alseda Soler
- Albert Ruiz Cirera
Prerequisitos
Es necesario 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 combinatorio 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]
Competencias
- Aplicar el espíritu crítico y el rigor para validar o refutar argumentos tanto propios como de otros.
- Demostrar una elevada capacidad de abstracción y de traducción de fenómenos y comportamientos a formulaciones matemáticas.
- Evaluar de manera crítica y con criterios de calidad el trabajo realizado.
- Formular hipótesis e imaginar estrategias para confirmarlas o refutarlas.
- 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.
- Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
- 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.
- Relacionar objetos matemáticos nuevos con otros conocidos y deducir sus propiedades.
- Trabajar cooperativamente en un contexto multidisciplinar asumiendo y respetando el rol de los diferentes miembros del equipo.
- Utilizar eficazmente bibliografía y recursos electrónicos para obtener información.
Resultados de aprendizaje
- Aplicar el espíritu crítico y el rigor para validar o refutar argumentos tanto propios como de otros.
- Contrastar, si es posible, el uso del cálculo con el uso de la abstracción para resolver un problema.
- Desarrollar estrategias autónomas para la resolución de problemas propios del curso, discriminar los problemas rutinarios de los no rutinarios y diseñar y evaluar una estrategia para resolver un problema.
- Describir los conceptos y objetos matemáticos propios de la asignatura.
- Evaluar de manera crítica y con criterios de calidad el trabajo realizado.
- Evaluar las ventajas e inconvenientes del uso del cálculo y de la abstracción.
- Explicar ideas y conceptos matemáticos propios del curso, así como comunicar a terceros razonamientos propios.
- Identificar las ideas esenciales de las demostraciones de algunos teoremas básicos y saberlas adaptar para obtener otros resultados.
- Leer y comprender un texto de matemáticas del nivel del curso.
- 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.
- Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
- 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.
- Redactar, de manera ordenada y con precisión, pequeños textos matemáticos (ejercicios, resolución de cuestiones de teoría, etc.).
- Trabajar cooperativamente en un contexto multidisciplinar asumiendo y respetando el rol de los diferentes miembros del equipo.
- Utilizar eficazmente bibliografía y recursos electrónicos para obtener información.
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 y programación orientada a objetos: Listas dinámicas y árboles
Algoritmos de representación de grafos. Avantatgews 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]
Metodología
Las sesiones semanales de la asignatura se dividirán, normalmente, en dos partes:
a) Una parte teórica en la que el profesor introducirá los conceptos, métodos y ejemplos relativos al temario de la asignatura.
b) 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. Estas sesiones se realizarán en alguna de las aulas de informática de la facultad. 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. La entrega será durante el día en que se realiza la práctica.
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.
Actividades
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Tipo: Dirigidas | |||
| Asistir a las clases teóricas y prácticas | 56 | 2,24 | 1, 7, 9, 13, 15 |
| Tipo: Supervisadas | |||
| Realización de las prácticas | 55 | 2,2 | 1, 5, 6, 2, 7, 9, 11, 12, 13, 14, 15 |
| Tipo: Autónomas | |||
| Resolución de ejercicios complementarios | 30 | 1,2 | 1, 5, 6, 2, 7, 9, 11, 12, 13, 14, 15 |
Evaluación
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]
Actividades de evaluación
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Entrega de ejercicios prácticos | 25% | 0 | 0 | 1, 5, 4, 3, 7, 9, 10, 11, 12, 13, 14, 15 |
| Examen final | 40% | 4 | 0,16 | 4, 7, 8, 9, 12, 13 |
| Trabajo pràctico individual | 35% | 5 | 0,2 | 1, 5, 6, 2, 4, 3, 7, 9, 11, 12, 13 |
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