PDF de programación - Algoritmos: Diseño de algoritmos por inducción

Algoritmos:

Diseño de algoritmos por inducción

Alberto Valderruten

LFCIA - Departamento de Computación

Facultad de Informática

Universidad de A Coruña, España

www.lfcia.org/alg

www.fi.udc.es

Contenido

Divide y Vencerás

Programación Dinámica

Sucesión de Fibonacci
Coeficientes binomiales
Devolver el cambio
Problema de la mochila
Principio de optimalidad

Algoritmos - Diseño de algoritmos por inducción - 2

Divide y Vencerás (1)

Descomponer el caso a resolver en subcasos del mismo problema,
resolverlos, independientemente entre sí (recursivamente), y
combinar las soluciones de los subcasos

para obtener la solución del caso original.

Ejemplos vistos:
suma de la subsecuencia máxima (algoritmo ssm3 ), mergesort, quicksort,
búsqueda binaria.

Esquema para la técnica:
Consideremos:

- un problema (ejemplo: ordenación)
- un algoritmo ad-hoc, sencillo, capaz de resolver ese problema y
eficiente para casos pequeños del problema (ejemplo: Inserción)

Esquema: función Divide y Vencerás

Ejercicio: contrastarla con los ejemplos vistos

Algoritmos - Diseño de algoritmos por inducción - 3

Función Divide y Vencerás

función Divide y Vencerás (x) : solución

si x es suficientemente pequeño entonces devolver ad-hoc(x)
sino

descomponer x en casos más pequeños x1, x2, ..., xa;
para i := 1 hasta a hacer

yi := Divide y Vencerás (xi);

combinar los yi para obtener una solución y de x;
devolver y

fin función

Algoritmos - Diseño de algoritmos por inducción - 4

Divide y Vencerás (2)

Características de a (no de subcasos):

- pequeño
- independiente de la entrada

Caso particular: a = 1 ⇒ algoritmo de reducción

→ el paso de recursivo a iterativo supondrá un ahorro

en tiempo (constante) y en espacio (pila de ejecución, Ω(n)).

Ejemplo: búsqueda binaria

Principales problemas:
- la descomposición y la combinación: ¿son posibles? ¿son eficientes?
- subcasos: en lo posible del mismo tamaño: n/b, donde b constante 6= a
- ¿umbral a partir del cual hay que utilizar el algoritmo ad-hoc?

Análisis:
Reglas ⇒ ¿relación de recurrencia?
→ Comprobar las condiciones de aplicación del teorema Divide y Vencerás.

Algoritmos - Diseño de algoritmos por inducción - 5

Programación Dinámica (1)

Divide y Vencerás → riesgo de llegar a tener

un gran número de subcasos idénticos ≡ ineficiencia!

Ejemplo: La sucesión de Fibonacci [1202] - Leonardo de Pisa [1170-1240]

La sucesión se define inductivamente del modo siguiente:

 f ib(0) = 0

f ib(1) = 1
f ib(n) = f ib(n − 1) + f ib(n − 2)
↔ sección áurea: s1 ≥ s2, s = s1 + s2
s1: segmento áureo de s ≡ s2
1 = s.s2
⇒ s2: segmento áureo de s1 ≡ s2
→ ley de armonía (arquitectura, arte)...

si n ≥ 2

2 = (s1 − s2)s1

Algoritmos - Diseño de algoritmos por inducción - 6

Fibonacci 1

Algoritmo Fibonacci 1:

función fib1(n)

si n < 2 entonces devolver n
sino devolver fib1(n-1) + fib1(n-2)

fin función

T (n) = Θ(Φn) , donde Φ = (1 +
(Cf. resolución de recurrencias)

√

5)/2

→ f ib1(5) produce 3 llamadas a f ib1(0), 4 llamadas a f ib1(1),...

en total, 15 llamadas.

Algoritmos - Diseño de algoritmos por inducción - 7

Programación Dinámica (2)

Programación Dinámica: resolver cada subcaso una sóla vez,
guardando las soluciones en una tabla de resultados,
que se va completando hasta alcanzar la solución buscada.

