comprimir: la lista que crece y el invariante que la sostiene
Aquí la salida no es un número: es una lista que se va
escribiendo. Un invariante sobre ella tiene que decir dos cosas —qué tan
larga es y qué hay en cada posición— y va a hacer falta una tercera
propiedad, pequeña, sin la cual la estabilidad no se deja escribir.
1. La especificación y la predicción
Entrada: un arreglo A[0..N) de números,
N ≥ 0. Salida: la lista de A sin repeticiones
consecutivas: cada racha de valores iguales seguidos deja un solo
elemento, y el orden se conserva. Sobre [1, 1, 2, 2, 2, 3, 1, 1] la
respuesta es [1, 2, 3, 1].
Arreglo:
¿Cuántos elementos tiene la lista devuelta?
2. Ejecute y mire las dos listas
Paso 0 de 0
Arriba, las casillas azules son A[0..i). Abajo,
res: la ficha ámbar es la última escrita. Mírela contra
A[i−1] en cada chequeo.
3. La traza por estados
Chequeo
i
A[0..i)
res
¿Qué se repite?
4. Los invariantes
Un invariante sobre una lista que crece no puede
limitarse a decir cuántos elementos tiene: hay que fijar también qué hay
en cada posición. Y todo escrito en términos de N, i y A.
¿Qué contiene res en cada chequeo? (ese será I₁)
El cuerpo del ciclo compara A[i] con
el último elemento de res. Para demostrar que esa comparación
es la correcta, ¿qué más hay que saber? (ese será I₂)
¿Entre qué valores se mueve i? (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: con i = 0 y res = [ ], ¿por qué se cumple I₂?
I₀: 0 ≤ 0 ≤ N. ✓ I₁: A[0..0) es el rango
vacío y comprimirlo da la lista vacía, que es lo que dejó la línea 2. ✓
I₂ está escrito como una implicación con antecedente i > 0; con
i = 0 el antecedente es falso y la implicación se cumple sin exigir
nada. ✓ Enunciar I₂ así no es un truco: es lo que permite que el
invariante valga desde el primer chequeo, cuando res
todavía no tiene último elemento.
Estabilidad: se toma i = t con t < N. ¿En cuántos casos se parte?
Caso 1, res vacía. Por I₁ eso solo ocurre
con t = 0. La línea 5 pone nuevo en True, la línea 6 no
entra —no hay último con quién comparar— y la línea 9 escribe A[0], así que res = [A[0]], que es la compresión de A[0..1). ✓
Y su último elemento es A[0] = A[t], o sea A[(t+1)−1]: I₂ evaluado en
t + 1. ✓
Caso 2, res no vacía y A[t] ≠ A[t−1]. Por I₂ el último de res es
A[t−1], de modo que la comparación de la línea 7 da True y la línea 9
escribe A[t]. Como A[t] difiere de A[t−1], empieza una racha nueva y la
compresión de A[0..t+1) es la de A[0..t) con A[t] al final: eso es
exactamente lo que quedó. ✓ El último pasa a ser A[t]. ✓
Caso 3, res no vacía y A[t] = A[t−1]. Otra vez por I₂ la
comparación da False, no se escribe nada, y en efecto A[t] continúa la
racha de A[t−1]: comprimir A[0..t+1) da lo mismo que comprimir
A[0..t). ✓ El último sigue siendo A[t−1], que es igual a A[t]. ✓
I₀ vale porque t < N implica 0 ≤ t + 1 ≤ N. Los tres invariantes son
estables. ✓ Fíjese en que los casos 2 y 3 usan I₂ para pasar de
«el último de res» a «A[t−1]». Sin ese invariante la comparación del
código no se puede relacionar con el enunciado, y la demostración se
queda sin argumento.
Terminación: ¿con qué valor de i termina el ciclo, y de dónde sale?
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, y
junto con I₀ queda i = N. Sustituyendo en I₁: res es A[0..N) sin
repeticiones consecutivas, que es la poscondición. ∎
Teorema 2. La invocación comprimir(A) sobre cualquier
arreglo A devuelve A sin repeticiones consecutivas.
Demostración: por el Teorema 1 los invariantes se cumplen; la
terminación deja i = N y sustituir en I₁ da la poscondición. ∎
Dos cosas para llevarse. La longitud de res no aparece en
ningún invariante: no hacía falta, porque decir qué es la lista ya
fija cuántos elementos tiene. Y el invariante que costó encontrar, I₂, no
habla de la salida sino de la relación entre la salida y la entrada; es
el puente entre lo que el código compara y lo que el enunciado pide.
6. Para llevarse
Sin solución aquí. Modifique comprimir
para que además construya una segunda lista veces, donde
veces[t] sea el largo de la racha que dejó res[t].
Escriba el invariante que relaciona las dos listas —tendrá que decir algo
sobre la suma de veces— y demuestre los tres pasos. Después
responda, en términos de N: ¿cuál es la longitud más corta y la más larga
que puede tener res, y con qué entradas?