Ciencias de la Computación (plan 1994) 2013-1

Optativas, Seminario de Temas Selectos de Computación

Profesora: María De Luz Gasca Soto

Motivación:

La complejidad computacional depende, principalmente de la forma cómo se representen, manipulen y estructuren los datos de un problema. Por lo cual resulta importante analizar y comparar las Estructuras de Datos para elegir la implantación eficiente de los algoritmos.

El análisis de algoritmos clásico se basa, sobre todo, en el análisis del peor caso, el cual tiende a ser muy pesimista y cuyas cotas quedan muy holgadas. El análisis del caso esperado resulta ser muy específico y poco práctico, ya que depende de la forma cómo se distribuyen los datos: si se modifica la distribución de los datos debe cambiar el análisis.

R.E. Tarjan [1] presenta una novedosa técnica llamada Análisis Amortizado con la cual genera un cambio muy importante en el área del Análisis de Algoritmos y Estructuras de Datos.

Objetivo:

• Introducir al alumno en el campo de la Investigación del Análisis de Algoritmos.
• Estudiar con detalle el Análisis Amortizado, sus enfoques y aplicaciones.
• Enfocar el estudio de las Estructuras de Datos englobadas en los Tipos de Datos Abastractos (TDA´s): Colas de Prioridades (Skew Hepas, Colas Binomiales, Fibonacci Heaps) y Conjuntos Ajenos, aplicados a problemas clásicos de Teoría de Gráficas.
• Realizar, con sumo detalle, el Análisis Amortizado de las Estructuras estudiadas: Skew Hepas, Colas Binomiales, Fibonacci Heaps y Conjuntos Ajenos, ilustrando las diversas técnicas y estrategias para realizar este tipo de análisis.
• Comprobar empíricamente los resultados teóricos obtenidos, implementando los diferentes TDA y aplicándolos a Problemas asociados con Teoría de Gráficas.

Temario

1. Introducción.
2. El Análsis Amortizado

2.1 El punto de vista del banquero

2.2 El enfoque de los físicos.

3. Colas Binomiales

3.1 Definición de árbol Binomial

3.2 Especificación de Cola Binomial

3.3 Tiempo Amortizado de las Colas Binomiales

4. Skew Heaps

4.1 Especificación de Skew Heaps

4.2 Modificación del Skew Heaps

4.3 Análisis Amortizado del Skew Heaps

5. Fibonacci Heaps

5.1 Especificación de Fibonacci Heaps

5.2 Modificación de Fibonacci Heaps

5.3 Análisis Amortizado de Fibonacci Heaps

6. Conjuntos Ajenos

6.1 Especificación de Conjuntos Ajenos

6.2 Modificación Conjuntos Ajenos

a. Unión por rango

b. Reducción de Trayectorias

6.3 Análisis Amortizado de Conjuntos Ajenos

7. Aplicaciones

Bibliografía

1. R. E. TARJAN, Amortized Computational Complexity, SIAM J. Algebraic Disc Math. Vol 6, No. 2, pp 306-318, 1985.
2. J.V. LEEUWEN and R.E. TARJAN, Worst-Case Analysis of Set Union Algorithms, Journal of ACM, 31(2):245-281, 1984.
3. R. E. TARJAN, Data Structures and Network Algorithms, CBMS-CNFS. Regional Conf Series in Applied Math. Society for Industrial and Applied Math., USA, 1988.
4. R. K. AHUJA, T.L. MAGNANTI, and J.B. ORLIN Networks Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
5. T.H. Cormen, C.L. Leiserson, and R.I. Riverst, Introduction to Algorithms, MIT Press and McGrawHill, NewYork, 2nd Edition, Third priting, 2002