Demostrar que un algoritmo recursivo sobre un conjunto es verdadero

Question

Si tengo un algoritmo que devuelve la entrada de un conjunto con el mayor valor, ¿cómo demuestro que el algoritmo es verdadero matemáticamente ? (Sé que podría escribir pruebas para ello.) Entiendo cómo utilizar la inducción matemática para demostrar un algoritmo recursivo sobre una relación de recurrencia lineal o una secuencia.

Creo que la diferencia con la que estoy teniendo dificultades es que una prueba inductiva de una secuencia o ecuación trata con variables escalares, mientras que un algoritmo que devuelve la entrada de un conjunto con el mayor valor trata con variables de conjunto con múltiples entradas y de longitud arbitraria.

Aquí está el sencillo algoritmo en pseudocódigo, por si le sirve a alguna persona amable que me ayude con esto:

function maximum(Set s) {
  if (s.length == 0) {
    return null;
  } else if (s.length == 1) {
    return s[0];
  } else if (s[0] > s[s.length - 1]) {
    s = s.removeLast();
    return maximum(s);
  } else {
    s = s.removeFirst();
    return maximum(s);
  }
}

Que removeFirst y removeLast devuelvan una nueva vista del conjunto, para que el conjunto original no sea troceado.

Así que no sé cómo aplicar la inducción a esto o si debo utilizar algún otro método.

Gracias de antemano por cualquier ayuda.

Chris

Answer 1

Supongo que se puede demostrar que el algoritmo devuelve la respuesta correcta para cualquier conjunto de entrada de tamaño $1$ .

Supongamos que ha demostrado que el algoritmo devuelve la respuesta correcta para cualquier conjunto de entrada de tamaño $n-1$ . Entonces, dado un tamaño $n$ conjunto, el primer elemento es mayor que el último, o no. Si lo es, el elemento mayor no es el último, por lo que debe estar dentro del primer $n-1$ elementos, y por lo tanto es igual a maximum(s.removeLast()) (porque sabemos que cualquier $n-1$ -sistema de tamaño t tiene un máximo igual a maximum(t) ).

De nuevo, si el primer elemento no es mayor que el último, entonces el elemento máximo debe estar dentro del último $n-1$ elementos, y por lo tanto es igual a maximum(s.removeFirst()) .