Algoritmi randomizzati
| Approfondimenti | Info |
|---|---|
Quest'argomento non è collegato ad altri approfondimenti correlati. Si consiglia, in ogni caso, di controllare sempre [ l'Indice ] degli Approfondimenti | Questa pagina è solo improntata in attesa di completamento da parte dei Collaboratori. Se sei interessato a collaborare attivamente con Extrapedia, leggi come fare [ Collabora ] |
Un Algoritmo randomizzato è un Algoritmo che utilizza un grado di casualità come parte della sua logica. L'algoritmo in genere utilizza bit uniformemente casuali come input ausiliari per guidare il suo comportamento, nella speranza di ottenere buone prestazioni nel “caso medio” su tutte le possibili scelte di bit casuali. Formalmente, la performance dell'algoritmo sarà una variabile casuale determinata dai bit casuali; quindi, sia il tempo di esecuzione, sia l'uscita (o entrambi) sono variabili casuali.
Si deve distinguere tra algoritmi che usano l'input casuale in modo che terminino sempre con la risposta corretta, ma dove il tempo di esecuzione previsto è finito (Algoritmi di Las Vegas, per esempio Quicksort) 1) e algoritmi che hanno la possibilità di produrre un risultato errato (Algoritmi di Monte Carlo, per esempio l'Algoritmo di Monte Carlo per il problema MFAS), 2) o non riescono a produrre un risultato segnalando un errore o non riuscendo a terminare.
Nel secondo caso, prestazioni casuali e output casuali, il termine “algoritmo” per una procedura è alquanto discutibile. Nel caso di output casuali, non è più formalmente efficace. 3) Tuttavia, in alcuni casi, gli algoritmi probabilistici sono gli unici mezzi pratici per risolvere un problema. 4)
Nella pratica comune, gli Algoritmi randomizzati sono approssimati usando un generatore di numeri pseudocasuali al posto di una vera fonte di bit casuali; tale implementazione può deviare dal comportamento teorico previsto.
“Qualora alcuni link non funzionassero, si prega di comunicarlo allo Staff - staff@extrapedia.org”
Strumenti Pagina
