PDF de programación - Tema 24: Técnicas de diseño ascendente de algoritmos - Informática (2016–17)

Tema 24: Técnicas de diseño ascendente de

algoritmos

Informática (2016–17)

José A. Alonso Jiménez

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Tema 24: Técnicas de diseño ascendente de algoritmos

1. Programación dinámica

2. Fibonacci como ejemplo de programación dinámica

3. Producto de cadenas de matrices (PCM)

4. Árboles binarios de búsqueda optimales (ABBO)

5. Caminos mínimos entre todos los pares de nodos de un grafo(CM)

6. Problema del viajante (PV)

2 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

Introducción a la programación dinámica

Tema 24: Técnicas de diseño ascendente de algoritmos

1. Programación dinámica

Introducción a la programación dinámica
El patrón de la programación dinámica

2. Fibonacci como ejemplo de programación dinámica

3. Producto de cadenas de matrices (PCM)

4. Árboles binarios de búsqueda optimales (ABBO)

5. Caminos mínimos entre todos los pares de nodos de un grafo(CM)

6. Problema del viajante (PV)

3 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

Introducción a la programación dinámica

Divide y vencerás vs programación dinámica

Inconveniente de la técnica divide y vencerás: la posibilidad de

crear idénticos supbroblemas y repetición del trabajo.
Idea de la programación dinámica: resolver primero los
subproblemas menores, guardar los resultados y usar los
resultados de los subproblemas intermedios para resolver los
mayores.

4 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

Introducción a la programación dinámica

Cálculo de Fibonacci por divide y vencerás

Definición de Fibonacci por divide y vencerás.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Cálculo de (fib 4) por divide y vencerás

fib 4

/

\

+-----+
|

fib 3

/

\

+--+
|

fib 2

/

\

fib 2

/

\

fib 1 fib 1

fib 0

fib 1
Calcula 2 veces (fib 2) y 3 veces (fib 1) y (fib 0).

fib 0

5 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

Introducción a la programación dinámica

Cálculo de Fibonacci por programación dinámica

Cálculo de (fib 4) por programación dinámica

fib 0

fib 1

|
|
+-----+=== fib 2

|

|

|
+-----+=== fib 3

|

|
+-----+=== fib 4

6 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

El patrón de la programación dinámica

Tema 24: Técnicas de diseño ascendente de algoritmos

1. Programación dinámica

Introducción a la programación dinámica
El patrón de la programación dinámica

2. Fibonacci como ejemplo de programación dinámica

3. Producto de cadenas de matrices (PCM)

4. Árboles binarios de búsqueda optimales (ABBO)

5. Caminos mínimos entre todos los pares de nodos de un grafo(CM)

6. Problema del viajante (PV)

7 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

El patrón de la programación dinámica

El patrón de la programación dinámica

Cabecera del módulo:

module Dinamica (module Tabla, dinamica) where

Librerías auxiliares

-- Hay que elegir una implementación de TAD Tabla
-- import TablaConFunciones as Tabla
import TablaConListasDeAsociacion as Tabla
-- import TablaConMatrices as Tabla

import Data.Array

8 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Programación dinámica

El patrón de la programación dinámica

El patrón de la programación dinámica

El patrón de la programación dinámica

dinamica :: Ix i => (Tabla i v -> i -> v) -> (i,i)

dinamica calcula cotas = t

-> Tabla i v

where t = tabla [(i,calcula t i) | i <- range cotas]

(calcula t i) es el valor del índice i calculado a partir de los

anteriores que ya se encuentran en la tabla t.

cotas son las cotas de la matriz t en la que se almacenan los

valores calculados.

9 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Tema 24: Técnicas de diseño ascendente de algoritmos

1. Programación dinámica

2. Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

3. Producto de cadenas de matrices (PCM)

4. Árboles binarios de búsqueda optimales (ABBO)

5. Caminos mínimos entre todos los pares de nodos de un grafo(CM)

6. Problema del viajante (PV)

10 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante programación dinámica

Importación del patrón de programación dinámica

import Dinamica

(fib n) es el n-ésimo término de la sucesión de Fibonacci,

calculado mediante programación dinámica. Por ejemplo,
fib 8 21

fib :: Int -> Int
fib n = valor t n

where t = dinamica calculaFib (cotasFib n)

