Indar

Estructuras de Datos
Tema 2. Diseño de Algoritmos

1. Recursividad


Implica plantear la resolución del problema con otra estrategia:
¿Cómo puedo resolver el problema?

Si me dieran la solución de un problema un poco menos complejo... ¿A partir de esa solución podría obtener la solución del problema original? =

Prob(n)
Reducción

Soluc(n)
Combinación

Prob(n-a) Prob(n-a)

=Soluc(n-a) Soluc(n-a)



En ese caso, sigue reducciendo el problema hasta que sea trivial

Estructuras de Datos – I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

Torres de Hanoi
a b c

  

Mover pirámide de n discos a otro poste Solo se mueve un disco cada vez, y tiene que ser el superior No se puede apilar un disco mayor sobre otro menor

La soluciónconsiste en una lista de movimientos, cada uno de ellos en el formato poste_origen → poste_destino (mueve el disco superior de poste_origen para que pase a ser el disco superior de poste_destino)

Estructuras de Datos – I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

Torres de Hanoi – Enfoque recursivo
a b c a→c

a

b

c

a

b

c

Estructuras de Datos –I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

Torres de Hanoi - Código
procedure Hanoi(n: integer; orig,dest,otro: char); begin if n > 1 then Hanoi(n-1,orig,otro,dest); writeln(output,orig,' -> ',dest); if n > 1 then Hanoi(n-1,otro,dest,orig) end;

T ( n) T ( n)

2 T (n 1) O(1) (2 )
n

E ( n) E ( n)

E ( n 1) O (1) ( n)

Estructuras de Datos – I.T.Informática Gestión,curso 2007/08 – Universidad de Valladolid

2. Divide y Vencerás
  

Dividir el problema en subproblemas de tamaño dividido por una constante Resolver los subproblemas mediante divide y vencerás Combinar las soluciones de los subproblemas para obtener la solución del problema original
= (nk) = Soluc(n)
Combinación

Prob(n)
División

a subproblemas

Prob(n/b) Prob(n-a)Soluc(n/b) Soluc(n-a)

T(n) = a·T(n/b) +

(nk)

Estructuras de Datos – I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

Divide y Vencerás - Esquema
P(n/8)

P(n/8)

P(n/4)
P(n/8) P(n/8)

P(n/4)

P(n/2)
P(n/8) P(n/8)

P(n/2)
P(n/4)
P(n/8) P(n/8)

P(n/4)

P(n)
P(n/8) P(n/8)

P(n)
P(n/4)
P(n/8) P(n/8)

P(n/4)

P(n/2)
P(n/8) P(n/8)

P(n/2)
P(n/4)P(n/8) P(n/8)

P(n/4)

Estructuras de Datos – I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

Producto de enteros grandes (PEG)
   

Enteros representados como un array de n bits n hace referencia al tamaño del mayor. El otro se puede suponer que también tiene n bits, rellenando con ceros al principio. El algoritmo tradicional realiza O(n2) productos de bitsindividuales (unidad básica de medida) El número de sumas de bits es del mismo orden que el de productos de bits. El número resultante tiene como máximo 2n bits
1234 x 9876 7404 86380 987200 11106000 12186984 16 productos

6x4 6x3 6x2 6x1 7x4 7x3 7x2 7x1 8x4 8x3 8x2 8x1 9x4 9x3 9x2 9x1

Estructuras de Datos – I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

PEG – Divide yvencerás
  

Queremos hallar el producto de enteros de n bits combinando el resultado de varios productos de enteros de n/2 bits. Supondremos n = 2m (par). Dividimos los enteros dos mitades de m bits, la mitad más significativa (H) y la menos significativa (L). Tomando los números como si fueran polinomios podemos ver como combinarles:
n n

A

AH
m

AL
m

B

BH
m

BL
m

A =2m·AH+AL A B = (2m·AH+AL)

B = 2m·BH+BL (2m·BH+BL) =

22m·(AH BH) + 2m·(AH BL) + 2m·(AL BH) + AL BL
Estructuras de Datos – I.T.Informática Gestión, curso 2007/08 – Universidad de Valladolid

PEG – Divide y vencerás directo












Necesitamos 4 productos de enteros de tamaño n/2 para poder reconstruir el resultado. Por ejemplo (en base 10), para calcular (1234x9876)...