PDF de programación - Divide y vencerás

Divide y vencerás

Diseño y Análisis de Algoritmos

Divide y vencerás

Contenidos

Contenidos

1

Introducción

2 Transforma y vencerás

3 Decrementa y vencerás

4 Divide y vencerás

URJC

DAA

2 / 54

Divide y vencerás

Introducción

Introducción

URJC

DAA

3 / 54

Divide y vencerás

Introducción

Divide y vencerás

Uno de los más importantes paradigmas de diseño algorítmico

Se basa en la resolución de un problema dividiéndolo en dos o más
subproblemas de igual tipo o similar

El proceso continúa hasta que éstos llegan a ser lo suficientemente
sencillos como para que se resuelvan directamente

Al final, las soluciones a cada uno de los subproblemas se combinan
para dar una solución al problema original

Muchos algoritmos basados en esta estrategia son recursivos

También hay algoritmos iterativos de divide y vencerás

URJC

DAA

4 / 54

Divide y vencerás

Introducción

Simplificación y descomposición de problemas

Las palabras clave en este tema van a ser la simplificación y la
descomposición de problemas

Veremos tres estrategias para simplificar y descomponer problemas:

Transforma y vencerás

Decrementa y vencerás

Divide y vencerás

URJC

DAA

5 / 54

Divide y vencerás

Transforma y vencerás

Transforma y vencerás

URJC

DAA

6 / 54

Divide y vencerás

Transforma y vencerás

Transforma y vencerás

Esta estrategia también se denomina reducción

Esta técnica procura resolver un problema transformándolo en otro
más simple, conocido, o para el que existan algoritmos eficientes

URJC

DAA

7 / 54

Problema AtransformaciónProblema Bsolución Bresoluciónsencillao eficienteresolucióndifícilo ineficientesolución Apaso sencillo Divide y vencerás

Transforma y vencerás

Encontrar la mediana de un array desordenado

Sea un array v de n números

1 Ordenar el array v −→ Θ(n log n)
2 Devolver

v [(n + 1)/2] si n es impar
v [n/2] + v [1 + n/2]

si n es par

2

URJC

DAA

8 / 54

425561034587425561034587ordenar4.5 Divide y vencerás

Transforma y vencerás

Estimación del valor de π

Planteamos un problema alternativo

Buscamos una aproximación del perímetro p de un círculo de
radio R

p = 2πR ⇒ π =

p
2R

Aproximamos un círculo con un polígono regular inscrito o
circunscrito al círculo

El perímetro del polígono inscrito pi nos dará una cota inferior de p

El perímetro del polígono circunscrito pc nos dará una cota superior
de p

pi
2R ≤ π ≤

pc
2R

URJC

DAA

9 / 54

Divide y vencerás

Transforma y vencerás

Estimación del valor de π

Comenzamos por un polígono regular inscrito (por ejemplo, un
hexágono), cuyo perímetro será 6R

A continuación, doblamos el número de lados, obteniendo una mejor
aproximación

El perímetro de un polígono con el doble de lados se puede obtener
fácilmente a partir del primero
Los perímetros de los polígonos circunscritos se pueden obtener de los
perímetros de los polígonos inscritos

URJC

DAA

10 / 54

DodecágonoregularHexágonoregular Divide y vencerás

Transforma y vencerás

Estimación del valor de π

URJC

DAA

11 / 54

RyL/2xlL' Divide y vencerás

Transforma y vencerás

Estimación del valor de π

Si el lado de un polígono inscrito mide L, se puede hallar la longitud un lado del
polígono l con el doble de lados

R 2 = y 2 + L
L

2


2
2 ⇒ y =
R 2 − L

2 − 2R
2 + R 2 + R 2 − L
R 2 − L

2

l =

2

2

2


R 2 − L

4 − L
2

2

R

x = R − y = R −



2 = R

2

2 −

El lado L de un polígono circunscrito se puede hallar a partir del lado L de un
polígono inscrito

L
R

=

L
y

⇒ L



=

LR
y

la estimación de π se obtiene a partir de los perímetros hallados:

L · número de lados

2R

≤ π ≤ L · número de lados

2R

URJC

DAA

12 / 54

Divide y vencerás

Transforma y vencerás

Otros métodos para estimar del valor de π

Simulación Monte Carlo

Integración numérica

Series
arctan x = x − x 3
3

+

x 5
5

− x 7
7

+ . . .

para x = 1 ⇒ π
4

= 1− 1
3

+

1
5

− 1
7

+ . . .

URJC

DAA

13 / 54

Divide y vencerás

Transforma y vencerás

Raíz cuadrada

Deseamos hallar √a
Transformamos el problema en el de hallar un cero de una función

x = √a → x 2 = a → x 2 − a = 0

Por tanto, querremos hallar un cero de la función y = x 2 − a
Como x será generalmente un número real, nos podemos conformar
con una aproximación

Hay varios métodos para resolver este nuevo problema, por ejemplo:

Método de Newton-Raphson (que veremos a continuación)
Método de bipartición (de “decrementa y vencerás”)

URJC

DAA

14 / 54

Divide y vencerás

Transforma y vencerás

Método de Newton-Raphson

Se trata de un método iterativo, que parte de un valor inicial x0, y aplica la
siguiente regla para hallar un cero de la función f (x):

xn+1 = xn − f (xn)
f (xn)

En cada iteración se busca la recta tangente a f (x) que pasa por el punto
(xn, f (xn))

El corte de la recta con el eje de abscisas constituye el nuevo punto xn+1

URJC

DAA

15 / 54

Divide y vencerás

Transforma y vencerás

Método de Newton-Raphson

El método surge del desarrollo de f (x) en serie de Taylor, para un
entorno del punto xn:

