Ingeniería de Sistemas y Computación

ISIS1105 – Diseño y análisis de algoritmos

Sección 1. Profesor: Jorge Duitama
Semestre: 2021-20

Solución Examen 1

Este examen es individual. Tiene una duración de 1 hora 20 min. Está prohibido usar el
libro, apuntes, impresiones y cualquier tipo de dispositivo electrónico (celulares,
agendas electrónicas, cámaras digitales, etc.).

Nombre:_________________________________________________ Código: _____________________

1. Verificar la corrección del siguiente programa que calcula las diferencias al cuadrado
entre dos arreglos

var p,r:array [0,n) of real

var i: nat
var e: real
{0 ≤ n}
s,i:=0,0
{i ≤ n Λ s=(∑ k| 0 ≤ k < i : (r[k] - p[k])2)}
do i < n →
e:= p[i] - r[i];
s,i := s + e*e, i+1
od
{s=(∑ k| 0 ≤ k < n : (r[k] - p[k])2)}

Para todos los puntos se define la función

S(p,r,x)=(∑ k| 0≤k<x : (r[k]-p[k])2)

Con esto, el invariante es: i≤n Λ s=S(p,r,i) y la postcondición es: s=S(p,r,n)

a. [10%] Verificar que la inicialización lleva al invariante

Se debe demostrar la tripla {Q}INIC{P}

{0≤n}s,i:=0,0{i≤n Λ s=S(p,r,i)}
≡ <Axioma de corrección con wp>
0≤n ⇒ wp(s,i:=0,0|i≤n Λ s=S(p,r,i))
≡ <wp de asignación>
0≤n ⇒ (i≤n Λ s=S(p,r,i))[s,i:=0,0]
≡ <Definición de sustitucion>
0≤n ⇒ (0≤n Λ 0=S(p,r,0))
≡ <Definición de S. orden total de enteros>
 0≤n ⇒ (0≤n Λ 0=(∑k| 0≤k<0 : (r[k] - p[k])2))
≡ <Rango vacio.>
0≤n ⇒ ( 0<n Λ 0=0)
≡ <Identidad Λ y reflexividad de = >
0≤n ⇒ 0<n
≡ <Reflexividad de ⇒ >
true

b. [10%] Verificar que si la guarda del ciclo es falsa se llega a la postcondición

Se debe demostrar que (P Λ ¬ BC) ⇒ R

(i≤n Λ s=S(p,r,i)) Λ ¬ (i<n) ⇒ s=S(p,r,n)

≡ <Definición de menor o igual y menor estricto>
(i=n Λ s=S(p,r,i)) ⇒ s=S(p,r,n)
≡ <Sustitución de iguales por iguales>
(i=n Λ s=S(p,r,n)) ⇒ s=S(p,r,n)
≡ <Debilitamiento>
true

c. [25%] Verificar que el invariante efectivamente es invariante

Se debe demostrar la tripla {P Λ BC}S{P}

{i≤n Λ s=S(p,r,i) Λ i<n}

e:= p[i] - r[i];
s,i := s + e*e, i+1
{i≤n Λ s=S(p,r,i)}

Se calcula primero la wp

wp (e:= p[i]-r[i];s,i := s+e*e,i+1 | i≤n Λ s=S(p,r,i))

≡ <wp de secuencia>
wp(e:= p[i]-r[i] | wp(s,i := s+e*e,i+1 | i≤n Λ s=S(p,r,i)))
≡ <wp de asignación>
wp(e:= p[i]-r[i] | (i≤n Λ s=S(p,r,i))[s,i := s+e*e,i+1])
≡ <wp de asignación>
(i≤n Λ s=S(p,r,i))[s,i := s+e*e,i+1][e:= p[i]-r[i]]
≡ <Definición de sustitucion>
(i+1≤n Λ s+e*e=S(p,r,i+1))[e:= p[i]-r[i]]
≡ <Aritmética, Definición de sustitucion>
(i+1≤n Λ s+(p[i]-r[i])2=S(p,r,i+1))
≡ <Orden total de enteros, Definición de S>
(i<n Λ s+(p[i]-r[i])2=(∑ k| 0≤k<i+1 : (r[k]-p[k])2))
≡ <Sacando último término>
(i<n Λ s+(p[i]-r[i])2=(∑ k| 0≤k<i : (r[k]-p[k])2))+(r[i]-p[i])2
≡ <(x-y)2=(y-x)2>
i<n Λ s=(∑ k| 0≤k<i : (r[k]-p[k])2)
≡ <Definición de S>
i<n Λ s=S(p,r,i)
Ahora se demuestra que P Λ BC implican esta wp.

i≤n Λ s=S(p,r,i) Λ i<n ⇒ i<n Λ s=S(p,r,i)

≡ <Debilitamiento>
true

d. [15%] Determinar una función de cota para verificar que el ciclo termina

Se escoge como función de cota t=n-i

Se debe demostrar primero que P Λ BC ⇒ t > 0