11 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante programación dinámica

(calculaFib t i) es el valor de i-ésimo término de la sucesión

de Fibonacci calculado mediante la tabla t que contiene los
anteriores. Por ejemplo,
0
calculaFib (tabla []) 0
calculaFib (tabla [(0,0),(1,1),(2,1),(3,2)] 4 3
Además,
ghci> dinamica calculaFib (0,6)
Tbl [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8)]

calculaFib :: Tabla Int Int -> Int -> Int
calculaFib t i

| i <= 1
| otherwise = valor t (i-1) + valor t (i-2)

= i

12 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante programación dinámica

(calculaFib t i) es el valor de i-ésimo término de la sucesión

de Fibonacci calculado mediante la tabla t que contiene los
anteriores. Por ejemplo,
0
calculaFib (tabla []) 0
calculaFib (tabla [(0,0),(1,1),(2,1),(3,2)] 4 3
Además,
ghci> dinamica calculaFib (0,6)
Tbl [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8)]

calculaFib :: Tabla Int Int -> Int -> Int
calculaFib t i

| i <= 1
| otherwise = valor t (i-1) + valor t (i-2)

= i

12 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante programación dinámica

(cotasFib n) son las cotas del vector que se necesita para

calcular el n-ésimo término de la sucesión de Fibonacci mediante
programación dinámica.

cotasFib :: Int -> (Int,Int)
cotasFib n = (0,n)

13 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante programación dinámica

(cotasFib n) son las cotas del vector que se necesita para

calcular el n-ésimo término de la sucesión de Fibonacci mediante
programación dinámica.

cotasFib :: Int -> (Int,Int)
cotasFib n = (0,n)

13 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante divide y vencerás
(fibR n) es el n–ésimo término de la sucesión de Fibonacci

calculado mediante divide y vencerás.

fibR :: Int -> Int
fibR 0 = 0
fibR 1 = 1
fibR n = fibR (n-1) + fibR (n-2)

Comparación:

ghci> fib 30
832040
(0.01 secs, 0 bytes)
ghci> fibR 30
832040
(6.46 secs, 222602404 bytes)

14 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante evaluación perezosa
fibs es la lista de los términos de la sucesión de Fibonacci. Por

ejemplo,
take 10 fibs [0,1,1,2,3,5,8,13,21,34]

fibs :: [Int]
fibs = 0:1:[x+y | (x,y) <- zip fibs (tail fibs)]

(fib’ n) es el n-ésimo término de la sucesión de Fibonacci,

calculado a partir de fibs. Por ejemplo,
fib' 8 21

fib' :: Int -> Int
fib' n = fibs!!n

15 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Fibonacci como ejemplo de programación dinámica

Definición de Fibonacci mediante programación dinámica

Definición de Fibonacci mediante evaluación perezosa

Comparaciones:
ghci> fib 30
832040
(0.02 secs, 524808 bytes)
ghci> fib' 30
832040
(0.01 secs, 542384 bytes)
ghci> fibR 30
832040
(6.46 secs, 222602404 bytes)

16 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Producto de cadenas de matrices (PCM)

Descripción del problema PCM

Tema 24: Técnicas de diseño ascendente de algoritmos

1. Programación dinámica

2. Fibonacci como ejemplo de programación dinámica

3. Producto de cadenas de matrices (PCM)

Descripción del problema PCM
Solución del PCM mediante programación dinámica
Solución del PCM mediante divide y vencerás

4. Árboles binarios de búsqueda optimales (ABBO)

5. Caminos mínimos entre todos los pares de nodos de un grafo(CM)

6. Problema del viajante (PV)

17 / 66

IM Tema 24: Técnicas de diseño ascendente de algoritmos

Producto de cadenas de matrices (PCM)

Descripción del problema PCM

Descripción del problema

Para multiplicar una matriz de orden m ∗ p y otra de orden p ∗ n

se necesitan mnp multiplicaciones de elementos.

El problema del producto de una cadena de matrices (en inglés,
“matrix chain multiplication”) consiste en dada una sucesión de
matrices encontrar la manera de multiplicarlas usando el menor
número de productos de elementos.

Ejemplo: Dada la sucesión de matrices

A(30x1), B(1x40), C(40x10), D(10x25)

las productos necesarios e