[curiosità] Algoritmi non deterministici

[Kashaman]

dalle dispense in mio possesso, sono incappato nella definizione di
algoritmo deterministico
cioè un algoritmo $A$ si dice deterministico se al momento della sua esecuzione sono note tutte le istruzioni da compiere. Cioè nota un'istruzione è nota anche quella successiva.
effetto $A$, al variare degli esecutori, produce sempre gli stessi risultati.
algoritmo non deterministico se non è deterministico. cioè se non sono note le istruzioni in maniera sequenziale.
tuttavia, di quest'ultimo , non ho trovato esempi.
che tipo di algoritmo si tratta? quando viene impiegato? un possibile esempio quale sarebbe?
grazie mille.

[hamming_burst]

"Kashaman":algoritmo non deterministico se non è deterministico. cioè se non sono note le istruzioni in maniera sequenziale.
tuttavia, di quest'ultimo , non ho trovato esempi.
che tipo di algoritmo si tratta? quando viene impiegato? un possibile esempio quale sarebbe?
grazie mille.

sono modelli teorici. Il discorso però è lunghetto ed ha tante sfaccettature che ci sono teorie autonome che ne descrivono le caratteristiche. Un'infarinatura la trovi su wiki en: http://en.wikipedia.org/wiki/Nondeterministic_algorithm

Un'utilità pratica di un algoritmo nondeterministico, o meglio una "scelta nondeterministica" (che fa parte di tali modelli) la si trova nei programmi concorrenti o se preferisci un esempio pratico, nelle macchinette del caffè c'è un principio di operatore nondeterministico.

[apatriarca]

In generale, un algoritmo non è deterministico se dipende da un qualche processo o scelta casuale. Abbiamo quindi per esempio algoritmi non-deterministici (quasi) ogni volta che vogliamo cercare di modellare un processo casuale come il mescolamento delle carte da gioco, il lancio di un dado.. Abbiamo poi situazioni in cui il calcolo preciso di una qualche quantità non sia molto pratico, mentre il calcolo di un valore approssimato (con un errore casuale dato da una certa distribuzione) sia fattibile. Abbiamo poi situazioni in cui scelte casuali possano ridurre la complessità di un algoritmo (vedi il quicksort nella scelta del pivot per esempio).

[Kashaman]

grazie mille ragazzi, siete stati molto chiari e mi avete reso l'idea. E io che pensavo che le macchinette del caffè funzionassero tipo come uno switch