Encabezado Facultad de Ciencias
Presentación

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

Optativas, Algoritmos Paralelos

Grupo 7105, 60 lugares. 12 alumnos.
Profesor María de Luz Gasca Soto lu mi vi 12 a 13
Ayudante Antonio César Álvarez García ma ju 12 a 13
Ayud. Lab. Andrea Fernanda Muñiz Patiño lu 14 a 16

 

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 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)

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

Requisito Ideal: Tener aprobados los cursos de

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>>

Imagen interactiva sobre el curso:

https://view.genial.ly/601b550aa60d6e0d7e78951a/vertical-infographic-algoritmosparalelos

Liga de la primera reunión:

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

+++ +++ Durante las primeras dos semana de clases usaremos esta liga +++ +++

https://meet.google.com/lookup/fd4vd3bomv

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

Dinámica del curso en línea

Plataforma en línea: Classromm y Meet

Sesiones de clases síncronas: 3 clases 2 con la profesora y 1 con la ayudante 1 sesión para dudas, para especificaciones asiste el primer día.

Sesiones de clases asíncronas: Se dejará material en el Classroom y en el Drive (página del curso)

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

Recursos Didácticos a usar en el curso

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

Además de la Página del curso y el Correo electrónico.

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.

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

Dinámica del Curso:

Habrá exposiciones, al menos dos, por parte de los estudiantes.
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. Aviso de privacidad.