⇒ Técnica ascendente, opuesta a la descendente de Divide y Vencerás.

Ejemplo: Algoritmo Fibonacci 2

función fib2 (n)

i := 1; j := 0;
para k := 1 hasta n hacer

j := i+j; i := j-i;

devolver j

fin función

T (n) = Θ(n) y espacio en Θ(1).

Algoritmos - Diseño de algoritmos por inducción - 8

Fibonacci 3

Algoritmo Fibonacci 3: T (n) = O(logn)

función fib3 (n)

i := 1; j := 0; k := 0; h := 1;
mientras n > 0 hacer

si n es impar entonces

t := j*h;
j := i*h + j*k + t;
i := i*k + t

t := h^2;
h := 2*k*h + t;
k := k^2 + t;
n := n div 2

devolver j

fin función


f ib(n + 2)
f ib(n + 1)

f ib(n + 1)

⇒

f ib(n)

=



1
1

1

1
0

=

1



×

1
0

f ib(n + 1)
f ib(1)
n×

f ib(n)

f ib(0)



Algoritmos - Diseño de algoritmos por inducción - 9



n

k

=



Coeficientes binomiales (1)



n − 1

k − 1

1

+

0

n − 1



k

si k = 0 ∨ k = n

si 0 < k < n

sino

Ejemplo: Teorema de Newton

(1 + x)n = 1 +

x +



n

1



n

2

Problema: Dados 0 ≤ k ≤ n → ¿



n

n − 1

xn−1 + xn

x2 + · · · +



n

k

?

Divide y Vencerás:

función C(n, k): valor

si k = 0 ó k = n entonces devolver 1
sino devolver C(n-1, k-1) + C(n-1, k)

→ muchos cálculos se repiten ≡ suma de 1’s (como en fib1) → Ω

fin función



n

k

Algoritmos - Diseño de algoritmos por inducción - 10

Coeficientes binomiales (2)

Programación Dinámica:
→ Tabla de resultados intermedios: triángulo de Pascal

0
1
1
1

1

1
2

0
1
2
. . .
n − 1

n

2

. . .

k − 1

k

1

n − 1

k − 1



n − 1

n

k

k

T (n) = Θ(nk) y la complejidad espacial también.

¿Mejora? La complejidad espacial puede ser Θ(k)
↔ manejar una sóla línea del triángulo de Pascal.

Ejercicio: escribir el pseudocódigo.

Algoritmos - Diseño de algoritmos por inducción - 11

Devolver el cambio (1)

Problema: el algoritmo voraz es eficiente pero

no “funciona” siempre: M = {1, 4, 6}, n = 8 ⇒ ¿S = {4, 4}?

Dado M = {v1, v2, . . . , vm}, vi > 0: denominaciones de las monedas
Objetivo: pagar exactamente n unidades de valor, con |S| mínimo
Hipótesis: ∃ suministro ilimitado de monedas

Programación Dinámica ↔ tabla c[1..m, 0..n]

c[i, j] = no mínimo de monedas para pagar j unidades de valor (0 ≤ j ≤ n)

utilizando monedas de denominación v1..vi (1 ≤ i ≤ m).

|S| = c[m, n]

c[i − 1, j]

Construcción de la tabla:
c[i, 0] = 0
c[i, j] = min
Caso particular: i = 1 ∧ j < v1 ⇒ c[i, j] = +∞ ≡ no existe solución

: no utilizar una moneda más de vi ↔ i > 1
↔ j ≥ vi
: utilizar una moneda más de vi

1 + c[i, j − vi]

Algoritmos - Diseño de algoritmos por inducción - 12

Devolver el cambio (2)

función monedas (n): número de monedas

const v[1..m]=[1,4,6]
{se construye una tabla c[1..m, 0..n]}
para i := 1 hasta m hacer c [i,0] := 0;
para i := 1 hasta m hacer

{denominaciones de las monedas}

para j := 1 hasta n hacer

