Metodología: Algoritmia

Informática. Análisis. Iteración. Recursivos. Diseño. Programación dinámica. Programas: verificación

  • Enviado por: Maria Luisa Moral
  • Idioma: castellano
  • País: España España
  • 116 páginas
publicidad

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

    -5 ! ! C " 1

    12

    -5 ! ! C " 2

    7

    -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

    n

    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

    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

    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 :

    Si

    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

  • m

    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

    1

    2

    3

    4

    5

    6

    7

    8

    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 =

    n

    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

    2

    1 6

    3 El árbol no es único

    4 7

    5

    7

    6

    2

    4

    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

    2

    1

    3

    4 6 7

    5

    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

    5

    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.

    1

    10 50

    30

    5 100 2

    20

    10 5

    4 3

    50

    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

    1

    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

    k

    0 1 2 3

    0 1

    r

    / * 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 :

    6

    3

    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

    0

    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

    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

    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

    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

    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.

    9

    6 A

    3 A 6

    A 3

    17

    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.

    7

    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

    8

    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.

    15

    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

    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 si

    fin desde

    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

    15

    1 3

    30 Tenemos un grafo dirigidos , caminamos

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

    5 malidad )

    2 4

    15

    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

    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

    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

    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

    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

    fin desde

    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

    A

    B

    C

    D

    E

    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

    6

    D DE

    4

    E EF

    12

    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

    12

    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

    12

    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

    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

    fin desde

    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.

    K

    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

    n

    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

    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

    A

    B

    C

    D

    E

    F

    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

    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

    k

    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 ) }

    D1

    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 ) }

    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 ) }

    D1

    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

    D1

    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

    g3 ( x3 ) = max { (R3 (x3 , D3 ) + g2 ( x3 - D3 ) }

    D2

    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

    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 ) }

    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 ) }

    D1

    g3 ( x3 ) = MIN { R3 ( x3 , D3 ) * g2 (x3 - D3 ) }

    23-3-98

    D1

    x1

    0 1 2 Decisión Ganancia Etapa

    0

    1

    2

    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

    C1

    C2

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

     P 

    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

    I1

    1 ! la Postcondición de la primera instrucción es la Precondición de la segunda

    I2

    2

    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 {  }

    B

    si no

    I1

     ( 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

    4

    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

    8

  • { true } si ... fin si { z = | x - y | } 4 , 8 RCD

  • 1,2,3 5,6,7

    4 8

    9

    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

     " B + INV " ¬B

    I

    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

    I

    INV

    - +

    B

    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

    n

    { 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

  • x

  • ( n " 1 " S = 0 " x = 0 ) ! (n " 1 " S =  i² " x + 1 " n ) / * precondición 1º I * /

  • i = 1

    x

  • { S =  i² " x + 1 " n } x ! x + 1

  • i = 1

    x

    { 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

  • x

  • 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

    x

    { 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

  • n

    { INV " ( x = n ) } ! { S =  i² } 

    i = 1

    n

  • { n " 1 " S = 0 " x = 0 } repetir hasta x = n { S =  i² } 7 , 11 , 12 RPT

  • i = 1

    n

  • { 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

    n

    { 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

    I

    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

    I

    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

    T

    A - Alfabeto

    M - Movimientos

    Q - Estados

    C - Cinta

    i =1

    k

    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

    1 / n

    n ! "

    f " g y g " f

    = lim

    n ! "

    n

    Ln

    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

    n log2 n n n log2 n n² n³ 2 n !

    k

    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

    k

    2

    n

    n / 2

    fin

    n

    inicio

    Array que se

    devuelve.

    Mezcla

    División

    ...

    ...

    L2

    n / 2

    L1

    n / 2

    n

    i

    n = 2

    i

    n / 2 =1

    i

    i

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

    4

    4

    4

    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

    3

    i

    i

    4

    4

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

    i

    i+1

    i

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

    i =0

    k - 1

    k

    k

    i

    i

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

    k

    k

    logb n = k

    n = b

    n / b = 1

    i =0

    k - 1

    logb n

    i

    i

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

    logb a

    logb a

    logb n

    T (n ) = a = n = O ( n )

    logb a

    logb a

    t

    Si d (n ) > n n = n

    n

    tn = x

    n-k

    n-2

    n-1

    n

    a0 x + a1 x + a2 x + ... + ak x = 0 Es un polinomio

    n-k

    k-2

    k-1

    k

    ( a0 x + a1 x + a2 x + ... + ak ) x = 0

    k-2

    k-1

    k

    a0 x + a1 x + a2 x + ... + ak = 0

    n

    n

    n

    T (n) = C1 r1 + C2 r2 + ... + Ck rk Solución

    i = 1

    k

    n

    tn =  ci ri = T (n)

    n

    tn = ri

    n

    tn = x

    n

    n - 2

    n - 1

    n

    x = tn

    x - 3x - 4 = 0

    x = 0

    n - 2

    h

    ( x - r1 ) (x - r2 ) ( x - rn-m ) = 0

    -2 / 2 = -1

    8 / 2 = 4

    2

    3 ± 5

    =

    2

    3 ± " 25

    =

    2

    x =

    3 ± " 9 + 16

    n

    n

    n

    T (n) = 1/5 4 - 1/5 ( -1 ) = O ( 4 )

    n

    n

    n

    T (n) = C1 4 + C2 ( -1 ) = O ( 4 )

    n

    n

    n

    x = C1 r1 + C2 r2

    n - 2

    n - 1

    n

    x - x - x = 0

    x = 0

    n - 2

    n - 2

    ( x² - x - 1 ) x = 0

    = 2

    = 1

    2

    1- " 5

    2

    1+ " 5

    r2 =

    r1 =

    2

    1± " 5

    =

    2

    1± " 1 + 4

    ri =

    n

    n

    n

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

    n

    n

    m - 1

    n

    n

    n

    T (n) = C1 r1 + C2 n r1 + C3 n² r1 + ... + Cm n r2 + ... + Ck rk-m

    n

    n

    n

    n

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

    n

    3

    n

    3

    n

    3

    n

    3

    n +1

    3

    n +1

    n

    n

    T (n) = C1 2 + C2 3

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

    n

    3

    n

    3

    n +2

    n +2

    3

    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

    n

    n

    T (n) = C1 T ( n-1 ) + C1 T ( n-1 ) + ... + Ck T ( n-k ) + P (n ) b d = grado de p

    n

    a0 tn + a1 tn-1 + a2 tn-2 + ... + ak t n-k = P (n ) b

    d+1

    k-1

    k

    ( a x + a1 x + ... + ak ) ( x - b ) = 0

    n

    n

    1

    n

    1

    n

    1

    n

    2

    n

    2

    n

    2

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n

    n - 1

    d1 + 1

    d2 + 1

    d m + 1

    n

    n

    n

    n

    n

    n

    n

    n + 1

    n

    n

    k

    k

    k

    2k-1

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k-2

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    k

    logb

    loga

    log2 3

    log2 3

    k

    logb

    loga

    log2 3

    log2 n

    n

    1 + j

    j =1

    C

    B

    A

    n-1

    4

    1

    1

    1

    1

    1

    1

    2

    2

    2

    2

    2

    3

    1

    3

    4

    B

    A

    C

    A

    B

    C

    A

    B

    C

    n / 2

    n / 2

    n / 2

    n

    n

    n / 2

    log2 3

    1'98

    Hemos reducido la complejidad

    n-2

    n-2

    n-2

    n

    log2 3

    n

    REC

    ...

    n/4

    n/4

    n/4

    n/2

    n/2

    n/2

    n

    k

    k

    2 ( n/2 )³

    2 ( n/2 )³

    2 ( n/2 )³

    2 ( n/2 )³

    A11 x B11 +

    + A12 x B21

    =

    B12

    B22

    B21

    B11

    X

    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

    4

    6

    6

    4

    2

    3

    4

    5

    4

    5

    3

    2

    7

    6

    5

    3

    4

    1

    2

    7

    6

    5

    3

    4

    1

    2

    j

    6

    4

    4

    1

    3

    4

    2

    3

    5

    2

    4

    2

    7

    6

    5

    3

    4

    1

    2

    2

    4

    3

    1

    2

    2

    B

    5

    6

    4

    7

    3

    2

    1

    n

    -k

    t

    t

    x +1

    t

    x + y

    t

    i

    j

    t

    i

    i

    t

    x

    y

    aux

    i+1

    x - y

    y - x

    f

    f

    y - 1