PDF de programación - Algoritmos "Divide y Vencerás"

Algoritmos “Divide y Vencerás”
Algoritmos “Divide y Vencerás”
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

Algoritmos “Divide y Vencerás”
Algoritmos “Divide y Vencerás”

Ejemplo: Multiplicación de enteros grandes
 Ejemplo: Multiplicación de enteros grandes
 La técnica “divide y vencerás”
La técnica “divide y vencerás”
Características
 Características
Método general “divide y vencerás”
 Método general “divide y vencerás”
 Eficiencia de los algoritmos “divide y vencerás”
 Eficiencia de los algoritmos “divide y vencerás”
Eficiencia de los algoritmos “divide y vencerás”
Eficiencia de los algoritmos “divide y vencerás”
Aspectos de diseño
 Aspectos de diseño
 Determinación del umbral
Determinación del umbral
 Aplicaciones
Aplicaciones

11

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo clásico
Algoritmo clásico

1234*5678 = 1234* (5*1000 + 6*100+7*10+8)
1234*5678 = 1234* (5*1000 + 6*100+7*10+8)
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8

Operaciones básicas:
Operaciones básicas:
Multiplicaciones de dígitos: O(1)
 Multiplicaciones de dígitos: O(1)
 Sumas de dígitos: O(1)
Sumas de dígitos: O(1)
 Desplazamientos: O(1)
Desplazamientos: O(1)

Eficiencia algoritmo: O(nO(n22))
Eficiencia algoritmo:

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple

1234 = 12*100 + 34
1234 = 12*100 + 34
5678 = 56*100 + 78
5678 = 56*100 + 78
5678 = 56*100 + 78
5678 = 56*100 + 78

1234*5678 = (12*100 + 34)*(56*100 + 78)
1234*5678 = (12*100 + 34)*(56*100 + 78)
= 12*56*10000 + (12*78+34*56)*100 + (34*78)
= 12*56*10000 + (12*78+34*56)*100 + (34*78)

Idea: Se reduce una multiplicación de 4 cifras
Idea: Se reduce una multiplicación de 4 cifras

a cuatro multiplicaciones de 2 cifras,
a cuatro multiplicaciones de 2 cifras,
más tres sumas y varios desplazamientos.
más tres sumas y varios desplazamientos.

22

33

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple

1.1. Dividir
Dividir

X = 12345678 = xi*1044 + + xdxd
X = 12345678 = xi*1044 + + xdxd
X = 12345678 = xi*10
X = 12345678 = xi*10
Y = 24680135 = yiyi*10*1044 + yd+ yd
Y = 24680135 =

xi=1234
xi=1234
xi=1234
xi=1234
yiyi=2468
=2468

xdxd=5678
xdxd=5678
=5678
=5678
yd=0135
yd=0135

2.2. Combinar
Combinar

X*Y X*Y = (xi*10

= (xi*1044 + + xdxd) * (
= xi*= xi*yiyi*10*1088 + (xi*+ (xi*yd+xd

) * (yiyi*10*1044 + yd)+ yd)
yd+xd**yiyi)*10

)*1044 + + xdxd*yd*yd

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple

En general:
En general:

X = xi*10n/2n/2 + + xdxd
X = xi*10
Y = Y = yiyi*10*10n/2n/2 + yd+ yd

X*Y X*Y = (xi*10

= (xi*10n/2n/2 + + xdxd) * (
= xi*= xi*yiyi*10*10nn + (xi*+ (xi*yd+xd

) * (yiyi*10*10n/2n/2 + yd)+ yd)

yd+xd**yiyi)*10

)*10n/2n/2 + + xdxd*yd*yd

44

55

Multiplicación de enteros
Multiplicación de enteros

función multiplica (
función multiplica (X,Y,n
{{

X,Y,n) )

(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;

} } else

else {{

Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
z1 = multiplica (xi,
z1 = multiplica (xi, yiyi, n/2);
z1 = multiplica (xi,
z1 = multiplica (xi, yiyi, n/2);
, n/2);
, n/2);
z2 = multiplica (xi, yd, n/2);
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xdxd, , yiyi, n/2);
z3 = multiplica (
, n/2);
z4 = multiplica (
z4 = multiplica (xdxd, yd, n/2);
, yd, n/2);
auxaux = suma(z2,z3);
= suma(z2,z3);
z1 =
z1 = desplaza_izq
auxaux = = desplaza_izq
z = suma(z1,aux);
z = suma(z1,aux);
z = suma(z,z4);
z = suma(z,z4);
return
return z;z;

desplaza_izq(z1,n);
(z1,n);
desplaza_izq((aux,n

aux,n/2);
/2);

// DIVIDIR
// DIVIDIR

// COMBINAR
// COMBINAR

}}

}}

Multiplicación de enteros
Multiplicación de enteros

función multiplica (
función multiplica (X,Y,n
{{

X,Y,n) )

(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;

} } else

else {{

Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
z1 = multiplica (xi, yiyi, n/2);
z1 = multiplica (xi,
z1 = multiplica (xi,
z1 = multiplica (xi, yiyi, n/2);
, n/2);
, n/2);
z2 = multiplica (xi, yd, n/2);
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xdxd, , yiyi, n/2);
z3 = multiplica (
, n/2);
z4 = multiplica (
z4 = multiplica (xdxd, yd, n/2);
, yd, n/2);
auxaux = suma(z2,z3);
= suma(z2,z3);
z1 =
z1 = desplaza_izq
auxaux = = desplaza_izq
z = suma(z1,aux);
z = suma(z1,aux);
z = suma(z,z4);
z = suma(z,z4);
return
return z;z;

desplaza_izq(z1,n);
(z1,n);
desplaza_izq((aux,n

aux,n/2);
/2);

}}

}}

