Algoritmo randomizzato: differenze tra le versioni
fix formato e note |
+S, +categorie |
||
| Riga 1: | Riga 1: | ||
{{S|informatica}} |
|||
Un '''algoritmo randomizzato''' è un [[algoritmo]] che include un certo grado di [[Aleatorietà|casualità]] nella sua logica. Tipicamente l'algoritmo utilizza [[Variabile casuale|variabili aleatorie]] come input ausiliario per guidare il suo comportamento con l'obiettivo di ottenere, [[Valore atteso|in media]], buone prestazioni. Le prestazioni dell'algoritmo, inclusi il tempo di esecuzione o l'output, saranno a loro volta casuali. |
Un '''algoritmo randomizzato''' è un [[algoritmo]] che include un certo grado di [[Aleatorietà|casualità]] nella sua logica. Tipicamente l'algoritmo utilizza [[Variabile casuale|variabili aleatorie]] come input ausiliario per guidare il suo comportamento con l'obiettivo di ottenere, [[Valore atteso|in media]], buone prestazioni. Le prestazioni dell'algoritmo, inclusi il tempo di esecuzione o l'output, saranno a loro volta casuali. |
||
| Riga 13: | Riga 14: | ||
{{portale|informatica}} |
{{portale|informatica}} |
||
[[Categoria:Statistica computazionale]] |
|||
[[Categoria:Algoritmi]] |
|||
Versione delle 15:12, 6 nov 2020
Un algoritmo randomizzato è un algoritmo che include un certo grado di casualità nella sua logica. Tipicamente l'algoritmo utilizza variabili aleatorie come input ausiliario per guidare il suo comportamento con l'obiettivo di ottenere, in media, buone prestazioni. Le prestazioni dell'algoritmo, inclusi il tempo di esecuzione o l'output, saranno a loro volta casuali.
In base all'utilizzo che viene fatto delle variabili casuali, l'algoritmo può essere progettato per restituire sempre la risposta corretta (algoritmo Las Vegas), a scapito del tempo di calcolo, o per prevedere anche che il risultato calcolato possa essere errato con una certa probabilità (algoritmo Monte Carlo).
Gli algoritmi randomizzati sono particolarmente utili di fronte a utenti malevoli, e quindi ampiamente utilizzati con applicazioni crittografiche; in questi casi, tuttavia, sono necessari accorgimenti per evitare che i numeri pseudo-casuali vengano predetti, rendendo l'algoritmo sostanzialmente deterministico.
Un tipico esempio di algoritmo randomizzato è il quicksort [1].
In alcuni casi, gli algoritmi probabilistici sono l'unico mezzo pratico per risolvere un problema [2].
Note
- ^ C. A. R. Hoare, Algorithm 64: Quicksort, in Commun. ACM, vol. 4, n. 7, July 1961, pp. 321–, DOI:10.1145/366622.366644, ISSN 0001-0782.
- ^ Hal Abelson e Gerald J. Sussman, Structure and Interpretation of Computer Programs, MIT Press, 1996.