PDF de programación - Tema 2. Divide y vencerás - Parte I. Estructuras de Datos

Programa de teoría
Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 2. Divide y vencerás.

1

PARTE II: ALGORÍTMICA

Tema 2. Divide y vencerás.

2.1. Método general.
2.2. Análisis de tiempos de ejecución.
2.3. Ejemplos de aplicación.

2.3.1. Multiplicación rápida de enteros largos.
2.3.2. Multiplicación rápida de matrices.
2.3.3. Ordenación por mezcla y ordenación rápida.
2.3.4. El problema de selección.

A.E.D.

Tema 2. Divide y vencerás.

2

1

2.1. Método general.

• La técnica divide y vencerás consiste en:

– Descomponer un problema en un conjunto de subproblemas

más pequeños.

– Se resuelven estos subproblemas.
– Se combinan las soluciones para obtener la solución para el

problema original.

PROBLEMA

SOLUCIÓN

PROBLEMA

SOLUCIÓN

PROBLEMA

SOLUCIÓN

A.E.D.

Tema 2. Divide y vencerás.

3

2.1. Método general.

• Esquema general:

DivideVencerás (p: problema)

Dividir (p, p1, p2, ..., pk)
para i:= 1, 2, ..., k

si:= Resolver (pi)

solución:= Combinar (s1, s2, ..., sk)

• Normalmente para resolver los subproblemas se utilizan

llamadas recursivas al mismo algoritmo (aunque no
necesariamente).

• Ejemplo. Problema de las Torres de Hanoi.

A.E.D.

Tema 2. Divide y vencerás.

4

2

2.1. Método general.

A

B

C

• Ejemplo. Problema de las torres de Hanoi.

Mover n discos del poste A al C:
– Mover n-1 discos de A a B
– Mover 1 disco de A a C
– Mover n-1 discos de B a C

A.E.D.

Tema 2. Divide y vencerás.

5

2.1. Método general.

Hanoi (n, A, B, C: entero)

si n==1 entonces

mover (A, C)

sino

finsi

Hanoi (n-1, A, C, B)
mover (A, C)
Hanoi (n-1, B, A, C)

• Si el problema es “pequeño”, entonces se puede

resolver de forma directa.

• Otro ejemplo. Cálculo de los números de Fibonacci:

F(n) = F(n-1) + F(n-2)

• F(0) = F(1) = 1

A.E.D.

Tema 2. Divide y vencerás.

6

3

2.1. Método general.

• Ejemplo. Cálculo de los números de Fibonacci.

– El cálculo del n-ésimo número de Fibonacci se

descompone en calcular los números de Fibonacci n-1 y
n-2.

– Combinar: sumar los resultados de los subproblemas.

• La idea de la técnica divide y vencerás es aplicada

en muchos campos:
– Estrategias militares.
– Demostraciones lógicas y matemáticas.
– Diseño modular de programas.
– Diseño de circuitos.
– Etc.

A.E.D.

Tema 2. Divide y vencerás.

7

2.1. Método general.

• Esquema recursivo. Con división en 2 subproblemas y

datos almacenados en una tabla entre las posiciones p y q:
DivideVencerás (p, q: indice)
var m: indice

sino

finsi

si Pequeño (p, q) entonces

solucion:= SoluciónDirecta (p, q)

m:= Dividir (p, q)
solucion:= Combinar (DivideVencerás (p, m),

DivideVencerás (m+1, q))

p

q

A.E.D.

Tema 2. Divide y vencerás.

8

4

2.1. Método general.

• Aplicación de divide y vencerás: encontrar la

forma de definir las funciones genéricas:
– Pequeño: Determina cuándo el problema es pequeño

para aplicar la resolución directa.

– SoluciónDirecta: Método alternativo de resolución para

tamaños pequeños.

– Dividir: Función para descomponer un problema

grande en subproblemas.

– Combinar: Método para obtener la solución al problema
original, a partir de las soluciones de los subproblemas.

• Para que pueda aplicarse la técnica divide y

vencerás debe existir una forma de definirlas
Aplicar un razonamiento inductivo...

A.E.D.

Tema 2. Divide y vencerás.

9

2.1. Método general.

