Ingeniero Técnico en Informática de Sistemas

Metodología: Algoritmia

Compartir 0 Me sirvió 0 No me sirvió

9 - 10 - 97

ALGORITMIA

JOAQUIN ABEGER

Análisis de Algoritmos ( eficiente , tiempo y memoria ).
Diseño de Algoritmos ( esquemas de diseño ).
Verificación de Algoritmos ( estudio lógico ).

BIBLIOGRAFIA

Diseño y Análisis de Algoritmos . Ed. Paraninfo . Carmen Torres.

1.- ANALISIS DE ALGORTIMOS

TEMA 1 : CONCEPTO DE ALGORITMO

Introducción

Valores / Datos : son distintos :

Tipo de Datos en Abstracto ( independientemente de la representación utilizada ) , esta formada por un conjunto de valores y las operaciones se pueden realizar con esos valores.

Tipo Datos " Estructura Algebraica ( N , + , . )

Valores , tienen un carácter abstracto independientemente de cómo se van a representar . No ocupan lugar ni tienen duración en el tiempo.

Nº 13 - 13 , 1101 , 26 / 2

Dato , elemento de información que representa a un valor de un determinado tipo . No son abstractos tienen entidad física ( ocupan espacio y tiene duración ) . El aspecto abstracto de un dato es el método de codificación . El dato representa físicamente un valor , cuesta tiempo operar con él.

Problemas - admiten especificación , la tarea de análisis de un problema consiste en la especificación del problema.

Precondición , es obtener los tipos de datos de entrada y las condiciones que deben cumplir sus valores.
Postcondición , tipos de datos de salida y la condición que cumplen sus valores.

Cada posibilidad de valor de entrada que cumple la precondición representa a un ejemplar o caso del problema ( caracteriza al problema ).

Los valores de salida que cumplen la postcondición representan una solución a ese caso del problema.

Definición de Algoritmo

Algoritmo - proviene de un matemático Persa 825.

Algoritmo de Euclides , calcula el máximo común divisor de dos enteros.

{ m y n Enteros positivos } Precondición

Forma clásica del algoritmo.

E1.- Dividir m por n y obtener el resto r.

E2.- Si r = 0 entonces n es el MCD ( m0 , n 0 ) y terminar.

E3.- m ! n ; n ! r ; ir a E1.

Definición Intuitiva - es un conjunto finito de reglas , que al aplicarse desencadena una secuencia de operaciones que permiten resolver el problema .

A este conjunto de reglas se le exige las siguientes características o condiciones :

Finitud - cualquiera que sean los valores de los datos de entrada , el número de operaciones que realiza el procesador debe ser un número finito.
Definibilidad - cada operación que debe realizarse debe estar bien definida para el procesador , y debe estar bien definido el orden en que se realizan la operaciones .
Generalidad - los valores de entrada representan a un caso del problema ( cumplen la precondición ) . Los valores de salida deben de representar siempre a la solución a ese caso del problema .
Efectividad - cada operación que ordena realizando el algoritmo debe ser eficaz y en un tiempo finito .

Uno de los criterios para saber si una operación es efectiva es si una persona puede realizarla en un tiempo finito .

* n ! nunca es efectivo , ya que nunca se utiliza con su valor exacto es una aproximación .

Observaciones

El procesador de un algoritmo es cualquiera capaz de procesar la información y capaz de entender el algoritmo .
No todos los problemas que admiten una especificación algorítmica tienen algoritmos que lo resuelvan , son problemas no computables.

Parada , algoritmo o programa que dado cualquier problema este se detiene al final para sus posibles datos de entrada .

Ej. : Algoritmo ; Dividir 17 entre 5 para hallar el cociente entero y el resto . No sabemos multiplicar.

-5 ! ! C " 1

-5 ! ! C " 2

-5 ! ! C " 3

2 < 5 cierto FIN

Representación mediante reglas Euclides ( si no se dice nada pasamos siempre a la siguiente regla ).

{ m y n enteros y m " 0 y n > 0 )

DE1 : C ! 0

DE2 : Si m< n entonces cociente = C y el resto = m Y terminar

DE3 : m ! m - n ; C ! C + 1 ; e ir a DE2

Métodos de Cálculo

Definición matemática del algoritmo ( formalizarlo ).

Cuaterna formada por elementos

( Q , I , , f )

Q - conjunto de estados de computación .

I - conjunto de estados iniciales ( I " Q ) .

- conjunto de estados finales ( " Q ) .

f - aplicación de Q en Q

f : Q Q

x f ( x )

Cumple la siguiente propiedad : " z " , f ( z ) = z

Una Secuencia de Cálculo es una sucesión de estados de x0 , x1 , x2 , ... / x0 " I ( x0 estado inicial ) y " k " 0 , f ( x k ) = x k+1 , es decir la secuencia de cálculo es :

x0 ! f ( x0 ) = x 1 ! f ( x1 ) = x2! ...

f f

estado de computación que le sigue

Se dice que una secuencia de cálculo termina cuando " un entero k tal que f ( xk ) = xk

" k , xk "

El valor más pequeño de k que cumple la condición , es el número de pasos que la secuencia de cálculo termina.

xk = f ( xk ) = x k+1 = f ( x k+1 ) = xk+2 = ...

A partir del estado k-ésimo todos los estados son el mismo.

16 - 10 - 97

Un método que termina en un número finito de pasos , cualquiera que sea el estado de entrada es un “ método de cálculo que termina “ .

Ej. : Método formalizado del algoritmo de Euclides

{ m > 0 y n > 0 }

E1 r ! m mod n

E2 si r = 0 entonces fin , n es el mcd.

E3 m ! n ; n !r ; e ir a E1

I = { ( m , n ) | m > 0 y n > 0 } # entrada #

Q = { ( m , n ) ; ( m , n , r , s ) ; ( n ) | s = 1 , 2 , 3 }

= { ( n ) } # salida #

f ( m , n ) = ( m , n , 0 , 1 ) # estado inicial #

f ( m , n , r , 2 ) = ( u ) si r = 0

( m , n , r , 3 ) si r " 0

f ( m , n , r , 3 ) = ( n , r , r , 1 )

f ( n ) = ( n )

Métodos Efectivos de Cálculo

Un método de cálculo definido formalmente como en el ejemplo anterior no tiene porque tener efectividad en cada una de sus operaciones.

Ej. : si x , y " R un método puede ser f ( x , y , ... = ( x / y , y , ...) , donde x / y no es una operación efectiva ( el cociente exacto ) .

La idea de efectividad se basa en la manipulación finita de un conjunto finito de símbolos.

El modelo formal lleva la sustitución de símbolos hasta sus últimas consecuencias para obtener así una idea matemática ( exacta ) de efectividad .

Los alfabetos utilizados son conjuntos finitos de símbolos ( A ) .

A* = conjunto de secuencias finitas de símbolos A que incluye la secuencia vacía.

N > 0

Conjunto : estados computación Q = { ( , j ) | " A* y " j " N }

Estado de entrada I = { ( E , ) | P ( E ) y E " A* }

siendo P la propiedad o condición que cumplen las

cadenas de entrada.

Estados de salida = { ( , N }ø " A* }

La definición de la función transformadora de estados ( f ) , requiere que se halla definido los siguientes parámetros :

j " A* , j " A* , aj " N , bj " N

que cumplen < aj " N y < bj " N

para " j < N.

( , j , , aj ) , si j aparece en de la forma = j

f ( , j ) con de la longitud mínima.

( , bj ) , si j no aparece en

f ( , N ) = ( , N )

Un método efectivo de cálculo que termina es muy similar a la idea intuitiva o informal de algoritmia .

Ej. : Obtener un método efectivo de cálculo que de el resultado de | A - B | siendo A y B enteros no negativos.

# alfabeto # A = { a , b } A B

# entrada # I = { ( E , ) | E = aa ... a bb ... b

S = aa ... a

| A - B |

| 3 - 5 | E = aaabbbbb S = aa ... a

| A - B |

N = 3 ! número de estados

Máquina Turing

Formalizar algoritmos , son ideales .

MT - es un autómata finito , una cinta se longitud infinita dividida en celdas , cada una contiene un símbolo de un alfabeto finito A.

El número de símbolos de la cinta distintos de uno especial , que llamaremos blanco , es finito.

La cabeza de la máquina esta siempre encima de una celda y se puede mover según el conjunto de movimientos M.

M = { ! , ! , stop } ! mover a la celda derecha .

! mover a la celda izquierda

La máquina pueden estar en uno de los estado de Q ( conjunto de estados ) , Q es finito ; Q = { q0 , q1 , ... , qn }.

En un ciclo la máquina lee el carácter de la celda y según su estado interno escribe un símbolo que sustituye al anterior , según el símbolo leído realiza un movimiento que en un caso especial es la señal de stop.

1.6.1. Descripción Formal

f : A x Q ! A x M la f lee un símbolo y según el estado interno de la máquina escribe

otro símbolo y se mueve.

f es la función de salida

g : A x Q ! Q según el símbolo leído y el estado interno produce otro estado.

( ei , Qj ) !qL

g es la función de transición

1.6.2. Funcionamiento

El funcionamiento particular de una MT queda determinado por :

Posición inicial de la cabeza en la fila.
Estado interno inicial.
Especificación de la máquina ( especificación de f y g ).

Se puede especificar poniendo todos los vectores posibles :

( ei , qj , ek , mh , qL ) para todos los valores de ei , qj

Se realiza una tabla de doble entrada.

Qj \ ei ... ei

...

qj ek mh qL

Dada una información en la cinta inicial pueden ocurrir dos cosas :

al cabo de un número finito de pasos la máquina se detiene ( stop ) . Se dice entonces que la máquina es aplicable a la cinta.

El caso contrario , nunca se produce la señal de stop . La máquina es inaplicable a la cinta.

Ej. : Se pretende sumar m y n ( m > 0 y n > 0 )

A = { 1 , * “ ” }

m n

111 ...1 * 11 ... 1 Cinta de E

Posición Inicial Máquina ; estado inicial q0

La suma aparece :

m + n

11 ........... 1

qj \ ei 1 * “ “

q0 “ “ ! q1 “ stop

q1 1 ! q1 * ! q2

q2 1 ! q2 1 ! q3

q3 1 ! q2 * ! q4

q4 1 ! q4 “ ” ! q0

Hipótesis de CHARCH ( 1936 )

Las siguientes ideas son equivalentes :

Idea intuitiva de algoritmo.
Método efectivo de cálculo que termina ( par aun especificación de entrada ).
Máquina de Turnig aplicable a una cinta inicial especificada.

Equivalencia , debe entenderse como todo cálculo que es posible realizar con una de las tres ideas , es realizable con las otras dos ( hipótesis plauxible , sin demostrar ).

TEMA 2 : ANALISIS DE ALGORITMOS

2.1. Introducción

Análisis de Algoritmos - consiste en la evaluación de la eficiencia del algoritmo . Los recursos que se evalúan son la memoria y el tiempo.

Eficiencia en memoria y en tiempo son conceptos inversos a la cantidad de memoria y tiempo que consume.

2.2. Evaluación de Memoria

La determinación de la cantidad de memoria que precisa un algoritmo suele ser sencilla en la mayoría de los casos , pero cuando el algoritmo utiliza memoria o variables dinámicas o consume gran cantidad de memoria estática se hace necesario el análisis de memoria . Para ello se utilizan los mismos métodos que en la evaluación del tiempo.

2.3. Evaluación de Tiempo

El tiempo que utiliza un algoritmo para resolver un determinado caso de un problema depende de tres factores :

1.- Tamaño del ejemplar

2.- Implantación del algoritmo ( ordenador + programación compilado ).

3.- Características del ejemplar sobre el que actúa.

2.4. Estrategias de Análisis

Empírica ( a posteriori ) - medir el tiempo con ejemplares bien escogidos.

Teórica ( a priori ) - a partir del número de veces que se realiza cada operación del algoritmo y de su coste unitario , se obtiene una función dependiente del tamaño . Se llaman funciones de complejidad respecto al algoritmo.

Híbrida - obtener una función de complejidad con coeficientes indeterminados ( parte a priori ) , después se mide el tiempo del programa para diversos tamaños . Por medios estadísticos se ajustan los coeficientes a los datos específicos.

2.5. Concepto de Tamaño

Formalmente - es el número de bits necesario para representar un ejemplar del problema de forma razonablemente compacta . En la práctica se sustituye por algún parámetro que sea más o menos proporcional al tamaño en bits.

en ordenación : número de elementos.
En problemas aritméticos : se usa la longitud de los operandos.
Etc.

Algunos problemas necesitan más de un parámetro como algoritmos de grafos ( en alguno de los cuales se hace necesario usar un número de vértices y número de arcos ).

2.6. Principio de Invarianza

Las funciones de complejidad (representa el tiempo que tarda un algoritmo) son el tipo :

T : N ! R* aplicación de N en R

n ! t ( n )

R* - números reales positivos y el cero R* " { }

N = { 0 , 1 , 2 , ... }

Cuando el tiempo de ejecución depende , además del tamaño de las características del ejemplar , no existe función de complejidad para el algoritmo . En ese caso se utiliza , según las necesidades alguna se las siguientes funciones de complejidad :

Tiempo del mejor caso : análisis del mejor caso.

Tiempo del peor caso : análisis del peor caso , es el más útil y no muy difícil.

Tiempo medio : se define :

Pi - probabilidad de que se de el caso i.

ti - tiempo de ejecución para ese caso.

¿ Valor de una función de complejidad teórica , obtenido en un procesador ideal cuando el tiempo depende de la implantación del algoritmo ?

t1 ( n ) " c t2 ( n ) , siendo t1 y t2 las funciones de complejidad de las dos implantaciones.

Principio de Invarianza :

( " c , d > 0 ) ( " n0 " N ) ( " n " n0 ) ( t1 ( n ) " c t2 ( n ) y t1 ( n ) " d t2 ( n ) )

Para todos los tamaños suficientemente grandes , la función t1 esta acotada por c t2 y t2 esta acotada por d y t1 .

Ej. : t1 ( n ) = 10 n + 3 n0 = 1 , c = 2 , d = 1

t2 ( n ) = 5 n + 4 " n " 1 , 10 n + 3 " 2 ( 5n + 4 )

" n " 1 , 10 n + 3 " 1 ( 5 n + 4 )

2.6.1. Acotación Sintótica

Concepto de Acotación Asintótica

Tenemos dos funciones del mismo tiempo

Sean f , g : N ! R*

F esta acotada asintóticamente por g ! (" c > 0) (" n0 " N) (" n " n0) (f (n) " c g (n) )

[ f " g ] ! símbolo

Ej. : t ( n ) = n exp 2 t' < t ya que " n " 11 = n0

t' ( n ) = 10 n + 5 t' ( n ) = 10 n + 5 " 1 ( n exp 2 ) = 1 t ( n )

t < t'

Propiedades :

Reflexiva f " f
Transitiva f " g y q " h ! f " h
Constante 1 " f

Por estas propiedades la relación " establece un orden parcial bien formado en las funciones N ! R*.

3 - 11 - 97

Teorema :

Si l = 0 , entonces f ( n ) es dominada asintóticamente por g .

f " g y g " f.

Si l = " , entonces g " f y g " f.

Si l " R y l " 0 , entonces f " g y g " f.

Ej. : f ( n ) = 2n² + n g ( n ) = 100 n + 500

Ej. : f ( n ) = ln g ( n ) = n

Consecuencias del teorema :

Si h < k ! ( n exp h ) " n ( exp k ) y ( n exp k ) " ( n exp h )

Si a > 1 y b > 1 ! logb m " loga y ! loga m " logb

Si k " 1 ! [ ( log n ) exp k ] " n y n " [ ( log n ) exp k ]

Si k " 1 y a > 1 ! ( n exp k ) " ( a exp n ) y ( a exp n ) " ( n exp k )

Si 1 < a < b ! ( a exp n ) " ( b exp n ) y ( a exp n ) " ( b exp n )

2.6.2. Notación O ( o grande )

Se define el siguiente conjunto de funciones :

O ( f ( n ) ) = { t : N ! R* | t " f }

Cuanto t ( n ) " O ( f ( n ) ) , se dice que t es el del O grande de f.

Observaciones :

La función que figura en el paréntesis es representativa del conjunto.

Se suele colocar la función mas sencilla de todo el conjunto que la acote superiormente.

Cuando un algoritmo tiene una función de complejidad t ( n ) " O ( f ( n ) ) , se dice que la complejidad del algoritmo es O grande de f . Conviene en ese caso que f ( n ) sea la función más pequeña que acota superiormente al tiempo que utiliza el algoritmo.

t ( n ) = 3 n² + 2 n + 5 " O ( n³ )

t2 ( n ) = n² + 1 " O ( n³ )

t2 ( n ) = 2n " O ( n³ )

Propiedades :

f ( n ) " O ( f ( n ) )

a ) O ( f ( n ) ) " O ( g ( n ) ) ! f ( n ) " g ( n )

b ) O ( f ( n ) ) = O ( g ( n ) ) ! f ( n ) " g ( n ) y g ( n ) " f ( n )

Si t ( n ) " O ( f ( n ) ) y t' ( n ) " O ( g ( n ) )

a ) c * t ( n ) " O ( f ( n ) )

b ) t ( n ) + t ` ( n ) " O ( f ( n ) + g ( n ) ) = O [ max ( f ( n ) , g ( n ) ) ]

si f ( n ) es comparable asintóticamente con g ( n )

c ) t ( n ) * t' ( n ) " O ( f ( n ) g (n ) )

Ej. : t ( n ) = 3n² + 6n " = ( 3n² + 6n ) = { 1º prioridad }

= O [ max ( 3n² , 6n ) ] = { 3º } = O ( 3n² ) ;

; 3n² " O ( n² ) = { 3º a }

Ej. : t ( n ) = 4 log n + 6n = O ( log n + n ) = O [ max ( log n , n ) ] = O ( n )

4 log n " O ( log n )

6n " O ( n )

Operaciones Conjuntísticas :

O ( f ( n ) ) + O ( g ( n ) ) = O ( f ( n ) + g ( n ) ) = 0 [ max ( f ( n ) , g ( n ) ) ]

si f y g son comparables

El conjunto suma esta formada por funciones se la forma t ( n ) + t' ( n ) que pertenece respectivamente al 1º y 2º sumando.

O ( f ( n ) ) * O ( g ( n ) ) = O ( f ( n ) g ( n ) )

Producto conjustístico esta formado por funciones del tipo t ( n ) * t` ( n ) que pertenecen respectivamente al primer factor y al segundo factor.

Ej. : t ( n ) = ( n² + n ) + log n " (1ª) O [ ( n² + n ) log n ] = O [ ( n² + n ) O ( log n )] =

max ( n² , n )

= O ( n² ) O ( log n ) = O ( n² log n )

Conjuntos O más usuales :

O (1) " O ( log n ) " O ( n ) " O ( n log n ) " O ( n exp k ) " O ( a exp n ) " O ( n! )

" " " " k > 1 " a > 1 "

Los algoritmos cuya función este en O ( log n ) su tiempo se dicen que tiene complejidad logarítmica . t ( n ) " O ( log n ).

t ( n ) = O ( n ) complejidad lineal | t ( n ) = O ( a exp n ) complejidad exponencial

t ( n ) = O ( n² ) complejidad cuadrática | t ( n ) = O ( n! ) complejidad factorial

Cuando la complejidad de un algoritmo es superior a n³ , se supone que el algoritmo no es práctico.

Cuando las complejidades son ( 2 exp n ) o n! , los algoritmos son impracticables.

Los problemas de las que se saben que los algoritmos existentes tienen complejidad superior a la polinómica se llaman problemas intratables.

2.6.3. Notación Omega

Dada f : N ! R* , se define

( f ( n ) ) = { t : N ! R* | t " f } ( todas las funciones acotadas inferiormente por f ).

Cuando de un problema se sabe que todos sus algoritmos tienen funciones de tiempo t ( n ) " ( f ( n ) ) , el problema es del tipo ( f ( n ) ).

Ej. : los tiempos de todas las ordenaciones por comparación son t ( n ) " ( n - log n ) , el problema es tipo ( n - log n ).

2.6.4. Notación Zeta

Dada f : N ! R*

( f ( n ) ) = { t : N ! R* | t " f y f " t }

Si t ( n ) " ( f ( n ) ) , su complejidad es del orden exacto de f ( n ).

Propiedades

f ( n ) " ( f (n) )

( f (n) ) = ( g (n) ) ! f " g y f " g.

Si t (n) " ( f (n) ) y t'(n) " ( g (n) )

a ) c t(n) " ( f (n) )

b ) t (n) + t'(n) " ( f (n) + g (n) ) = [ max ( f (n) , g (n) ) ]

si t y g son compatibles

c ) t (n) t'(n) " ( f (n) g (n) )

Relaciones Utiles

a ) ci " ( n )

i = 1

n k + 1

b ) ci " ( n )

i = 1 si k > 0

c ) log ( n! ) " ( n log n )

