Page 181 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 181
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
a. Choice(S)... en forma arbitraria se escoge un elemento del conjunto S.
b. Failure... señala una terminación sin éxito.
c. Success... señala una terminación con éxito.
X choice (1: n) puede resultar en X la asignación de un entero en el rango [1, n]. No existe una
regla especifica de cómo se escogió el número entero. La señal de éxito o no éxito se utiliza para
definir un estado del algoritmo. Estas declaraciones son equivalentes a definir un stop y no son uti-
lizadas para efectuar un retorno. Un algoritmo termina sin éxito si y solo si no existe un conjunto de
elecciones que conduzcan al éxito.
Los tiempos de cómputo para choice, success y failure son tomados como O (1). Una máquina que
sea capaz de ejecutar un algoritmo no determinístico se conoce como máquina no determinística.
Mientras no exista una máquina no determinística (como la definida en este escrito), se tienen las su-
ficientes razones intuitivas para concluir que ciertos problemas no se pueden resolver en algoritmos
determinísticos en tiempo polinomial.
Por ejemplo: considere el problema de buscar para un elemento x en un conjunto dado de elemen-
tos A(1: n), n ≥1. Se requiere determinar el índice tal que A(j) = x o j = 0 si x no se encuentra en A. Un
algoritmo no determinístico es este:
j choice (1: n)
if A(j) =x entonces
imprime(j)
success
endif
else
print (‘0’);
failure
En este ejemplo, una computadora no determinística imprimirá un cero si y solo si no existe algún
j tal que A(j) = x. El algoritmo es no determinístico con complejidad O(1). Note que como A no está
ordenado, cualquier algoritmo determinístico de búsqueda tiene una complejidad Ω(n).
Una interpretación de un algoritmo no determinístico puede ser permitida utilizando una computa-
dora paralela sin límites. Se puede hacer en cada instante cada choice(S), el algoritmo realiza varias
copias de él mismo. Una copia para cada choice(S), por lo que todas las copias son ejecutadas al
mismo tiempo. La primera copia que termine con un sucessful obliga que terminen las demás co-
175
