Estrategia del Adversario

La estrategia del adversario se usa para demostrar cotas inferiores de peor caso. La idea es demostrar que, para responder correctamente frente a cualquier input, el algoritmo necesita aprender lo suficiente sobre el input, y para ello debe pagar un cierto costo. La figura del adversario se utiliza como metáfora del peor caso. El adversario actúa como intermediario entre el algoritmo y el input. Cada vez que el algoritmo paga el costo de preguntar algo sobre el input, el adversario decide qué responder. Es decir, el input no existe de antemano, sino que el adversario lo va construyendo de modo de provocar el costo más alto posible al algoritmo. Su única restricción es que lo que responde debe ser consistente, es decir, debe existir algún input cuyas respuestas a las preguntas del algoritmo sean las mismas que las del adversario.

Un ejemplo ilustrativo es el juego de las 20 preguntas. Éste consiste en que un jugador $A$ piensa en un personaje $X$ y el otro jugador $B$ debe adivinar el personaje mediante hacer a lo sumo 20 preguntas a $A$, de respuesta sí/no. Aquí $B$ es el algoritmo y $A$ actúa como adversario, haciendo de interfaz entre $B$ y el personaje que tiene en mente. ¿Alguna vez jugó a este juego? ¿Se le ocurrió, siendo $A$, no decidir $X$ de entrada sino irlo definiendo a medida que $B$ preguntaba, para asegurarse de que $B$ nunca llegara a una respuesta correcta en 20 preguntas? ¿De qué debe cuidarse si hace esto?

En general, para aplicar este método requerimos crear un modelo de lo que el algoritmo va aprendiendo acerca del input. El modelo debe tener un estado inicial, que corresponde al comienzo de la ejecución, cuando el algoritmo no sabe nada del input. Debe tener uno o más estados finales, cuando el algoritmo aprendió lo suficiente del input como para responder correctamente. Y el mínimo costo de llegar del estado inicial a algún estado final es una cota inferior al costo del algoritmo: no importa qué algoritmo sea, este modelo es válido e implica que el algoritmo no puede responder siempre correctamente si no paga un cierto costo. El rol del adversario es elegir el peor resultado posible (que el algoritmo avance lo menos posible hacia un estado final) por cada acción que realiza. Veremos la forma de aplicar esta técnica a lo largo de varios ejemplos.

📄️ Búsqueda en un arreglo

Como un caso muy simple, que ni siquiera requiere de un modelo,

📄️ Máximo de un arreglo

Consideremos el problema de buscar el máximo elemento en un arreglo $A[1,n]$

📄️ Mínimo y máximo de un arreglo

Consideremos ahora el problema de encontrar el mínimo y el máximo de un arreglo

📄️ Máximo y segundo máximo de un arreglo

Supongamos que deseamos encontrar el máximo y el segundo máximo elemento de

📄️ Mediana de un arreglo

Encontrar la mediana $z$ de un arreglo $A[1,n]$ (con $n$ impar) es un problema