Profesora: Luz Gasca Soto
Ayudante: José de Jesús Vargas
Objetivos generales:
Conocer y establecer conceptos de la Complejidad y Análisis de Algoritmos Paralelos.
Introducir diferentes modelos de cómputo paralelo y establecer conceptos básicos sobre el área.
Comprender y explicar las diferentes técnicas sobre el Diseño y Justificación de Algoritmos Paralelos.
Revisión de novedosas Topologías para Redes de interconexión (Interconnection Networks)
T E M A R I O
I. Conceptos Básicos
II. Técnicas Básicas
III. Listas y Árboles
IV. Búsquedas y Ordenamientos
V. Teoría de Gráficas
VI. Geometría Computacional
VII. Cadenas.
VIII. Métodos Numéricos.
IX. Algoritmos Aleatorios.
X. Topologías para Redes de Interconexión
--- --- --- ---
Dinámica del Curso:
Habrá exposiciones, al menos dos, por parte de los estudiantes sobre algunos temas.
Se programarán algunos Algoritmos Básicos
Habrá, al menos, una tarea por Tema
--- --- ---
Evaluación:
40% Exposiciones,
20% Programas
40% Tareas
--- --- --- ---
T E M A R I O (Desglosado)
I. Conceptos Básicos
1. Procesamiento Paralelo
2. Modelos de Cómputo Paralelos
3. Desempeño computacional de algoritmos paralelos.
4. Complejidad de la comunicación.
II. Técnicas Básicas
1. Árboles balanceados.
2. Técnica Pointer Jumping.
3. Técnica Divide y vencerás.
4. Particionamiento (Partitioning)
5. Técnica de Pipelining
6. Aceleramiento en cascada
7.Técnica Symmetry Breaking
III. Listas y Árboles
1. Técnica List Ranking.
2. Técnica de Euler.
3. Contracción de árboles.
4. Antecesor común más cercano.
IV. Búsquedas y Ordenamientos
1. Búsquedas.
2. Mezclas (Merging).
3. Ordenamiento.
4. Ordenamiento en redes (Sorting Network).
5. Problema de selección.
6. Cotas Mínimas.
V. Teoría de Gráficas
1 . Componentes conexas.
2 . Árboles generadores de peso mínimo.
3 . Componentes bi-conexas.
4 . Descomposición por orejas.
5. Gráficas dirigidas.
VI. Geometría Computacional
1 . Envolvente convexa (revisado).
2 . Intersección de conjuntos convexos.
3 . Traslape de planos (Plane Sweeping).
4 . Problemas de visibilidad.
5. Dominancia (DominanceCounting).
VII. Cadenas.
1. Apareamientos.
2. Análisis de texto.
3. Análisis de patrones.
4. Árboles de sufijos.
5. Aplicaciones para árboles de sufijos.
VIII. Métodos Numéricos.
IX. Algoritmos Aleatorios.
X. Topologías para Redes de Interconexión
B I B L I O G R A F Í A
1. Casanova, H., Legrand, A., Robert, Y.
Parallel Algorithms, CRC Press, 2008.
2. Chartran, G. And Oellermann, O.R.
Applied and Algorithmic Graph Theory. Mc Graw Hill. USA, 1993.
3. Cormen, T.H; L.C.E. & R.R.L.
Introduction to Algorithms, Addison Wesley, USA, 1990
4. JáJá, J.
An Introduction to Parallel Algorithms. Addison Wesley, USA, 1992.
5. Grama, A. Karypis, G., Kumar, V. Gupta, A.,
Introduction to Parallel Computing, 2nd ed.,Addison Wesley, 2003.
6.Leopold, C.,
Parallel and Distributed Computing: A Survey of Models, Paradigms and Approaches,
Wiley Series on Parallel and Distributed Computing, John Wiley y Son Inc. 2001.
7. Manber, Udi
Introduction to Algorithms. A Creative Approach, Addison Wesley, USA, 1989.
8. Sharp, J. A.
An Introduction to Distributed and Parallel Algorithms. Oxford, 1987.
9. Chandí, K.M. & M.J.
Parallel Program Design, A foundation.
Addison Wesley, USA, 1988.