Programa
Algoritmia Avanzada (AA)
Técnicas Avanzadas para el Desarrollo de Software Inteligente
Bienio 2005/2007

Datos administrativos de la Universidad

Asignatura

Código de la materia	t151a012
Nombre de la materia	Algoritmia Avanzada
Centro	Escuela Superior de Ingeniería Informática
Tipo Curso	fundamental
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	invitado	1	por correo electrónico
Formella, Arno	3142	1	Miércoles: 11-14, 16-19
Olivieri, David	3118	1	Lunes: 10-14, 16-18

Horarios

Las clases teóricas se darán los siguientes días:

Fecha	Hora	Aula	Profesor
Miércoles	16-18	Aula 3.3	Arno Formella
11.Ene.06			David Olivieri
Miércoles	16-18	Aula 3.3	David Olivieri
18.Ene.06	18-21	Aula 3.3	Arno Formella
Miércoles	16-18	Aula 3.1	Fernando Díaz Góme z
25.Ene.06	19-21	Aula 3.1	David Olivieri
Jueves	16-19	Aula 3.1	Fernando Díaz Góme z
26.Ene.06	19-20	Aula 3.1	Arno Formella

La presentación de los trabajos será a partir de marzo. Se acordará la fecha durante las clases.

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

1. 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
      • Métodos multiarranque (Multi-Start methods)
      • 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)

2. 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

3. Transformadas
   1. Teoría de transformaciones de Fourier
      • Teoría de Espacios vectoriales y abstractos de funciones
      • Metodo Espectrales
      • Expansión de Fourier
      • Algoritmo para transformada de Fourier (FFT)
      • Aplicaciones
   2. Teoría de transformaciones de Wavelet
      • Derivación de Filter Banks y el concepto de expansión de multiresolución
      • Aplicación de filtros
      • Compresión de datos
      • Derivación de Wavelet expansión
      • Aplicación de Wavelets

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, ejemplos son:

• 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

1. 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.

2. Teoría de los grafos
   • Reinhard Diestel. Graph Theory. 2nd edition, Springer Verlag, 2000.

3. Transformadas
   • por incluir

Método docente

Se imparte la signatura en tres partes:

1. clases de teoría con transparencias y pizarra (el conocimiento también se puede adquirir con estudio propio de la bibliografía recomendada)
2. realización de un trabajo
3. presentación del trabajo

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.