ISIS 1105 Diseño y Análisis de Algoritmos

Semestre 2020-20 – Sección 2 / Parcial 2

Septiembre 25, 2020
Prof. Rodrigo Cardoso

Parte 1 Trabajo individual

Límite de entrega Octubre 31, 2020, 8:30 a.m.
Por Sicua+
Archivo respuesta login-uniandes.docx 
login-uniandes.pdf 
login-uniandes.zip

IMPORTANTE: Soy consciente de que cualquier tipo de fraude en los exámenes es considerado
como una falta grave en la Universidad. Al entregar este examen doy expreso testimonio de que este
trabajo fue desarrollado de acuerdo con las normas establecidas. Del mismo modo, aseguro que no
participé en ningún tipo de fraude.

Nombre : ________________________________________

Código : _________________

1 [25/100]

1a (15/25) Especifique y desarrolle un programa GCL que, para un número natural n:nat,
n>0, determine un valor entero r que sea igual al logaritmo en base 3 de n,
aproximado al mayor entero menor que él (piso, floor). Por ejemplo: si n=4, r=1; si
n=30, r=3.

La especificación debe incluir: contexto, pre- y poscondición y aserciones intermedias

que documenten la corrección. Además, si usa ciclos: invariante(s) y cota(s); o bien,
indicación de paradigma(s) utilizado(s).

[Ctx C: n:nat+

q,r:= 1,0;

{Inv P: q = 3r  n }
{Cota t: n-3r+1 }

do 3*q  n → q,r:= 3*q,r+1 od

{R2: 3r  n < 3r+1 }

{R1: r  log3 n < r+1 }
{Pos R: r = log3 n }
]
Ctx, Pre, Pos: [3/15]
R1, R2: [2/15]
Inv, Cota: [5/15]
Código: [5/15]

Variante: Paradigma BLC

(todo como en la respuesta anterior, sin indicar invariante ni cota)

[Ctx C: n:nat+

DAlgo 2020-2 P2 Sol 1

 q,r:= 1,0;

do 3*q  n → q,r:= 3*q,r+1 od

{R2: 3r  n < 3r+1 }

{R1: r  log3 n < r+1 }
{Pos R: r = log3 n }
]
Ctx, Pre, Pos: [3/15]
R1, R2: [2/15]
Paradigma BLC: [5/15]
Código: [5/15]

1b (5/25) Para su respuesta en 1a, explique:

• si usa ciclos: qué técnica ha usado para el desarrollo de invariante(s) y cota(s);
• si usa paradigma(s): cómo se cumplen las respectivas condiciones de aplicación.

Técnicas usadas para desarrollar invariante:

Eliminar una conjunción + Fortalecimiento de invariante.
[5/5]

Variante BLC
E = {30, 31, 32, …}
e0 = 30 = 1
suc.3k = 3*3k, k0
p.3k  (3*3k > n)
[5/5]

1c (5/25) Considere como operación básica la asignación. Estime y explique los costos en
tiempo y en espacio del algoritmo propuesto con una cota de la forma (…).

S(n) = (1)
Solo se usan variables adicionales.
[2/5]

T(n) = (log n)
El algoritmo incrementa la variable r en 1 unidad, empezando en 0, hasta conseguir la respuesta.
Es decir, hace log3 n iteraciones, cada una de costo (1).
Por tanto:
T(n) = (log3 n)
= (log n)
[3/5]

2 [25/100]

Suponga un tesoro escondido en un punto (a,b) del plano cartesiano int  int. El punto
(a,b) es el único en el plano que satisface un predicado tesoro(.,.) cuyo cálculo cuesta
O(1) en tiempo.

2a (15/25) Plantee el problema como una búsqueda lineal con certeza.

DAlgo 2020-2 P2 Sol 2

Para una búsqueda BLC:
E = nat  nat
[4/15]
e0 = (0,0)
[1/15]
suc(i,j) = (i-1,j+1) , si 0<i
= (j+1,0) , si 0=i
[5/15]
p(i,j)  tesoro(i,j)  tesoro(-i,j)  tesoro(i,-j)  tesoro(-i,-j)
[5/15]

La siguiente figura explica cómo es el recorrido. En realidad, basta hacer el recorrido por el promer
cuadrante (nat  nat) y enseguida consultar las otras esquinas (x,y) con |x|=i e |y|=j. Para
saber dónde está el tesoro hace falta preguntar en qué coordenada del final se cumple el predicado
de búsqueda.

…
(-i,j) (i,j)

(-i,-j) (i,-j)

Variantes

Recorridos lineales sobre el plano cartesiano. Por ejemplo, alredeor del origen:
• Cuadrados
• Rectángulos
• Rombos
• Espirales
• etc.

Es fácil describir los recorridos de manera gráfica, i.e., establecer el primer elemento y la función
sucesor.

El predicado de búsqueda debería ser tesoro(.,.).

E = int  int
[4/15]
e0 = (0,0)
[1/15]
suc(i,j) = …
[5/15]
p(i,j)  tesoro(i,j)
[5/15]

2b (5/25) Escriba el código que corresponda a su diseño en 2a.

 i,j:= 0,0;