• Requisitos para aplicar divide y vencerás:

– Necesitamos un método (más o menos directo) de

resolver los problemas de tamaño pequeño.

– El problema original debe poder dividirse fácilmente en

un conjunto de subproblemas, del mismo tipo que el
problema original pero con una resolución más sencilla
(menos costosa).

– Los subproblemas deben ser disjuntos: la solución de

un subproblema debe obtenerse independientemente de
los otros.

– Es necesario tener un método de combinar los

resultados de los subproblemas.

A.E.D.

Tema 2. Divide y vencerás.

10

5

• Ejemplo.
Problema
del viajante.

2.1. Método general.

11

45

0

4

55

10

2

5

25

50

44

22
55
30

5

1

2

0

33

• Método directo de resolver el problema:

Trivial con 3 nodos.

• Descomponer el problema en subproblemas más pequeños:

• Los subproblemas deben ser disjuntos:

¿Por dónde?

...parece que no

• Combinar los resultados de los subproblemas:

¡¡Imposible aplicar divide y vencerás!!

A.E.D.

Tema 2. Divide y vencerás.

11

2.1. Método general.

• Normalmente los subproblemas deben ser de

tamaños parecidos.

• Como mínimo necesitamos que hayan dos

subproblemas.

• Si sólo tenemos un subproblema entonces

hablamos de técnicas de reducción (o
simplificación).

• Ejemplo sencillo: Cálculo del factorial.

Fact(n):= n*Fact(n-1)

A.E.D.

Tema 2. Divide y vencerás.

12

6

2.2. Análisis de tiempos de ejecución.

• Para el esquema recursivo, con división en dos

subproblemas con la mitad de tamaño:

t(n) =

g(n)
2*t(n/2) + f(n)

Si n≤n0 (caso base)
En otro caso

• t(n): tiempo de ejecución del algoritmo DV.
• g(n): tiempo de calcular la solución para el caso base,

• f(n): tiempo de dividir el problema y combinar los

algoritmo directo.

resultados.

A.E.D.

Tema 2. Divide y vencerás.

13

2.2. Análisis de tiempos de ejecución.
• Resolver suponiendo que n es potencia de 2

n = 2k y n0 = n/2m

• Aplicando expansión de recurrencias:

(
nt

2)
=

m

(
ng

)2/
m
+

1

m

∑−

i

=

0

i

(2(
nf

i

))2/

• Si n0=1, entonces m=k, y tenemos:
2)(
)1(
nt

(2(
nf

)2/
k
+

))2/

