PDF de programación - Programación II - Tema 6. Divide y Vencerás

Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos

Tema 4. Introducción a los Algoritmos
Tema 5. Algoritmos voraces, heurísticos y aproximados

Tema 6. Divide y Vencerás

Tema 7. Ordenación
Tema 8. Programación dinámica
Tema 9. Vuelta atrás
Tema 10.Ramificación y poda
Tema 11.Introducción a los Algoritmos Genéticos
Tema 12.Elección del esquema algorítmico

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

Tema 6. Divide y Vencerás
6.1. Características Generales
6.2. Eficiencia de los algoritmos DyV
6.3. Búsqueda binaria
6.4. Problema de la selección
6.5. Subsecuencia de suma máxima
6.6. Otros algoritmos DyV
6.7. Bibliografía



1



Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

6.1 Características Generales

6.1 Características Generales

Técnica “Divide y Vencerás” (Divide and Conquer):

• Se divide el problema en subproblemas

- y, recursivamente, cada subproblema se divide de nuevo
• Cuando el caso es lo suficientemente sencillo se resuelve

utilizando un algoritmo directo (no recursivo)
- el algoritmo directo debe ser eficiente para problemas

sencillos

- no importa que no lo sea para problemas grandes

• Cada subproblema se resuelve de forma independiente
• Finalmente se combinan las soluciones de todos los

subproblemas para formar la solución del problema original

Programación II

© Mario Aldea Rivas

13/04/11

2

3

Tema 6. Divide y Vencerás

6.1 Características Generales

Pseudocódigo genérico de un algoritmo DyV
método divideYVencerás(x) retorna y
si x es suficientemente sencillo entonces
// caso directo
retorna algoritmoDirecto(x)
fsi
// caso recursivo
descompone x en subproblemas x1, x2, .., xs
desde i := 1 hasta s hacer
// llamadas recursivas
yi := divideYVencerás(xi)
fhacer
// combina las soluciones
y := combinación de las soluciones parciales (yi)
retorna y
fmétodo

© Mario Aldea Rivas

13/04/11

4

Programación II

Tema 6. Divide y Vencerás

6.1 Características Generales

Cuando utilizar algoritmos DyV
Para que resulte interesante aplicar DyV debe verificarse que:

• la formulación recursiva nunca resuelva el mismo subproblema

más de una vez

• la descomposición en subproblemas y la combinación de las

soluciones sean operaciones eficientes

• los subproblemas sean aproximadamente del mismo tamaño

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

5

6.2 Eficiencia de los algoritmos DyV

6.2 Eficiencia de los algoritmos DyV

• Se obtiene aplicando el “Master Theorem” que permite resolver
recurrencias del tipo:
t(n) = s·t(n/b) + g(n) (donde g(n) es O(nk))

• Donde se supone que:
• el algoritmo divide el problema en s subproblemas
- cada uno de un tamaño aproximado n/b
• g(n) es el tiempo necesario para realizar la descomposición y
combinación de resultados

• Cuando g(n) es O(nk) puede demostrarse que t(n) es:
• Θ(nk) si s<bk
• Θ(nk log n) si s=bk
• Θ(nlogb s) si s>bk

Programación II

© Mario Aldea Rivas

13/04/11

6

Tema 6. Divide y Vencerás

Selección del umbral de utilización del algoritmo

6.2 Eficiencia de los algoritmos DyV

directo

Utilizaremos el algoritmo directo cuando el tamaño del problema
sea menor que el umbral elegido
Tiene gran influencia en el tiempo de ejecución del algoritmo

• aunque no en su ritmo de crecimiento

El valor apropiado estará cerca del
tamaño para el que el tiempo empleado
por el algoritmo recursivo se iguala con
el utilizado por el algoritmo directo

T(n)

directo

recursivo

Puede obtenerse teóricamente o realizando medidas de tiempos

umbral

n

7

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

6.3 Búsqueda binaria

6.3 Búsqueda binaria
Búsqueda de un elemento en una tabla ordenada
Solución secuencial:
método búsquedaSecuencial(entero[1..n] t, entero x)
retorna entero
desde i:=1 hasta n hacer
si t[i] = x entonces
retorna i // encontrado
fsi
fhacer
retorna -1 // no encontrado
fmétodo

Eficiencia: O(n)

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

Solución DyV: algoritmo “búsqueda binaria”
Se trata de una de las aplicaciones más sencillas de DyV

• realmente no se va dividiendo el problema sino que se va

reduciendo su tamaño a cada paso
- algoritmos DyV denominados de reducción o simplificación

6.3 Búsqueda binaria

Ejemplo: búsqueda de x=9

1

2

-5

-2

3

0

4

3

5

8

paso 1

i

paso 2

6

8

k

7

9

i

8

9

10

11

12

15

26

31

j

j

k

paso 3

• En cada paso (hasta que x=t[k] o i>j)

i,k

j

- si x > t[k] ⇒ i = k+1
- si x < t[k] ⇒ j = k-1
- k = (i + j) / 2

x = t[k]

x > t[k]

no

no

sí

sí

no

-

Programación II

© Mario Aldea Rivas

13/04/11

8

9

Tema 6. Divide y Vencerás

6.3 Búsqueda binaria
Búsqueda binaria (cont.)