Eficiencia
Eficiencia

O(1)
O(1)
O(1)
O(1)

O(n)
O(n)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O(1)

66

77

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple
Algoritmo “divide y vencerás” simple

T(n) = 4T(n/2) + n ∈∈ O(nO(n22))
T(n) = 4T(n/2) + n

El cuello de botella está en el número de
 El cuello de botella está en el número de
multiplicaciones de tamaño n/2.
multiplicaciones de tamaño n/2.

Para mejorar la eficiencia debemos reducir el número
 Para mejorar la eficiencia debemos reducir el número
de multiplicaciones necesario…
de multiplicaciones necesario…

88

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”

xi+xd)*()*(yi+yd

yi+yd) = xi*

) = xi*yiyi + (xi*+ (xi*yd+xd

r = (
r = (xi+xd
p = xi*
p = xi*yiyi
p = xi*
p = xi*yiyi
q = q = xdxd*yd*yd

yd+xd**yiyi) +

) + xdxd*yd*yd

X*Y = p*10nn + (r+ (r--pp--q)*10
X*Y = p*10

q)*10n/2n/2 + q+ q

Luego podemos realizar una multiplicación de tamaño n
 Luego podemos realizar una multiplicación de tamaño n
a partir de 3 multiplicaciones de tamaño n/2.
a partir de 3 multiplicaciones de tamaño n/2.

99

Multiplicación de enteros
Multiplicación de enteros

función
función multiplicaDV
{{

multiplicaDV ((X,Y,n

X,Y,n) )

(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;

} } else

else {{

xi,xd););
xi,xd););
yi,yd););

(xi, yiyi, n/2);
multiplicaDV (xi,
, n/2);
multiplicaDV ((xdxd, yd, n/2);
, yd, n/2);
multiplicaDV (s1, s2, n/2);
(s1, s2, n/2);
= suma(r,--p,p,--q);
q);

Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
s1 = suma(
s1 = suma(xi,xd
s1 = suma(
s1 = suma(xi,xd
s2 = suma(
s2 = suma(yi,yd
p =
p = multiplicaDV
q =
q = multiplicaDV
r =
r = multiplicaDV
auxaux = suma(r,
auxaux = = desplaza_izq
p =
p = desplaza_izq
z = suma(
z = suma(p,aux,q
return
return z;z;

desplaza_izq((p,np,n););

desplaza_izq((aux,n

aux,n/2);
/2);

p,aux,q););

// DIVIDIR
// DIVIDIR

// COMBINAR
// COMBINAR

}}

}}

Multiplicación de enteros
Multiplicación de enteros

función
función multiplicaDV
{{

multiplicaDV ((X,Y,n

X,Y,n) )

(P es pequeño) {
ifif (P es pequeño) {
return X*Y;
return
X*Y;

} } else

else {{

xi,xd););
xi,xd););
yi,yd););

(xi, yiyi, n/2);
multiplicaDV (xi,
, n/2);
multiplicaDV ((xdxd, yd, n/2);
, yd, n/2);
(s1, s2, n/2);
multiplicaDV (s1, s2, n/2);
= suma(r,--p,p,--q);
q);

Obtener xi,
Obtener xi, xdxd, , yiyi, yd;
, yd;
s1 = suma(
s1 = suma(xi,xd
s1 = suma(
s1 = suma(xi,xd
s2 = suma(
s2 = suma(yi,yd
p =
p = multiplicaDV
q =
q = multiplicaDV
r =
r = multiplicaDV
auxaux = suma(r,
auxaux = = desplaza_izq
p =
p = desplaza_izq
z = suma(
z = suma(p,aux,q
return
return z;z;

desplaza_izq((p,np,n););

desplaza_izq((aux,n

aux,n/2);
/2);

p,aux,q););

}}

}}

Eficiencia
Eficiencia

O(1)
O(1)
O(1)
O(1)

O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n/2)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O(1)

1010

1111

Multiplicación de enteros
Multiplicación de enteros

Multiplicación de enteros de n cifras:
Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”

=
)(

nT

∈+

3T(n/2)

(O n

log 2

3

n

=

)

.1
nO

(

585

)

Implementación

Implementación

Operaciones

n = 10

n = 100

n = 1000

básica

n2

0.1 ms

10 ms

1 segundo

eficiente

n1.585

0.04 ms

1.48 ms

56.9 ms

n = 10000

100 segundos

2.19 segundos

La técnica “divide y vencerás”
La técnica “divide y vencerás”

La técnica “divide y vencerás” (DV) consiste en:
La técnica “divide y vencerás” (DV) consiste en:

 Descomponer el problema que hay que resolver en
Descomponer el problema que hay que resolver en
cierto número de
subproblemas más pequeños del
más pequeños del
cierto número de subproblemas
mismo tipo.
mismo tipo.
mismo tipo.
mismo tipo.

 Resolver de forma sucesiva e independiente todos
Resolver de forma sucesiva e independiente todos
estos subproblemas
estos
subproblemas..

Combinar las soluciones obtenidas para obtener la
 Combinar las soluciones obtenidas para obtener la
solución del problema original.
solución del problema original.

1212

1313

La técnica “divide y vencerás”
La técnica “divide y vencerás”

Características de los problemas
Características de los problemas
resolubles utilizando “divide y vencerás”
resolubles utilizando “divide y vencerás”

El problema se puede descomponer en otros del mismo
 El problema se puede descomponer en otros del mismo
tipo que el original y de tamaño más pequeño
tipo que el original y de tamaño más pequeño
tipo que el original y de tamaño más pequeño
t