DAlgo 2020-2 P2 Sol 3

 do (tesoro(i,j)  tesoro(-i,j)  tesoro(i,-j)  tesoro(-i,-j))
→ if i0 then i,j:= i-1,j+1
else i,j:= j+1,0

fi
od;

if tesoro(i,j) then a,b:= i,j

elsf tesoro(-i,j) then a,b:= -i,j
elsf tesoro(i,-j) then a,b:= i,-j
else a,b:= -i,-j
fi

[5/5]

Variantes

Programas que implementen las ideas planteadas en 2a.

Fuentes de error (o de dificultad): implementar la función sucesor.

[5/5]

2c (5/25) Estime los costos en espacio y tiempo de su solución.

En espacio: se usan solo 4 variables, i.e.,

S(a,b) = (1)
[1/5]

En tiempo: el algoritmo encuentra (a,b) en la diagonal y = -x+a+b, b pasos después de haber

recorrido las diagonales y=-x+h, para 0h<a+b, cada una en el segmento en que ambas
coordenadas no son negativas. La diagonal h tiene h+1 elementos, por lo que (a,b) se encuentra
después de 1 + 2 + … + (a+b) + b pasos.

Entonces:
T(a,b) = 1 + 2 + (a+b) + b
= (a+b)(a+b+1)/2 + b
= O((a+b)2)
[4/5]

Variantes

Dependientes de los recorridos planteados en 3a.

Deben justificarse las respuestas, tanto en espacio como en tiempo.

Para recorridos como los previstos (rombos, cuadrados, …) es de esperarse que las complejidades
sean similares a las descritas en la solución detallada (espacio constante, tiempo cuadrático).
Espacio [1/5]
Tiempo [4/5]

DAlgo 2020-2 P2 Sol 4

ISIS 1105 Diseño y Análisis de Algoritmos
Semestre 2020-20 – Sección 2 / Parcial 2
Septiembre 25, 2020
Prof. Rodrigo Cardoso

Parte 2 Trabajo individual o por parejas (de la misma sección)

Límite de entrega Octubre 31, 2020, 9:50 a.m.
Por Sicua+
Archivo respuesta login-uniandes.docx 
(solo uno por grupo) login-uniandes.pdf 
login-uniandes.zip

IMPORTANTE: Soy consciente de que cualquier tipo de fraude en los exámenes es considerado
como una falta grave en la Universidad. Al entregar este examen doy expreso testimonio de que este
trabajo fue desarrollado de acuerdo con las normas establecidas. Del mismo modo, aseguro que no
participé en ningún tipo de fraude.

Nombre(s) : ________________________________________

Código(s) : _________________

3 [25/100]

Un arreglo b[p..q-1]:nat es un morro si sus valores son tales que existe un índice k,
pk<q, el pico (del morro), tal que b[p..k-1] es creciente y b[k..q-1] es decreciente.

En este caso se dice que se cumplen los predicados morro(b,p,q) y k=pico(b,p,q).

b:

p k q

3a (15/25) Escriba código GCL que cumpla la siguiente especificación.

[Ctx C: n:nat+  b[0..n-1]:nat  b=B  morro(b,0,n-1)

…
{Inv P: 0p<qn  morro(b,p,q)  pico(b,p,q)=pico(b,0,n)}
{Cota t: q-p+1}

…
{Pos R: p = pico(b,0,n-1)}
]

[Ctx C: n:nat+  b[0..n-1]:nat  b=B  morro(b,0,n-1)

p,q:= 0,n-1;
[2/15]

{Inv P: 0p<qn  morro(b,p,q)  pico(b,p,q)=pico(b,0,n)}

{Cota t: q-p+1}

DAlgo 2020-2 P2 Sol 5

do p+1q
[3/15]

→ r1,r2:= p+(q-p)3, p+2*(q-p)3;

if b[r1]<b[r2] then p:= r1

elsf b[r1]>b[r2] then q:= r2
else p,q:= r1,r2
fi
[10/15]
{Pos R: p = pico(b,0,n-1)}
]

Variante

Una solución que itere rebajando en 1 el intervalo de incertidumbre, es decir, aumentando p en 1 o

disminuyendo q en 1 en cada iteración.
[8/15]

3b (10/15) Estime las complejidades espacial y temporal de su solución.

Espacio: solo 4 variables, i.e.,

S(n) = (1).
[2/10]

Tiempo: en cada iteración, en el peor caso, el tamaño del intervalo de incertidumbre disminuye de
q-p a 2*(q-p)/3. Es decir, se termina en r pasos, donde
(2/3)r n = 1
 r = (log n)/(1-log 3)

Por tanto:
T(n) = (log n).
[8/10]

Variante

La solución que itera rebajando en 1 el intervalo de incertidumbre:

Espacio:
S(n) = (1).
[2/10]

Tiempo:
T(n) = (n).
[3/10]

4 [25/100]

