PDF de programación - Divide y vencerás

Divide y vencerás

Índice

• Bibliografía ->
• Introducción.->
• Esquema. ->
• Ejemplos.
• Simplificación ->

Marta Patiño & Ricardo Jiménez (c) 2001

1

Marta Patiño & Ricardo Jiménez (c) 2001

Bibliografía

Introducción

• “Fundamentals of Algorithms”. Brassard,

Bratley. 1996. (Cap. 7)

• “Algorithms. A Functional Programming

Approach”. Rabhi, Lapalme. 1999. (Cap. 8)

• “Fundamentals of Algorithms”. E.
Horowitz, S. Sahni. 1978. (Cap. 3)

• Divide y vencerás es una técnica de diseño
que consiste en descomponer un problema
en subproblemas, resolver cada
subproblema y combinar las soluciones. El
resultado es la solución del problema
original.

Marta Patiño & Ricardo Jiménez (c) 2001

3

Marta Patiño & Ricardo Jiménez (c) 2001

Introducción

Función DyV (x)
Si x es pequeño o sencillo Entonces

Devolver Resolver(x)

Si no

Descomponer en subproblemas x1,x2,...,xp
Desde i <- 1 hasta p

yi <- DyV(xi)

y <- Combinar(y1, y2, ...,yp)
Devolver y

Introducción

• En algunos problemas hay que resolver los

subproblemas en un orden determinado.

• El número de subproblemas (p)

generalmente es pequeño e independiente
del tamaño del problema.

• Si el número de subproblemas es 1, la

técnica se denomina simplificación.
Ejemplo: búsqueda binaria.

Marta Patiño & Ricardo Jiménez (c) 2001

5

Marta Patiño & Ricardo Jiménez (c) 2001

2

4

6

1

Introducción

• Consideraciones de uso:

– Decidir cuándo es un caso básico o dividir el

problema.

– El problema (las soluciones) se debe poder

dividir (combinar) de manera eficiente.

– Los subproblemas deben ser del mismo tamaño.

Esquema

dyv::(tproblema -> Bool) -> -- Es Trivial ?

(tproblema -> tsolucion) -> -- Resolver Caso Trivial
(tproblema -> [tproblema]) -> -- Dividir
([tsolucion] -> tsolucion) -> -- Combinar
tproblema -> -- problema
tsolucion

dyv estrivial resolver dividir combinar problema =

if estrivial problema then

resolver problema

else

combinar (map (dyv estrivial resolver dividir combinar)

(dividir problema))

Marta Patiño & Ricardo Jiménez (c) 2001

7

Marta Patiño & Ricardo Jiménez (c) 2001

8

Ordenación por mezcla (mergesort).

Dividiendo por la mitad

Ordenación por mezcla (mergesort).

Dividiendo por la mitad

type Problema = [Int]
type Solucion = [Int]
estrivial:: Problema -> Bool
estrivial [] = True
estrivial (primero:resto) = resto == []
resolver :: Problema -> Solucion
resolver xs = xs
dividir :: Problema -> [Problema]
dividir xs = [take mitad xs, drop mitad xs]

where mitad = length xs `div` 2

combinar :: [Solucion] -> Solucion
combinar [[], lista2] = lista2
combinar [lista1, []] = lista1
combinar [primero1:resto1, primero2:resto2] =

if primero1 <= primero2 then

primero1:(combinar [resto1, primero2:resto2])

else

primero2:(combinar [primero1:resto1, resto2])

Marta Patiño & Ricardo Jiménez (c) 2001

9

Marta Patiño & Ricardo Jiménez (c) 2001

10

Ordenación por mezcla (mergesort).

Dividiendo por la mitad

mergesort :: Problema -> Solucion
mergesort = dyv estrivial resolver dividir combinar

mergesort [3,6,1,3]

Ordenación por mezcla (mergesort).

Repartir los elementos

dividir :: Problema -> [Problema]
dividir [] = [[], []]
dividir [elto] = [[elto], []]
dividir (primero:segundo:resto) =

