Algoritmos e Invariantes

Algoritmos y Estructuras de Datos

1
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

2
Búsqueda sobre secuencias ordenadas

I La clase pasada vimos un ejemplo de especificación +

algoritmos + demostración de la búsqueda lineal
(contiene()).
I Supongamos ahora que la secuencia está ordenada.
I ¿Cómo cambiarı́a ahora la especificación?
proc contieneOrdenada(in s: seqhZi, in x: Z): Bool){
requiere {ordenada(s)}
asegura {result = true ↔ (∃i : Z)(0 ≤ i < |s| ∧L s[i] = x) }

I ¿Podemos aprovechar que la secuencia está ordenada para crear un

programa más eficiente ?
I Ejercicio: Escribir el predicado ordenada(s).

3
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

4
Búsqueda sobre secuencias ordenadas

I En vez de interrumpir el ciclo al encontrar el elemento,

podemos interrumpirlo tan pronto como verificamos que
s[i] ≥ x.

bool contieneOrdenada(vector<int> &s, int x) {

int i = 0;
while( i < [Link]() && s[i] < x ) {
i=i+1;
}
return (i < [Link]() && s[i] == x);
}

I ¿Es este código realmente más eficiente que el de búsqueda

lineal?
I Una forma de analizar esto es comparando “cuánto tardan” en
el peor caso (i.e. cuando el elemento no está en la secuencia)
5
Búsqueda sobre secuencias ordenadas

I Analicemos cómo se ejecuta el código (contando operaciones)

en el peor caso.

Función contieneOrdenado Texec máx.# veces

int i = 0; c10 1
while( i < [Link]() && s[i] < x ) { c20 1 + |s|
i=i+1; c30 |s|
}
return (i < [Link]() && s[i] == x); c40 1
I Sea n la longitud de s, ¿cuál es el tiempo de ejecución en el
peor caso?

TcontieneOrdenado (n) = 1 ∗ c10 + (1 + n) ∗ c20 + n ∗ c30 + 1 ∗ c40

I El tiempo de ejecución de peor caso de contiene y este

contieneOrdenado dependen linealmente de n.
6
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

7
Búsqueda sobre secuencias ordenadas

I Vamos de nuevo: ¿Podemos aprovechar el ordenamiento de la

secuencia para mejorar el tiempo de ejecución de peor caso?
I Pensemos en el juego de “Adivinar un número” o “Adivinar el
personaje”
I ¿Necesitamos iterar si |s| = 0? Trivialmente, x 6∈ s
I ¿Necesitamos iterar si |s| = 1?Trivialmente,
s[0] == x ↔ x ∈ s
I ¿Necesitamos iterar si x < s[0]? Trivialmente, x 6∈ s
I ¿Necesitamos iterar si x ≥ s[|s| − 1]? Trivialmente,
s[|s| − 1] == x ↔ x ∈ s

8
Búsqueda sobre secuencias ordenadas

Asumamos por un momento que |s| > 1 ∧L (s[0] ≤ x < s[|s| − 1])

↑ ↑
low high
?
↑ ↑ ↑
low mid high
≤x ≤x ≤x ≤x ≤x
↑ ↑
low high

9
Búsqueda sobre secuencias ordenadas

≤x ≤x ≤x ≤x ≤x ?
↑ ↑ ↑
low mid high
≤x ≤x ≤x ≤x ≤x >x >x >x >x
↑ ↑
low high
≤x ≤x ≤x ≤x ≤x ? >x >x >x >x
↑ ↑ ↑
low mid high
≤x ≤x ≤x ≤x ≤x >x >x >x >x >x
↑ ↑
low high

Si x ∈ s, tiene que estar en la posición low de la secuencia.

10
Búsqueda sobre secuencias ordenadas

≤x ≤x ≤x ≤x ≤x >x >x >x >x >x

↑ ↑
low high

I ¿Qué invariante de ciclo podemos escribir?

I ≡ 0 ≤ low < high < |s| ∧L s[low ] ≤ x < s[high]

I ¿Qué función variante podemos definir?

fv = high − low − 1

11
Búsqueda sobre secuencias ordenados

boolean contieneOrdenada(int []s, int x) {

// casos triviales
if ([Link] == 0 ) {
return false;
} else if ([Link] == 1) {
return s[0] == x;
} else if (x<s[0]) {
return false;
} else if (x ≥ s[[Link]−1]) {
return s[[Link]−1] == x;
} else {
// casos no triviales
◦ ...
}
}

12
Búsqueda sobre secuencias ordenadas

} else {
// casos no triviales
int low = 0;
int high = [Link] − 1;
while( low+1 < high ) {
int mid = (low+high) / 2;
if( s[mid] ≤ x ) {
low = mid;
} else {
high = mid;
}
}
return s[low] == x;
}
}
A este algoritmo se lo denomina búsqueda binaria