i≤n Λ s=S(p,r,i) Λ i<n ⇒ n-i > 0

≡ <Sumando i a ambos lados en el consecuente>
i≤n Λ s=S(p,r,i) Λ i<n ⇒ n>i
≡ <Reordenando desigualdad>
i≤n Λ s=S(p,r,i) Λ i<n ⇒ i<n
≡ <Debilitamiento>
true

Ahora se debe demostrar la tripla {P Λ BC Λ t=C}S{t<C}

{i≤n Λ s=S(p,r,i) Λ i<n Λ n-i=C}
be:= p[i] - r[i];
s,i := s + e*e, i+1
{n-i<C}

Se calcula primero:
wp (e:= p[i]-r[i];s,i := s+e*e,i+1 | n-i<C)
≡ <wp de secuencia>
wp(e:= p[i]-r[i] | wp(s,i := s+e*e,i+1 | n-i<C))
≡ <wp de asignación>
wp(e:= p[i]-r[i] | (n-i<C)[s,i := s+e*e,i+1])
≡ <wp de asignación>
(n-i<C)[s,i := s+e*e,i+1][e:= p[i]-r[i]]
≡ <Definición de sustitución>
(n-(i+1)<C)[e:= p[i]-r[i]]
≡ <Aritmética, Definición de sustitución>
n-i-1<C

Se prueba ahora
i≤n Λ s=S(p,r,i) Λ i<n Λ n-i=C ⇒ n-i-1<C
≡ <Orden total de enteros>
i≤n Λ s=S(p,r,i) Λ i<n Λ n-i-1<C ⇒ n-i-1<C
≡ <Debilitamiento>
true
2. Determinar la complejidad temporal T(n) del programa del punto 1
a. [10%] Determinar cuáles son las operaciones que se ejecutan en tiempo constante y
cuantas veces se ejecuta cada operación en función de n.

Operacion(es) Constante Veces que se ejecuta

Asignación (:=) c1 2n+1

Suma, resta (+,-) c2 3n

Comparación (>,≤) c3 n+1

Multiplicación (*) c4 n

b. [10%] Utilizando el resultado del punto anterior, describir una fórmula para la
complejidad temporal T(n) del programa. Determinar el orden de complejidad de esta
función

T(n) = (n+1)c1 + 3nc2 + (n+1)c3 + nc4

T(n) = n(c1 + 3c2 + c3 + c4) + (c1 + c3)

T(n) es O(n)
3. [20%] Calcular la complejidad temporal para el siguiente programa que
invierte un arreglo de números enteros

void invertir(int [] numeros, int i, int j) {

if(i>=j) return;
int n = numeros[i];
numeros[i] = numeros[j];
numeros[j] = n;
invertir(numeros, i+1,j-1);
}

Esta es la tabla de operaciones básicas llamadas en el caso base y en el caso

recursivo. Como la ecuación de recurrencia va a necesitar dos casos base, se
determina el tiempo con cero datos (caso i>j) y con un dato (caso i=j)

Operación Constante Veces caso base Veces caso recursivo

Asignación (=) c1 0 3

Comparación (>=) c2 1 1

Suma, resta (+,-) c3 0 2

T(0) = T(1) = c2
T(n) = 3c1 + c2 + 2c3 + T(n-2)
= k1 + T(n-2)

Donde k1 = 3c1 + c2 + 2c3

T(n) es una ecuación de recurrencia lineal de orden 2.

T(n) - T(n-2) = k1

Se resuelve como T(n) = h(n) + p(n) donde h(n) es solución a la ecuación de

recurrencia homogenea correspondiente h(n) - h(n-2) = 0 y p(n) es una solución
particular. El polinomio carácterístico relacionado con h(n) es:

λ2 - 1 = 0

con raices r = 1 y r = -1. Por lo tanto

h(n) = d1(1)n + d2(-1)n = d1 + d2(-1)n

donde d1 y d2 son constantes. Como la función constante soluciona h(n), se busca una
solución particular p(n) = d3*n Reemplazando en la ecuación original:

T(n) - T(n-2) = k1
d3*n - d3*(n-2) = k1
2 d3 = k1
d3 = k1/2

La solución es entonces

T(n) = d1 + d2(-1)n + nk1/2

Reemplazando las condiciones iniciales T(0) y T(1):

c2 = T(0) = d1 + d2(-1)0 + 0*k1/2 = d1 + d2

c2 = T(1) = d1 + d2(-1)1 + 1*k1/2 = d1 - d2 + k1/2

Restando las dos ecuaciones

0 = 2d2 - k1/2

d2 = k1/4 = (3c1 + c2 + 2c3)/4

d1 = c2 - d2 = c2 – k1/4 = c2 - (3c1 + c2 + 2c3)/4 = (3c2 - 3c1 - 2c3)/4

Finalmente

T(n) = (3c2 - 3c1 – 2c3)/4 + (-1)n(3c1 + c2 + 2c3)/4 + n(3c1 + c2 + 2c3)/2

por lo tanto T(n) es O(n)