Differenza tra algoritmo deterministico e non deterministico in informatica

Che cos’è un algoritmo deterministico?

L’algoritmo deterministico (in inglese Deterministic Algorithms) è l’algoritmo che, dato un particolare input, produrrà sempre lo stesso output, con la macchina sottostante che passa sempre attraverso la stessa sequenza di stati. In altre parole, l’algoritmo deterministico fornirà sempre lo stesso risultato con gli stessi input.

Gli algoritmi deterministici sono di gran lunga il tipo di algoritmo più studiato e familiare, nonché uno dei più pratici, poiché possono essere eseguiti su macchine reali in modo efficiente. Formalmente, un algoritmo deterministico calcola una funzione matematica; una funzione ha un valore univoco per qualsiasi input nel suo dominio e l’algoritmo è un processo che produce questo particolare valore come output.

Gli algoritmi deterministici possono essere definiti in termini di una macchina a stati: uno  stato  descrive ciò che una macchina sta facendo in un particolare istante di tempo. Le macchine a stati passano in modo discreto da uno stato all’altro. Subito dopo entriamo l’ingresso, la macchina è nel suo  stato iniziale  o di  avvio dello stato . Se la macchina è deterministica, significa che da questo punto in poi il suo stato corrente determina quale sarà il suo stato successivo; il suo corso attraverso l’insieme degli stati è predeterminato. Si noti che una macchina può essere deterministica e tuttavia non si ferma o non finisce mai, e quindi non riesce a fornire un risultato.

Esempi di particolari macchine astratte deterministiche includono la  macchina di Turing  deterministica e l’ automa finito deterministico .

Caratteristiche algoritmo deterministico

• L’algoritmo deterministico è l’algoritmo che, dato un particolare input, produrrà sempre lo stesso output, con la macchina sottostante che passa sempre attraverso la stessa sequenza di stati.  
• Nell’algoritmo deterministico il percorso di esecuzione dell’algoritmo è lo stesso in ogni esecuzione.
• In base all’esecuzione e al risultato in caso di algoritmo deterministico, vengono classificati anche come algoritmi affidabili in quanto per una particolare istruzione di input la macchina darà sempre lo stesso output.
• Nell’esecuzione degli algoritmi deterministici, la macchina di destinazione esegue la stessa istruzione e produce lo stesso risultato che non dipende dal modo o dal processo in cui l’istruzione viene eseguita.
• Poiché il risultato è noto ed è coerente su diverse esecuzioni, l’algoritmo deterministico richiede tempo polinomiale per la loro esecuzione.

Che cos’è un algoritmo non deterministico?

Un algoritmo non deterministico (in inglese Non-deterministic Algorithms) è un algoritmo che, anche per lo stesso input, può esibire comportamenti diversi su corse diverse. In altre parole, è un algoritmo in cui il risultato di ogni algoritmo non è definito in modo univoco e il risultato potrebbe essere casuale.

Un algoritmo che risolve un problema in tempo polinomiale non deterministico può funzionare in tempo polinomiale o tempo esponenziale a seconda delle scelte che fa durante. Gli algoritmi non deterministici sono spesso usati per trovare un’approssimazione a una soluzione, quando la soluzione esatta sarebbe troppo costosa usando una soluzione deterministica.

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. 

Cosa rende un algoritmo non deterministico?

Una varietà di fattori può far sì che un algoritmo si comporti in un modo che non è deterministico o non deterministico:

• Se utilizza uno stato esterno diverso dall’input, come l’input dell’utente, una variabile globale, un valore del timer hardware, un valore casuale o dati del disco memorizzati.
• Se funziona in modo sensibile al tempo, ad esempio se ha più processori che scrivono sugli stessi dati contemporaneamente. In questo caso, l’ordine preciso in cui ciascun processore scrive i propri dati influirà sul risultato.
• Se un errore hardware fa sì che il suo stato cambi in modo imprevisto.

Caratteristiche algoritmo non deterministico

• Gli algoritmi non deterministici sono gli algoritmi in cui il risultato di ogni algoritmo non è definito in modo univoco e il risultato potrebbe essere casuale.
• Nell’algoritmo non deterministico il percorso di esecuzione non è lo stesso per l’algoritmo in ogni esecuzione e potrebbe prendere qualsiasi percorso casuale per la sua esecuzione.
• Gli algoritmi non deterministici sono classificati come algoritmi non affidabili per un particolare input che la macchina fornirà output diverso su diverse esecuzioni.
• Negli algoritmi non deterministici, la macchina che esegue ciascuna operazione può scegliere uno qualsiasi di questi risultati soggetti a una condizione di determinazione da definire in seguito.
• Poiché il risultato non è noto e non è coerente su diverse esecuzioni, l’algoritmo non deterministico non può essere eseguito in tempo polinomiale.

Differenza tra algoritmo deterministico e non deterministico

BASE DI CONFRONTO	ALGORITMO DETERMINISTICO	ALGORITMO NON DETERMINISTICO
Descrizione	L’algoritmo deterministico è l’algoritmo che, dato un particolare input, produrrà sempre lo stesso output, con la macchina sottostante che passa sempre attraverso la stessa sequenza di stati.	Gli algoritmi non deterministici sono gli algoritmi in cui il risultato di ogni algoritmo non è definito in modo univoco e il risultato potrebbe essere casuale.
Percorso di esecuzione	Nell’algoritmo deterministico il percorso di esecuzione dell’algoritmo è lo stesso in ogni esecuzione.	Nell’algoritmo non deterministico il percorso di esecuzione non è lo stesso per l’algoritmo in ogni esecuzione e potrebbe prendere qualsiasi percorso casuale per la sua esecuzione.
Base di confronto	In base all’esecuzione e al risultato in caso di algoritmo deterministico, vengono classificati anche come algoritmi affidabili in quanto per una particolare istruzione di input la macchina darà sempre lo stesso output.	Gli algoritmi non deterministici sono classificati come algoritmi non affidabili per un particolare input che la macchina fornirà output diverso su diverse esecuzioni.
Operazione	Nell’esecuzione degli algoritmi deterministici, la macchina di destinazione esegue la stessa istruzione e produce lo stesso risultato che non dipende dal modo o dal processo in cui l’istruzione viene eseguita.	Negli algoritmi non deterministici, la macchina che esegue ciascuna operazione può scegliere uno qualsiasi di questi risultati soggetti a una condizione di determinazione da definire in seguito.
Output	Poiché il risultato è noto ed è coerente su diverse esecuzioni, l’algoritmo deterministico richiede tempo polinomiale per la loro esecuzione.	Poiché il risultato non è noto e non è coerente su diverse esecuzioni, l’algoritmo non deterministico non può essere eseguito in tempo polinomiale.