13
Búsqueda binaria

I Veamos ahora que este algoritmo es correcto.

PC ≡ ordenada(s) ∧ (|s| > 1 ∧L s[0] ≤ x ≤ s[|s| − 1])

∧ low = 0 ∧ high = |s| − 1
QC ≡ (s[low ] = x) ↔ (∃i : Z)(0 ≤ i < |s| ∧L s[i] = x)
B ≡ low + 1 < high
I ≡ 0 ≤ low < high < |s|
∧L (∀i : Z)(0 ≤ i ≤ low =⇒ s[i] ≤ x)
∧L (∀i : Z)(high ≤ i < |s| =⇒ x < s[i])
fv = high − low − 1

14
Corrección de la búsqueda binaria

I ¿Es I un invariante para el ciclo?

I El valor de low es siempre menor estricto que high
I low arranca en 0 y sólo se aumenta
I high arranca en |s| − 1 y siempre se disminuye
I Siempre se respecta que s[low ] ≤ x y que x < s[high]

I ¿A la salida del ciclo se cumple la postcondicion QC ?

I Al salir, se cumple que low + 1 = high
I Sabemos que s[high] > x y s[low ] <= x
I Como s está ordenada, si x ∈ s, entonces s[low ] = x

15
Corrección de la búsqueda binaria

I ¿Es la función variante estrictamente decreciente?

I Nunca ocurre que low = high
I Por lo tanto, siempre ocurre que low < mid < high
I De este modo, en cada iteración, o bien high es estrictamente
menor, o bien low es estrictamente mayor.
I Por lo tanto, la expresión high − low − 1 siempre es
estrictamente menor.

I ¿Si la función variante alcanza la cota inferior la guarda se

deja de cumplir?
I Si high − low − 1 ≤ 0, entonces high ≤ low + 1.
I Por lo tanto, no se cumple (high > low + 1), que es la guarda
del ciclo

16
Búsqueda binaria
I ¿Podemos interrumpir el ciclo si encontramos x antes de
finalizar las iteraciones?
I Una posibilidad no recomendada (no lo hagan en casa!):

I ◦ ..
while( low+1 < high) {
int mid = (low+high) / 2;
if( s[mid] < x ) {
low = mid;
} else if( s[mid] > x ) {
high = low;
} else {
return true; // Argh!
}
}
return s[low] == x;
}

17
Búsqueda binaria

I Una posibilidad aún peor (ni lo intenten!):

I bool salir = false;

while( low+1 < high && !salir ) {
int mid = (low+high) / 2;
if( s[mid] < x ) {
low = mid;
} else if( s[mid] > x ) {
high = mid;
} else {
salir = true; // Puaj!
}
}

return s[low] == x || s[(low+high)/2] == x;

}

18
Búsqueda binaria

I Si queremos salir del ciclo, el lugar para decirlo es ...

la guarda!

I while( low+1 < high && s[low] != x ) {

int mid = (low+high) / 2;
if( s[mid] ≤ x ) {
low = mid;
} else {
high = mid;
}
}
return s[low] == x;
}

I Usamos fuertemente la condición s[low ] ≤ x < s[high] del

invariante.

19
Búsqueda binaria
I ¿Cuántas iteraciones realiza el ciclo (en peor caso)?

Número de
high − low
iteración
0 |s| − 1
1 ∼
= (|s| − 1)/2
2 ∼
= (|s| − 1)/4
3 ∼
= (|s| − 1)/8
.. ..
. .
t ∼
= (|s| − 1)/2t

I Sea t la cantidad de iteraciones necesarias para llegar a

high − low = 1.

1 = (|s|−1)/2t entonces 2t = |s|−1 entonces t = log2 (|s|−1).

Luego, el tiempo de ejecución de peor caso de la búsqueda binaria
es = proporcional a log2 |s| y no proporcional a |s|.
20
Búsqueda binaria

I ¿Es mejor un algoritmo que ejecuta una cantidad logarı́tmica

de iteraciones?
Búsqueda Búsqueda
|s| Lineal Binaria
10 10 4
102 100 7
106 1, 000, 000 21
2,3 × 107 23, 000, 000 25
7 × 109 7, 000, 000, 000 33 (!)

I Sı́! Búsqueda binaria es más eficiente que búsqueda lineal

I Pero, requiere que la secuencia esté ya ordenada.

21
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

22
Bonus Track: Nearly all binary searches are broken!

[Link]

23
Nearly all binary searches are broken!

I En 2006 comenzaron a reportarse accesos fuera de rango a

vectores dentro de la función binarySearch implementada en
las bibliotecas estándar de Java.
I En la implementación en Java, los enteros tienen precisión
finita, con rango [−231 , 231 − 1].
I Si low y high son valores muy grandes, al calcular k se
produce overflow.
I La falla estuvo dormida muchos años y se manifestó sólo
cuando el tamaño de los vectores creció a la par de la
capacidad de memoria de las computadoras.
I Bugfix: Computar mid evitando el overflow:
int mid = low + (high-low)/2;

