PDF de programación - Tema 08: Divide y vencerás (DyV) - Análisis de algoritmos

Análisis de algoritmos

Tema 08: Divide y vencerás (DyV)

M. en C. Edgardo Adrián Franco Martínez
http://www.eafranco.com
[email protected]

@edfrancom

edgardoadrianfrancom

1

Contenido
• Introducción
• Divide y vencerás
• Observaciones sobre Divide y Vencerás
• Complejidad de divide y vencerás
• Ejemplo: Búsqueda del máximo y del mínimo

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



2



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



Introducción
• En la cultura popular, divide y vencerás hace referencia a un
refrán que implica resolver un problema difícil, dividiéndolo
en partes más simples tantas veces como sea necesario,
hasta que la resolución de las partes se torna obvia. La
solución del problema principal se construye con las
soluciones encontradas.

• En las ciencias de la computación, el término divide y
vencerás hace referencia a uno de los más importantes
paradigmas de diseño algorítmico.

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



3



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



• El paradigma divide y vencerás, está basado en buscar la
resolución recursiva de un problema dividiéndolo en dos o
más subproblemas de igual tipo o similar (Sin que se
solapen). El proceso continúa hasta que éstos llegan a ser lo
suficientemente sencillos como para que se resuelvan
las soluciones a cada uno de los
directamente. Al final,
subproblemas
se combinan para dar una solución al
problema original.

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



Ordenamiento por mezcla

4



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



• Dividir y vencer es la base de varios algoritmos
eficientes para casi cualquier tipo de problema
como, por ejemplo, algoritmos de ordenamiento
(mergesort, quicksort, entre otros), multiplicar
números grandes (Karatsuba), análisis sintácticos
(top-down),
la transformada discreta de Fourier,
multiplicación rápida de matrices (Strassen), etc.

• Analizar y diseñar algoritmos de DyV son tareas que
lleva tiempo dominar. Al igual que en la inducción, a
veces es necesario sustituir el problema original por
uno más complejo para conseguir
la
recursión, y no hay un método sistemático de
generalización.

realizar

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



5



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



Divide y vencerás

• “El método divide y vencerás
consiste en
descomponer el problema en una serie de
subproblemas de menor tamaño, al resolver estos
subproblemas usando siempre la misma técnica,
las soluciones parciales se combinan para obtener
la solución del problema original”.

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



6



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



• "Tenemos un problema complejo al cual dividimos
en subproblemas mas pequeños a resolver. Para
resolver cada subproblema seguimos el mismo
procedimiento hasta que llegamos a un problema
que es trivial. Una vez resueltos los subproblemas los
combinamos para dar
solución al problema
original".

• De esta forma DyV se expresa de manera natural
mediante un algoritmo recursivo.

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



7

fun divide_y_venceras(x: problema) dev y:solución

si pequeño(x) entonces

y:=metodo_directo(x)

si no

{descomponer x en k >= 1 problemas más pequeños}
{x1, x2, ..., kx}:=descomponer(x)}
{resolver recursivamente los subproblemas}
para j=1 hasta k hacer

yj:= divide_y_venceras(xj)

fin para
{combinar los yj para obtener una solución y para x}
y:=combinar(y1, ..., yk)

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



fin si

fin

La función pequeño(x) es un predicado que
determina si el tamaño del problema x es
suficientemente pequeño para ser resuelto sin
dividir más. Si es ese el caso, el problema se
resuelve mediante la función método_directo(x).

8



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P



• Para que la aplicación del método divide y vencerás,
convenga debe cumplirse que:
1. Las operaciones descomponer y combinar deben ser

bastante eficientes.

2. El número de subproblemas generados sea pequeño
sean aproximadamente del
3. Los

subproblemas

mismo tamaño y no solapen entre sí.

• La función complejidad para un problema de
tamaño n es un sistema de ecuaciones recurrentes
de la forma:

s
o
m



l

t
i
r
o
g
a
e
d

s
i
s
i
l

á
n
A

)
V
y
D



(

s
á
r
e
c
n
e
v
y
e
d
i
v
i
D
8
0



z
e
n
í
t
r
a
M
o
c
n
a
r
F
n
á
i
r
d
A
o
d
r
a
g
d
E

.
f
o
r
P