PDF de programación - Tema 2. Diseño de Algoritmos - Estructuras de Datos

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

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

=

=

Soluc(n)

Combinación

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ón consiste 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;

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

)2()()1()1(2)(nnTOnTnT)()()1()1()(nnEOnEnE 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

Prob(n)

División

a subproblemas

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

=

(nk)

=

Soluc(n)

Combinación

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)

P(n/2)

P(n/2)

P(n/4)

P(n/4)

P(n/4)

P(n/4)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/8)

P(n/4)

P(n/4)

P(n/4)

P(n/4)

P(n/2)

P(n/2)

P(n)

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 bits individuales

(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

6x4 6x3 6x2 6x1

16 productos

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 y vencerá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

A = 2m·AH+AL

B

BH

m

BL

m

B = 2m·BH+BL

A B = (2m·AH+AL)

(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) necesitamos

saber (12x98), (12x76), (34x98) y (34x76) y reconstruimos el
resultado así:

 (1234x9876) = 104·(12x98) + 102·(12x76) + 102· (34x98) + (34x76)

 Nota: Por supuesto cada subproducto se calcula usando divide y

vencerás: 12x98 se calcula dividiendo y calculando (1x9), (1x8), (2x9)
y (2x8) y combinándolos mediante la fórmula

 Los productos por potencias de dos no cuestan nada, son equi-
valentes a un desplazamiento de dígitos y llevando adecuadamente
los índices no son necesarias operaciones extra.

 Sumar dos números de n bits tiene un coste O(n).

T(n) = 4·T(n/2) +

(n)

T(n)

(n2)

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

PEG – Algoritmo de Karutsaba

 Se parte del siguiente resultado..

(AH+AL)

(BH+BL) = AH BH + AH BL + AL BH + AL BL

 ..para modificar la fórmula de combinación:

A B = 22m·(AH BH) + 2m·(AH BL) + 2m·(AL BH) + AL BL =

22m·(AH BH) + 2m·((AH+AL) (BH+BL) - AH BH - AL BL) + AL BL

 Se obtiene una fórmula más compleja pero donde sólo se necesitan 3

productos, (AH BH) y (AL BL) se usan dos veces pero sólo es
necesario calcularlos una vez!

T(n) = 3·T(n/2) +

(n)

T(n)

(nlg3) =

(n1.58)

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

3. Fuerza Bruta

 Problemas difíciles, sin un método directo de resolución.

 Dada una posible solución, conocemos un algoritmo para saber si es

válida o no (criterio de verificación).

 Tipos de problemas:

 Una única solución válida.

 Varias soluciones válidas: Enumerar todas.

 Varias soluciones válidas: Obtener una cualquiera.

 Optimización: Obtener la mejor de entre las soluciones válidas. Cada

solución se evalúa con una función de coste.

 Estrategia Fuerza Bruta: Explorar el espacio de posibles resultados

aplicando a cada posible solución el criterio de verificación.

 El encontrar un modo de generar todas las posibles soluciones puede

no ser trivial.

 Es muy importante encontrar una representación de los resultados

que elimine la mayor cantidad posible de soluciones no válidas

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

Problema de las N-Reinas

 Problema histórico, propuesto en 1848 por Max Bezzel y examinado,

entre otros, por Gauss y Cantor.

 Dado un tablero de ajedrez de tamaño n x n, colocar n reinas sin que

existan amenazas entre ellas.

 Una reina amenaza a cualquier otra que se encuentre en su misma

fila, columna, diagonal izquierda o diagonal derecha.

 Dependiendo del tamaño del tablero pueden existir 0 ó varias

soluciones (para el tablero de 8x8 habitual existen 92).

 Aunque no sepamos cómo resolver el

problema, dada una posible solución es
sencillo comprobar si lo es realmente
(criterio de verificación)

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

N-Reinas – Representación 1

type

TTablero = array[1..N,1..N] of boolean;

Fila

Columna

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

tableros22n N-Reinas – Representación 2

type

TTablero = array[1..N] of record

Fil,Col: 1..N;

Indice
reina

end;

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

nn)(2 N-Reinas – Representación 3

type

TTablero = array[1..N] of 1..N;

Indice reina

Fila

Columna

N

2

3

4

5

6

7

8

2n^2

(n2)n

nn

16

512

65.536

33.554.432

16

729

65.536

9.765.625

68.719.476.736

2.176.782.336

562.949.953.421.312

678.223.072.849

4

27

256

3.125

46.656

823.543

18.446.744.073.709.600.000

281.474.976.710.656

16.777.216

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

nn Arbol de Soluciones

 En muchos problemas, los resultados se representan mediante un

array o una estructura similar.

 En estos casos la generación de todos los posibles resultados se

puede hacer recursivamente haciendo uso de resultados parciales:
 En cada llamada recursiva, una zona de la solución ya está asignada, y el

resto sin asignar (libre).

 En un bucle se van asignando todos los valores posibles a una

componente libre y se llama recursivamente para rellenar el resto.

 La representación gráfica de este método es el arbol de soluciones:

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

N-Reinas – Fuerza Bruta (todos)

function Amenazas(const T: TTablero; N: integer) : boolean;
{ Detecta si existen amenazas entre las reinas del tablero }

procedure NReinas(var T: TTablero; Fil,N: integer);
{ Genera y comprueba todos los posibles tableros

obtenidos colocando reinas en las filas Fil..N }

var Col : integer;
begin

if Fil > N then { tablero completo }
begin

if not Amenazas(T,N) then Escribir(T,N);

end else begin { tablero parcial }

for Col := 1 to N do
begin

T[Fil] := Col; { colocar reina }
NReinas(T,Fil+1,N); { generar tableros }

end

end

end;

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

N-Reinas – Fuerza Bruta (1 solución)

function NReinas(var T: TTablero; Fil,N: integer): boolean;
{ Busca un tablero solución entre aquellos obtenidos

colocando reinas en las filas Fil..N. Devuelve true
si lo encuentra. }

var Col : integer;
begin

if Fil > N then { tablero completo }
begin

Result := not Amenazas(T,N);

end else begin { tablero parcial }

Col := 1;
repeat

T[Fil] := Col; { colocar reina }
Result := NReinas(T,Fil+1,N); { buscar solución }
Col := Col+1

until Result or (Col > N);

end

end;

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

Sudoku

 En este caso la representación es evidente, una matriz de 9x9

números del 1 al 9. Se añadirá el valor 0 para distinguir entre una
celda asignada inicialmente y una celda libre.

 Aunque tenemos una matriz, es sencillo tratarla como un vector de 81

valores asignando a cada celda el índice (Fila-1)*9 + Columna.

type TSudoku = array[1..9,1..9] of 0..9;

Estructuras de Datos – I.T.Informática Gest