Encabezado Facultad de Ciencias
Presentación

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

Optativas, Algoritmos Paralelos

Grupo 7068, 23 lugares. 6 alumnos.
Profesor María de Luz Gasca Soto lu mi vi 13 a 14 Taller de Computación Visual e Innovación Tecnológica
Ayudante Fernando Michel Tavera ma ju 13 a 14 Taller de Computación Visual e Innovación Tecnológica
Ayud. Lab. Daniel Michel Tavera lu 14 a 16 Laboratorio de Ciencias de la Computación 1
 

Sitio del curso:

https://sites.google.com/a/ciencias.unam.mx/algoritmos-paralelos-2018-2/

Motivación:

La computación en paralelo ha transformado el campo de las Ciencias de la Computación.
Prácticamente todos los aspectos de la computación se vieron afectados, afortunadamente, con ello se generó una riqueza de nuevos conceptos.
Desde la arquitectura de la computadora hasta los sistemas operativos; desde los lenguajes de programación y compiladores hasta las bases de datos y la inteligencia artificial; y desde la computación numérica hasta la combinatoria, cada rama de las ciencias de la computación ha sido obligada a resurgir con la computación en paralelo.
El cambio más impactante se dió en los fundamentos de las ciencias de la computación: El Diseño y Análisis de Algoritmos.
Justo cuando el estudio tradicional de los algoritmos había alcanzado un cierto grado de madurez y estabilidad con resultados importantes, la revolución de la computación en paralelo tomo lugar. Este rejuvenecimiento impacta y lleva al renacimiento del campo y se espera que esto continúe sin cesar por un largo tiempo.

Este curso es acerca de Algoritmos Paralelos. Dado un problema computacional, nuestro objetivo es mostrar cómo un algoritmo paralelo puede ser diseñado para ejecutarse sobre una computadora en paralelo y cómo puede seranalizado para determinar que tan bueno es.
En el proceso, se espera que el alumno desarrolle una nueva manera de pensar y pueda resolver los problemas, llegando así a apreciar la belleza y efectividad de los algoritmos paralelos.

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.
Programar algoritmos básicos.
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. Algoritmos Aleatorios.

IX. 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,
30% Programas
30% 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. Algoritmos Aleatorios.

IX. Topologías para Redes de Interconexión

B I B L I O G R A F Í A

1. Akl, Selim G. The Design and Analysis of Parallel Algoritms, Prentice-Hall, Inc, 1989.
2. Akl, S.G . Parallel Computation. Models and Methods. Printence Hall, 1997.
3. Casanova, H., Legrand, A., Robert, Y. Parallel Algorithms, CRC Press, 2008.
4. Chandí, K.M. & M.J. Parallel Program Design, A foundation.Addison Wesley, USA, 1988.
5. Chartran, G. And Oellermann, O.R. Applied and Algorithmic Graph Theory. Mc Graw Hill. USA, 1993.
6. Cormen, T.H; L.C.E. & R.R.L.Introduction to Algorithms, Addison Wesley, USA, 1990
7. Grama, A. Karypis, G., Kumar, V. Gupta, A.,Introduction to Parallel Computing, 2nd ed.,Addison Wesley, 2003.
8. JáJá, J.An Introduction to Parallel Algorithms. Addison Wesley, USA, 1992.
9.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.
10. Manber, Udi. Introduction to Algorithms. A Creative Approach, Addison Wesley, USA, 1989.
11. Rajasekaran, S. & Reif, J. Handbook of Parallel Computing. Models, Algorithms and Applications. Chapman & Hall/CRC, 2008
12. Sharp, J. A.An Introduction to Distributed and Parallel Algorithms. Oxford, 1987.

 


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.