Supóngase que se dispone de un arreglo A[0..n-1]:int, con n>0, que guarda el estado
de una cuenta bancaria durante el intervalo de tiempo 0..n-1. Para 0≤p≤q≤n, se define
cred(p,q), la credibilidad de la cuenta en el intervalo p..q-1, como la diferencia entre el
número de valores positivos y negativos en el segmento, i.e.,
cred(p,q) = (#i| p≤i<q : A[i]>0) - (#i| p≤i<q : A[i]<0).

4a (20/25) Determinar la máxima credibilidad posible para el arreglo A.

DAlgo 2020-2 P2 Sol 6

 Por ejemplo, si A[0..9] =[-43,-43,-12,-20,39,42,27,-32,24,-47], se puede
responder 3, porque cred(4,9)=3, ya que el segmento [39,42,27,-32,24] tiene 4
valores positivos y uno negativo. Este valor es maximal dentro de A, aunque también
cred(4,7)=3.

Diseñe una solución de programación dinámica para el problema de encontrar el valor

máximo posible de cred(p,q), 0≤p≤q≤n. Utilice la "receta" que para esto se estudió en
clase. Para empezar, use el siguiente lenguaje:
maxc.k  "máxima credibilidad cred(p,q), 0pqk", 0kn

Puede definir más notación auxiliar, si lo requiere.

Lenguaje
maxc.k = (max p,q| 0pqk : cred(p,q)), 0kn
maxcf.k = (max p| 0pk : cred(p,k)), 0kn

maxc : 0..n → nat // siempre es, al menos 0, porque cred(k,k)=0

maxcf: 0..n → nat // siempre es, al menos 0, porque cred(k,k)=0

maxc.n = ?
[4/20]

Recurrencias
maxcf.0 = (max p| 0p0 : cred(p,0))
= cred(0,0)
= 0
maxcf(k+1) = if b[k+1]=0 then maxcf.k
elsf b[k+1]<0 then max(maxcf.k – 1,0)
else maxcf.k + 1
fi , 0k<n

[4/20]
maxc.0 = (max p,q| 0pq0 : cred(p,q))
= cred(0,0)
= 0

maxc(k+1) = if maxc.k < maxcf(k+1) then maxcf(k+1)

else maxc.k
fi

[4/20]

Diagramas de necesidades

k+1
maxcf
0 k

maxc
0 k k+1
[3/20]

DAlgo 2020-2 P2 Sol 7

Estructura de datos + Invariante

MAXCF = maxcf.k
MAXC = maxc.k

Inv: 0kn  MAXCF=maxf.k  MAXC=maxc.k

[3/20]

Complejidades

Espacio:
2 variables
S.n = (1)
[1/20]

Tiempo:
Para k=0..n-1, el cálculo de maxcf.k y de maxc.k toma (1). Por tanto:
T.n = (n).
[1/20]

Variantes

• El algoritmo de fuerza bruta pasa por todos los posibles intervalos p..q-1 calculando su
credibilidad.

El cálculo de cred(p,q) es O(q-p), i.e., O(n).

Para contar los intervalos posibles:

p se puede elegir de n maneras, después de lo cual,
q se puede elegir de n-p maneras: p..p+1, p..p+2, …, p..n-1
En total: n-p-1 intervalos de la forma p..q-1.
Gran total:
(+p| 0pn : n-p-1)
=
(+p| 0pn : n) - (+p| 0pn : p+1)
=
n(n+1) - (n+1)(n+2)/2
=
(n2)

Es decir el algoritmo de fuerza bruta es (n3).

El diseño presentado puede tener complejidad temporal (n3).

(Incluso si hay corrección) [8/20]

• Otra posibilidad es revisar, cada vez que se avanza, si el maxc.k debe cambiar (pero sin contar
con maxcf.k), lo que implica un cálculo (n) para cada k. Esto da lugar a un gasto temporal de
(n2).

El diseño presentado puede tener complejidad temporal (n2).

(Incluso si hay corrección) [12/20]

DAlgo 2020-2 P2 Sol 8

 4b (5/25) Explique cómo se pueden encontrar índices p y q, 0pqn, tales que maxc.n =
cred(p,q) y cuánto es el costo en espacio y tiempo adicional a lo desarrollado en 1a.

Hay que fortalecer el invariante recordando las decisiones tomadas.

Se puede guardar un arreglo f[0..n-1]:bool tal que

f[0]  true
f[k]  true ssi maxc.k > maxc(k-1), 0<k<n

Al final f[0..n-1] tiene todas las decisiones guardadas. Como maxc es creciente, p es el mayor
índice para el que f[p]true. Y entonces: q = p + maxc.n - 1.

En espacio adicional:
S1(n) = (n)
[2/5]

Tiempo adicional (buscar p de derecha a izquierda, el peor caso):

T1(n) = (n)
[3/5]

Variante

Mejor: fortalecer el invariante con solo una variable p tal que

p  índice del primer elemento del subarreglo donde se alcanza maxc.k, 0<k<n.

Mantener p cuesta (1).

Al final, se define q = p + maxc.n - 1.

En espacio adicional:
S1(n) = (1)
[2/5]
+3 (Bono)

Tiempo adicional (es lineal, pero se hace al tiempo que se encuentra p):
T1(n) = (n).
[3/5]

DAlgo 2020-2 P2 Sol 9