Algoritmo randomizzato: differenze tra le versioni

Versione delle 15:05, 6 nov 2020

Versione attuale delle 17:04, 16 mar 2025

(4 versioni intermedie di 3 utenti non mostrate)

Riga 1:

{{S|algoritmi}}

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 6:

Gli algoritmi randomizzati sono particolarmente utili di fronte a utenti malevoli, e quindi ampiamente utilizzati con applicazioni [[Crittografia|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]] <ref>{{Cita pubblicazione|autorecognome=Hoare|nome=C. A. R.|data=Julyluglio 1961|titolo=Algorithm 64: Quicksort|rivista=Commun. ACM|volume=4|numero=7|ppp=321–321|doi=10.1145/366622.366644|issn=0001-0782}}</ref>.

In alcuni casi, gli algoritmi probabilistici sono l'unico mezzo pratico per risolvere un problema <ref>"In [[Primality test|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>.

In alcuni casi, gli algoritmi probabilistici sono l'unico mezzo pratico per risolvere un problema<ref>{{Cita libro|cognome=Abelson|nome=Hal|cognome2= Sussman|nome2=Gerald J.|titolo=Structure and Interpretation of Computer Programs|anno=1996|editore=MIT Press}}</ref>.

== Note ==

<nowiki><references/></nowiki>

{{portale|informatica}}

[[Categoria:Statistica computazionale]]

[[Categoria:Algoritmi]]