-1

d ) i " ( log n )

( suma armónica = (1 /1 ) + ( 1/2 ) + ( 1/3 ) + ... + ( 1/n ) )

2.7. Notación Asintótica con varios Parámetros

Si el tiempo de un algoritmo depende de dos parámetros de tiempo :

Sea f : N x N ! R*

( m , n ) ! f ( m , n )

O ( f ( m , n ) ) = { t : N x N ! R* | ( " c > 0 ) ( " m0 , n0 " N )

( " m " m0 ) ( " n " n0 )

t ( m , n ) " c f ( m , n ) }

Ej. : la multiplicación normal se números de longitudes m y n es un tiempo :

T ( m , n ) " ( m n )

Del mismo modo se definen :

( f ( m , n ) ) y ( f ( m , n ) )

f ( n , m ) = O ( g ( n , m ) ) si " c " R c > 0 n0 " N

| f ( n , m ) | " c | g ( n , m ) |

2.8. Notación Asintótica Condicional

Definición :

F ( n ) = O ( g (n ) / P ( n ) ) si " c > 0 c " R n0 " N

P ( n ) : N ! B | f ( n ) | " c | g ( n ) | " P ( n ) "n " 1

T ( n ) = O ( n² | n es par )

T ( n ) = O ( log n | n = ( 2 exp k ) )

TEMA 3 : ANALISIS ALGORITMOS ITERATIVOS

Propiedades de la Suma

Si T1 (n) = O ( f (n) ) y T2 (n) = O ( g (n) ) entonces

T1 (n) + T2 (n) = O ( f (n) + g (n) )

T1 (n) " C1 f (n) " T2 (n) " C2 g (n) " n01 > n " n02 > n

T1 (n) + T2 (n) " C1 f (n) + C2 g (n) " max ( C1 , C2 ) ( f(n) + g(n) ) " n > max (n01 , n02 )

T1 (n) + T2 (n) " C ( f (n) + g (n) ) " n > n0

C = max ( C1 , C2 ) n0 = max ( n01 , n02 )

T1 (n) + T2 (n) " C ( f (n) + g (n) ) " C ( max ( f (n) + g (n) )

T1 (n) + T2 (n) = O ( max ( f (n) , g (n) )

T = T1 + T2 ! El conjunto tiene la complejidad de la parte que tenga más complejidad.

Propiedades :

Si g (n) " f (n) " n > n' ( Para valores grandes de n ).

O ( f (n) + g (n) ) = O ( f (n) )

Si T1 (n) = O ( f (n) ) " T2 (n) = O ( g (n) )

T1 (n) + T2 (n) = O ( f (n) + g (n) )

Si T (n) = O ( C f (n) ) entonces

T (n) = O ( f (n) )

Ej. : ( n + 1 )² = O ( ? )

( n + 1 )² = n² + 2n + 1

n² = O ( n² ) 2n = O ( 2n ) = O ( n )

1 = O ( 1 )

n² + 2n + 1 = O ( n² ) + O ( n ) + O ( 1 )

= ( max ( n² , 2n , 1 ) = O ( n² )

Para averiguar cual es l complejidad de un algoritmo vamos a contar las instrucciones de las que consta.

Ej. : Burbuja ( a : vector [ 1 .. n ] de elementos )

Inicio

Desde i ! 1 hasta n-1 hacer

Desde j ! 1 hasta i + 1 paso-1 hacer

Si A [ j - 1 ] > A [ j ] entonces

temp ! A [ j - 1 ]

A [ j - 1 ] ! A [ j ]

A [ j ] ! temp

finsi

findesde

fin

Ej. : Selección ( T [ 1 .. n ] )

Desde i ! 1 hasta n-1 hacer

min j ! i 2b O ( 1 ) + O ( i ) = O ( 1 )

min x ! T [ i ]

desde j ! i + 1 hasta n hacer

si T [ j ] < min x entonces

min j ! j O ( 1 ) a = comparaciones b + (n - i) * a + a +

min x ! x b = asignaciones + 4b

T [ min j ] ! T [ i ] O ( 1 ) a + 4 * b O ( n - i )

T [ i ] ! min x - O ( 1 ) O(1) + O(1) + O(1) = 1

fin

Se halla la complejidad sin usar la propiedad de la suma.

n-1

b + ( n - 1 ) ( 3b + a ) + ( 2a + 4b ) n - i

[ n ( n-1 ) ] / 2

= b + ( 3b + a ) ( n - 1 ) + [ n ( n - 1 ) ] / 2 ( 2a + 4b )

n² ( a + 2b ) + n ( -a - 2b + 3b + a ) + ( b - 3b - a ) =

n² ( a + 2b ) + n b - 2b - a = T (n)

Utilizando la propiedad de la suma :

O ( 1 ) + O ( 1 ) + O ( 1 ) = O ( max ( O ( 1 ) ) = O ( 1 )

Desde interno

O ( 1 ) + ( n - i ) ( O ( 1 ) + O ( 1 ) ) = O ( 1 ) + ( n - i ) ( O ( 1 ) ) =

O ( 1 ) + ( n - i ) = O ( n - i )

Desde externo

n-1 comp asig

O ( 1 ) + O ( 1 ) + O ( 1 ) + O ( n - i )

i=1

n-1 n -1

= O ( 1 ) + O ( n - i ) = O ( 1 ) + O ( n - i ) =

i=1 i = 1

= O ( 1 ) + O [ ( n ( n - 1 ) ) / 2 ] = O ( 1 ) + O ( n² ) = O ( n² )

CUADRATICA

Ej. :

Binaria ( A [ 1 .. n ] , elem )

Inicio ! 1

Fin ! n

Medio = n /2

Mientras fin > inicio hacer

Si e = = A [ medio ] devolver ( medio ) O ( 1 )

Sino si e < A [ medio ] entonces O ( 1 )

Fin ! medio - 1 O ( 1 )

Sino inicio ! medio + 1 O ( 1 )

finsi

medio ! ( fin - inicio ) / 2 O ( 1 )

fin

El bucle mientras se ejecuta como máximo log2 n.

T (n) = O ( 1 ) + log n O ( 1 )

O ( 1 ) + O ( log n ) = O ( log n )

T (n) = O ( log2 n ) = O ( log n )

COMPLEJIDAD LOGARITMICA

Esta búsqueda es mejor que la lineal , pero debe estar ordenado el array.

Si hubiera que ordenarlo , la complejidad sería de O ( n² ) , luego sería mejor la lineal.

Pistas para el Análisis

La complejidad de toda asignación , lectura o escritura de variables simples ( no arrays ) es constante es decir O ( 1 ).

La complejidad de una secuencia de instrucciones es la complejidad de la más compleja ( propia suma ).

La complejidad de la rama más compleja

La complejidad de un bucle , es igual a la suma de las complejidades de todos las ejecuciones del cuerpo más la complejidad de la evaluación de la condición de terminación.

Cuando en un programa hay llamadas a funciones , comenzar por evaluar la complejidad de las funciones que no llaman a otras funciones , y proceder de la misma manera hasta obtener la complejidad total.

Si tenemos una instrucción GOTO ; ESTA PROHIBIDO USAR LA SENTENCIA GOTO.

TEMA 4 : ANALISIS ALGORITMOS RECURSIVOS

4.1. Introducción

Ordenación por Mezcla :

MezclaOrd ( L [ 1 .. n ] ) : array [ 1.. n ]

Inicio

Si n = = 1 entonces devolver ( L )

Sino

DividirEnDos ( L , L1 , L2 ) O (n)

Devolver ( mezcla ( MezclaOrd ( L1 [ 1 .. n/2 ] ) , MezclaOrd ( L2 [ 1 .. n/2 ] )

O (n) T [ n/2 ] T [ n/2 ]

Finsi

Fin

T (n) = O ( 1 ) n = = 1 T (n) = C1 n = = 1

2 T ( n/2 ) + O (n) 2 T ( n/2 ) + C2 n

4.2. Ecuaciones de Recurrencia

4.1. Suposición de una solución ( NO )

Escogemos una solución que salga deducida de cómo funciona el algoritmo ( no lo vamos a utilizar ).

4.2. Expansión de Recurrencias

Partimos de la parte más compleja :

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

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

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

... sustituyo en

T [ n / ( 2 exp i )] = = 2 T [ n / ( 2 exp i + 1 ) ] + n / ( 2 exp i ) t ( n / 2 )

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

Sustituyo en t (n)

= 8 T ( n / 8 ) + 4 ( n / 4 ) + 2n = 8 T ( n / 8 ) + 3n = 16 T ( n / 16 ) + 8 ( n / 8 ) + 3n =

= 16 T ( n / 16 ) + 4n

log n = i

T (n) = n T1 + n log n = n + n log n = O ( n log n )

3-11-97

Divide y Vencerás DIVISION ... RECOMBINACION , dan lugar a ecuaciones :

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

a , b - valores positivos.

d (n ) - coste o tiempo en hacer la división y recombinar.

En la ecuación cambio n / b , hallar T , sustituyo en la ecuación de abajo :

T (n / b) = a T (n / b²) + d (n / 2) = a² T (n / b²) + a d (n / b) + d (n) =

T (n / b²) = a³ T (n / b³) d (n / b²) = a³ T (n / b³) + a² d (n / b²) + a d (n) + d (n)

...

Tenemos que llegar en algún momento a n = 1

Pararemos

Solución homogénea

La recurrencia se utiliza para resolver ecuaciones diferenciales.

Si solo hubiera solución homogénea la complejidad sería :

Los mejores valores de a y b deben hacer mínimo el exponente

logb a sea menor , b debe ser mayor y a menor , si aumentamos la base el

exponente puede ser más pequeño.

a - número de subdivisiones

b - tamaño relativo de la subdivisión

Para conseguir la eficiencia se realiza esto , hay que intentar que la a sea pequeña y que b sea grande , nos conformaremos que a = b.

Todo esto suponiendo que la solución sea mayor ( mucho más ) o no solo exista.

Regla :

Si d (n) es >" (n exp logb a) , n log n entonces la complejidad T (n) = O ( d (n) n log n ).

T (n) = O ( d (n) ) Casi todo el coste o complejidad esta en dividir y recombinar . Este

caso no es bueno , el mayor coste debe estar en solucionar el problema

4.2. Resolución por el Método de la Ecuación Característica

4.2.1. Recurrencias Homogéneas

Se aplica para problemas en que T (n) = C1 T ( n-1 ) + C2 T ( n-2 ) + ... + Cn T ( n-k )

Ej. : Fib (n)

Inicio

Si n = = 1 o n = = 2 entonces devolver 1

Sino devolver Fib ( n-1 ) + Fib ( n-2 )

Fin Dos llamadas recursivas

T (n) = T ( n-1 ) + T ( n-2 )

Manipular simbólicamente la ecuación :

Los términos con T ( n-k ) los paso a la izquierda.

T (n) - C1 T ( n-1 ) - C2 T ( n-2 ) - ... - Cn T ( n-k ) = 0

Cambio de signo , cambio el nombre por haber tanto negativo

a0 T(n) + a1 C1 T ( n-1 ) + a2 C2 T ( n-2 ) + ... +ak Cn T ( n-k ) = 0

ai = -Ci ; i = 1 .. k ; a0 = 1

Cambio T (n) = tn

a0 tn + a1 tn-1 + a1 tn-2 + ... + ak tn-k = 0

Cambio

Sacamos factor común

tiempo = 0 , T = 0 ( solución cuando no ejecuto el algoritmo ).

Ecuación Característica de la Recurrencia

Puede ocurrir :

Todas la raíces son diferentes , Raíces Simples

x = ri solución para todos las i = 1 .. k . Deshacer las sustituciones

Ej. : Tenemos la ecuación de recurrencia de un algoritmo :

T (n) = 3 T ( n-1 ) + 4 T ( n-2 ) T (0) = 0 T (1) = 1 Condiciones iniciales

T (n) - 3 T ( n-1 ) - 4 T ( n-2 ) = 0

tn - 3 tn-1 - 4 tn-2 = 0 T (n) = tn

x² - 3x - 4 = 0 Saco factor común

r1 = 4 r2 = -1

T (n) = tn =

Calculamos C1 y C2 .

T (0) = C1 4º + C2 ( -1 )º = C1 + C2 = 0

T (0) = C1 4¹ + C2 ( -1 )¹ = 4 C1 - C2 = 1

5 C1 = 0 C1 = 1/5

1/5 + C2 = 0 C2 = - ( 1/5 )

Ej. : Resolver el de fibonacci T (0) = 0 T (1) = 1

T (n) = T ( n-1 ) + T ( n-2 )

Primero la ecuación característica

T (n) - T ( n-1 ) - T ( n-2 ) = 0

tn - tn-1 - tn-2 = 0

x² - x - 1 = 0

C1 = 1 / " 5 ; C2 = -1 / " 5

Existe alguna raíz diferente , Raíces Múltiples

Ej. : T (n) = 5 T ( n-1 ) - 8 T ( n-2 ) + 4 T ( n-3 )

Primero ecuación característica x = nº términos + 1

x³ - 5x² + 8x - 4 = 0

( x-1 ) ( x-2 )² = 0

4.2.2. Ecuaciones de Recurrencias no Homogéneas

T (n) = C1 T ( n-1 ) + C2 T ( n-2 ) + ... + Ck T ( n-k ) + b p(n)

Dividir y reorganizar

Ej. : T (n) = 2 T (n-1) +

T (n) - 2 T (n) =

tn - 2 tn-1 =

3 tn - 6 tn-1 = * 3 multiplico por tres porque quiero eliminar el término

t n+1 - 2 tn = en la original n ! n + 1 independiente , ahora resto 2-1.

t n+1 + 5 tn + 6 tn-1 = 0 Ecuación homogénea equivalente

x² - 5x + 6 = 0

r1 = 2

r2 = 3

T (n) = 2 T ( n-1 ) ! ecuación homogénea de la del enunciado.

tn - 2 tn-1 = 0

( x - 2 ) = 0

Ej. :

tn - 2 tn-1 = ( n+5 )

9 tn - 18 tn-1 = ( n+5 ) * 9

tn+2 - 2 tn+1 = ( n + 7 )3 n ! n + 2 Sumo las tres

- 6 tn+1 +12 tn = - 6 ( n + 6 ) n ! n+1 + - 6

tn+2 - 8 tn+1 + 12 tn - 18 tn-1 = 0

x³ - 8x² + 21 x - 18 = 0 ( n+5 ) 3 ! ( x - 3 )² = 0

( x-2 ) ( x-3 )² = 0 T (n) = 2 T ( n-1 ) ! ( x-2 ) = 0

La ecuación característica

Ej. : T (n) = 2 T ( n-1 ) + n No homogénea , termino independiente = 0 , nos falta b

T (n) = 2 T ( n-1 ) + n 1

tn - 2 tn-1 + = n b = 1 p (n) = n d = 1

Ecuación característica ( x-2 ) ( x-1 )²

T (n) = C1 + C2 + C3 n = C1 + C2 + C3 n = O ( )

Ej. : Torres de Hannoi

Procedimiento MoverTorres ( n , a , b , c )

Si n > 0 entonces

MoverTorres ( n-1 , a , b , c ) ; escribir es constante = 1

Escribir ( ` Paso un disco de ` , a , `a' , c ) ;

MoverTorres ( n-1 , b , a , c ) ;

Fin

T (n) = 2 T ( n-1 ) + 1

tn - 2 tn-1 = 1 (1 ) p (n) = 1 b = 1 d = 0

( x-2 ) ( x-1 ) = 0

T (n) = C1 2 + C2 1 = C1 2 + C2 = O ( 2 ) Ineficiente algoritmo

10-11-97

T (n) = 2 T ( n-1 ) + n

tn - 2 tn-1 = c (1 ) b p (n)

( x-2 ) ( x-1 )² = 0

T (n) = C1 2 + C2 1 + C3 n 1 = C1 2 + C2 + C3 n = O (2 )

Si tenemos ahora

a1 tn + a2 tn-1 + a3 tn-2 + ... + an tn-n = b1 p1 (n) + b2 p2(n) + ... + bm pm (n)

Ec. característica ( a1 x + a2 x + ... + ak ) ( x-b1 ) ( x-b2 ) ... ( x - bm ) = 0

Parte homogénea di = grado polinomio Pi

Ej. : T (n) = 2 T ( n-1 ) + n + 2 sustituyo T ( 1 , 2 y 3 )

tn - 2 tn-1 = n + 2 b ( n ) d1 = 1

polinomio = 1 d2 = 0

1 n +2 1 exp = 1

Ec. Característica ( x-2 ) ( x-1 )² ( x-2 ) = 0

T (n) = C1 2 + C2 n 2 + C3 1 + C4 n 1 = C1 2 + C2 n 2 + C3 + C4 n

Para los coeficientes sustituyo en la ecuación inicial

T (0) = 0 ; T (1) = 3 ; T (2) = 12 ; T (3) = 35 ( 4 incógnitas , 4 valores de t ).

T (0) = C1 + + C3 = 0 C1 = 2

T (1) = 2 C1 + 2 C2 + C3 + C4 = 3 C2 = 1

T (2) = 4 C1 + 8 C2 + C3 + 2 C4 = 12 C3 = -2

T (3) = 8 C1 + 24 C2 + C3 + 3 C4 = 35 C4 = -1

T (n) = 2 + n 2 - 2 - n = O ( n 2 )

4.2.3. Cambio de Variable

Transformar las ecuaciones divide y vence al tipo anterior

T (n) = T ( n/2 ) Se realiza mediante un cambio de variable.

Ej. : T (n) = 4 T( n/2 ) + n n = 2

T ( 2 ) = 4 T ( 2 ) + 2

tk = T ( 2 )

tk = 4 tk-1 + 2

tk - 4 tk-1 = 2 1

Ecuación característica ( k-4 ) ( k-2 ) = 0

T (k) = C1 4 + C2 2 4 = ( 2² ) = ( 2 )² = n²

T (n) = C1 n² + C2 n = O ( n² | n = 2 ) Notación asintótica condicional , solo cuando

n sea potencia de 2.

La complejidad de un algoritmo siempre crece ( no tiene derivada negativa , pendiente positiva ) , por eso aunque solo sepamos para 2 será más o menos una parábola , es decir n².

•

Ej. : T (n) = 4 T (n/2 ) + n² n = 2 n² = ( 2 ) ² = ( 2² ) = 4

t ( 2 ) = 4 2 +4 log2 n = k

tk = 4 tk-1 + 4

tk - 4 tk-1 = 4 1

( x-4 ) ( x-4 ) = 0

T (k) = C1 4 + C2 k 4

T (n) = C1 n² + C2 n² log2 n = O ( n² log2 n | n = 2 )

Ej : T (n) = 2 ( n/2 ) + n log n n = 2 n² = ( 2 )² = ( 2 ² )

tk = 2 tk-1 + 2 k log n = k

tk - 2 tk-1 = 2 k

( x-2 ) ( x-2 )² = 0

t (k) = C1 2 + C2 k 2 + C3 k² 2

T (n) = C1 n + C2 log n + C3 k log² n n = 0 ( n log² n | n = 2 )

Ej. : T (n) = 3 T (n/2) + 5 2 n = 2

tk = 3 tk-1 + 5 2

tk - 3 tk-1 = 5 2 b = 2 pk = 5 d =0

( x-3 ) ( x-2 ) = 0

T (k) = C1 3 + C2 2 3 a = b

T (n) = C1 n + C2 n = O ( n | n = 2 )

log a = log b ; log b log a = log b loga ; 3 = n

DISEÑO DE ALGORITMOS

TEMA 5 : FUERZA BRUTA

Antitécnica , no hacer.

Diseñamos el algoritmo sin pensar , sin aplicar ninguna técnica.

Ej. : Cálculo del determinante de una matriz.

a11 a12 a13 ... a1n

a21 a22 a23 ... a1n

... ... ... ...

an1 an2 an3 ... ann

A nxn An

Det (A) = ( -1 ) aij Det ( A1j )

Si A nxn n det de n-1 por n-1

Determinante ( A : array [ 1..n , 1..n ] , n : entero ) : entero

Si n = 2 Entonces

devolver A [ 1,1 ] * A [ 2,2 ] - A [1,2 ] * A [ 2,1 ]

sino

s = -1

Desde j!1 hasta n hacer /* Calcula la suma una vez positivo y otra negativa */

m ! 1

Desde k ! 2 hasta n hacer / * filas * /

p ! 1

Desde l ! i hasta n hacer / * columnas * /

Si l < > j entonces /* menos la columna j */

B [ m , p ] ! A [ k , l ] ; p++ construimos la matriz B

Fin_si p - filas B n-1

Fin_desde m - columnas n-1

m++

Fin_desde

Suma = S * A [ 1 , j ] * Det ( B , n-1 ) ! lio , además del problema de

S ! -S ; memoria , usamos muchas submatrices

Fin_desde

Devolver suma

Fin

Análisis

n = 2 1 comprobación , 2 multiplicaciones , 1 asignación , 1 resta - constante

n > 2 , bucles :

Más interno comparación y dos operaciones , n iteraciones.
Central , n * ( n-1 ). multiplicación
Más externo n T (n-1) + (n-1) n n + C2 n

n llamadas recursivas al problema

T (n) = n T ( n-1 ) + n³ - n² + C2 n

Suponemos Det ( A , 5 )

5 n

Determinante B , cinco llamadas a una matriz de 4 X X

4 n-1

Determinante ( B , 3 ) X X n!

3 ...

Det ( B , 2 ) X X

cte. cte.

T (n) = n T (n-1 ) + n³ - n² + C2 n

T (n) " n T ( n-1 ) + n³ Por expansión de recurrencias

T (n-1) = n-1 T (n-2) + ( n-1 )³

T (n-2) = n-2 T (n-3) + ( n-2 )³

T (n) " n T (n-1) + n³ = n (n-1) T (n-2) + n (n-1) + n³ =

= n (n-1) (n-2) T (n-3) + n (n-1) (n-2)³ + n ( n-1 ) n³ =

= n (n-1) ... ( n - k ) T ( n - k ) + " n n!

+ n ( k-1 ) ... ( n-k+1 )³ +

...

n = 20 ! tiempo = 20 millones de años . INEFICIENTE

Ej. : Serie de Fibonacci ( suma los anteriores )

1 1 2 3 5 8 13 21 34 ...

Fibonacci (n) : entero

Si n = = 1 o n = = 2 Entonces

Devolver 1

Sino Fib (n)

Devolver Fibonacci ( n-1 ) + Fibonacci ( n-2 ) Fib (n-1) Fib (n-2)

Finsi

T (n) = 2 ( T n-1 ) O ( [ ( 1 + "5 ) / 2 ] exp n ) Fib(n-2) Fib(n-3) Fib(n-3) Fib(n-4)

Una forma más sencilla :

Fib (n) : Entero

Si n " 2 Entonces

a-b ! 1

cont ! 2

repetir

t ! a + b

a ! b

b ! t

hasta cont = = n

17-11-97

TEMA 6 : DIVIDE Y VENCE

Torres de Hanoi

No puede haber un disco de mayor tamaño sobre otro de menor tamaño.

Pasar los discos de la barra A a la Barra B ( para ello se usa la barra C como auxiliar ).

No se pueden mover dos discos a la vez

Torres de Hanoi

Mover Torre ( n , A , B , C : entero )

Inicio

Si n > 0 Entonces

Mover Torre ( n-1 , A , C , B ) ;

Escribir ( “ Mover un disco de “ , A “a” , B ) ;

Mover Torre ( n-1 , B

Fin_si

Fin

Multiplicación de Números Grandes

X e Y.

X n / 2 n / 2 Operaciones : número dígitos X * número de dígitos de Y

A B T (n) = n²

Y n / 2 n / 2

C D

X = A 2 + B

Y = C 2 + D X Y = A C 2 + ( AD + CB ) 2 + BD

T (n) = T ( n/2 ) + c n = O ( n / 2 )

X Y = A * C 2 + [ ( A - B ) ( D - C ) + AC + BD ] *2 + BD

Hemos descompuesto el problema en tres subproblemas de tamaño medio más la suma.

T (n) = 3 T ( n / 2 ) + c n = O ( n ) = O ( n )

Mult ( x , y , n : enteros ) : enteros

Var

S , m1 , m2 , m3 , A , B , C , D : enteros

Inicio

S ! signo ( x ) * signo ( y ) /* quitar el signo */

x ! abs ( x ) /* quitar el signo de x e y */

y ! abs ( y )

Si n = = 1 Entonces /* Cantidad de dígitos en número es 1 */

Si x = = 1 && y = = 1 Entonces

Devolver (S)

Sino

Devolver (0)

Sino

A = x >> n / 2

B = x % exp ( 2 , n / 2 ) /* % ! módulo */

C = y >> n / 2

D = y % exp ( 2 , n / 2 )

m1 = Mult ( A , C , n / 2 ) /* T ( n / 2 ) */

m2 = Mult ( A-B , D-C , n / 2 ) /* T ( n / 2 ) */

m3 = Mult ( B , D , n / 2 ) /* T ( n / 2 ) */

Devolver ( S * ( m1 << n + m1 + m2 + m3 << n / 2 + m3 ) )

Fin_si

Fin

Elaboración Calendario Deportivo

n equipos ( EQ ) , tienen que jugar todos contra todos en el menor número de días posibles

Días

EQ 1 2 3 4 5 6 7

La casilla 5,5 indica que juega con el equipo 5 el día 5 , en esa columna ya no aparecerá más el 5.

Usamos n-1 , un equipo juega un partido diario.

Se podría dividir en cuatro partes

Días

EQ 1 2 3 4 5 6 7

1 2 3 4 5 8 7 6 1 2 3 1

2 1 4 3 6 5 8 7 1 2 3 4 1 2

3 4 1 2 7 6 5 8 2 1 4 3 2 1

4 3 2 1 8 7 6 5 3 4 1 2 Sencillo , igual

5 6 7 8 1 2 3 4 4 3 2 1 bloque inferior

6 5 8 7 2 3 4 1

7 8 5 6 3 4 1 2 1 2 3 1

8 7 6 5 4 1 2 3 5 6 7 8 5 6

Permutaciones 6 5 8 7 6 5

sin repetición 7 8 5 6

8 7 6 5

Estas ya da igual , una vez

rellenado uno relleno el otro

Un número impar es más complicado.

Esquema General

DV ( x )

Si x es pequeño o simple entonces /* ver si es simple , si lo es solución directa */

devolver ( solución ( x ) )

sino

descomponer ( x , x1 , x2 , ... , xn ) x en n partes /* dividir de alguna forma */

desde i ! 1 hasta n hacer

yi ! DV ( xi ) /* reaplicamos el esquema para buscar una solución parcial

Fin desde

Recombinar ( y1 , y2 , y3 , ... , yn )

Devolver ( y )

Fin si

La complejidad es el número de divisiones de n y el tamaño de cada parte , la combinación y recombinación suele ser lineal.

Problemas

Que es pequeño - cuando descomponemos o dividimos ( cuando es simple ).
Merece la pena hacer la recursión , umbral de no seguir haciendo recursión.

A veces es mejor dividir una sola vez.

Calculo del Umbral

Por ejemplo en lugar de multiplicar dos números de n dígitos sabemos hacerlo con tres de n / 2.

n/2

n n/2

n/2

Por fuerza Bruta la complejidad es n² , TB (n) = n²

Que ahorro haciendo una división , tres multiplicaciones y una recombinación.

lineal ( descomposición y recombinación )

TA (n) = 3 TB ( n/2 ) + cn = 3 ( n/2 )² = 3/4 n² + cn es un 25% de n²

Algoritmo ( una sola división )

Hemos ganado un 25% y algo lineal = 20%

Si hacemos recursividad en lugar de pararme la primera vez.

TR - recursivo

TR (n) = 3 TR ( n/2 ) + cn = O ( n ) ; Ecuaciones recursivas n = 2 lo realizamos por Expansión de recurrencias o Cambio de variable.

Para n muy grandes

Si n = = ? entonces solucionar

24-11-97

Búsqueda Binaria

Búsqueda Binaria ( T : array [ 1..n ] de Elementos , x : elemento ) : entero

i ! 1 ;

j ! 1 ;

Si i = = j entonces devolver i

k ! ( i + j ) ;

Si x < T [k] entonces devolver Búsqueda Binaria ( T [ i .. k + 1 ] , x )

Sino

Devolver Búsqueda Binaria ( T [ k .. j ] , x )

T (n) = T ( n/2 ) + cte. ! complejidad = O ( log n )

Una desventaja es que es recursivo , hay que intentar que sea iterativo.

Búsqueda Binaria ( T : array [ 1..n ] de elementos ; x : elemento ) : entero

i ! 1 ;

j ! 1 ;

mientras i < j hacer

k ! ( i + j + 1 ) div 2

Si x < T [k] entonces j ! k - 1

Sino

i ! k + 1

fin mientras

Si T [k] = = x entonces sino devolver -1

Tiene complejidad parecida a la anterior , un poco menor , usa menos memoria al no ser recursivo , como mucho las divisiones del array.

Selección del Elemento K-èsimo

Tenemos un array desordenado

de n elementos

nos interesa saber que elementos estarían en la posición k - ésima si estuviera ordenada ( para la mediana ).

Parecido a la Búsqueda Binaria , tratamos de quitar el máximo de elementos del array del medio.

T 10 5 11 -1 3 14 18 6 7 20

Elemento mediana cumple :

{ # { i " [ 1..n ] / T [ i ] < m } < n/2

" { # { i " [ 1..n ] / T [ i ] " m } " n/2

porque la mediana se puede repetir

Tomamos un elemento al azar , pivote , comprobamos cuantos elementos menores que él hay ( esto es recorriendo el array ) . 5

Luego los que son menores o igual al pivote ( incluye el pivote ) , 6 . El pivote esta en la posición 6 si estuviera ordenado , sería la mediana . Suponemos que esta en el lugar 5 , entonces cogemos un array con los menores que él.

5 -1 3 6 7

nuevo ; menores 2 , menor o igual a él 3 ; mediana en T [ 5 ]

pivote posición 5

Buscamos en los elementos mayores al pivote

6 7 Mediana en T [ 2 ] si estuviera ordenada ( en teoría no lo vemos ).

Pivote menores 0 , menor o igual 1 ; mediana

En lugar de la mediana elemento k - ésimo

K - ésimo { # { i " [ 1..n ] / T [ i ] < m } < k

" { # { i " [ 1..n ] / T [ i ] " m } " k

Ej. : k = 8

10 -1 20 7 18 11 5 14 6 3

pivote , menor 5 menor o igual 6 , k = 8 , ni el pivote ni los menores.

20 18 11 14

pivote , menor 3 menor o igual 4 ; k = 8 , será el lugar segundo , no es el pivote ni los mayores.

18 11 14

nuevo pivote , menor 2 menor o igual 3 ; k = 8 sigue en el segundo

11 14

0 1 k = 2 14

Cuando el array sea pequeño puede ordenarse. El algoritmo quedaría :

Selección ( T : array [ 1..n ] de enteros , k : enteros ) : enteros

Si n es pequeño entonces

Ordenar ( T ) ;

Devolver T [ n ] ;

Sino

p ! T [ 1 ] ;

u ! 0 ;

v ! 0 ;

desde j ! 1 hasta n hacer

Si T [ j ] < p entonces u ++

Si T [ j ] " p entonces v ++

Fin desde

Si k " u entonces

j ! 1

desde i ! 1 hasta n hacer

Si T [ i ]< p entonces

U [ j ] ! T [i ] ; j ++

Fin si

Fin desde

devolver selección ( U [ 1.. n ] , k )

fin si

Si k " v entonces

devolver p

sino

j ! 1

desde i ! 1 hasta n hacer

Si T [ i ] > p entonces

V [ j ] ! T [ i ] ; j ++

Fin desde

devolver selección ( V [ 1 .. n-v ] , k-v )

fin si

fin

Multiplicación de Matrices

A nxn B nxn C nxn

X =

Cada elemento C i,j = a i,k b k,j

k = 1

La complejidad n multiplicaciones y sumas , n x n x n = n³ por fuerza bruta . Parecido a Multiplicaciones de Grandes Números.

Suponemos n = 2

Dividimos las matrices en 4 partes

Dos matrices de n/2 8 ( n/2 )³ + 4 sumas ; 4 x 2 ( n/2 )³ = 8 ( n³/8 ) = n³

sumas = n² ; no mejoro nada.

Manipulamos los productos intermedios . Si definimos :

M1 = ( A21 + A22 - A11 ) x ( B22 - B12 + B11 )

M2 = A11 x B11

M3= A11 x B21

M4 = ( A11 - A21 ) x ( B22 - B12 )

M5 = ( A21 + A22 ) x ( B12 - B11 )

M6 = ( A12 - A21 + A11 - A22 ) x B22

M7 = A22 x ( B11 + B22 - B12 - B21 )

C quedara

7 ( n/2 )³ + 24 n² ( 24 sumas )

Si en lugar de hacer las multiplicaciones directamente las hacemos recursivas.

A B C

X =

T (n) = 8 T ( n/2 ) + 4 n² n³

T (n) = 7 T ( n/2 ) + 24 n² n

Intercambio de Elementos en un Vector

A B C D E F G H I J K L M

Trasladar sin vectores auxiliares

J K L M A B C D E F G H I

Intercambiar subvectores , elemento a elemento , usamos como mucho una posición auxiliar.

O ( n log n )

TEMA 7 : PARAMETROS ACUMULADORES

Parámetros Acumuladores y el Diseño de Algoritmos

Analizar el problema o algoritmo y deducir el número de llamadas que se hace en la recursión por medio de los parámetros.

Fib ( n : entero ) : entero

Si n = = 1 || n = = 2 entonces

Devolver 1

Sino

Devolver Fib ( n-1 ) + Fib ( n-2 )

Fin

FibPar ( n , y z = entero ) : entero

Si n = = 0 entonces devolver y

Sino devolver FibPAr ( n-1 , z , y + z )

Fin

La Llamada original :

Fib ( n ) : entero

devolver FiBPar ( n , 0 , 1 )

Fib (5) ! FibPar (5 , 0 , 1) ! FibPar (4 , 1 , 1) ! FibPar (3 , 1 , 2) ! FibPar (2 , 2 , 3 )

n = 0 no sumo la 2º y 3º posición 0 + 1 = 1

! FibPar ( 1 , 3 , 5 ) ! FibPar ( 0 , 5 , 8 ) ! 5

Las cosas se calculan en la llamada y los resultados se acumulan en los parámetros.

En el algoritmo anterior.

Fib (5)

Fib (4) Fib (3) El cálculo no se realiza hasta devolver las llamadas

...

En FibPar la complejidad es lineal , n.

1-12-97

TEMA 8 : ALGORITMOS VORACES

Problemas con una o varias soluciones , buscaremos la óptima ( puede no funcionar ).

Ej. : Máquina de cambio automático de monedas , utilizando la mínima cantidad de monedas posibles y la máquina tiene monedas ilimitadas.

Monedas : 1 5 25 50 100

Devolver 288 ptas.

Primero las monedas de 100 luego vamos bajando

288-100 = 188

188-100 = 88 resultado positivo vuelvo a restar una de 100

88-100 = negativo , paso a las de 50

88-50 = 38

38-50 = negativo

38-25 = 13

13-5 = 8

8-5 = 3

3-1 = 2

2-1 = 1

1-1 = 0

9 monedas

Estrategia Voraz , porque vamos de lo más grande a los más pequeño de lo que podemos aplicar.

Es más sencilla no hay algoritmos recursivos , la cuestión es elegir.

Hay que determinar los Elementos Fundamentales para aplicar la estrategia :

Conjunto de candidatos ( monedas disponibles ).

Conjunto de candidatos seleccionados , tiene un inconveniente la acoplación de los tipos de datos ( conjunto ) a los lenguajes de programación ( monedas utilizadas en cada momento ).

Función que compruebe si un conjunto de candidatos seleccionados es ya la solución.

Función que determine si un conjunto de candidatos puede formar parte de la solución ( del conjunto de candidatos lo pasamos al conjunto de candidatos seleccionados , queremos saber que el último seleccionado no lo estropea ) . Es un conjunto de restricciones.

Función que seleccione al siguiente candidato.

Función que expresa un objetivo a optimizar ( número de monedas mínimo ).

Lo eficiente de este algoritmo es que no hay vuelta atrás , o incluimos el candidato o no lo incluimos y ya no nos ocupamos de él.

8.1. Esquema General

Voraz ( C : conjunto ) : conjunto partimos de C

Var ( Candidatos ) S ( Solución )

S : conjunto ; x y x x

S ! { 0 }

Mientras ( ( No ( Solución ( S ) ) ) y ( C < > { 0 } )

X ! seleccionar ( C )

C ! C \ { X } /* si no lo cogemos lo eliminamos de los candidatos */

Si ( factible ( S " { X } ) ) Entonces

S ! S " { X }

Fin mientras

Si solución ( S ) Entonces

Devolver S

Sino

Escribir ( “ No hay solución “ )

Fin

El mientras es el bucle voraz , normalmente solo hay uno.

8.2. Arboles de Recubrimiento Mínimos

Yo tengo un grafo dirigido G formado por un conjunto de nodos y uno de aristas , quiero encontrar el número mínimo de aristas que unan todos los nodos , que formen un árbol y la suma del peso de todas las aristas sea un valor mínimo.

G < N , A > , sin ciclos y no más de tres aristas por nodos.

Hacemos una lista de las aristas ordenadas de menor a mayor.

{ 1,2 } , { 4,3 } , { 1,4 } , { 2,6 } , { 1,3 } , { 4,5 } , { 5,7 } , { 7,6 } , { 2,3 } , {3,6 } , { 3,5 } , { 3,7 }.

Solución = número de aristas = número de nodos - 1 # S = n-1 # - elementos de S.

Factible ( S " {x ,y} ) = no haya ciclos = { x ,y } no conecten nodos ya conectados , en cada paso del algoritmo determinado que nodos están unidas entre si ( nodos conexos ).

La función de selección es tomar la siguiente arista de menor peso.

Optimización u objetivo , la suma del peso de las aristas sea mínimo , objetivo = min ( peso { x , y }.

En las componentes conexas tendremos cada nodo al principio CC = { { 1 } , { 2 } , { 3 } , { 4 } , { 5 } , { 6 } , { 7 } }.

Cogemos la primera arista { 1,2 }.

CC = { { 1,2 } , { 3 } , { 4 } , { 5 } , { 6 } , { 7 } }

Arista { 3,4 }.

CC = { { 1,2 } , { 3,4 } , { 5 } , { 6 } , { 7 } }

Arista { 1,4 }.

CC = { { 1,2,3,4 } , { 5 } , { 6 } , { 7 } }

Arista { 2,6 }

CC = { { 1,2,3,4,7 } , { 5 } , { 6 } }

Arista { 4,5 }

CC = { { 1,2,3,4,7,5 } , { 6 } }

Arista { 6,7 }

CC = { { 1,2,3,4,7,5,6 } } ya tenemos el árbol

1 6

3 El árbol no es único

4 7

3 5

Este es el método KRUSKAL

Kruskal ( G = < N , A > : grafo ; A : conjunto ) : Conjunto

Inicio

Ordenar ( A ) ;

n ! # N ; /* número de nodos */

T ! { 0 } ; /* Conjunto solución */

Inicializar _n_conjunto ( ) ; /* Componentes conexas , uno por nodo */

Repetir /* bucle voraz */

{ n , v } ! seleccionar ( A ) ; /* siguiente Candidato */

ncomp ! ComponenteConexa { n }

vcomp ! ComponenteConexa { v }

Si ( ncomp != vcomp ) entonces

Unir ( ncomp , vcomp ) /* son distintos no están unidos */

T ! T " { { n , v } } /* uno los nodos */

Fin si

Hasta que ( # T = = n-1 )

Devolver T

Fin

8.2.1. Arboles de Recubrimiento Mínimo ( Prim )

Kruskal construye varios árboles hasta llegar al último ( bosque ).

Prim escoge las aristas en orden , partiendo de un nodo ( el primero generalmente ) , siempre tenemos un único árbol.

G = < N , A > B

B - conjunto de nodos conectados en un momento dado.

El siguiente paso es mirar el resto de las aristas que van de los nodos iniciales en B hacia el resto de nodos ( otros caminos ) , no considero las aristas que unen entre si a las no B.

Que arista escojo , la menor ( mínimo ).

Ej. :

El desarrollo

Cogemos una arista de menor peso { 1,2 } , B es ahora el nodo 1 y 2 más la arista que los une.

Todos los nodos unidos con 1 y con 2 , escojo la arista de menor peso.

{ 1,2 } , { 1,3 } , { 3,7 } , { 3,4 } , { 4,5 } , { 3,6 }

Arbol no binario

Peso = 1

4 6 7

Prim ( L [ 1..n , 1..n ] ) : conjunto

Inicio

T ! { 0 }

Desde i ! z hasta n hacer

Cercano [ i ] ! 1

Maindist [ i ] ! L [ i , 1 ]

Fin desde

Repetir

Min ! MAXINT

Desde j ! 2 hasta n

Si ( mindist [ j ] " 0 y ( mindist [ j ] < min ) entonces

Min ! mindist [ j ]

K ! j

Fin si

Fin desde

T ! T " { { k , cercano [ k ] } }

Mindist ! [ k ] ! -1

Desde j ! 2 hasta n hacer

Si [ k,j ] < mindist [ j ] entonces

Mindist [ j ] ! L [ k,j ]

Cercano [ j ] ! k

Finsi

Fin desde

Fin repetir

Devolver T

Fin

Cercano - nodos que no están en B que esta más cerca

Mindist [ j ] - longitud o distancia que va desde j hasta cercano de j.

Cercano distmin

L [ i,j ] = dist { i,j } L [ i , i ] = 0

15-12-97

Ej.: Kruskal en C

# define N 10

int encontrar ( int elem , int conjvert [ ] )

{ return ( conjvert [ elem ] ) } ;

void mezclar ( int compu ; int compv , int conjvert [ ] ) {

int x ;

for ( conjvert [ x ] ; x = 0 ; x < N ; x++ )

if ( conjvert [ x ] = = comp v ) conjvert [ x ] = compu ;

} ;

void inicializar ( int comp , int elem , int conjvert [ ] )

{ conjvert [ elem ] = comp } ;

void Kruskal ( int ariini [ ] , int arifin [ ] , int aricoste [ ] , int Tini [ ] , int Tfin [ ] );

{

int conjvert [ N ] , i , min = 0 , n , v , ucomp , vcomp , i = 0

ordenar ( ariini , arifin , aricoste ) ;

for ( i = 0 ; i < N , i++ ) { inicializar ( i , 1 , conjvert )

do {

u = ariini [ min ] ; v = arifin [ min ] ;

min ++ ;

ucomp = encontrar ( u , conjvert ) ;

ucomp = encontrar ( v , conjvert ) ;

if ( ucomp ! = vcomp )

{ mezclar ( ucomp , vcomp , conjvert ) ;

Tini [ t ] = u ; Tfin [ t++ ] = v } ;

while ( t < N ) ;

} ;

Estructura de Datos :

Arrays paralelos para el conjunto de aristas , tres arrays :

ariini - nodo desde el que se parte.

arifin - nodo al que llega correspondiente.

aricoste - peso

Las componentes conexas son conjuntos.

Conjvert - de tamaño N , en cada posición del array hay nodo , en esa posición se indica la componente conexa

Al inicializar cada nodo pertenece a su propia componente conexa

Conjvert [ elem ] = comp ;

Primero ordenamos.

Inicializamos las componentes conexas.

Algoritmo voraz do - while

t - índice que recorre el array Tini indicando que arista voy a coger , donde va Tfin.

min - arista de mínimo peso.

Mezclar - unión de conjuntos.

1 2 3 4

1 3 1 2 3 4

1 1

2 1 y 3 pertenecen a la misma componente conexa.

8.3. Dijkstra

Caminos más cortos entre nodos de un grafo.

Tenemos un grado dirigido , camino más corto entre un nodo y el resto de los nodos.

10 50

5 100 2

10 5

4 3

Conjunto de candidatos - vamos a ir eligiendo los nodos , de los que sabemos cual es el camino más corto.

C 2,3,4,5

S nodos con camino más corto conocido.

Factible.
Solución - C = { }.
Objetivo ( ).
Siguiente ( ) - busca el nodo de camino más corto usando ese nodo ( esta elegido porque tiene el camino más corto ).

C D

2 3 4 5

2 , 3 , 4 , 5 50 30 100 10 Caminos directos

2 3 4 5

2 , 3 , 4 50 30 20 10 Vemos si pasando por 5 reducimos los

anteriores.

2 3 4 5

2 , 3 40 30 20 10 2 ! 4 ! 5 ! ; C - { 3 } , porque es el

de camino más pequeño.

2 3 4 5

3 35 30 20 10 Este array no indica por donde pasa ,

para ello usamos un array auxiliar P.

Cada vez que paso por otro nodo lo guardo , en principio todos apuntan a 1 . En el primer paso el 4 pasa por el 5.

P P P P

1 2 1 2 4 2 4 2

1 3 1 3 1 3 1 3

1 4 5 4 5 4 5 4

1 5 1 5 1 5 2 5

Para sacar la información ( 1 , 2 ) P indica el paso siguiente es el 3 2 3 luego

con el 1 2 3 1 camino más corto.

El camino más corto entre el nodo k y 1 esta formado solo por caminos mínimos , sino es directo .

k 1 de j a 1 es un camino mínimo . No me

10 10 me preocupo por otros camino , solo

j j a k porque es mínimo.

Dijkstra ( L [ 1..n , 1..n ] : array [ 2..n ] )

C ! { 2..n }

desde i ! 2 hasta n ; D [ i ] ! L [ i ]

repetir n-2 veces

v ! mínimo ( D ) ; /* busco el elemento mínimo de D que esté. en C */

C ! C \ { v }; /* elimino el elemento de C */

para cada W " C hacer

Si D [ W ] > D [ v ] + L [ v , W ] entonces

D [ W ] ! D [ v ] + L [ v , W ]

P [ W ] ! v

fin si

fin para

fin repetir

Devolver D

Fin.

El grafo esta en L que es de adyacencia , el peso esta en L [ i , j ] , L [ i , j ] " L [ j , i ],

L [ i , i ] = 0 Diagonal

L [ i , j ] = " " { i , j }

# Define N 5

void Dijstra ( int L [ n ] [ ] , int D [ ] , int P [ ] )

{ int C [ N + 1 ] , i , v , w , minc = MAXINT , veces = N - 2 ;

for ( i = 2 ; i < = N ; i ++ ) C [ i ] = 1 ;

for ( i = 2 ; i < = N , i ++ ) D [ i ] = L [ 1 ] [ i ] ;

do { minc = MAXINT

for ( i = 2 ; i < N ; i ++ )

if ( C [ i ] && ( D [ i ] < minc ) ) /* si es 0 no esta en C */

{ v = i ; min = D [ i ] ; }

C = [ v ] ;

for ( w = 2 ; w < = N ; w ++ )

if [ w ] && ( D [ w ] > D [ v ] + L [ v ] [ w ] )

{ D [ w ] = D [ v ] + L [ v ] [ w ] ;

P [ w ] = v ;

} ;

while ( -- veces ) ;

}

8.4. Mochila

Tenemos una mochila de capacidad C , se puede llenar con objetos que tienen un cierto valor o beneficio , llenar la mochila con el máximo de beneficio.

Puede no haber límite de objetos.

Primero cogemos los objetos menos pesados y que valgan más , la solución puede ser la solución no optima , pero el tiempo es rápido.

8.5. Planificador de Tareas

Asignar recursos

T1 = 5 ; T2 = 10 ; T3 = 3

El tiempo de espera , hasta realizar las tres tareas , sea el mínimo posible.

5 + 5 espera + 10 + 5 espera + 10 espera + 3 = 38

La orden de ejecución de tareas minimiza los tiempos de espera

132 - 5 + 5 espera + 3 + 5 + 3 + 10 = 31

213 - 10 + 10 + 5 + 10 + 5 + 3 = 41

231 - 10 + 10 + 3 + 10 + 3 + 5 = 37

312 - 3 + 3 + 5 + 3 +5 + 10 = 29 es el mejor.

Primero las tareas pequeñas , es voraz una vez elija no se vuelve a utilizar

8.5.1. Tareas con Plazo

Ahora además de su tiempo tienen un plazo para realizar las tareas.

Ej. : T1 = 1 T2 = 1 T3 = 1 T4 = 1

B1 = 50 B2 = 10 B3 = 15 B4 = 30 Beneficio de realizarlo antes del plazo

P1 = 2 P2 = 1 P3 = 2 P4 = 1

Conjunto de tareas que se pueden realizar y en que orden de manera que se maximi-

ce el beneficio.

Subconjuntos Una tarea Dos tareas

1 50 2,1 60

2 10 1,3 65

3 15 4,1 80

4 30 3,2 25

4,3 45

Primero elegir las tareas según el máximo beneficio.

Tiempo 1 2 3 1 2 3

1 ! 4 1

50 50

Ej. : T1 T2 T3 T4 T5 T6

B 25 15 10 7 5 3

P 3 1 1 3 1 3

8.5.2. Solución

T1 T2 T3

t1 t2 t3

t1 + ( t2 + t3 ) + ( t1 + t2 + t3 ) = espera ! minimizarlo.

Ordenamos las tareas de menor a mayor , es lo óptimo , primero ejecuto las menores.

Las restricciones :

T1 T2 T3

Plazo d1 d2 d3

Ganancias g1 g2 g3

t1 = t2 = t3 = 1

NO se pueden realizar todas las tareas en su plazo , minimizo las tareas.

Elementos Básicos

Candidatos : Tareas

Seleccionadas : Tareas que pueden realizarse dentro de su plazo.

Funciones :

Factible ( ) : La nueva tarea puede ejecutarse además de las anteriores dentro de su

plazo.

Solución ( ) : El número de tareas seleccionadas es igual mínimo de tareas seleccio -

nadas es igual a Min { número de tareas , distancia , i = 1 .. n }.

Objetivo ( ) : Maximizar la suma de las ganancias de las tareas ejecutables.

Siguiente ( ) : Tarea de mayor ganancia no seleccionada aun.

T1 T2 T3 T4 T5 T6

g : 25 15 10 7 5 3

d : 3 1 1 3 1 3

Como mucho tres tareas ya que el plazo máximo es tres

1 2 3

T1 ya se ejecuta ( sino por lo menos esta escogida ).

T2 no se puede ejecutar , si desplazamos la uno

1 2 3

2 1

T3 no es factible sustituirla por ninguna , la 1 y 2 ya están escogidas.

2 1 4

T5 plazo 1 no es posible

T6 plazo 3 y no se pueden mover la 1 y la 4.

Planificación ( d [ 0 .. n ] ) : array [ 1 .. k ]

j : array [ 0 .. n ]

Inicio

d [ 0 ] ! j [ 0 ] ! 0

k ! j [ 1 ] ! 1 / * 1 * /

desde i ! 2 hasta n hacer

r ! k / * r apunta a la primera tarea * /

mientras d [ j [ r ] ] > max ( d [ i ] r ) hacer r -- / * 2 * /

si d [ i ] > r " d [ j [ r ] ] " d [ i ] entonces / * 3 * /

desde m ! k hasta r + 1 paso -1

j [ m + 1 ] ! j [ m ]

findesde

j [ r + 1 ] ! i

finsi

findesde

devolver j [ 1 .. k ]

fin

d 0 3 1 1 3 1 3 ambos arrays se empiezan a numerar por 0 y

0 1 2 3 su primer valor 0 .

j 0 j - array tareas

/ * 1 * / siempre elegimos la primera tarea

k - número de tareas seleccionadas , uno al principio.

/ * 2 * / el plazo de la última tarea con la tarea que estamos mirando y r da el lugar

0 3 1 1 3 1 3

0 1 2 3

0 1

/ * 3 * / 1 > 0 " 0 " 1 Si

0 1 2 3

0 2 1

0 3 1 1 3 1 3

k = 3

8.6. Viajante

Vendedor que recorre una serie de ciudades , sabe el coste entre cada dos ciudades , recorrido de manera que no se pase dos veces por la misma ciudad ( excepto si la ciudad inicial es también la final ) y coste mínimo.

Parecido al kruskal : no formar ciclos

En un nodo no deben incidir más de dos aristas.

Modificar Kruskal , al decidir la siguiente arista incluyendo estas dos condiciones.

12-1-98

este no vale porque pasamos dos veces por el

mismo nodo.

Igual al árbol de recubrimiento mínimo :

Todos los nodos están conectados.

Se minimiza la suma de los pesos de las aristas.

No se forman ciclos ( salvo para cerrar el recorrido , el primero y el último ).

La diferencia

En un nodo no inciden más de dos aristas ( árbol especial ).

Grado de un nodo = número de aristas que inciden en él.

4'. El grado de los nodos es dos , siempre coinciden dos aristas.

ELEMENTOS BASICOS

Candidatos =

aristas del grafo

Candidatos Seleccionados =

aristas seleccionadas ( forman el itinerario ).

Cuatro funciones :

Factible ( ) - aristas no forman ciclos y grado de los nodos " 2.

Solución ( ) - Todos los nodos seleccionados están conectados por el conjunto de

aristas.

Objetivo ( ) - ( parte voraz del algoritmo ) , minimiza la suma de los costes de

aristas.

Siguiente ( ) - ( Criterio para elegir al candidato ) , arista de menor coste no

escogida todavía.

Viajante ( G : < N , A > grafo ) : conjcertices

grado : array [ 1 .. # N ] de enteros

T : conjvertices

Inicio

n ! # N

T ! { 0 }

Inicializar NComponentes ( )

desde i ! 1 hasta n hacer grado [ i ] = 0

ordenar ( A )

{ bucle voraz }

repetir

[ u , v } ! Siguiente ( A )

ucomp ! encontrar ( u )

vcomp ! encontrar ( v )

Si ( ucomp != vcomp ) && ( grado [ u ] < 2 ) && ( grado [ v ] < 2 ) entonces

mezclar ( ucomp , vcomp )

T ! T " { { u , v } }

grado [ u ] ++

grado [ v ] ++

finsi

hasta que # T == n - 1

devolver T

fin

16 - 2 - 98

TEMA 9 : PROGRAMACION DINAMICA

La estrategia es para optimizar el número de cálculos para conseguir la información de la manera más simple posible.

9.1. Números Combinatorios

n n - 1 n - 1

= +

k k k - 1

n n

= = 1

0 n

Cogemos el método divide y vence

NC ( n , k : enteros ) : entero

Si k == 0 o k == n entonces

devolver 1

sino

devolver NC ( n - 1 , k ) + NC ( n - 1 , k - 1 )

finsi

fin

La complejidad es exponencial , si vemos las llamadas :

5 5

2 3

4 4 4 4

1 2 2 3

es mejor hacer los cálculos al revés de la base hacia el resultado final , reducimos las llamadas usando el triángulo de Tartaglia.

0 1

1 1 1 1

0 1

2 2 2 1 2 1

0 1 2

No usamos llamadas recursivas , reorganizamos los cálculos ( es lo común en la programación dinámica ) , pero empezando por el final ( lo más sencillo ).
Utilizamos tablas o vectores para no realizar dos veces el mismo cálculo.

NCD ( n , k : enteros ) : entero / * D - dinámica * /

Var

NCV - array [ 0 .. n ] de enteros

Inicio

NCV [ 0 ] ! NCV [ 1 ] ! 1

desde i ! 1 hasta n hacer

NCV [ i ] ! 1 / * en la posición 1 un 1 * /

desde j ! i - 1 hasta 1 paso -1 hacer

NCV [ j ] ! NCV [ j ] + NCV [ j - 1 ]

findesde

devolver NCV [ k ]

fin

NCV - cada vez es una línea diferente del triángulo de Tartaglia.

NCV

0 1 2 3 4 5 6 6

1 1 1 3

NCD ( 6 , 3 )

2ª fila del triángulo

en la posición 2 un 1 y en la 1 la suma de 0 y 1 = 2 dejándolo en j

1 2 1 1

en la posición 3 un 1 y vuelvo para atrás sumando

9.2. Fibonacci

Si n = 1 o n = 2 entonces

devolver 1

sino

devolver Fib ( n - 1 ) + Fib ( n - 2 )

a ! 1 b ! 1

repetir n_veces

aux ! a + b

a ! b

b ! aux 1 1 2 3 5

fin repetir

devolver b

9.3. Campeonato

Tenemos dos equipos A y B , gana el que primero gane n partidos , como mucho jugaran 2n - 1 partidos , hay que descubrir la probabilidad de que A gane el torneo.

Tenemos ciertos datos :

Misma probabilidad en todos los partidos de que A o B gane el partido

p = probabilidad A gane un partido cualquiera

0 < p < 1

q = probabilidad de que B gane un partido

q = 1 - p

Lo que queremos calcular

P ( i , j ) = probabilidad de que el equipo A gane el torneo cuando le faltan i partidos por ganar y a B le faltan j partidos.

N = 10 A ganados 2

B ganados 5

P ( 8 , 5 )

d P ( n , n ) ? Antes de empezar el torneo

P ( 0 , j ) = 1 ! a A le faltan 0 partidos por ganar

P ( i , 0 = ) 0 ! B ha ganado los partidos necesarios

P ( i , j ) = P * P ( i - 1 , j ) + q * P ( i , j - 1 ) / * + " o * /

Si A gana el partido le quedan i - 1 partidos por ganar.

Si B gana el partido le quedan j - 1 partidos por ganar.

Divide y Vence :

P ( i , j : enteros ) : real

Si i == 0 entonces

Devolver 1 , 0

Sino

Si j == 0 entonces

Devolver 0 , 1

Sino

Devolver p * p ( i - 1 , j ) + q * p ( i , j - 1 )

finsi

fin

T ( n ) = 2 T ( n - 1 ) + C

Ec. Característica O = ( 2 ) , la complejidad esta en las llamadas

P ( 10 , 10 )

P ( 9 , 10 ) P ( 10 , 9 )

P ( 8 , 10 ) P ( 9 , 9 ) P ( 9 , 9 ) P ( 10 , 8 )

... cálculo repetido

Empezamos P ( 0 , x ) y P ( x , 0 )

Campeonato ( n : entero , p : real ) : array [ 0 .. n ] [ 0 .. n ] de reales

Var

p : array [ 0.. n ] [ 0 .. ] de reales

q : real

Inicio

q ! 1 - p

desde s ! 1 hasta n hacer

P [ 0 ] [ s ] ! 1 , P [ s ] [ 0 ]! 0

desde k ! 1 hasta s - 1 hacer

P [ k ] [ s - k ] ! p * P [ k - 1 ] [ s - k ] + q * P [ k ] [ s - k - 1 ]

fin desde

desde s ! 1 hasta n hacer

desde k ! 0 hasta n - s hacer

P [ s + k ] [ n - k ] ! p * P [ s + k - 1 ] + q * P [ s + k ] [ n - k - 1 ]

fin desde

devolver P

fin

j s = 1 s = 2 s = 3 s = 4 s = 5

i 0 1 2 3 4 5

0 1 1 1 1 1 s = 1

1 0 k =1 k =1 k =1 k =1 s = 2

2 0 k =2 k =2 k =2 s = 3

3 0 k =3 k =3 P(i,j) s = 4

4 0 k =4 s = 5

5 0 Para P ( i , j ) necesitamos

P ( i - 1 , j ) y P ( i , j - 1 )

Devolvemos la matriz entera

Rellenar la matriz sin repetir cálculos :

Columna a columna
Diagonal a Diagonal , la del algoritmo empezando por el final

s - recorre cada diagonal

k - elemento de la diagonales que no son primera fila y columna

los dos primeros bucles rellenan la mitad.

Complejidad n²

23 - 2 - 98

9.4. Problema de la Mochila

Lo haremos con una mochila de tamaño 17 , M = 17

Meter objetos en la mochila :

Los objetos no se pueden fraccionar o dividir en partes.

A B C D E

3 4 7 8 9 Tamaño

4 5 10 11 13 Valores ( por unidad )

Llenar la mochila con el máximo valor y máximo número de objetos.

Empezamos por lo más pequeño , usamos una estructura de datos que es una array y tamaño de mochilas de 1 a 17.

Costes - array en el que indico el valor de los objetos que meto en el array hasta ese momento.

Mejor - indica el último elemento introducido en la mochila.

Lo hacemos en x pasos ( x - número de objetos ) . Primero objetos de A , luego de A y B , etc. ( de pequeño a mayor ).

Solo A

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4 4 4 8 8 8 12 12 12 16 16 16 20 20 20 Coste

A A A A A A A A A A A A A A A Mejor

tam [ A ]

En la mochila de tamaño 3 cabe un objeto de tamaño A.

En la mochila de tamaño 6 vamos a ver lo que podemos meter considerando que la mochila de tamaño 3 esta llena de la mejor manera , le resto al tamaño de la mochila en cada momento el tam [ A ] . Solo guardo el último objeto.

6 A

3 A 6

A 3

A 4

16 para ver con detalle , 14 ! A + mochila tamaño 11! A + mochila tamaño 8 ... , 5 A' s huecos

A y B , podemos mejorar sacando algún objeto A y meter uno de b o meter uno de B antes de meter un A

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4 5 5 8 9 10 12 13 14 16 17 18 20 21 22 Coste

A B B A B B A B B A B B A B B Mejor

Mochila de tamaño 6 , ¿ puedo meter un objeto de tamaño B ? , si y queda un hueco de 2 , ¿ Es mejor que lo que teníamos ? , no dejamos lo que teníamos.

Mochila de tamaño 7 , ¿ puedo meter un objeto de tamaño B ? , si queda un hueco de 3 , miro la mochila de 3.

B ! 5

3 4

9 ! miramos la última información , actualizando

Mochila de tamaño 7 , ¿ puedo meter un objeto de tamaño B ? , si queda un hueco de 4 , en una de cuatro miro la mochila de tamaño 4 a otro B

4 B 5

B 4 5

Mochila de tamaño 15 , ¿ puedo meter un B ? , si deja un hueco de 11 , valor de la mochila 11.

B 5

11 14

19 , no mejoro , tenía 20 no cambia

A , B y C

Coste y Mejor son vectores no tablas , C es de tamaño 7 entonces la mochilas inferiores 3 , 4 , 5 , 6 quedan como están.

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4 5 5 8 10 10 12 14 15 16 18 20 20 22 24 Coste

A B B A C B A C C A C C A C C Mejor

Mochila de tamaño 8 , ¿ Un B ? , si igual que antes dejo lo que había antes.

Mochila de tamaño 9 , ¿ Un B ? , si valor 10 peor que antes no cambio.

Mochila de tamaño 10 , ¿ Un B ? , si hueco de 3 , 10 + 4 = 14 cambio.

Mochila de tamaño 17 , ¿ Un B ? , si hueco de 10 , 10 + 14 = 24 cambio

A , B , C y D

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4 5 5 8 10 11 12 14 15 16 18 20 21 22 24 Coste

A B B A C D A C C A C C D C C Mejor

A , B , C , D y E

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4 5 5 8 10 11 13 14 15 17 18 20 21 23 24 Coste

A B B A C D E C C E C C D E C Mejor

Mochila de tamaño 17

E 13

8 11

24 , igual que lo anterior

El mayor valor de la mochila = 24 , ¿ Como lo lleno ? , vamos a mejor

Hay un C , 17 - tamaño [ C ] = 10 , mochila tamaño 10 un C , 10 - 7 = 3 , mochila tamaño 3 un A , CAA.

17 Si hubiera dejado la E

C 17 E D

C E

A D

Este problema cumple :

Principio de Optimalidad

Para que funcione mejor un problema de programación dinámica “ obtener el mejor ... “.

Para que el resultado sea óptimo las etapas han de ser óptimas.

No calcular desordenadamente , si una parte en llenar es óptima y la otra también es óptima el resultado es óptimo.

Mochila Dinámica ( tamaño , valor : array [ 1 .. M ] : array [ 1 .. M ] )

Desde j ! 1 hasta N hacer / * A .. E , N - número de objetos * /

Desde i ! 1 hasta M hacer / * M - tamaño mochila , 1 - M * /

Si ( i - tamaño [ j ] " 0 ) entonces / * índice mochila , puedo meter el objeto * /

Si (coste [ i ] < (coste [ i-tamaño ]+ valor [ j ] ) entonces /* mejor anterior */

coste [ i ] ! coste [ i - tamaño [ j ] ] + valor [ j ] / * lo cambio * /

mejor [ i ] ! j

fin si

fin desde

devolver coste

fin

Reconstruir la mochila una vez llenada

Ercr Mochila ( mochila : entero ; tamaño : array [ 1 .. N ] ; coste , mejor : array [1 .. N])

Inicio

mientras mochila > 0 && coste [ mochila ] > 0 hacer

escribir ( mejor [ mochila ] )

mochila = tamaño [ mejor [ mochila ] ]

fin mientras

fin

9.5. Grafos : Caminos Más Cortos

Floyd

1 3

30 Tenemos un grafo dirigidos , caminamos

5 50 15 5 más cortos entre todos los nodos ( opti -

5 malidad )

2 4

Ir por orden empezando por poco escribiendo en una estructura.

Primero por el nodo 1 , luego 1; 2 , 1; 2 ; 3 hasta 1 ; 2 ; 3 ; 4.

En un momento dado se el camino más corto entre el nodo i y j pasando por los nodos 1..k ( por 1 o todos ).

i j

[ 1..k ] [ 1 .. k ] [ 1 .. k ] es menor i ! k+1 ! j que i ! j , si lo cambio

si no el que tenía k ! k + 1

k+1

definimos el grafo como Matriz de Adyacencia

L [ i , j ] = distancia { i , j } si " { i , j } ( existe camino )

= 0 si i = j

= " si " { i , j }

0 5 " "

50 0 15 15

L = 30 " 0 15

15 " 5 0

Estructura - una matriz Dk [ i , j ] = caminos más corto entre i y j usando los nodos 1 , 2 hasta k.

La matriz D0 = L ( caminos directos )

D1 caminos que pasan por 1

D1 = 0 5 " " La fila y columna 1 no cambian ya que es 1

50 0 15 5

30 35 0 15

15 20 5 0

Camino entre 2 y 3 que pasen por el 1 , no ! se queda como esta.

Camino entre 2 y 4 que pasen por el 1 , no ! se queda como esta.

Camino entre 3 y 2 que pasen por el 1 , si 3 - 1 (30) , 1 - 2 (5) , si 35 < " cambio.

Camino entre 4 y 2 que pasen por el 1 , si 4 - 1 (15) , 1 - 5 (5) = 15 + 5 = 20

D2 = 0 5 20 10

50 0 15 5

30 35 0 15

15 20 5 0

Camino entre 2 y 3 pasando por el 2

Camino 3 y 4 , si peso 35 y del 2 al 4 peso 5 ; 35 + 4 = 40 < 15 , no , no se cambia.

3 15 4

D1 [ 3 , 4 ]

D1 [ 3 , 2 ] D1 [ 2 , 4 ]

35 2 5

D3 = 0 5 20 10

45 0 15 5

30 35 0 15

15 20 5 0

Camino 2 , 1 2-3 peso 15 , 3 - 1 peso 30 , 30 + 15 = 45 < 50 , si cambio

D4 = 0 5 15 10

20 0 10 5

30 35 0 15

15 20 5 0

Del 2 al 1 pasando por el 4 si , 20 < 45 , si cambio

Tenemos los caminos mínimos , ahora nos preguntamos ¿Por donde pasan los caminos? , tenemos una matriz P inicializada a 0 , cuando meto un nuevo nodo en el camino lo pongo , dejo el último al ser cada etapa óptima.

0 0 4 2 0 son caminos directos

P = 4 0 4 0

0 1 0 0

Camino corto entre el nodo 1 y 3 pasa por el nodo 2

1 3

Camino directo en P 0 entre 1 y 2 2 4

Floyd ( L : array [ 1 .. n , 1 .. n ] ) : array [ 1 .. n , 1.. n ]

Inicio

D ! L

desde k ! 1 hasta n hacer / * D1 , D2 , D3 , ... * /

desde i ! 1 hasta n hacer / * Cada matriz por * /

desde j ! 1 hasta n hacer / * fila y columnas * /

Si D [ i , j ] > D [ i , k ] + D [ k , j ] / * antiguo > nuevo camino * /

D [ i , j ] ! D [ i , k ] + D [ k , j ]

P [ i , j ] ! k

fin si

fin desde

devolver D

fin

2-3-98

9.6. Multiplicación de Matrices

Más de dos matrices , n matrices :

M1 M2 M3 ... Mn

Colocaremos los paréntesis de forma que el número de multiplicaciones sea el mínimo posible y sin repetir cálculos. Puede haber matrices no cuadradas.

Mi * Mi+1 = M filas Mi columnas Mi+1 ! filas de Mi y columnas Mi+1

Cogemos todas las filas de Mi * columnas Mi+1 , el total de multiplicaciones.

filas Mi * columnas Mi * columnas Mi+1

array r [ 1 .. N + 1 ]

r [ i ] = filas de la matriz Mi

r [ i+1 ] = columnas de Mi tienen que ser iguales para poder multiplicar

filas de Mi+1

C [ N+1 ] = columnas de MN

Número de Multiplicaciones ( Mi * Mi+1 ) = r [ i ] * r [ i+1 ] * r [ i+2 ]

Ahora hay que colocar los paréntesis entre las matrices

( M1 ... Mj ) ( Mj+1 ... MN ) es menor el coste de poner aquí los paréntesis , antes tengo que ver cada conjunto , voy a ir en conjunto de dos matrices , luego tres , etc. Sin repetir cálculos.

( M1 ... Mj ) ( Mj+1 ... MN ) ! r [ j+1 ] * r [ N+1 ] dimensiones de la segunda matriz

r [ i ] * r [ j+1 ] dimensiones de la primera matriz

El coste de la matriz total = r [ i ] * r [ N+1 ] * r [ j+1 ].

Ahora veo cada parte

Nº Multiplicaciones ( M1 ... Mk ) ( Mk+1 ... Mj ) = r [ i ] * r [ N+1 ] * r [ j+1 ]

Columnas de la 1ª

La función quedaría Num Mult ( i , j , k )

Ej. : tenemos 6 matrices

A4x2 B2x3 C3x1 D1x2 E2x2 F2x3

Utilizamos una tabla de 5x5

B C D E F

Primero multiplicamos matrices de 2 en 2 ( sin paréntesis ) , vemos lo que cuesta multiplicar A x B poniéndole en la casilla.

A x B = 4 x 2 x 3 = 24 B C D E F

B x C = 6 x 2 x 1 = 6 A AB

C x D = 3 x 1 x 2 = 6 24

D x E = 1 x 2 x 2 = 4 B BC

E x F = 2 x 2 x 3 = 12 6

C CD

D DE

E EF

Grupos de tres matrices :

( AB )4x3 C 24 + 4 x 3 x 1 = 36 B C D E F

A4x2 ( BC )2x1 6 + 4 x 2 x 1 = 14 A AB A(BC) (ABC) D

( BC )2x1 D2x1 6 + 2 x 1 x 2 = 10 24 14 22

B2x3 ( CD )3x2 6 + 1 x 2 x 2 = 10 B BC (BC) D (BC) (DE)

... 6 10 14

Indico donde poner el C CD C ( DE )

paréntesis , solo apunto el 6 10

último D DE (DE) F

4 10

E EF

Grupos de 4 matrices , cada parte tiene que ser óptima para que todo sea óptimo

A ( BCD ) A ( C ( CD ) )

A ( ( BC ) D ) ! ya esta calculado

( AB ) ( CD )

( ABC ) D ( A ( BC ) ) D ! calculada

( ( AB ) C ) D

Se queda en tres posibilidades :

A4x2 (BCD)2x2 = 10 + 4 x 2 x 2 = 26

(AB)4x3 (CD)3x2 = 24 + 6 + 4 x 3 x 2 = 54

(ABC)4x1 D1x2 = 14 + 4 x 1 x 2 = 22

Otro :

C3x1 (DEF)1x3 = 10 + 3 x 1 x 3 = 19

(CD)3x2 (EF)2x3 = 6 + 12 + 3 x 2 x 3 = 36

(CDE)3x2 F2x3 = 10 + 3 x 2 x 3 = 28

Grupo de 5 matrices :

A4x2 (BCDE)2x2 = 14 + 4 x 2 x 2 = 30

(AB)4x3 (CDE)3x2 = 24 + 10 + 4 x 3 x 2 = 58

(ABC)4x1 (DE)1x2 = 14 + 4 x 1 x 2 = 26

(ABCD)4x2 E2x2 = 22 + 4 x 2 x 2 = 38

Grupos de 6 matrices :

A4x2 (BCDEF)2x3 = 14 + 4 x 2 x 2 = 30

(AB)4x3 (CDEF)3x3 = 24 + 19 + 4 x 3 x 3 = 79

(ABC)4x1 (DEF)1x3 = 14 + 10 + 4 x 1 x 3 = 36

(ABCD)4x2 (EF)2x3 = 26 + 12 + 4 x 2 x 3 = 62

(ABCDE)4x2 F2x3 = 26 + 4 x 2 x 3 = 50

fila A columna E

B C D E F

A AB A (BC) (ABC) D (ABC) (DE) (ABC) ( DEF)

24 14 22 26 36

B BC (BC) D (BC) (DE) (BC) (DEF)

6 6 14 22

C CD C (DE) C (DEF)

6 10 19

D DE (DE) F

4 10

E EF

Hacia atrás :

( A ( BC ) ) ( ( DE ) F ) 36 ! 14 A ( BC )

10 ( DE ) F

Multi Matrices ( r : array [ 1 .. N+1 ] de enteros ) : enteros

Var

coste : array [ 1.. N , 1 .. N ] de enteros ;

mejor : array [ 1.. N , 1 .. N ] de enteros ;

Inicio

desde i ! 1 hasta N hacer

desde j ! i+1 hasta N hacer

coste [ i , j ] ! MAXINT

fin desde

desde i ! 1 hasta N hacer coste [ i ,i ] ! 0 / * la diagonal a 0 * /

desde j ! 1 hasta N-1 hacer / * de 2 en 2 , 3 en 3 , etc. * /

desde i ! 1 hasta N- j hacer / * para cada grupo de x matrices donde ponemos

desde k ! i+1 hasta i+ j hacer / * el paréntesis * /

t ! coste [ i , k-1 ] + r [ i ] * r [ k ] + r [ i+j+1 ]

Si t < coste [ i , i+ j ] entonces

coste [ i , i+ j ] ! t

mejor [ i , i+ j ] ! k

fin si

fin desde

devolver coste [ 1 , N ]

fin

i - en los grupos de 3 en 3 cuantos se pueden formar de tres en tres.

k - paréntesis , lugar donde pongo el paréntesis.

t - cuanto cuesta realizar una multiplicación.

Mi Mk-1 Mk M i +j

coste [i , k-1 ] + coste [ k, i+ j ] + coste multiplicación r [ i ] * r [ k ] * r [ i+j+1 ]

Escribir el orden de los paréntesis :

orden ( i , j : enteros )

Si i == j entonces

escribir ( nombre [ i ] )

sino

escribir ( ` ( ` )

orden ( i , mejor [ i , j ] - 1 ) / * que poner de la matriz 1 hasta k - 1 * /

escribir ( ` * ` )

orden ( mejor [ i , j ] , j ) / * de k hasta N * /

escribir ( ` ) ` )

fin si

fin

Existirá una tabla con el nombre de las matrices :

char nombre [ ] = { ` A ` , ` B ` , ` C ` , ` D ` , ` E ` , ` F ` } ;

9.7. Arbol de Claves

Tenemos una serie de claves o palabras que están en un árbol binario ordenado , tenemos que intentar que la búsqueda sea lo más fácil.

Las palabras más fáciles de encontrar ( las que buscamos más veces , tienen menor esfuerzo ) están en la raíz , las que menos buscamos están en la hojas.

Como decidimos cual colocamos más arriba.

K1 < K2 < ... < Kn Palabras o claves ordenadas

f1 < f1 < ... < fn frecuencias de búsqueda de las palabras , números enteros.

Arbol Binario - rama izquierda hijo más pequeño

K K rama derecha hijo más mayor.

K K K K

...

Arriba las de frecuencia mayor

Peso del árbol = fi * ( di + 1 )

i = 1

profundidad d = distancia entre niveles y la raíz

raíz = 1 ( +1 sino 0 )

nivel = 2

...

Como construyo un árbol ordenando de claves con el menor peso posible.

Ej. : Palabras de C If , else , do , etc. , primero cogemos las palabras de dos en dos

do else if

5 10 15

do else En el primer árbol según el peso

cuesta más buscar.

else do

5 x 1 + 10 x 2 = 25 10 x 1 + 5 x 2 = 20

else if

if else

10 x 1 + 15 x 2 = 40 15 x 1 + 10 x 2 = 35

de tres en tres

do do else if if

else if do if do else

if else else do

Se cumple el principio de optimalidad , un árbol es óptimo si sus subárboles son óptimos.

Peso do else if

35 do if 20

5x1 + 35 + (10+15) = 65 5x2 + 10x1 + 15x2 = 50 15 + 20 + (5+10) = 50

hay que sumar uno más de cada porque ha cambiado la profundidad

Quedan dos árboles iguales , else o if de raíz.

9-3-98

4 2 1 3 5 2 1

A B C D E F G

Letras ordenadas , los números son las frecuencias de esas letras o claves , árbol que busque esas claves empleando el mínimo coste , para ello las claves de mayor coste estarán en la raíz , se calcula el coste o peso del árbol.

Peso = fi ( di + 1 )

Se cumple el principio de optimalidad.

Tabla de 6 x 6

B C D E F G

i,j

coste [ i ][ j ] = peso opt ( ki ... ki+j ) , árboles que tengan como raíz cualquier nodo

kl si es óptimo sus subárboles también

ki ... kl-1 kl-1 ... ki+j

desde l ! i hasta i + j

si coste [ i ] [ j ] > coste [ i ] [ l - 1 ] + coste [ l + 1 ] [ j ] + fi

Empezamos por árboles de dos nodos :

A B

B A

4 x 1 + 2 x 2 4 x 2 + 2 x 1 Peso

8 10

C D

D C

1 x 1 + 3 x 2 1 x 2 + 3 x 1

7 5

Tres nodos :

A B C B C D

BC A C AB CD B D DC

1x4 + 4+ 2 + 1 2x1 + 4x2 + 1x2 8 + 4 +2 + 1x1 5+2+1+3 2x1+2x1+3x2 4+2+1+3

11 12 15 11 12 10

Se suma al bajar el valor de los nodos que han bajado.

Cuatro nodos :

A B C D

BCD A CD AB D ABC

10 + 4 + 2 + 1 + 5 4x2 + 2x1 + 5 + 3 + 1 8 + 4x2 + 1x1 + 2x3 11 + 4 + 2 + 1 + 3x1

20 19 24 21

C D E F

DEF C EF CD F CDE

15 1 + 9 5 + 2 14

Arboles de cinco nodos , solo tres :

A B C D E

BCDE A CDE AB DE ABC E ABCD

20 4 + 14 8 + 11 11 + 5 19

Con seis nodos :

A B C D E F

BCDEF A CDEF AC DEF ABC EF ABCD F ABCDE

26 4 + 18 8 + 15 11 + 9 19 + 2 31

Con siete nodo :

D D D

ABC EFG A EFG A E

BC B F

C D

El árbol ABC ! raíz A ! BC ! B

Arbol Claves ( f : array [ 1.. N ] de enteros ) : array [ 1 .. N+1 , 1 .. N+1 ] de enteros

Var

coste , mejor : array [ 1 .. N + 1 , 1 .. N + 1 ] de enteros

Inicio

desde i ! 1 hasta N hacer / * inicializar el triángulo superior * /

desde j ! i + 1 hasta N + 1 hacer coste [ i , j ] ! MAXINT

fin desde

desde i ! 1 hasta N hacer coste [ i , i ] ! f [ i ] / * inicializo la diagonal con su * /

desde j ! 1 hasta N-1 hacer / * frecuencia * /

desde i ! 1 hasta N - j hacer

desde k ! 1 hasta i + j hacer

t ! coste [ i , k - 1 ] + coste [ k + 1 , i + j ] / * coste de subárboles * /

Si t < coste [ i , i + j ] entonces / * encontrar el menor * /

coste [ i , i + j ] ! t

mejor [ i , i + j ] ! k

fin si

fin desde

t ! 0

desde k ! i hasta i + j hacer / * árbol de menor peso * /

t ! t + f [ k ]

fin desde

coste [ i , i + j ] ! coste [ i , i + j ] + t

fin desde

devolver mejor

fin

f ! array de frecuencias claves ( ordenadas )

j ! dos nodos , 3 , etc.

i ! todos los posibles árboles dentro de dos nodos , 3 , etc.

k! raíces posibles en cada posibilidad , encontrar el menor

i " raíz k " i + j

i .. k - 1 k + 1 ... i + j

Complejidad n³.

9.8. Investigación Operativa

Tenemos una empresa alimenticia , tiene que recoger la materia prima de un territorio dividido en partes A , B , C , D . Lo recoge a base de camiones , decide comprar 6 camiones más , pero un camión no puede recorrer dos zonas.

¿ Como asignamos los 6 camiones a las cuatro zonas maximizando el beneficio adquirido ?.

El beneficio de un camión en cada zona :

columnas - zonas

filas - beneficio según los camiones a cada zona

R - rendimiento

R1 R2 R3 R4

A B C D

0 0 0 0 0

1 4 2 6 2

2 6 4 8 3

3 7 4 8 4

4 8 8 9 5

5 8 9 9 6

6 10 10 10 6

Otro nombre del problema es de la decisión en n etapas

D1 D2 D3 D4

x0 x1 x2 x3 x4 = 0

6 A B C D

r1 r2 r3 r4

cada decisión es casi independiente de las demás

! - número de camiones

D1 - decisión zona ( 1 - zona1 )

x1 = x0 - D1

x2 = x1- D2

x3 = x2 - D3

x4 = x3 - D4 x3 = D4

x4 = 0

Las D las tomo en función de los beneficios ( tabla ).

r1 = R1 ( x0 - D1 )

D! mayor beneficio posible = ganancia g

g4 ( x0 ) = max ( R1 ( x0 , D1 ) + R2 ( x1 , D2 ) + R3 ( x2- D3 ) + R4 ( x3 - D4 ) )

D1 D2 D3 D4

x1 depende de D1 , de lo anterior

g4 ( x0 ) = max { R1 ( x0 , D1 ) + g4 ( x1 ) }

g4 - mayor rendimiento para D1 D2 D3 D4

g3 - mayor rendimiento para las últimas etapas

g3 ( x1 ) = max { R2 ( x1 , D2 ) + R3 ( x2- D3 ) + R4 ( x3 - D4 ) }

D2 D3 D4

g3 ( x1 ) = max { R2 ( x1 , D2 ) + g2 ( x1 - D1 ) }

D2 x2

g2 ( x2 ) = max { R3 ( x2- D3 ) + R4 ( x3 - D4 ) }

D2 D1

g2 ( x2 ) = max { R3 ( x2 , D3 ) + g2 ( x3 ) }

D3 x2 - D3

g2 ( x3 ) = max { R4 ( x3 , D4 ) } / * última columna de la tabla * /

Recursivo g4 , g3 , g2 , g1

gk ( xn-k ) = opt { Rk ( xk-1 , Dk ) + gk ( xn-k + 1 ) }

Dn-k ... Dn

Dinámica empiezo por g1

16-3-98

El esquema anterior se llama Formulación Delantera ( primero etapa 1 , luego etapa 2 , etc. ).

D1 D2 D3 D4

x0 x1 x2 x3 x4 = 0

6 A B C D

r1 r2 r3 r4

Esto se llama ahora Formulación Trasera ( primero la última y al final la primera ).

g4 ( x0 ) = max { R4 ( x4 , D4 ) + R3 ( x3 , D3 ) + R2 ( x2 , D2 ) + R1 ( x1 , D1 ) }

D1 D2 D3 D4

g3 ( x3 ) = max { R3 ( x3 , D3 ) + R2 ( x2 , D2 ) + R1 ( x1 , D1 ) }

D1 D2 D3

g2 ( x2 ) = max { R2 ( x2 , D2 ) + R1 ( x1 , D1 ) }

D1 D2

g1 ( x1 ) = max { R1 ( x1 , D1 ) }

g0 ( x0 = 0 )

rescribo g4

g4 ( x4 ) = max { R4 ( x4 , D4 ) + g3 ( x3 ) }

D4 x3 = x4 - D4

g3 ( x3 ) = max { R3 ( x3 , D3 ) + g2 ( x2 ) }

D3 x2 = x3 - D3

g2 ( x2 ) = max { R2 ( x2 , D2 ) + g1 ( x1 ) }

D2 x1 = x2 - D2

g1 ( x1 ) = max { R1 ( x1 , D1 ) + g0 ( x0 ) }

g0 ( x0 ) = g0 ( 0 ) = 0

g4 ! g3 ! g2 ! g1 ! g0

g0 ! g1 ! g2 ! g3 ! g4

La formulación trasera nos indica que es mejor empezar por la última etapa.

El problema es que no se la entrada de la última etapa , para ello uso tablas , g1 quedara en función de x1 , g2 de x2 , etc.

g1 - D1 = área D

g1 ( x1 ) = max { R1 ( x1 , D1 ) } ; x1 entrada en la etapa filas de la tabla

x1 \ D1 0 1 2 3 4 5 6

0 0

1 2

2 3

3 4

4 5

5 6

6 6

x1 - entradas x1 x0 = x1 - D1

D - decisiones x1 = D1

Rellenamos la tabla con los valores de suma ( el valor de la casilla es beneficio rx ) , si nos dejan 0 camiones beneficio 0.

D1 - número de camiones que cogemos ; g1 - ganancia

D1 g1

0 0

1 2

2 3

3 4

4 5

5 6

6 6

g2 D2 D1

x2 x1 x0 = 0

C D

r2 r1

0 1 2 3 4 5 6 D1 g1

0 0+0 0 0

1 0+2 6+0 1 2

2 0+3 6+3 8+0 2 3

3 0+4 6+3 8+3 8+0 3 4

4 0+5 6+4 8+3 8+2 9+0 4 5

5 0+6 6+5 8+4 8+3 9+2 9+0 5 6

6 0+6 6+6 8+5 8+4 9+3 9+2 10+0 6 6

g2 - guarda las etapas g2 y g1 juntas

D2 g2

0 0

1 6

1,2 8

2 10

2 11

2 12

2 3

g3 ( x3 ) = max { (R3 (x3 , D3 ) + g2 ( x3 - D3 ) }

0 1 2 3 4 5 6 D1 g1

0 0+0 0 0

1 0+6 2+0 0 6

2 0+8 2+6 4+0 0,1 8

3 0+10 2+8 4+6 6+0 0,1,2 10

4 0+11 2+6 4+8 6+0 8+0 1,2,3 12

5 0+2 2+11 4+10 6+8 8+0 9+0 2,3,4 14

6 0+10 2+12 4+11 6+0 8+8 8+6 0 3,4 16

g4 D4 D3

g4 x3

A B

r4 r3

g4 ( x4 ) = max { (R4 (x4 , D4 ) + g3 ( x4 - D4 ) }

6 D4

0 1 2 3 4 5 6 D4 g4

6 0+16 4+14 6+12 7+10 8+8 9+8 10+6 1,2 18

Como lo repartimos , según el algoritmo una o todas

A B C D

1 2 2 1

1 3 1 1

1 3 2 0

1 4 1 0

2 2 1 1

2 2 2 0

Todos beneficios 18

Camiones ( R : array [ 0 .. M , 1.. N ] ; g , D : array [ 0..M , 1..N] )

Inicio

desde i ! 0 hasta M hacer

g [ i , 1 ] ! R [ i , N ] / * lleno la primera etapa que es la 1ª columna copiada de la

D [ i , 1 ] ! i / * última columna de R a la 1ª de g * /

fin desde

desde j ! 2 hasta N hacer / * etapas * /

desde i ! 0 hasta M hacer / * desde 0 hasta 6 filas * /

maxg ! MAXINT

desde k ! 0 hasta i hacer / * mejor entrada posible * /

si R [ k , N-j+1 ] + g [ i-k , j-1 ] > maxg entonces / * suma * /

maxg ! R [ k , N-j+1 ] + g [ i-k , j-1 ]

maxk ! k

fin si

fin desde

g [ i , j ] ! maxg

D [ i , j ] maxk

fin desde

devolver g [ M , N ]

i ! M

desde j ! N hasta 1 paso -1 hacer / * como se forma esa solución * /

escribir ( ` ETAPA ` , ; ,' - ` , D [ i , j ] )

i - = D [ i , j ]

fin desde

fin

R N - número de etapas ( columnas )

M - valor de la entrada ( filas )

Ej. : Tenemos una empresa y queremos hacer una reestructuración , pedimos a tres consultoras que nos asesoren A , B y C . Sabemos que estas tres no son perfectas tienen un porcentaje de que se equivoquen al hacer el estudio :

A B C

40% 60% 80%

Cual es la probabilidad de que se equivoquen las tres a la vez 0.4 * 0.6 * 0.8 = 0.19 casi un 20% , como podemos mejorar , contratamos a un empresa Americana y otra Japonesa para asesorar a esas tres , pero solo pueden asesorar a unas de las tres ( que las una asesore a A o B o C o las 2 a 1 ).

Probabilidad de que se equivoquen aun siendo asesorada por los USA y los Japoneses.

A B C

0 40% 60% 80% No le asesora ninguna

1 20% 40% 50% le asesora una

2 15% 20% 30%

Dos recursos ( asesorías extranjeras ) entre dos empresas.

Formulación Delantera 1-A , C-3.

D1 D2 D3

x0 = 2 x1 x2 x3 = 0

A B C

r1 r2 r3

g - tasa de error

Fuerza bruta

g3 ( x0 ) = MIN { R1 ( x0 , D1 ) * R2 ( x1 , D2 ) * R3 ( x2 , D3 ) }

D1 D2 D3

Recursivo

g2 ( x1 ) = MIN { R2 ( x1 , D2 ) * R3 ( x2 , D3 ) }

D2 D3

g1 ( x2 ) = MIN { R3 ( x2 , D3 ) }

Formulación trasera

D3 D2 D1

x3 x2 x1 x0

A B C

r3 r2 r1

g3 ( x3 ) = MIN { R3 ( x3 , D3 ) * R2 ( x2 , D2 ) * R1 ( x1 , D1 ) }

D3 D2 D1

g2 ( x2 ) = MIN { R2 ( x2 , D2 ) * R3 ( x3 , D3 ) }

D2 D1

g1 ( x1 ) = MIN { R1 ( x1 , D1 ) }

g3 ( x3 ) = MIN { R3 ( x3 , D3 ) * g2 (x3 - D3 ) }

23-3-98

0 1 2 Decisión Ganancia Etapa

Etapa C D1 \ x1

0 1 2 D1 g1

0 0.80 0 0.80

1 0.50 1 0.50

2 0.30 2 0.30

Si no asesora ninguna empresa la tasa de error es la misma 80%.

Etapa B D2 \ x2

0 1 2 D1 g1 D2 g2

0.60 * 0 0.80 0 0.48

0 0.80 = 1 0.50 1 0.30

0.48 2 0.30 2 0.16

0.60 * 0.40 *

1 0.50 = 0.80 =

0.30 0.32

0.60 * 0.40 * 0.20 *

2 0.30 = 0.50 = 0.80 =

0.18 0.20 0.16

Etapa A D3 \ x3

0 1 2 D3 g3

0.15 * 0.20 * 0.15 * 1 0.06

2 0.16 = 0.30 = 0.48 = Menor tasa de error que podemos conseguir

0.064 0.060 0.072

La asignación óptima

A B C

1 0 1

# define M 3

# define N 3

float R [ ] [ ] = { { 0.4 , 0.6 , 0.8 } ,

{ 0.2 , 0.4 . 0.5 } ,

{ 0.15 , 0.2 , 0.3 } } ;

main ( ) {

int i , j , k , mink ;

float g [ M ] [ N ] , ming ;

int D [ M ] [ N ] ;

for ( i = 0 , i < M , i++ ) { / * Etapas * /

g [ i ] [ 0 ] = R [ i ] [ N-1 ] , D [ i ] [ 0 ] = i };/*ganancia última columna del inicio*/

for ( j = 1 , j < N , j++ ) { / * Resto etapas * /

for ( i = 0 , i < M , i ++ ) {

ming = MAXINT ;

for ( k = 0 , k " i , k ++ ) / * Encontrar el menor * /

if ( R [ k ] [ N-j-1 ] * g [ i-k ] [ j-1 ] < ming ) { / * valor mínimo * /

ming = R [ k ] [ N-j-1 ] * g [ i-k ] [ j-1 ] ;

mink = k ; }

g [ i ] [ j ] = ming ;

D [ i ] [ j ] = mink ;

}

printf ( “ Probabilidad de error total : %f \n “ , g [ M-1 ] [ N-1 ] ) ;

i = M-1 ;

for ( j = N-1 ; j > = 0 ; j -- ) {

printf ( “ Empresa %c %d \n “ , j + ` A ` , D [ i ][ j ] );

i -= D [ i ] [ j ] } ;

M - número de etapas

N - número de valores

Matrices D y C guardan los resultados de cada etapa.

Ej. : una distribución de comestibles tiene un capital disponible de 10 Millones de que va a usar en tres zonas de expansión A , B , C .

Los planes de expansión diseñadas vienen descritos por la siguiente tabla ( coste y beneficio del plan ).

Plan \ Coste 0 2 4 Millones

A 0 5 6

0 5 6 8

B 0 6 9 12

0 1

C 0 3

Distribuir los 10 Millones de empresa entre las tres zonas.

Ej. : Tengo 2 cadenas de caracteres

Encontrar el número mínimo de caracteres mínimo que tengo que quitar en las dos cadenas para que queden las dos cadenas iguales.

TEMA 11 : ALGORITMOS PROBABILISTICOS

Para problemas en los que no sabemos encontrar la solución o es muy difícil entonces probamos a utilizar esta técnica.

Tenemos una función que recibe un número/s como parámetro y genera un número al azar ( pseudoaltorio ) int uniforme ( int ) ;

Cuatro tipos :

Algoritmos NUMERICOS - usa la probabilidad , solución aproximada a base de probar.

MONTECARLO - no nos valen soluciones aproximadas , solo las exactos el algoritmo nos da respuestas que a veces son correcta , incorrectas o no sabemos.

Respuesta verdadera y falsas

LAS VEGAS - se diferencia de la de MONTECARLO en que las respuestas que dan son siempre verdaderas o no hay respuesta.

SHERWOOD - problemas en que sabemos que tienen una complejidad diferente en función de cómo entren los datos de entrada.

Pueden estar los datos ordenados en el caso mejor o peor.

Intercambio los datos de manera que quedan en el caso.

11.1. Numéricos

11.1.1. Area de un Círculo

El círculo esta en un cuadrado de lado 2r , genero puntos de forma aleatorio y miro los que están dentro del círculo.

Area del Círculo Número de Puntos dentro

Area Cuadrado Número de Puntos Totales

Número de Puntos Dentro

Area Círculo = * ( 2 r )² ( Area del cuadrado )

Número de Puntos Totales

Circulo ( n )

k ! 0

desde i ! 1 hasta n hacer

x ! uniforme ( -r , r )

y ! uniforme ( -r , r )

si ( x² + y² ) " r² entonces k ! k + 1

fin desde

devolver ( k * 4 r² ) / n

fin

n ! puntos que se generan

k ! puntos que caen dentro

Esto se puede aplicar a cualquier otra integral.

1 f ( x )

f ( x ) dx

0 1 se encierra la curva en un rectángulo ( altura > f ( x ) ) y se generan puntos aleatoriamente , se supone que será uniforme por todo el área ).

1 número puntos dentro

f ( x ) dx = * ( 1 * f ( x )max )

0 número puntos totales

Para calcular integrales

Integral 1 ( n )

k ! 0

desde i ! 1 hasta n hacer

x ! uniforme ( 0 , 1 )

y ! uniforme ( 0 , f ( x )max )

si y " f ( x ) entonces k ++

fin desde

devolver ( k * f ( x )max ) / n

fin

Otra interpretación de la integral es que esta es una suma de rectángulos muy pequeños

1 1

f ( x ) dx = lim f ( x ) * Ax

0 x! 0 x = 0

base del rectángulo muy pequeña , sus sumas son el área.

Integral 2 ( n )

suma ! 0

desde i ! 1 hasta n hacer

x ! uniforme ( 0 , 1 )

suma ! suma + f ( x )

fin desde

devolver 1 * ( suma / n )

fin

Hay un problema especial , contar elementos de un conjunto muy grande ( es muy lento ).

Contar ( C : conjunto )

k ! 0 ;

s ! 0 ;

a ! uniforme ( c ) ; / * parámetro un conjunto * /

repetir

k ! k + 1

s ! S " { a }

a ! uniforme ( c )

hasta que a " s / * elemento que ya pertenece a k * /

devolver 2 k² /

2 k² /

Complejidad O ( " n ) veces que se repite el bucle

Lineal O ( n )

30-3-98

11.2. Sheerwood

Algoritmo ( como una caja negra ) que realiza una función

f ( )

Es un algoritmo aceptable para el caso medio y muy malo para el caso peor , queremos que este caso no nos moleste al aparecer ( lo evitamos con un algoritmo ).

UNIFORME

y f ( y )

x u (x) f ( ) v (y) f (x)

Los datos se pasan antes por una función u ( ) que modifica los datos según un método aleatorio , luego deshacemos la modificación con otra función v ( y ).

Ej. : ordenar una lista , v ( y ) no hará nada ya que sale ordenada y solo hay una solución . u ( x ) cambiara el orden de los datos ( puede ocurrir que quede ordenada al revés ).

11.2.1. Listas Ordenadas por Punteros

Tenemos una lista de claves de siete elementos :

1 2 3 4 5 6 7

valor 2 3 13 1 5 21 8

Usamos un segundo array como punteros

Ptr 2 5 6 1 7 0 3 ! 0 fin , último elemento

El array puntero indica la posición en la cual esta

siguiente elemento ordenado.

cabeza [ ] ! donde esta el primer elemento de la lista ( 4 ).

valor [ ptr [ i ] ] ! pregunta donde esta el siguiente elemento.

Busca un elemento de la lista valor

buscar1 ( x : clave , i : índice ) : índice

Inicio

mientras x > valor [ i ] hacer

i ! ptr [ i ] ;

fin mientras

devolver i

fin

La primera llamada seria ( supongo que la cláusula esta en la lista ) :

buscar1 ( x , cabeza ) ;

Otra forma de realizar la búsqueda

buscar2 ( x : clave ) : entero ;

i ! cabeza

max ! val [ i ]

desde j ! 1 hasta raizCuad ( n ) hacer

y ! valor [ j ] / * primer elemento de la lista * /

si max < y " x entonces / * elemento es menor al límite * / Elemento más cerca

i ! j / * nuevo límite * / de la cabeza

max ! y / * nuevo límite * /

fin si

fin desde

devolver buscar ( x , i )

fin

Complejidad O ( " n ) ! el caso medio en bueno

Vamos a quitar los casos peores . En lugar de buscar desde la cabeza elige uno al azar desde 1 a n.

buscar3 ( x : clave )

Inicio

i ! aleatorio ( 1.. n )

y ! val [ i ]

si x < y entonces / * me he pasado * /

devolver buscar ( x , cabeza ) / * si , busco desde el principio * /

sino

si x > y entonces

devolver buscar1 ( x , ptr [ i ] ) / * no , busco ese elemento * /

fin si

fin

Elección al azar para disminuir la aparición del caso malo.

11.3. Las Vegas

Algoritmos que son poco eficientes o no sabemos resolverlos , cuando nos den la solución es correcta , lo probamos hasta que nos den la solución o nos cansemos.

Ej. : ocho reinas

Reinas ( V ( ) : booleano )

Inicio

col ! diag 45 ! diag 135 ! { 0 }

k ! 0 ;

repetir

nb ! 0

desde i ! 1 hasta 8 hacer

si ( i " col ) && ( 1-k " diag 45 ) && ( i + h " diag 135 ) entonces

nb ! nb + 1

si ( uniforme ( 1 , nb ) = = 1 ) entonces

j ! i

fin si

fin desde

si nb > 0 entonces

intento [ k + 1 ] ! j

col ! col " { j } / * ocupada la columna * /

diag 45 ! diag 45 " { j - k } / * ocupada la diag 45º * /

diag 135 ! diag 135 " { j + k } / * ocupada la diag 135 * /

k ! k + 1 / * siguiente reina * /

fin si

hasta ( nb = 0 ) || ( k == 8 )

return ( nb > 0 )

fin

Tres conjuntos :

- col - columnas ocupadas

- diag 45 - diagonal 45º ocupados

- diag 135 - diagonal 135º ocupados

k - reinas colocadas en el tablero
nb - número de posiciones libres en la fila considerado.
La posición i pertenece a una col ocupada y a una diagonal de 45 grados ( todos los elementos tienen el mismo valor la resta de la fila y de la columna ) , sino esta libre la casilla.

nb lo incremento en 1.

Coloco la reina , si el número uniforme ( entre 1 y el número de casillas libres ) responde uno entonces la reina j ! i y sigo buscando una casilla libre.

La primera reina se coloca en la primera fila ( entre 1 y 1 )

1 2 3 4 5 6 7 8

1 el azar elige si la segunda reina la coloco en

2 la columna 1 , 5 , 6 , 7 , 8 de la segunda fila

Dos bucles que como mucho se ejecutan 8 veces cada uno

8 * 8 = 64

11.4. Montecarlo

Son p correctos si hay una posibilidad p de que nos de la solución correcta , algunos son consistentes si da la misma entrad dan la misma solución correcta.

Ej. : encontrar el elemento mayoritario de un array , es el elemento que se repite en más de la mitad de las posiciones del array.

if { i " [ 1 .. n ] / T [ i ] = x } " n / 2

mayoritario ( T [ 1 .. n ] , x ) : booleano

k ! 0

desde j ! 1 hasta n hacer

si T [ j ] ! x entonces

k ++

fin si

fin desde

devolver ( k " n / 2 )

fin

Función que dado un array nos diga si un elemento es mayoritario

buscarM1 ( T [ 1 .. n ] ) : elemento

inicio

desde i ! 1 hasta n hacer

si mayoritario ( T , i ) entonces

devolver i

fin si

fin desde

fin

Si esta recorre la mitad del array , si no hay recorre todo el array

buscarM2 ( T [ 1 .. n ] ) : elemento

Inicio

x ! T [ uniforme ( 1 .. n ) ]

si mayoritario ( T , x ) entonces

devolver x

fin si

fin

50% de posibilidad de acertar , algoritmo 0,5 correcto.

buscarMC ( T [ 1 .. n ] )

devolver T [ uniforme ( 1 .. n ) ]

50% o 0,5 correcto , Tasa de error = 1 / 2

Mejorándolo

buscarMC2 ( T [ 1 .. n ] )

inicio

si no mayoritario ( T [ uniforme ( 1 .. n ) ] ) entonces

Devolver T [ uniforme ( 1 .. n ) ]

fin si

fin

Busco dos veces , 75% o 0.75 de que sea correcto , Tasa de Error = 1 / 4

Puedo fijar la tasa de error repitiendo x veces el algoritmo

E > 2 k - número de veces en repetir la búsqueda log2 ( 1 / E )

E - tasa de error

buscarMC3 ( T [ 1 .. n ] , E : real ) : elemento

inicio

k ! log2 ( 1 / E ) / * k - tasa de error * /

desde i ! 1 hasta k hacer / * lo hago hasta k * /

x ! T [ uniforme ( 1 .. n ) ]

si mayoritario ( T , x ) entonces

devolver x

fin si

fin desde

devolver x

fin

O ( n log2 ( 1 / E ) )

24 - 4 - 98

TEMA 13 : VERIFICACION FORMAL DE PROGRAMAS

Que la programación sea un técnica.

Cuando conseguimos hacer un programa vemos si la salida es lo que esperamos , Validación Externa , pero los programas pueden tener infinitas combinaciones de los datos.

Necesitamos un método mejor , sean cual sean los datos obtener la salida esperada Verificación Interna.

COMPILACION ! SINTAXIS , lo normal al terminar un programa

Nosotros necesitamos saber si el programa funciona como se espera , la SEMANTICA.

Construimos un lenguaje especial que nos indica como funciona el programa Especificación.

Especificación - como funciona el problema , descripción de la semántica o significado o como funciona el programa.

ESPECIFICACION DERIVACION VERIFICACION

FUNCIONAL AUTOMATICA FORMAL

ABSTRACTA DE PROGRAMAS

Dada un especificación se pueda construir un programa , que la construcción sea automática ( todavía no hay ninguna herramienta que lo realice todo ).

Verificación Formal - que el programa funcione ( proceso ).

13.1. Especificación

Hay muchos lenguajes especializados ( Ej. Lenguaje z , etc. ).

Una especificación debe tener las siguientes características :

Claridad - estar claro lo que la especificación pide.
Conciso - breve.
Precisión - sin ambigüedades.
Restrictivo - tiene que dejar fuera todas las implementaciones que no cumplan las especificaciones.
Generalidad - libertad para poder hacer el programa ( no se hace de una sola manera ).

ESPECIFICACION NORMAL

Sintaxis :

< NONMBRE > ................................

< DATOS > .......................................

< SALIDA > ......................................

< MODIFICACIONES > ..................

< CONDICIONES PREVIAS > ........

< EFECTO > .....................................

< EXCEPCIONES > .........................

Son etiquetas que preceden a una explicación

< NONMBRE > nombre

< DATOS > entrada

< SALIDA > salida

< MODIFICACIONES > datos de entrada modificados

< CONDICIONES PREVIAS > conjunto permitido de datos de entrada

< EFECTO > funcionamiento

< EXCEPCIONES > posibles condiciones y mensajes de error

Ej. : Programas que de la división entre dos números

< NONMBRE > División

< DATOS > a , b enteros

< SALIDA > c entero

< MODIFICACIONES >

< CONDICIONES PREVIAS > b " 0

< EFECTO > c = a / b

< EXCEPCIONES > / * sin condición previa , si b = 0 mensaje de error */

ESPECIFICACION FORMAL PRE-POST

Determinar el conjunto permitido de datos de entrada " PRE-CONDICION

Determinar el conjunto permitido de datos de salida " POST-CONDICION

Que lenguaje usamos Lógica de Primer Orden , para especificar la PRE y POST CONDICION.

LOGICA DE PRIMER ORDEN

Necesitamos saber :

TIPOS DE DATOS

Elementos básicos , conjunto de valores y operaciones que pueden hacerse con esos valores :

VALORES - abstracciones matemáticas ( 5 , no se lo que es un 5 si lo que representa ).
OBJETOS - donde están los datos , entidad que cambia en el espacio y tiempo y contiene valores . Tipos :

Constante.
Variables.

Un objeto es una posición de memoria.

OPERACIONES - función matemática sobre valores y objetos . Se identifican porque tiene :

Rango

Dominio

Las instrucciones son funciones matemáticas.

Nos basaremos en programación procedimental.

SINTAXIS

Conjunto de reglas del lenguaje , necesitamos :

ALFABETO DE SIMBOLOS

CONSTANTES - valores , 5 “ A “ “ cadena ”.
VARIABLES - objetos , x i.
FUNCIONES - operaciones aritméticas hasta los nombres para funciones.
DIFERENCIAS ENTRE FUNCIONES Y PREDICADOS

Predicado - operaciones que da un resultado booleano. ( = ).

TERMINOS - construidos a partir del alfabeto.

Constantes son términos.
Las variables son términos.
Si t1 , t2 ... tn son términos y f es una función de n argumentos.

f ( t1 , t2 ... tn ) es un término.

y + 3 * x

FORMULAS - construidas con términos

Se construyen utilizando los predicados n - arios.

Si t1 ... tn son términos y P predicado entonces P ( t1 , t2 ... tn ) es una fórmula atómica.

Símbolos lógicos , si y son fórmulas entonces ¬ , " , " , ! , ! .

Hasta aquí Lógica de Primer Orden , para la Lógica de orden 1

Si x es una variable y es una fórmula entonces " x y " x son fórmulas ( cuantificadores ).

SEMANTICA

A partir del concepto de estado :

ESTADO - función que asocia a cada variable un valor del tipo a que pertenece.

En un punto del programa vemos el estado de todas las variables.

x ! x + 1 necesito saber el estado de una variable mediante una función

que ocurre con la variable x y como funciona x = x + 1.

s ( variable ) = valor actual de la variable

s - función

s ( x ) " 5

s ( x ) " s ( y ) " s ( z ) " s ( x ) + s ( y ) / * verdad si se cumple * /

"x s ( x ) " s ( y ) + s ( z )

s ( z ) > s ( x ) + 7 ! s ( y ) + 5

"{ x / s ( x ) > 5 } / * lo que significa la fórmula * / ASERCION = CONJUNTO DE

ESTADOS DE UNA VARIABLE

PRECONDICION - conjunto de valores de las variables a la entrada.

PROGRAMA

POSTCONDICION - conjunto de valores de las variables a la salida

Es más corto de escribir

PRE POST

" { s ( a ) " 0 " s ( b ) > 0 }

= { s ( c ) = s ( a ) / s ( b ) }

Sirve para cada instrucción de un programa y nos indica que hace esa instrucción.

1 ! la Postcondición de la primera instrucción es la Precondición de la segunda

Ej. : No sabemos que hace el programa dado a continuación , tenemos que mirar las variables y sus estados para ver lo que hacen

s ( a ) = 7 s ( b ) = 8

Inicio s ( x ) = 0 s ( y ) = 0

x ! a s ( x ) = 7

y ! b s ( x ) = 7 " s ( y ) = 8

mientras y > 0 hacer

x ! x + 1

y ! y - 1

fin mientras

fin

Si quiero ver el programa para todos los valores de x e y positivos

{ s ( a ) > 0 " s ( b ) > 0 } PRECONDICION

{ s ( x ) = s ( a ) " s ( y ) = s ( b ) }

En una iteración del bucle { s ( x ) + s ( y ) = s ( a ) + s ( b ) }

Finalizado el bucle { s (x ) = s ( a ) + s ( b ) " s ( y ) = 0 } POSTCONDICION

Son fórmulas que expresan el conjunto de estados ( valores de las variables ) , visión interna del programa , no lo hace la máquina . No hemos tomado valores concretos.

El problema se basa en la fórmula de Aserción , fórmula de lógica de primer orden que describe el conjunto de los estados posibles de las variables de un programa en un instante del mismo.

S ( x ) = 7

{ x = 7 } / * Aserción que describe un estado * /

x ! 7 / * instrucción que realiza algo sobre x * /

27-4-98

Forma Normal de HOARE

Inicio { a > 0 " b > o }

x ! a

y ! b { x = a " y = b }

mientras y > 0 hacer

x ! x + 1

y ! y + 1 { x + y = a + b }

fin mientras { x = a + b " y = 0 }

fin

Todas las fórmulas se meten entre llaves , son conjuntos de valores le puedo dar nombre a estas fórmulas.

= { x = a " y = b }

x = fórmula que resulta de sustituir donde pone x poner t

= { "x ( x > 7 + y " z = x + 3 }

x = { "t ( t > 7 + y " z = t + 3 }

Puede ocurrir colisiones de variables al cambiarla

x = { "x+1 ( x + 1 > 7 + y " z = x + 1 + 3 } No es igual a los anteriores

Dos fórmulas que describen el mismo conjunto se llaman equivalentes la una y la dos son equivalentes pero no la tercera.

{ x = 4 " y = 16 } fuerte

{ x² = y } débil

No son equivalentes , pero la primera describe un solo estado que esta incluido en el conjunto de estados de la segunda , el primero es Fuerte y el segundo Débil.

Fórmula :

Más Fuerte - cuanto menor es el número de estados que permite . Impone más restricciones.
Débil - conjunto de estados más grande.

Buscamos un sistema que deduzca lo que haga el problema , automatizar.

aserción precondición

instrucción = instrucción

aserción postcondición

Tengo que construirlo como un axioma

{ x > 0 }

x ! 7 ; Axioma , se como funciona la instrucción y que esta bien

{ x = 7 }

Axiomas

{ x } x ! t ; { } x - variable

Pre Post t - término

{ x > 0 } ; x ! 7 ; { x = 7 }

postcondición

{ x = x } para que cumpla el axioma y que sea verdadera la fórmula más débil.

x t

Ej. : { x + y = 10 } x ! x + y { x = 10 } AA ! es verdad coincide con el axioma de

x la condición

x + y = 10

{ true } x ! y ; { x = y }

true - forma más débil de todas , caven todos los estados.

x y = y AA

x t

{ " j ( i = 2 ) z - i ; { " j [ z = 2 ] } AA

potencia derecha

x = Pz = { " j ; [ i = 2 ] )

x t

Ej. : { true } x ! x + y { x = x + y }

x = x + y ! x + y + y { x + y = x + y }/ * No es una aserción es el efecto de una

{ 0 = y } es verdad instrucción * /

13.2. Métodos de Deducción

Indican si el programa es correcto o no

Regla de la Composición Secuencial ( RCP )

{ } I1 { 1 } , { 1 } I2 { 2 }

{ } inicio I1 , I2 fin { }

{ } I1 { 1 } , { 1 } , I2 { 2 } ... { n-1 } In { }

{ } Inicio I1 ; I2 ; ... In { }

Para poder deducir varias instrucciones encima de la raya son premisas y después de la raya esta la conclusión.

Si se cumplen las premisas se cumplen la condición

Premisas

Conclusión

Si todas se cumplen la precondición del bloque es la de la primera y la postcondición es la de la última instrucción.

Ej. : Es correcto el siguiente programa

Un programa es correcto Parcialmente si cumpliéndose la precondición y ejecutándose el programa se cumple la postcondición.

Un programa es totalmente Correcto si además de ser parcialmente correcto todos sus bucles terminan.

Ej. : Es parcialmente el siguiente programa

{ x = a " y = b }

Inicio

aux ! x

x ! y

y ! aux

fin

{ x = a " y = b }

Al ser secuencial no indica usar la regla RCP.

Numero los pasos

{ x = a " y = b } aux ! x ; { x = a " y = b } AA

aux = x = a ; y = b

es verdad por el Axioma de Asignación

{ a " x = a " y = b } y ! x ; { aux = a " x = b } AA Si una postcondición no la usas

y = b la pones

x = { aux = a " y = b }

{ aux = a " x = b } y ! aux { x = a " y = b } AA

y = { aux = a " x = b }

Cogiendo las 3

1 , 2 , 3

{ x = a " x = b } inicio ... fin { x = a " x = b } , es verdad porque usando como premisas 1 , 2 , 3 y usando la RCP lo demuestran.

2. Regla de la Consecuencia ( RCN )

! 1 , { 1 } I { 1 } , 1 !

{ } I { }

A veces no coincide la precondición y la postcondición.

Si puedo demostrar con una instrucción / es puedo encontrar una precondición y una postcondición entonces son las nuevas y

Ej. : { x > y } x ! x - y ; { x " 0 }

x - y

x = { x - y " 0 }

( x " y ) ! ( x - y " 0 ) / * esto es verdad * /

! 1

{ x - y " 0 } x ! x - y ; { x " 0 } ! coincide con la que necesito

Ej. : { 1 " i < n } i ! i + 1 { 1 " i " n }

i " { 1 " i+1 " n } no es igual símbolo a símbolo a la precondición

{ 1 " i < n } ! { 1 " i " n } / * ! 1 primera parte RCN * /

n = 4

i = 3

transformación de la pre y postcondición.

3. Regla de la Condición ( RCD )

Interpretar los bloques si - entonces y si - sino { }

{ " B } I1 { } , { " ¬ B } I2 { } si no

{ } si B entonces I1 sino I2 fin si { } B

I1 I2

{ }

{ " B } I , { } ; " ¬ B ! / * esta ya cumple la precondición * /

{ } si B entonces I1 finsi { }

si no

( precondición ) y ( postcondición ) deben ser igual para las dos ramas.

Ej. : Demostrar que le programa es parcialmente correcto

{ true }

si x " y entonces

z ! x - y

sino

z ! y - x

fin si

{ z = ø x - y ø }

Lo más externo es un si , regla RCP

( x " y ) ! ( x - y " 0 ) / * lo transformo porque no saldría * / " B z ! x - y

{ x " y " 0 } z ! x - y { x - y " 0 " z = x - y }

z = x - y " 0 " x - y = x - y en la postcondición

true se puede quitar

{ x - y " 0 " z = x - y } ! ( z = | x - y | )

{ x " y } z ! x - y ( z = | x - y | ) 1 , 2 , 3 RCN

1,2,3 RCN

Con la otra rama

" ¬ B I2

x < y z = ( x - y )

( x < y ) ! { y - x " 0 }

{ y - x " 0 } z ! y - x { y - x " 0 " z = y - x } AA

z y - x " 0 " y - x = y - x

true

( y - x " 0 " z = y - x ) ! ( z = | x - y | )

{ x " y } z ! y - x ; { z = | x - y | } 5 , 6 , 7 RCN

¬ ( x " y )

5,6,7 RCN

{ true } si ... fin si { z = | x - y | } 4 , 8 RCD

1,2,3 5,6,7

4 8

Ej. : Demostrar que le siguiente programa es correcto

{ x = a " y = b }

si x < y mientras

inicio

aux ! x

y ! x max - mayor dos números ( x ! mayor , y ! menor )

y ! aux min

fin

fin si

{ x = max ( a , b ) " y = min ( a , b ) }

4-5-98

4. Regla del Bucle Mientras RWH

! INV , { INV " B } I { INV } , INV " ¬B !

{ } mientras B hacer I fin mientras { }

INV

INV -

" B + INV " ¬B

INV

INV - invariante , aserción que se cumple al final de cada iteración de un bucle , describe el efecto bucle.

Antes de empezar el bucle se cumple la precondición , al pasar la condición del bucle se cumple la precondición y el bucle " B o INV " B ( precondición de las instrucciones ).

INV se deduce de la precondición ( considera también las variables al inicio del bucle ). El invariante se construye mirando la postcondición y quitando la condición del bucle.

Ej. : Corrección parcial de

inicio { true }

i ! 1

m ! A [ 1 ]

mientras i " n hacer

i ! i + 1

si m < A [ i ] entonces m ! A [ i ]

fin mientras

fin { " j ( 1 " j " n ! m " A [ j ] " " j ( 1 " j " n ! m = A [ j ] ) }

{ true } i ! 1 { i = 1 } AA

{ i = 1 } m ! A [ 1 ] { i = 1 " m = A [ 1 ] } AA

INV " { " j ( 1 " j " i ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ j ] ) "

1 " i " n }

{ i = 1 " m = A [ 1 ] }! ( " j ( 1 " j " i ! m " A [ j ] ) " ! INV

" j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n )

{ INV " i " n } ! ( " j ( 1 " j " i ! m " A [ j ] ) " / * precondición 1ª

" j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n ) / * sentencia bucle * /

i ! i + 1

( " j ( 1 " j " i ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n ) "

" j ( 1 " j " i + 1 ! m = A [ j ] " 1 " i + 1 " n )

{ " j ( 1 " j " i ! m " A [ j ] ) " " j ( 1 " j " i + 1! m " A [ j ] }

i ! i +1 { " j ( 1 " j " i - 1! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n } AA

i + 1 - 1 = i

Si m " A [ i ]

" j ( 1 " j " i - 1 ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ i ] ) " 1 " i " n "

m " A [ j ] ! ( " j ( 1 " j " i ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ i ] ) "

1 " i " n )

{ " j ( 1 " j " i ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ i ] ) " 1 " i " n }

m ! A [ i ]

INV [{" j ( 1 " j " i ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n }] AA

El otro lado del si ( no se cumple ).

( " j ( 1 " j " i - 1 ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n "

m " A [ 1 ] )

! INV

Interior del bucle 5 INV " i " n

...

8 7 INV

{ " j ( 1 " j " i - 1 ! m " A [ j ] ) " " j ( 1 " j " i ! m = A [ j ] ) " 1 " i " n }

Si m < A [ i ] entonces m ! A [ i ] 7 , 8 , 9

{ INV } 7 , 8 , 9 RCD 10 RCD

Resumen desde el quinto paso

{ INV " i " n }

inicio i ! i +1 ... fin mientras

{ INV } 5 , 6 , 10 RCP , RC ( Regla de Composición )

11 - salida del bucle.

( INV " i " n ) ! " j ( 1 " j " n ! m " A [ j ] )

" j ( 1 " j " n ! m = A [ j ] )

/ * Podría meter 1 " i " n pero ya da * /

4 , 11 , 12

RWH

{ i = 1 " m = A [ 1 ] }

mientras ... fin mientras

{ } A , 11 , 12 RWH

{ true } inicio .. fin { } 1 , 2 , 13 RCP

5. Regla del Bucle Repetir

{ } I { INV } , { INV " ¬B } I { INV } , INV " B ! 0

{ } repetir I hasta B { }

INV " ¬B

INV

- +

INV " ¬B INV " B

Ej. : Es correcto parcialmente

{ n " 1 }

inicio

S ! 0 ;

x ! 0 ;

repetir / * La primera vez , el resto INV " ¬B * /

x ! x + 1

S ! S + x²

hasta que x = n

fin

{ s = i² }

i = 1

{ n " 1 } S ! 0 { n " 1 " S = 0 } AA

{ n " 1 " S = 0 } x ! 0 { n " 1 " S = 0 " x = 0 } AA

( n " 1 " S = 0 " x = 0 ) ! (n " 1 " S = i² " x + 1 " n ) / * precondición 1º I * /

i = 1

{ S = i² " x + 1 " n } x ! x + 1

i = 1

{ S = i² " x " n }

i = 1

x - 1 x -1

{ S = i² " x " n } ! ( S + x² = i² + x² " x " n )

i = 1 ! i = 1 ! / * x² a ambos lados de la ecuación * /

x x

{ S + x² = i² + x² " x " n } S ! S + x² { S = i² " x " n }

i = 1 i = 1

{ n " 1 " S = 0 " x = 0 } x ! x + 1 ; S ! S + x² { INV } 3 , 4 , 5 , 6 RCP RCD

INV " ( x " n ) ! ( S + ( x + 1 )² = i² + ( x + 1 )² " x + 1 " n ) INV " ¬B

! i = 1 !

INV x " n x + 1 podría ser igual

x < n

x " n

x+1

{ S + ( x + 1 )² = i² " x + 1 " n } x ! x + 1

i = 1

{ S + x² = i² " x " n } AA

i = 1

x x

{ S + x² = i² " x " n } S ! S + x² { S = i² " x " n } AA

i = 1 i = 1

{ INV " ( x " n ) } x ! x + 1 ; S ! S + x² { INV } 8 , 9 , 10 RCP RCD

Segunda premisa de salida

{ INV " ( x = n ) } ! { S = i² }

i = 1

{ n " 1 " S = 0 " x = 0 } repetir hasta x = n { S = i² } 7 , 11 , 12 RPT

i = 1

{ n " 1 } inicio ... fin { S = i² } 1 , 2 RCP

i = 1

Ej. : Es correcto

{ n " 1 }

inicio

S ! 0 ;

x ! 0 ;

mientras x < n

x ! x + 1

S ! S + x²

fin mientras

fin

{ s = i² }

i = 1

11-5-98

13.3. El Problema de la Terminación

{ true } { true }

Inicio Inicio

r ! 0 r ! 0

z ! x z ! x

mientras z " y hacer mientras z < y hacer

z ! z + 1 z ! z + 1

r ! r + 1 r ! r + 1

fin mientras fin

fin { r = y - x } { r = y - x }

Los dos programas cumplen la misma postcondición y no tienen precondición.

Vemos si los programas terminan.

Hay valores de y que no hacen terminar el programa , si termina no cumple la postcondición.

Para valores de y no termina , no cumple la postcondición si los hace.

Para que un bucle termine se tiene que cumplir :

Que el bucle modifique las variables de terminación del bucle.

Que los cambios no sean infinito , que cambie la condición.

Bucle de carácter general

mientras B hacer

fin mientras

I tiene que modificar algo de B en un número finito de veces.

Para que un bucle termine :

ORDEN BIEN FUNDADO - consta de un conjunto S y una relación binaria " ( un símbolo ) tales que :

La relación es un orden parcial en S , orden parcial es reflexivo , antisimétrico y transitivo.

Reflexivo - x "S x " x

Antisimétrico - x " y " y " x

Transitivo - x " y y " z ! x " z

No hay cadenas descendentes infinitas

serie

" < xi " S / i " N >

x0 > x1 > x2 > ... > xn > ...

x > y ! y " x " y " x hay un elemento mínimo del conjunto , no es infinito.

( N , " )

relación de orden 15 , 9 , 7 , 6 ...... 0 acaba sola si no la paro yo

orden bien fundada

( Z , " )

15 , 9 , 7 , 6 , 3 , -1 , -4 , ... No es un orden bien formado , cadena infinita

Ej. : Ordenes bien fundadas

( N² , << )

( x , y ) << ( u , v )

( x < u ) " ( x = u " y < v ) orden parcial y también orden bien fundado , elemento

mínimo posible ( 0 , 0 ).

( p ( c ) , " - estar incluido o coincide

p - conjunto de los subconjuntos de C ( que es finito ).

Luego tendré finitos subconjuntos , en cada uno esta incluido en el anterior.

Si tengo un bucle y quiero saber si termina

mientras B hacer

fin

modifica a B en un número finito de pasos , buscamos una expresión que nos de una serie con elementos que este bien fundado , que pertenezca a un orden bien fundado.

e expresión tal que INV " B ! e " S

cada vez que se ejecuta el bucle { INV " B " e = v } I { e " v " INV }

Ej. : Inicio

x ! a INV = { x + y = a + b " y " 0 }

y ! b

mientras y > 0 hacer

x ! x + 1

y ! y - 1

fin mientras

fin

( N , " ) y - decrece siempre

e " y

{ INV , y > 0 " y = v } + { y < v } ! orden bien fundada , termina con lo cual el bucle también termina.

{ INV " y > 0 " y = v } y ! y - 1 { y + 1 = v " INV }

y = y - 1 + 1 y - 1 + 1

y + 1 = v ! y = v - 1 - y < v

En cada iteración y disminuye , cadena finita . La expresión " N.

Ej. : programa que manipula una matriz

var A : array [ 1..n , 1..n]

inicio { n " 1 " m " 1 }

x ! 1 ;

j ! 1 ;

mientras i " n hacer

tratar A [ i , j ]

si j < m entonces

j = j + 1 ;

i ! i + 1 ! j - 1

sino

i ! i + 1

fin si

fin mientras

fin { P ( A , n + 1 , m ) }

Instrucción que diga cuantos elementos de la matriz quedan

e : ( n - i , m - j ) número de filas f ( N ²² , << )

Cuando se ejecuta el bucle la expresión disminuye.

{ INV " i " n " ( n - i ) n - 1 ) " ( u , v ) B

Algoritmia 93 METODOLOGIA

______________________________________________________________________

cadena a buscar

cadena a sustituir

estado al que ir

2º estado a ir

Cambiar la cadena “ab“ por 0

S = bbb

Estado final = bbb ( las cambio por a )

E = aaabbbbb | 3 - 5 |

0 ab 0 1

1 ab 0 1 2

2 b a 2 3

3 0 0 3

j j j aj bj

A - Alfabeto

M - Movimientos

Q - Estados

C - Cinta

i =1

t ( n ) = Pi ( n ) ti ( n )

n ! "

g ( n )

f ( n )

Si existe lim = l , entonces se pueden dar tres casos :

g " f y f " g

= "

100 n + 500

2n² + n

= lim

n ! "

g ( n )

f ( n )

lim

1 / n

n ! "

f " g y g " f

= lim

n ! "

lim

i =1

n-1

b + ( a + 2b + b + ( n - i ) * ( 2a + 4b ) )

i =1

n-1

( n - 1 ) ( 2a + 4b ) +

( n - 2) ( 2a + 4b )

( n - 3 ) ( 2a + 4b ) +

226

150

1000 9,97 seg 1msg 9,96 mseg 1 seg 16,6 min 1,1 * 10 años ........

100 6,64 seg 100 seg 664,4 seg 10 mseg 1seg 4,02 *10²² años >10 años

tiempo ( en seg )

10 3,32 seg 10 seg 33,2 seg 100 seg 1 msg 1,024seg 3,63 seg

n log2 n n n log2 n n² n³ 2 n !

n = 2 ! log2 n = k

Hay que hallar k para saber

la complejidad.

Hasta que nos quede

un elemento.

¿ Hasta cuando ?

...

n / 8

n / 4

= 1

n / 2

fin

inicio

Array que se

devuelve.

Mezcla

División

...

n / 2

n = 2

n / 2 =1

T (n) = 2 T ( n / 2 ) + i * n

T (n / b³) = a T (n / b ) + d (n / b³) = a T (n / b ) + a³ d (n / b³) + a² d (n /b²) +

+ a d (n/b) + d (n)

i=0

a T (n / b ) + a d ( n / b )

i+1

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

i =0

k - 1

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

logb n = k

n = b

n / b = 1

i =0

k - 1

logb n

T (n ) = a T ( 1 ) + a d ( n / b )

logb a

logb n

T (n ) = a = n = O ( n )

logb a

Si d (n ) > n n = n

tn = x

n-k

n-2

n-1

a0 x + a1 x + a2 x + ... + ak x = 0 Es un polinomio

n-k

k-2

k-1

( a0 x + a1 x + a2 x + ... + ak ) x = 0

k-2

k-1

a0 x + a1 x + a2 x + ... + ak = 0

T (n) = C1 r1 + C2 r2 + ... + Ck rk Solución

i = 1

tn = ci ri = T (n)

tn = ri

tn = x

n - 2

n - 1

x = tn

x - 3x - 4 = 0

x = 0

n - 2

( x - r1 ) (x - r2 ) ( x - rn-m ) = 0

-2 / 2 = -1

8 / 2 = 4

3 ± 5

3 ± " 25

x =

3 ± " 9 + 16

T (n) = 1/5 4 - 1/5 ( -1 ) = O ( 4 )

T (n) = C1 4 + C2 ( -1 ) = O ( 4 )

x = C1 r1 + C2 r2

n - 2

n - 1

x - x - x = 0

x = 0

n - 2

( x² - x - 1 ) x = 0

= 2

= 1

1- " 5

1+ " 5

r2 =

r1 =

1± " 5

1± " 1 + 4

ri =

T (n) = C1 1 + C2 2 = O ( 1 )

m - 1

T (n) = C1 r1 + C2 n r1 + C3 n² r1 + ... + Cm n r2 + ... + Ck rk-m

T (n) = C1 2 + C2 n 2 + C3 1 = O ( n 2 )

n +1

T (n) = C1 2 + C2 3

T (n) = 2 T ( n-1 ) + ( n+5 ) 3

n +2

n +1

n +2

n +1

- 6 ( n + 6 ) 3 = -2 ( n + 6 ) 3

n +2

2 ( n + 6 ) 3

n +2

( n+7 ) 3

n +2

( n+5 ) 3

T (n) = C1 T ( n-1 ) + C1 T ( n-1 ) + ... + Ck T ( n-k ) + P (n ) b d = grado de p

a0 tn + a1 tn-1 + a2 tn-2 + ... + ak t n-k = P (n ) b

d+1

k-1

( a x + a1 x + ... + ak ) ( x - b ) = 0

n - 1

d1 + 1

d2 + 1

d m + 1

n + 1

2k-1

k-2

logb

loga

log2 3

logb

loga

log2 3

log2 n

1 + j

j =1

n-1

n / 2

log2 3

1'98

Hemos reducido la complejidad

n-2

log2 3

REC

...

n/4

n/2

2 ( n/2 )³

A11 x B11 +

+ A12 x B21

B12

B22

B21

B11

A22

A21

n/2 x n/2

A12

A11

M1 + M2 + M4 + M5

M1 + M2 + M5 + M6

M1 + M2 + M3 - M7

M2 + M3

2,81

-k

x +1

x + y

aux

i+1

x - y

y - x

y - 1

Tal vez te pueda interesar:

Descargar

Enviado por:	Maria Luisa Moral
Idioma:	castellano
País:	España

Palabras clave:

Informática Análisis Iteración Recursivos Diseño Programación dinámica Programas: verificación

Te va a interesar