[primero:restolista1, segundo:restolista2]
where [restolista1, restolista2] = dividir resto

Complejidad:

n ⋅Θ

(

log

2 n

)

Marta Patiño & Ricardo Jiménez (c) 2001

11

Marta Patiño & Ricardo Jiménez (c) 2001

12

2

Ordenación rápida (quicksort)

import Divyvenc
type Problema = [Int]
type Solucion = [Int]

estrivial:: Problema -> Bool
estrivial [] = True
estrivial (primero:resto) = resto == []

resolver :: Problema -> Solucion
resolver xs = xs

Ordenación rápida (quicksort)

dividir :: Problema -> [Problema]
dividir [] = []
dividir (primero:resto) =

[menores, [primero], mayores] where

(menores, mayores) = separarmayoresymenores (resto,

primero)

combinar :: [Solucion] -> Solucion
combinar [primero, [segundo], tercero] =

concat [primero, segundo:tercero]

quicksort :: Problema -> Solucion
quicksort = dyv estrivial resolver dividir combinar

Marta Patiño & Ricardo Jiménez (c) 2001

13

Marta Patiño & Ricardo Jiménez (c) 2001

14

Ordenación rápida (quicksort)

--Nota: "Ord a" en declaración por utilización del "<"

estándar

separarmayoresymenores :: Ord a => ([a], a) -> ([a], [a])
separarmayoresymenores ([], n) = ([], [])
separarmayoresymenores (primero:resto, n) =

let (menores, mayores) =

separarmayoresymenores (resto, n) in

if primero < n then

(primero:menores, mayores)

else

(menores, primero:mayores)

Ordenación rápida (quicksort).

Caso básico, longitud = 2

estrivial:: Problema -> Bool
estrivial [] = True
estrivial [primero] = True
estrivial (primero:segundo:resto) = resto == []
resolver :: Problema -> Solucion
resolver [] = []
resolver [primero] = [primero]
resolver (primero:segundo:[]) =
if primero <= segundo then

primero:segundo:[]

else

segundo:primero:[]

Marta Patiño & Ricardo Jiménez (c) 2001

15

Marta Patiño & Ricardo Jiménez (c) 2001

16

Ordenación rápida

Complejidad:

En el peor caso.
Caso medio.

( 2nΘ
n ⋅Θ

(

)
log

2 n

)

