← Volver a los ejercicios

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

Chequeoimayorsegundo¿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?