si i = 1 y j < v[i] entonces c[1,j] := infinito
sino si i = 1 entonces c[1,j] := 1 + c[1, j-v[1] ]
sino si j < v[i] entonces c[i,j] := c[i-1,j]
sino c[i,j] := min ( c[i-1, j], 1 + c[i, j-v[i] ] )

devolver c[m,n]

fin función

Algoritmos - Diseño de algoritmos por inducción - 13

Devolver el cambio (3)

Ejemplo: M = {1, 4, 6}, ¿c[3, 8]?

n
{1}
{1, 4}
{1, 4, 6}

0

0

0

0

1

1

1

1

2

2

2

2

3

3

3

3

4

4

1

1

5

5

2

2

6

6

3

1

7

7

4

2

8

8

2

2

Análisis: T (n) = Θ(mn)

Problema: ¿Conjunto de monedas?

⇒ Algoritmo voraz sobre c: camino c[m, n] → c[0, 0]
m “pasos” hacia arriba ≡ “no utilizar más vi”
+c[m, n] “saltos” hacia la izquierda ≡ “utilizar una vi más”

En total, Θ(m + c[m, n]) :

trabajo adicional a la construcción de la tabla

Algoritmos - Diseño de algoritmos por inducción - 14

El problema de la mochila II (1)

Versión II: los objetos no se pueden fraccionar ≡ xi ∈

¿Qué pasa con el algoritmo voraz?

Ejemplo: n = 3, W = 9:

0 ≡ dejar

1 ≡ tomar

Objetos

vi
wi

vi/wi

xi (voraz)
xi (óptimo)

2
7
5
1,4
0
1

1,25 Objetivo (Pn

1
9
6
1,5
1
9
0
12
⇒ ¡Ha dejado de funcionar!

3
5
4

0
1

i=1 xivi)

Algoritmos - Diseño de algoritmos por inducción - 15

El problema de la mochila II (2)

Programación Dinámica ↔ tabla v[1..n, 0..W ]

v[i, j] = valor de la carga máxima para la capacidad j (0 ≤ j ≤ W )

considerando los objetos 1..i (1 ≤ i ≤ n).

Construcción de la tabla:

v[i − 1, j]

v[i, j] = max

v[i − 1, j − wi] + vi

: no añadir el objeto i
: añadir el objeto i

Observación: a diferencia del caso de las monedas,
cada objeto sólo se puede incluir “una vez” en la carga de la mochila.

Ejercicio: ¿algoritmo?

Algoritmos - Diseño de algoritmos por inducción - 16

El problema de la mochila II (3)

Ejemplo:

{1}
{1, 2}
{1, 2, 3}

vi wi

9

7

5

6

5

4

0

0

0

0

1

0

0

0

2

0

0

0

3

0

0

0

4

0

0

5

5

0

7

7

6

9

9

9

7

9

9

9

8

9

9

9

9

9

9

12

Análisis: T (n) = Θ(nW )

Problema: ¿Composición de la carga?

⇒ Recorrido sobre v: camino v[n, W ] → v[0, 0]

máximo n “pasos” hacia arriba ≡ “no incluir el objeto i”
+ máximo W “saltos” hacia arriba y a la izquierda

≡ “incluir el objeto i”

En total, Θ(n + W ) : trabajo adicional a la construcción de la tabla

Algoritmos - Diseño de algoritmos por inducción - 17

Programación Dinámica (conclusión)

Principio de optimalidad:

La Programación Dinámica se utiliza
para resolver problemas de optimización
que satisfacen el principio de optimalidad:

“En una secuencia óptima de decisiones
toda subsecuencia ha de ser también óptima”

¡No siempre es aplicable!

Ejemplo: Hallar el camino simple más largo entre dos nodos.

Algoritmos - Diseño de algoritmos por inducción - 18

Algoritmos:

Diseño de algoritmos por inducción

Alberto Valderruten

LFCIA - Departamento de Computación

Facultad de Informática

Universidad de A Coruña, España

www.lfcia.org/alg

www.fi.udc.es