f (x) = f (xn) + f (xn)(x − xn) + (x − xn)2 f (xn)

2!

+ ...

Si se trunca el desarrollo a partir del término de grado 2, se obtiene la
recta tangente (que pasa por el punto (xn, f (xn)))

Posteriormente evaluamos en xn+1:

f (xn+1) = f (xn) + f (xn)(xn+1 − xn)

Si asumimos que xn+1 tiende hacia el cero de la función, podemos
sustituir f (xn+1) = 0, obteniéndose el algoritmo

URJC

DAA

16 / 54

Divide y vencerás

Transforma y vencerás

Raíz cuadrada - método de Newton-Raphson
Debemos aplicar la regla para f (x) = x 2 − a, con f (x) = 2x

xn+1 = xn −

x 2
n − a
2xn

=

2x 2
n
2xn −

x 2
n − a
2xn

=

x 2
n + a
2xn

URJC

DAA

17 / 54

−10123456−25−20−15−10−50510152025xnxn+1f(x)=x2−13 Divide y vencerás

Transforma y vencerás

Factorización LU

Supongamos que queremos resolver un sistema de ecuaciones Ax = b repetidas
veces, para muchos valores diferentes de b, pero para la misma matriz A

Para acelerar el cálculo se puede realizar una factorización LU

Sea A una matriz cuadrada en invertible, buscamos una factorización A = LU,
donde L es triangular inferior, y U triangular superior (del mismo tamaño). Para
una matrix de 3 × 3 tendríamos:

a11

a21
a31

 =

l11

l21
l31

a12
a22
a32

a13
a23
a33

u11

0
0

0
l22
l32

0
0
l33



u12
u22
0

u13
u23
u33

Para resolver el sistema Ax = b ahora se van a resolver dos, pero más sencillos:

Ax = LUx = b ⇒ Ly = b, Ux = y

Una descomposición es útil cuando hay que hacer repetidas operaciones con la
matriz A

URJC

DAA

18 / 54

Divide y vencerás

Decrementa y vencerás

Decrementa y vencerás

URJC

DAA

19 / 54

Divide y vencerás

Decrementa y vencerás

Decrementa y vencerás

La descomposición de un problema genera un solo subproblema

La solución al subproblema puede ser la solución al problema original

Para otros problemas se requiere realizar alguna operación adicional
con la solución al subproblema

URJC

DAA

20 / 54

ProblemasoluciónoperaciónsencillaSubproblemadecrementa Divide y vencerás

Decrementa y vencerás

Búsqueda binaria en un array ordenado

Se compara el elemento central con el elemento a buscar

Si no se encuentra se busca en alguna de las dos mitades

a

b + T (n/2)

T (n) =

si n = 1
si n ≥ 2

∈ Θ(log n)

URJC

DAA

21 / 54

Divide y vencerás

Decrementa y vencerás

Método de bipartición

Método para hallar un cero de una función f continua en un intervalo [a, b]

Los signos de f (a) y f (b) son distintos

Se busca un cero en la mitad
del intervalo c = (a + b)/2

Si no se encuentra se busca en
[a, c] o [c, b]

Se repite el proceso hasta una
determinada precisión ε (hasta
que el ancho del intervalo sea
menor que 2ε)

URJC

DAA

22 / 54

Divide y vencerás

Decrementa y vencerás

Ordenación por selección

1 Encontrar el menor elemento de una lista

2

Intercambiarlo con el primero de la lista

3 Aplicar el algoritmo de nuevo al resto de la lista (toda la lista salvo el

primer elemento)

Observad que se ha omitido a propósito mostrar más niveles para
ilustrar 2, 3, 4. . . elementos ordenados

Sólo se muestra la descomposición necesaria para realizar el diseño

URJC

DAA

23 / 54

problema (tamaño n)problema (tamaño n-1) Divide y vencerás

Decrementa y vencerás

Algoritmo de Euclides

La reducción del tamaño del problema no siempre es tan obvia

El algoritmo de Euclides encuentra el máximo común divisor de dos
números naturales

Hay dos versiones

mcd1(m, n) =

 n

mcd1(n, m)
mcd1(m, n − m)

n

mcd2(m, n) =

mcd2(n %m, m)

si m = 0
si m > n
si (m ≤ n) y (m = 0)

si m = 0
si m = 0

En cada paso nos vamos acercando al caso base

URJC

DAA

24 / 54

Divide y vencerás

Decrementa y vencerás

Algoritmo de Euclides - Demostración mcd1

 n

mcd1(m, n) =

mcd1(n, m)
mcd1(m, n − m)

si m = 0
si m > n
si (m ≤ n) y (m = 0)

Supongamos que m ≤ n (en caso contrario el propio algoritmo intercambia
los parámetros)
m = az, n = bz, con a ≤ b

z son los factores primos (máximo común múltiplo)
a y b no comparten factores primos

Hacemos b = a + c
n = bz = (a + c)z = (a1 ··· ak + c1 ··· cl )z

No se puede sacar factor común. Si se pudiera sería otro factor de z.
a, c no comparten primos

Por tanto, dado que z = mcd1(az, bz) = mcd1(az, cz), y c = b − a
tenemos:

mcd1(m, n) = mcd1(az, bz) = mcd1(az, cz) = mcd1(m, n − m)

URJC

DAA

25 / 54

Divide y vencerás

Decrementa y vencerás

Algoritmo de Euclides - Demostración mcd2

n

mcd2(m, n) =

mcd2(n %m, m)

si m = 0
si m = 0

Supongamos que m ≤ n (en caso contrario el propio algoritmo intercambia los
parámetros)
m = az, n = bz, con a ≤ b

z son los factores p