Encabezado Facultad de Ciencias
Presentación

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

Optativas, Algoritmos Paralelos

Grupo 7106, 20 lugares. 8 alumnos.
Profesor María de Luz Gasca Soto lu mi vi 12 a 13 P204
Ayudante Rodrigo Fernando Velázquez Cruz ma ju 12 a 13 P204
Ayud. Lab. Mario Arturo Nieto Butron ju 13 a 15 Laboratorio de Ciencias de la Computación 3

 

Motivación:

La computación en paralelo ha transformado el campo de las Ciencias de la Computación (CC). Prácticamente todos los aspectos de CC 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 CC 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 ser analizado para determinar qué 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, efectividad y bondada 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)

---------- ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Requisito Ideal: Haber cursado las materias:

Estructuras de Datos y Análisis de Algoritmos

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Sitio del curso:

https://sites.google.com/ciencias.unam.mx/algoritmosparalelos

<<Es necesario acceder desde una cuenta de ciencias>>

Primera reunión:

***---*** La primera reunión será el Lunes 30 de Enero a la hora de clase ***---**

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Dinámica del curso: Curso Presencial

Habrá exposiciones, al menos dos, por parte de los estudiantes.

Se programarán algunos Algoritmos Básicos

Habrá, al menos, una tarea por Tema

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Recursos Didácticos a usar en el curso

Herramientas digitales: Jamboard, Google Chat, Google Slides, Google Drive, Mail y Meet

Material didáctico digital:

Libros de texto, tesis y artículos digitales (Bidi-Unam)
Lectures (material tomado de alguna universidad)
Notas de clase del profesor
Ejercicios y Notas preparadas por el profesor y ayudante.

--- --- --- ---

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. Aviso de privacidad.