Complejidad

)(nf

nTp
(

n es pequeño

)

+

ng
)(

b

e.o.c.

=)(nT

⋅{
{∈)(nT

( knΘ
)
nk ⋅Θ
(
( log pbnΘ

log
)

n

)

p <
p =
p >

kb
kb
kb

p nº de subprob.
b
fracción prob.
g(n) func. comb.
f(n)

func. resolver

Marta Patiño & Ricardo Jiménez (c) 2001

17

ngZk
)(.
∈∃
Marta Patiño & Ricardo Jiménez (c) 2001

Si

(
Θ∈

kn

)

18

3

Análisis de la Complejidad

de Mergesort

• Mergesort:

– p = 2 (se parte en 2 subproblemas).
– b = 2 (los subproblemas son ½ del problema orig.).
– g(n) es lineal, es decir, Θ(n1=nk).
– p = bk, ya que 2= 21.
– Luego t(n) es Θ(nk·log n)= Θ(n·log n).

Análisis de la Complejidad

de Quicksort

• Quicksort:

– Al no dividir en problemas de igual tamaño no puede

aplicársele la fórmula genérica de la complejidad del divide y
vencerás.

– Informalmente la complejidad se puede calcular como el

producto de:
• La complejidad de la profundidad del grafo de divide y vencerás

(lineal en el peor caso, logarítmica en mejor caso).

• La mayor de entre las complejidades de la división (lineal) y la

combinación (lineal).

• En peor caso, el quicksort tendría complejidad Ο(n2).
• En mejor caso, el quicksort tendría complejidad Ο(n·log n).

Marta Patiño & Ricardo Jiménez (c) 2001

19

Marta Patiño & Ricardo Jiménez (c) 2001

20

Simplificación

• Al dividir el problema se considera un único

subproblema.

• Ejemplos:

– Método logarítmico de la Potencia.
– Ceros de una función
– Búsqueda en un árbol binario

Esquema
module Simplif (simplificacion) where
simplificacion::

(tproblema -> Bool) -> -- Es Trivial ?
(tproblema -> tsolucion) -> -- Resolver Caso Trivial
(tproblema -> tproblema) -> -- Simplificar
tproblema -> -- problema
tsolucion

simplificacion estrivial resolver simplificar problema =

if estrivial problema then

resolver problema

else

simplificacion estrivial resolver simplificar

(simplificar problema)

Marta Patiño & Ricardo Jiménez (c) 2001

21

Marta Patiño & Ricardo Jiménez (c) 2001

22

Ejemplo: Potencia
=



impar(e)



b

no Si

Si



bb
•

e/2

1-e

e/2

•

b

eb

De este modo, en lugar de hacer e-1 productos se hacen
menos productos. ¿Cuántos se harían en el peor caso?
Los exponentes impares son los que ocasionan más productos.
Como un impar se transforma en un par (restándole 1), en el
peor caso el exponente alternaría entre pares e impares.

Ejemplos: Potencia

type Problema = (Int, Int)
type Solucion = Int
estrivial:: Problema -> Bool
estrivial (base, exp) = exp <= 1

resolver :: Problema -> Solucion
resolver (base, exp) =

if exp == 1 then

base

else
1

Marta Patiño & Ricardo Jiménez (c) 2001

23

Marta Patiño & Ricardo Jiménez (c) 2001

24

4

Ejemplos: Potencia

dividir :: Problema -> [Problema]
dividir (base, exp) = if (exp `mod` 2) == 0 then

[(base, exp `div` 2)]

else

[(base, 1), (base, exp-1)]

combinar :: [Solucion] -> Solucion
combinar [resultado] = resultado * resultado
combinar [base, resultado] = base * resultado

potencia :: (Int, Int) -> Int
potencia = dyv estrivial resolver dividir combinar

Ceros de una Función

• Los ceros de una función pueden buscarse

dicotómicamente de forma similar a la búsqueda
binaria.

• La condición básica es que la función sea continua

y tenga signo contrario en los dos extremos del
intervalo de búsqueda.

• El cero se considera encontrado cuando f(x) es

suficientemente pequeño.

• Si se particiona en el intervalo de la búsqueda por
la mitad, el cero sólo puede estar en una de las dos
mitades.

Marta Patiño & Ricardo Jiménez (c) 2001

25

Marta Patiño & Ricardo Jiménez (c) 2001

26

Ceros de una Función

Ejemplos: Ceros de una función

X

1

2

3

4

5

6

7

8

9 10 11 12

f(0) > 0

f(6) > 0

f(12) < 0

X

X

0

200

100

0

-100

-200

-300

-400

import Simplif
type Parcial = (Double, Double, -- Intervalo actual

(Double -> Double), -- función
(Double -> Bool)) -- EsCero

type Solucion = Double

-- cero de la función

estrivial:: Parcial -> Bool
estrivial (a, b, f, escero) = escero (f ((a+b)/2))

resolver:: Parcial -> Solucion
resolver (a, b, _, _) = (a+b)/2

El problema [0,12] se simplifica en [6,12]

Marta Patiño & Ricardo Jiménez (c) 2001

27

Marta Patiño & Ricardo Jiménez (c) 2001

28

Ejemplos: Ceros de una función

simplificar:: Parcial -> Parcial
simplificar (a, b, f, escero) =
let medio = ((a+b)/2) in

if f(a)*f(medio) < 0 then

(a, medio, f, escero)

else

(medio, b, f, escero)

cero::(Double -> Bool) -> Double -> Double -> (Double ->

Double) -> Double

cero escero a b f = simplificacion estrivial resolver simplificar (a,

b, f, escero)

Búsqueda en un Árbol de Búsqueda

• En un árbol de búsqueda se puede realizar

búsqueda dicotómica.

• Si el valor que