Descomposicion Recursiva
Click here to load reader
-
Upload
israel-cueva -
Category
Education
-
view
1.141 -
download
5
Transcript of Descomposicion Recursiva
MULTIPROCESAMIENTO
DESCOMPOSICIÓN RECURSIVA
2010
Israel Cueva Bryan Coronel
INTRODUCCIÓN
3.2 TÉCNICAS DE DESCOMPOSICIÓN
•Uno de los pasos fundamentales que necesitamos llevar a cabo para resolver un problema en paralelo es el de dividir los cálculos a realizar en un conjunto de tareas
=> Divide y vencerás
INTRODUCCIÓN
Clasificación – Técnicas de descomposición:
•Descomposición recursiva, •Descomposición de datos,
•Descomposición de exploración•Descomposición especulativa.
Propósito general
Carácter más especial
3.2.1 DESCOMPOSICIÓN RECURSIVA
•La descomposición recursiva es un método para inducir la concurrencia en problemas que pueden resolverse mediante la estrategia "divide y vencerás".
Ejemplo: Quicksort
Reestructurar un cálculo
•A veces, es posible reestructurar un cálculo para que sea susceptible a la descomposición recursiva, incluso si el algoritmo utilizado para el problema no se basa en la estrategia "divide y vencerás".
•Por ejemplo, considere el problema de encontrar el elemento mínimo en una secuencia desordenada A de n elementos:
Ejemplo
El algoritmo en serie para solucionar este problema, escanea la secuencia completa A, guardando en cada paso el elemento mínimo encontrado hasta el momento como se ilustra en el algoritmo. Es fácil ver que este algoritmo de serie no muestra la concurrencia.
Una vez que reestructuramos este cálculo como un algoritmo divide y vencerás, se puede utilizar la descomposición recursiva para extraer la concurrencia. El algoritmo 3.2 es un algoritmo "divide y vencerás" para encontrar el elemento mínimo de una matriz.
Ejemplo
Ejemplo
Después de haber reestructurado el cálculo en serie de este modo, es fácil construir una tarea gráfica de dependencias para este problema.
BIBLIOGRAFÍA:
•Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, INTRODUCTION TO PARALLEL COMPUTING, Second Edition, Addison-Wesley.
ENLACES:
•http://es.wikipedia.org/wiki/Reglas_de_asociaci%C3%B3n
Sitios Web Administrador www.utpl.edu.ec/videoconferenciasBlogwww.utpl.edu.ec/blog/videoconferenciasRecursos Videoconferenciaswww.utpl.edu.ec/recursovideoconferencias