Algoritmo non deterministico - Nondeterministic algorithm
Nella programmazione di computer , un algoritmo non deterministico è un algoritmo che, anche per lo stesso input, può esibire comportamenti diversi su corse diverse, a differenza di un algoritmo deterministico . Esistono diversi modi in cui un algoritmo può comportarsi in modo diverso da un'esecuzione all'altra. Un algoritmo simultaneo può funzionare in modo diverso su esecuzioni diverse a causa di una condizione di gara . Un algoritmo probabilistico 's comportamenti dipende da un generatore di numeri casuali . Un algoritmo che risolve un problema in tempo polinomiale non deterministico può essere eseguito in tempo polinomiale o tempo esponenziale a seconda delle scelte che fa durante l'esecuzione. Gli algoritmi non deterministici vengono spesso utilizzati per trovare un'approssimazione a una soluzione, quando la soluzione esatta sarebbe troppo costosa da ottenere utilizzando una soluzione deterministica.
La nozione è stata introdotta da Robert W. Floyd nel 1967.
Uso
Spesso nella teoria computazionale , il termine "algoritmo" si riferisce a un algoritmo deterministico . Un algoritmo non deterministico è diverso dalla sua controparte deterministica più familiare nella sua capacità di arrivare a risultati utilizzando vari percorsi. Se un algoritmo deterministico rappresenta un singolo percorso da un input a un risultato, un algoritmo non deterministico rappresenta un singolo percorso derivante da molti percorsi, alcuni dei quali possono arrivare allo stesso output e alcuni dei quali possono arrivare a output unici. Questa proprietà viene catturata matematicamente in modelli di calcolo "non deterministici" come l' automa finito non deterministico . In alcuni scenari, tutti i percorsi possibili possono essere eseguiti contemporaneamente.
Nella progettazione di algoritmi, gli algoritmi non deterministici vengono spesso utilizzati quando il problema risolto dall'algoritmo consente intrinsecamente più risultati (o quando esiste un unico risultato con più percorsi attraverso i quali il risultato può essere scoperto, ciascuno ugualmente preferibile). Fondamentalmente, ogni risultato prodotto dall'algoritmo non deterministico è valido, indipendentemente dalle scelte che l'algoritmo fa durante l'esecuzione.
Nella teoria della complessità computazionale , gli algoritmi non deterministici sono quelli che, ad ogni possibile passo, possono consentire più continuazioni (immagina una persona che cammina lungo un sentiero in una foresta e, ogni volta che fa un passo avanti, deve scegliere quale bivio desidera prendere). Questi algoritmi non arrivano a una soluzione per ogni possibile percorso computazionale; tuttavia, è garantito che arrivino a una soluzione corretta per alcuni percorsi (cioè, la persona che cammina attraverso la foresta può trovare la propria capanna solo se sceglie una combinazione di percorsi "corretti"). Le scelte possono essere interpretate come ipotesi in un processo di ricerca .
Un gran numero di problemi può essere concettualizzato attraverso algoritmi non deterministici, inclusa la più famosa questione irrisolta nella teoria informatica, P vs NP .
Implementazione di algoritmi non deterministici con algoritmi deterministici
Un modo per simulare un algoritmo non deterministico N utilizzando un algoritmo deterministico D è quello di trattare serie di stati di N come stati di D . Ciò significa che D traccia simultaneamente tutti i possibili percorsi di esecuzione di N (vedi costruzione powerset per questa tecnica in uso per automi finiti ).
Un altro è la randomizzazione , che consiste nel lasciare che tutte le scelte siano determinate da un generatore di numeri casuali . Il risultato è chiamato algoritmo deterministico probabilistico .
Guarda anche
Riferimenti
Ulteriore lettura
- Cormen, Thomas H. (2009). Introduzione agli algoritmi (3a ed.). MIT Press. ISBN 978-0-262-03384-8 .
- "Algoritmo non deterministico" . Istituto nazionale di standard e tecnologia . Estratto il 7 luglio 2013 .
- "Algoritmi non deterministici" . Informatica della New York University . Estratto il 7 luglio 2013 .