24
Conclusiones

I La búsqueda binaria implementada en Java estaba

formalmente demostrada ...
I ... pero la demostración suponı́a enteros de precisión infinita
(en la mayorı́a de los lenguajes imperativos son de precisión
finita).
I En AED no nos preocupan los problemas de aritmética de
precisión finita (+Info: Orga1/Sistemas Digitales).
I Es importante validar que las hipótesis sobre las que se realizó
la demostración valgan en la implementación (aritmética finita,
existencia de acceso concurrente, multi-threading, etc.)

25
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

26
Apareo (fusión, merge) de secuencias ordenadas
I Problema: Dadas dos secuencias ordenadas, fusionarlas en
una única secuencia ordenada.
I El problema es importante per se y como subproblema de
otros problemas importantes.
I Especificación:
proc merge(in a, b : seqhZi) : seqhZi {
requiere {ordenada(a) ∧ ordenada(b)}
asegura {ordenada(result) ∧ mismos(result, a + +b)}
}

pred mismos(s, t : seqhZi){

(∀x : Z)(#apariciones(s, x) = #apariciones(t, x))
}
I ¿Cómo lo podemos implementar?
I Podemos copiar los elementos de a y b a la secuencia c, y
después ordenar c.
I Pero no sabemos ordenar ¿Se podrá fusionar ambas secuencias
en una única pasada?
27
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

28
Apareo de secuencias ordenadas
Ejemplo:

1 3 5 7 9
I a= ↑ ↑ ↑ ↑ ↑ ↑
i i i i i i
2 4 6 8
I b= ↑ ↑ ↑ ↑ ↑
j j j j j
?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9
I c= ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
k k k k k k k k k k

29
Búsqueda sobre secuencias ordenadas
Especificación
Programa 1
Programa 2: Búsqueda binaria
Puede fallar

Apareo/Merge
Especificación
Pensemos el algoritmo
Pensemos el invariante

30
Apareo de secuencias

I ¿Qué invariante de ciclo tiene esta implementación?

I ≡ ordenada(a) ∧ ordenada(b) ∧ |c| = |a| + |b|

∧ ((0 ≤ i ≤ |a| ∧ 0 ≤ j ≤ |b| ∧ k = i + j)
∧L (mismos(subseq(a, 0, i) + +subseq(b, 0, j), subseq(c, 0, k))
∧ ordenada(subseq(c, 0, k))))
∧ i < |a| →L (∀t : Z)(0 ≤ t < j →L b[t] ≤ a[i])
∧ j < |b| →L (∀t : Z)(0 ≤ t < i →L a[t] ≤ b[j])

I ¿Qué función variante deberı́a tener esta implementación?

fv = |a| + |b| − k

31
Apareo de secuencias
int [ ] merge( int [ ] a , int b [ ] ) {
int [ ] c = new int [ a . length+b . length ] ;
int i = 0; // Para recorrer a
int j = 0; // Para recorrer b
int k = 0; // Para recorrer c

while( k < c . length ) {

i f ( /∗Si tengo que avanzar i ∗/ ) {
c [ k++] = a [ i++] ;
} else i f (/∗ Si tengo que avanzar j ∗/) {
c [ k++] = b[ j++] ;
}
}
return c ;
}

I ¿Cuándo tengo que avanzar i? Cuando j está fuera de rango ó

cuando i y j están en rango y a[i] < b[j]
I ¿Cuándo tengo que avanzar j? Cuando no tengo que avanzar i
32
Apareo de secuencias

int [ ] merge( int [ ] a , int b [ ] ) {

int [ ] c = new int [ a . length+b . length ] ;
int i = 0; // Para recorrer a
int j = 0; // Para recorrer b
int k = 0; // Para recorrer c

while( k < c . length ) {

i f ( j ≥ b . length | | ( i<a . length () && a [ i ] < b[ j ] ) ) {
c [ k++] = a [ i++] ;

} else {
c [ k++] = b[ j++] ;

}
}
return c ;
}

33
Apareo de secuencias

I Al terminar el ciclo, ¿ya está la secuencia c con los valores

finales?
I ¿Cuál es el tiempo de ejecución de peor caso de merge?
I Sea n = |c| = |a| + |b|
I El while se ejecuta n + 1 veces.
I Por lo tanto, Tmerge (n) ∈ O(n)

34
Bibliografı́a

I David Gries - The Science of Programming

I Chapter 16 - Developing Invariants (Linear Search, Binary
Search)
I Cormen et al. - Introduction to Algorithms
I Chapter 2.2 -Analyzing algorithms
I Chapter 3 - Growth of Functions

35