Programa
Algoritmia Avanzada (AA)

Datos administrativos de la Universidad

Asignatura

Código de la materia
Nombre de la materia	Algoritmia Avanzada
Centro/Titulación	Escuela Superior de Ingeniería Informática/Ingeniería Informática
Curso	curso de doctorado
Créditos	3
Departamento	Informática
Área de conocimiento	Área de Lenguajes y Sistemas Informáticos

Profesorado de la materia

Nombre Profesor/a	Código	Créditos	Tutorías
Díaz Gómez, Fernando	1019	1	1 $\underline{\mathrm o}$ cuatri.: Mi 10-13, 17-20
			2 $\underline{\mathrm o}$ cuatri.: Mi 10-13, 17-20
			no lectivo: Mi 10-13, 17-20
Formella, Arno	3142	1	1 $\underline{\mathrm o}$ cuatri.: Mi 11-14, 16-19
			2 $\underline{\mathrm o}$ cuatri.: Mi 10-12, 16-19; Vi 18-19
			no lectivo: Mi 11-14, 16-19
Olivieri, David	3118	1	1 $\underline{\mathrm o}$ cuatri.: Mi 10-12, 16-18; Ju 10-12
			2 $\underline{\mathrm o}$ cuatri.: Mi 10-12, 16-18 Ju 10-12
			no lectivo: Mi 10-12, 16-18; Ju 10-12

Horarios

Las clases teóricas se darán los siguientes miércoles:

Fecha	Hora	Aula	Profesor
5.Nov.03	16-18	Salón de Grados	Arno Formella
	18-21	Salón de Grados	Fernando Díaz Gómez
12.Nov.03	16-18	Aula 1.3	David Olivieri
	18-21	Aula 1.3/1.2	Arno Formella
19.Nov.03	16-19	Salón de Grados	David Olivieri
	19-21	Salón de Grados	Fernando Díaz Gómez

La presentación de los trabajos será finales de enero.

Temario de la materia

Objetivos de la materia

Se ha dividido la asignatura en tres módulos, cuyos objetivos principales son la breve introducción a los conceptos de tres aspectos fundamentales en la algoritmia avanzada en el ámbito del curso de doctorado.

Temarios de clases teóricas

Búsquedas:

 

1. Problemas de búsqueda y optimización.
2. Metaheurísticas: Definición, tipos de metaheurísticas, propiedades deseables.
3. Metaheurísticas de búsqueda local.

   Búsquedas no informadas:

   búsqueda en anchura, búsqueda en profundidad, profundización iterativa, apertura iterativa.

   Búsquedas locales monótonas:

   método de escalada (hill climbing), búsqueda mejor-primero (best-first search).

4. Metaheurísticas de búsqueda global.
   1. Métodos multiarranque (Multi-Start methods)
   2. Métodos de búsqueda no monótonas

      Búsqueda probabilística:

      recocido simulado (simulated annealing).

      Búsqueda con memoria:

      búsqueda tabú (tabu search)

Teoría de los grafos:

 

1. Nociones básicas
2. Algoritmos básicos
3. Conectividad
4. Planaridad
5. Coloración
6. Flujos
7. Emparejamientos
8. Teorías avanzadas
9. Grafos aleatorios
10. Algoritmos dinámicos
11. Visualización y Aplicaciones

Transformadas:

 

1. Nociones básicas para Informática
2. Motivación: Integrales, Espacios, y Decomposición Espectral
3. Teoría de la Transformada de Fourier
4. Implementación del algoritmo de FFT
5. Convolución y Filtración
6. Teoría de Wavelets (ondículas)
7. Algoritmos y Implementación de la Transformada Discreta de Ondículas
8. Métodos Multi-escala para el Análisis

Temario de Trabajos

Una vez proporcionados a los alumnos una serie de conocimientos básicos se proponen áreas de interés en las que los alumnos podrán desarrollar su trabajo en el marco del curso Algoritmia Avanzada:

• Búsqueda por entornos Variables (VNS, Variable Neigborhood Search)
• Búsqueda reactiva (Reactive Search)
• Sistemas de colonias de hormigas (Ant Colony Systems)
• Aplicaciónes de grafos
• Herramientas software para trabajar con grafos

Referencias bibliográficas

Búsquedas:

 

• García-Serrano, A. (Ed.) (2003). Monografía: Metaheurísticas. Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, 19.
• Ginsberg, M. Essentials of Artificial Intelligence. Morgan Kaufmann Publishers, 1993.
• Glover, F., y Kochenberger, G.A. Handbook of metaheuristics. Kluwer Academic Publishers, 2003.
• Rayward-Smith, V.J., Osman, I.H., Reeves, C.R., y Smith, G.D. (Eds.). Modern Heuristic Search Methods. John Wiley & Sons, 1996.

Teoría de los grafos:

 

• Reinhard Diestel. Graph Theory. 2nd edition, Springer Verlag, 2000.

Transformadas:

 

• por incluir...

Método docente

Se imparte la signatura en tres partes:

1. clases de teoría con transparencias y pizarra
2. realización de un trabajo
3. presentación del trabajo

Los apuntes estarán disponibles en la Red.

Sistema de evaluación

Se supone una asimilación de los conceptos básicos del curso como presentado en las clases teóricas, y la realización de un trabajo que se presentará en sesión abierta a finales de enero.

Información complementaria

Se complementa la bibliografía de la asignatura con documentos y artículos relacionados con los temas.