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