(
ng

gn

⋅

=

=

k

i

i

k

−

1

∑

=

0

i

+

k

−

1

∑

=

0

i

i

2(2(

f

A.E.D.

Tema 2. Divide y vencerás.

14

ik
−

))

7

2.2. Análisis de tiempos de ejecución.
• Ejemplo 1. La resolución directa se puede hacer

en un tiempo constante y la división y combinación
de resultados también.
f(n) = d

g(n) = c;

t(n) ∈ Θ(n)

• Ejemplo 2. La solución directa se calcula en O(n2)

y la combinación en O(n).
g(n) = c·n2; f(n) = d·n

t(n) ∈ Θ(n log n)

A.E.D.

Tema 2. Divide y vencerás.

15

2.2. Análisis de tiempos de ejecución.

• En general, si el realiza a llamadas recursivas de

tamaño n/b, y la combinación requiere
f(n) = d·np ∈ O(np), entonces:

t(n) = a·t(n/b) + d·np

Suponiendo n = bk ⇒ k = logb n

t(bk) = a·t(bk-1) + d·bpk
Podemos deducir que:

O(nlogba)

Si a > bp
t(n) ∈ O(np·log n) Si a = bp
Si a < bp
A.E.D.

O(np)

Tema 2. Divide y vencerás.

Fórmula
maestra

16

8

2.2. Análisis de tiempos de ejecución.

• Ejemplo 3. Dividimos en 2 trozos de tamaño n/2,

con f(n) ∈ O(n):

a = b = 2
t(n) ∈ O(n·log n)

• Ejemplo 4. Realizamos 4 llamadas recursivas con

trozos de tamaño n/2, con f(n) ∈ O(n):

a = 4; b = 2
t(n) ∈ O(nlog24) = O(n2)

A.E.D.

Tema 2. Divide y vencerás.

17

2.3. Ejemplos de aplicación.

2.3.1. Multiplicación rápida de enteros largos.

• Queremos representar enteros de tamaño

arbitrariamente grande: mediante listas de cifras.
tipo EnteroLargo = Puntero[Nodo]

nodo = registro

valor : 0..9
sig : EnteroLargo

finregistro
u
v

1

3

2

2

3

1

4

5

• Implementar operaciones de suma, resta,

multiplicación, etc.

A.E.D.

Tema 2. Divide y vencerás.

18

9

2.3.1. Multiplicación rápida de enteros largos.

• Algoritmo clásico de multiplicación:

– Inicialmente r= 0
– Para cada cifra de v hacer

• Multiplicar todas las cifras de u por v
• Sumar a r con el desplazamiento correspondiente
u
v

2

3

4

5

1

3

2

1

• Suponiendo que u es de tamaño n, y v de tamaño m,

¿cuánto es el tiempo de ejecución?

• ¿Y si los dos son de tamaño n?

A.E.D.

Tema 2. Divide y vencerás.

19

2.3.1. Multiplicación rápida de enteros largos.

• Algoritmo de multiplicación con divide y vencerás:

w

x

u

v

1

3

y

2

2

3

1

z

4

5

– SoluciónDirecta: si el tamaño es 1, usar la multiplicación

escalar

– Dividir: decomponer los enteros de tamaño n en dos trozos de

tamaño n/2

– Resolver los subproblemas correspondientes
– Combinar: sumar los resultados de los subproblemas con los

desplazamientos correspondientes

A.E.D.

Tema 2. Divide y vencerás.

20

10

2.3.1. Multiplicación rápida de enteros largos.

u
v

w
y
n/2

x
z

n/2=S

u = w·10S + x
v = y·10S + z

• Cálculo de la multiplicación con divide y vencerás:

r = u·v = 102S·w·y + 10S·(w·z+x·y) + x·z

• El problema de tamaño n es descompuesto en 4 problemas

de tamaño n/2.

• La suma se puede realizar en un tiempo lineal O(n).
• ¿Cuánto es el tiempo de ejecución?
•

t(n) = 4·t(n/2) + d·n ∈ O(n2) No mejora el método clásico.

A.E.D.

Tema 2. Divide y vencerás.

21

2.3.1. Multiplicación rápida de enteros largos.

u
v

w
y

n/2

x
z
n/2=S

u = w·10S + x
v = y·10S + z

• ¿Y si en vez de 4 tuviéramos 3 subproblemas...?
• Multiplicación rápida de enteros largos (Karatsuba y

Ofman):

r = u·v = 102S·w·y + 10S·[(w-x)·(z-y) + w·y + x·z] + x·z

• Subproblemas:

– m1= w·y
– m2= (w-x)·(z-y)
– m3= x·z

A.E.D.

Tema 2. Divide y vencerás.

22

11

2.3.1. Multiplicación rápida de enteros largos.
operación Mult(u, v: EnteroLargo; n, base: entero) : EnteroLargo

si n == base entonces

devolver MultBasica(u,v)

sino

finsi

asignar(w, primeros(n/2, u))
asignar(x, ultimos(n/2, u))
asignar(y, primeros(n/2, v))
asignar(z, ultimos(n/2, v))
asignar(m1, Mult(w, y, n/2, base))
asignar(m2, Mult(x, z,n/2, base))
asignar(m3, Mult(restar(w,x), restar(z,y), n/2, base))
devolver sumar(sumar(Mult10(m1,n),

Mult10(sumar(sumar(m1,m2),m3),n/2)),m2)

• ¿Cuánto es el tiempo de ejecución?

A.E.D.

Tema 2. Divide y vencerás.

23

2.3.1. Multiplicación rápida de enteros largos.

• En este caso se requieren 3 multiplicaciones de tamaño n/2:

t(n) = 3·t(n/2) + d’·n ∈ O(nlog23) ≈ O(n1.59)

• El método es asintóticamente mejor que el método clásico.
• Sin embargo, las constantes y los térm