← Volver a los ejercicios

La mayor diferencia: los invariantes del recorrido

UVa 11078, Open Credit System, pide el mayor valor de A[i] − A[k] con i < k. El enunciado está en https://vjudge.net/problem/UVA-11078. La solución lo resuelve con un solo recorrido y dos acumuladores. Aquí se busca lo que ese recorrido sostiene en cada chequeo del while, se escribe como fórmula y se demuestra en tres pasos: inicialización, estabilidad y terminación.

1. La especificación y la predicción

Entrada: un arreglo A[0..N) de enteros con N ≥ 2.  Salida: máx {A[i] − A[k] : 0 ≤ i < k < N}.

Arreglo:
Los tres últimos son los casos del enunciado.
¿Qué devuelve mayorDiferencia(A)?

2. Ejecute y mire

Paso 0 de 0
Las casillas azules son A[0..j), las que el ciclo ya leyó. Cada vez que la ejecución pasa por la línea 5, el while evalúa su condición y la terna (j, maximo, mejor) queda en la tabla.

3. La traza por estados

Chequeojmaximomejor¿Qué se repite?
Una fila en rojo es el chequeo donde falla la fórmula que eligió en la tarjeta 4. La columna de la derecha se llena cuando acierte los tres invariantes.

4. Los invariantes

Busque lo que se cumple en todas las filas, incluida la primera y la última, escrito en términos de N, j y A. Para abreviar, Dj = {A[i] − A[k] : 0 ≤ i < k < j} es el conjunto de las diferencias cuyas dos posiciones ya se leyeron.

¿Entre qué valores se mueve j en los chequeos? (I₀)
¿Qué guarda maximo? (I₁)
¿Y mejor? (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 1 a 4, ¿qué vale (j, maximo, mejor)?
Para I₀: 1 ≤ 1 ≤ N, que vale porque la precondición pide N ≥ 2. ✓  Para I₁: {A[t] : 0 ≤ t < 1} = {A[0]}, cuyo máximo es A[0] = maximo. ✓  Para I₂: no hay i, k con 0 ≤ i < k < 1, así que D₁ = ∅ y máx (∅ ∪ {A[0] − A[1]}) = A[0] − A[1] = mejor. ✓
Estabilidad. Se toma una vuelta con j = t, 1 ≤ t < N, y se asumen I₀, I₁ e I₂ en t. ¿Qué parejas tiene Dt+1 que Dt no tenía?
Dt+1 = Dt ∪ {A[i] − A[t] : 0 ≤ i < t}.
¿Cuál es la mayor de esas diferencias nuevas?
máx {A[i] − A[t] : 0 ≤ i < t} = (máx {A[i] : 0 ≤ i < t}) − A[t] = maximo − A[t], por I₁ en t.
La línea 6 usa maximo antes de que la línea 9 lo actualice. ¿Por qué ese orden?
I₂ en t + 1. Las líneas 6 y 7 dejan mejor' = máx (mejor, maximo − A[t]). Por I₂ en t y el paso anterior, mejor' = máx (máx (Dt ∪ {A[0] − A[1]}), máx {A[i] − A[t] : 0 ≤ i < t}) = máx (Dt+1 ∪ {A[0] − A[1]}). ✓

I₁ en t + 1. Las líneas 8 y 9 dejan maximo' = máx (maximo, A[t]) = máx (máx {A[i] : 0 ≤ i < t}, A[t]) = máx {A[i] : 0 ≤ i < t + 1}, usando I₁ en t. ✓

I₀ en t + 1. La línea 10 deja j = t + 1, y de 1 ≤ t < N sale 2 ≤ t + 1 ≤ N, luego 1 ≤ t + 1 ≤ N. ✓

La estabilidad de I₂ usó I₁; la de I₁ no usó I₂. Por eso se enuncian juntos.
Terminación: ¿con qué valor de j termina el ciclo?
El ciclo termina porque j crece de 1 en 1 e I₀ lo acota por N. Al salir, la condición j < N es falsa, o sea j ≥ N; con j ≤ N de I₀ queda j = N. Sustituyendo en I₂: mejor = máx (DN ∪ {A[0] − A[1]}). Como N ≥ 2, la pareja (0, 1) está en DN, así que mejor = máx DN = máx {A[i] − A[k] : 0 ≤ i < k < N}, que es la poscondición. ∎
Teorema 2. La invocación mayorDiferencia(A) sobre cualquier arreglo con N ≥ 2 devuelve máx {A[i] − A[k] : 0 ≤ i < k < N}. Demostración: por el Teorema 1 los invariantes se cumplen; la terminación deja j = N, y sustituir ese valor en I₂ da la poscondición. ∎

El recorrido hace N − 1 vueltas de costo constante: O(N), contra las N(N − 1)/2 parejas que revisa la solución con dos ciclos.

6. Para llevarse

Sin solución aquí. Cambie el código para que arranque con j = 2, maximo = máx (A[0], A[1]) y mejor = A[0] − A[1]. ¿Qué dicen ahora I₀ e I₂? ¿Sigue haciendo falta el término {A[0] − A[1]}? Después agregue dos variables que guarden la pareja (i, k) de la mejor diferencia y escriba su invariante.