Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 2013) 2014-2

Optativas, Algoritmos Paralelos

Grupo 7060, 30 lugares. 8 alumnos.
Profesor María de Luz Gasca Soto lu mi vi 10 a 11 Taller de Ingeniería de Software
Ayudante Augusto Julio César Vega Gutiérrez ma ju 10 a 11 Taller de Ingeniería de Software
Ayud. Lab.

 

Algoritmos Paralelos Semestre 2014-II

Profesora: Luz Gasca Soto

Ayudante: Julio C. Vega

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.

T E M A R I O

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

XI. Algoritmos Distribuidos.

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.

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.