método búsquedaBinaria(entero[1..n] t, entero i,
entero j, entero x) retorna entero
// calcula el centro
k := (i + j)/2
// caso directo
si i > j entonces
retorna -1 // no encontrado
fsi
si t[k] = x entonces
retorna k // encontrado
fsi
// caso recursivo
si x > t[k] entonces
retorna búsquedaBinaria(t, k+1, j, x)
sino
retorna búsquedaBinaria(t, i, k-1, x)
fsi
fmétodo

© Mario Aldea Rivas

13/04/11

10

Programación II

Tema 6. Divide y Vencerás

6.3 Búsqueda binaria

Eficiencia de “búsqueda binaria”
Como vimos, el tiempo requerido por un algoritmo DyV es de la
forma:t(n) = s·t(n/b) + g(n)
Para este algoritmo:
• cada llamada genera una llamada recursiva (s=1)
• el tamaño del subproblema es la mitad del problema original
(b=2)
• sin considerar la recurrencia el resto de operaciones son O(1)
luego g(n) es O(1)=O(n0) (k=0)

Estamos en el caso:
• s=bk (1=20)
• luego t(n) es Θ(nk log n) = Θ(n0 log n) = Θ(log n)

Programación II

Tema 6. Divide y Vencerás

6.4 Problema de la selección

© Mario Aldea Rivas

13/04/11

11

6.4 Problema de la selección

Búsqueda del k-ésimo menor elemento de una tabla

• es decir: si la tabla estuviera ordenada crecientemente, el

elemento devuelto sería el que ocuparía el k-ésimo lugar

Solución obvia: ordenar la tabla y acceder al k-ésimo elemento
• coste O(n log n) (coste de la ordenación)
Es posible encontrar un algoritmo más eficiente utilizando DyV:

• se elige un valor como “pivote”
• se reorganiza la tabla en dos partes, una con los elementos

mayores que el pivote y otra con los elementos menores
- la clave estará en la selección correcta del pivote

• se realiza de nuevo el proceso sobre la parte de la tabla que

contiene el elemento buscado

Programación II

© Mario Aldea Rivas

13/04/11

12

Tema 6. Divide y Vencerás

Implementación del algoritmo de selección
Método público select
• llama a selectRec con los parámetros iniciales

6.4 Problema de la selección

/**
* Retorna el elemento del array t que ocuparía la
* posición k-ésima en el caso de que el array
* estuviera ordenado
* @param t array
* @param k posición del elemento buscado (la primera
* posición es la 1, no la 0)
* @return valor del elemento buscado
*/
public static int select(int[] t, int k) {
}

return selectRec(t,0,t.length-1,k);

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

13

6.4 Problema de la selección

Implementación del algoritmo de selección (cont.)

Método privado selectRec
• es el realmente implementa el algoritmo recursivo DyV
/**
* Retorna el elemento de la parte del array t
* comprendida entre los índices ini y fin que ocuparía
* la posición k-ésima (en esa parte) en el caso de que
* esa parte estuviera ordenada
* @param t array
* @param ini índice inicial de la parte de t utilizada
* @param fin índice final de la parte de t utilizada
* @param k posición del elemento buscado (la primera
* posición es la 1, no la 0)
* @return valor del elemento buscado
*/
private static int selectRec(int[] t,

int ini, int fin, int k) {

... código en la transparencia siguiente ...

}

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

14

6.4 Problema de la selección

private static int selectRec(int[] t,

int ini, int fin, int k) {

Implementación del algoritmo de selección (cont.)

return t[ini]; // elemento en la pos. k-ésima

// caso directo
if (ini == fin) {
}
// reorganiza los elementos y retorna la posición
// del último elemento menor que el pivote
int p = reorganiza(t, ini, fin);
int k1 = p - ini + 1; // offset del primer elemento
// mayor que el pivote
// divide
if (k <= k1) {
} else {
}

return selectRec(t,ini,p,k);
return selectRec(t,p+1,fin,k-k1);

}

Programación II

© Mario Aldea Rivas

13/04/11

15

Tema 6. Divide y Vencerás

6.4 Problema de la selección

Implementación del algoritmo de selección (cont.)

/**
* Reorganiza la parte de t comprendida entre los
* índices ini y fin en dos partes, una con los
* elementos mayores que el pivote y otra con los
* menores. Se toma como pivote t[ini]
* @param t array
* @param ini índice inicial de la parte de t utilizada
* @param fin índice final de la parte de t utilizada
* @return índice del último ele. menor que el pivote
*/
private static int reorganiza(int[] t,

int ini, int fin){

... código en la transparencia siguiente ...

}

Programación II

Tema 6. Divide y Vencerás

© Mario Aldea Rivas

13/04/11

16

6.4 Problema de la selección

private static int reorganiza(int[] t,

int ini, int fin) {

Implementación del algoritmo de selección (cont.)

int x=t[ini]; // usa el primer ele. como pivote
int i=ini-1; int j=fin+1;
while (true) {

Es más eficiente usar la
“pseudo-mediana” (ver pg. 21)

i++;

j--;

do { // busca ele. menor o igual que el pivote
}while (t[j]>x);
do { // busca ele. mayor o igual que el pivote
} while (t[i]<x);
if (i < j) {
} else {
}

int z=t[i]; t[i]=t[j]; t[j]=z; // intercambio
return(j);

}

}

Programación II

Tema 6. Divide y Vencerás

Ejemplo d