Matematica Estructural

Daniel Felipe Duarte Sánchez David Tavera Sánchez Diseño y análisis de algoritmos Tarea 2 1 [Ctx C : a; b : nat ^ b 0 {Q: true } ... {Inv P: y 0 ^ z xy = ab } {cota t: y } do . . . od {R: z = ab } ]cod 201012670 cod 201016123

1a) Para hallar el invariante pudo haberse utilizado la técnica sintáctica de cambio de constante por una variable, ya que en el invariante se usan variables x y yque representan el valor de la exponencial y eventualmente, por la cota, se convertirán en la exponencial que realmente quiero calcular. 1b) Para resolver el algoritmo en tiempo logarítmico es necesarioesblecer una recurrencia. Así llamanos a este programa exp(a,b): [ Ctx C : a,b : nat ^ b 0 {Q: true} z; x; y := 1; a; b {Inv P : y 0 ^ z xy = ab } {cota t: y} do y > 1 ! if y mod 2 =0 thenz,x,y:=exp(x,b 2);x,y=b/2; else z,x,y:=x*exp(x,b 2),x,y=b/2; … y=1! z = a y=0! z = 1 od {R: z = ab } 1c) El algoritmo en tiempo es O(log b) porque la cota disminuye en cada iteracion a la mitad

2. a)Explicación de la precondición, postcondición y Contexto [Ctx C: b:[0...n-1] of Carácteres ] b) Se usa la técnica de balanceo de información 1

fInv P : C : ^0 6 i 6 ng fCot t : n ig c) Desarrollo delalgorito correspodiente [Ctx C: b:[0...n-1]:Carácteres m; i := 0; 0; c := " "; do n 6= i ! if b[i] 6= " " then c[m]; m := b[i]; m + 1 else if m > 0^b[i 1] 6= " "then c[m]; m := 0 =0 ; m+1 else skip f i;i := i + 1 ] d) La Complejidad temporal es : T(n) = (n). Debido el ciclo se hace preguntando por cada posición del arreglo ’ , y asignando un valor a las posiciones b’ del arreglo ’ c’de acuerdo aello. e) La complejidad espacial es: S(n) = (n): Debido a que se crea un vector solución de igual tamaño a ’ b’y dos variables que de…nen la cota y la invariante. 3 a) mm(i,x) : mínimo número de monedasde denominaciones a1,a2,...,ai para expresar la cantidad x, para 0 i n. Entonces dicho lenguaje expresaría la solución del problema como: mm(n,C). b)De…nición8 la recurrencia correspondiente: de 9 x...