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)gráfica de visualizaciones

Publicado el 6 de Agosto del 2017
639 visualizaciones desde el 6 de Agosto del 2017
410,7 KB
93 paginas
Creado hace 4a (12/09/2016)
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
  • Links de descarga
http://lwp-l.com/pdf6132

Comentarios de: Tema 24: Técnicas de diseño ascendente de algoritmos - Informática (2016–17) (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad