dosMayores: dos variables que se sostienen entre sí
Un solo recorrido, dos acumuladores. Ninguno de los dos se
deja demostrar solo: el argumento de segundo necesita saber qué
guarda mayor, y al revés. Ese es el invariante conjunto que va a
encontrar aquí.
1. La especificación y la predicción
Entrada: un arreglo A[0..N) de números con
N ≥ 2. Salida: el segundo mayor de A contando repeticiones,
esto es, si se ordena A de mayor a menor, el elemento que queda en la
segunda casilla.
Arreglo:
¿Qué devuelve dosMayores(A)?
2. Ejecute y mire
Paso 0 de 0
Las casillas azules son las que el ciclo ya leyó:
A[0..i). Cada vez que la ejecución pasa por la línea 8, el while
evalúa su condición y esa foto de (i, mayor, segundo) queda en la
tabla.
3. La traza por estados
Chequeo
i
mayor
segundo
¿Qué se repite?
La columna de la derecha se llena cuando acierte el
invariante en la tarjeta 4.
4. El invariante conjunto
Todo cambia de fila en fila. Busque lo que se
cumple en todas, incluida la primera y la última, y escrito en
términos de N, i y A: no de los números de este arreglo.
¿Qué guarda mayor en cada chequeo? (ese será I₁)
¿Y segundo? (ese será I₂)
¿Entre qué valores se mueve i en los chequeos? (ese será I₀)
5. La demostración
Encuentre primero los
tres invariantes en la tarjeta 4. El teorema a demostrar:
Teorema 1 — los invariantes I₀, I₁ e I₂ se cumplen.
Inicialización: tras las líneas 2 a 7, ¿qué vale el estado (i, mayor, segundo)?
Para I₀: 2 ≤ 2 ≤ N, que se cumple porque la
precondición pide N ≥ 2. ✓ Para I₁ e I₂: A[0..2) tiene exactamente
dos elementos, A[0] y A[1]. Las líneas 2 a 6 los comparan y dejan el mayor
de los dos en mayor y el otro en segundo; eso
es justamente A[0..2) ordenado de mayor a menor. ✓
Estabilidad: ¿cuántos casos hay que considerar?
Se toma una iteración arbitraria i = t con
2 ≤ t < N y se asume que antes de ella valen I₀, I₁ e I₂ evaluados en
t. Al terminar el cuerpo, i = t + 1 y A[0..t+1) es A[0..t) con A[t]
añadido, de modo que hay que ver quiénes son ahora los dos primeros de
esa lista ordenada de mayor a menor.
Caso 1, A[t] > mayor. Como mayor era el máximo de A[0..t),
A[t] es mayor que todos los de A[0..t) y por tanto es el máximo de
A[0..t+1): la línea 11 lo pone en mayor. ✓ El segundo de la
lista nueva es el primero de la vieja, que era mayor, y la
línea 10 lo guardó en segundo antes de sobrescribirlo. ✓
Caso 2, segundo < A[t] ≤ mayor. El máximo no cambia, así que
I₁ sigue valiendo sin tocar nada. ✓ Y A[t] se cuela entre
mayor y segundo: pasa a ser el segundo de la
lista nueva, que es lo que hace la línea 13. ✓
Caso 3, A[t] ≤ segundo. A[t] no supera a ninguno de los dos, de
modo que los dos primeros de la lista nueva son los mismos de la vieja y
el código no asigna nada. ✓
I₀ vale porque t < N implica 2 ≤ t + 1 ≤ N. Los tres invariantes son
estables. ✓
Terminación: ¿con qué valor de i termina el ciclo?
El ciclo termina porque i crece de 1 en 1 e I₀
lo acota por N. Al salir, la condición i < N es falsa, o sea i ≥ N;
intersecando con I₀, que da i ≤ N, queda exactamente i = N. Sustituyendo
en I₂: segundo es el segundo elemento de A[0..N) ordenado de
mayor a menor, que es la poscondición. ∎
Teorema 2. La invocación dosMayores(A) sobre
cualquier arreglo A con N ≥ 2 devuelve el segundo mayor de A contando
repeticiones. Demostración: por el Teorema 1 los invariantes se
cumplen; la terminación deja i = N, y sustituir ese valor en I₂ da la
poscondición. ∎
Fíjese en lo que hizo falta: la estabilidad de I₂ usó I₁ (el caso 1
necesita saber que mayor era el máximo) y la de I₁ no usó
I₂. No se pueden demostrar por separado y por eso se enuncian juntos.
6. Para llevarse
Sin solución aquí. Modifique el algoritmo para que
devuelva el tercer mayor con un solo recorrido, escriba los
invariantes de las tres variables y diga cuántos casos tiene ahora la
estabilidad. Después responda: con k variables, ¿cuántos casos hay y
cuánto cuesta el recorrido?