Utente:Lorsss98/Algoritmo randomizzato
In informatica, un algoritmo randomizzato è una procedura che contiene passi non-deterministici, ovvero istruzioni che prevedono decisioni casuali.
Algorimo Las Vegas[modifica | modifica wikitesto]
Un algoritmo randomizzato Las Vegas è una procedura che termina sempre con un output corretto. Al suo interno contiene decisioni casuali che potranno rallentare o velocizzare l'algoritmo in base a quanto sia "fortunata" l'esecuzione dell'algoritmo. Un esempio di algoritmo Las Vegas è il Quicksort con partizionamento casuale. Ad ogni iterazione questo algoritmo sceglie come pivot un elemento casuale della sequenza input e sposta gli elementi minori del pivot alla sua sinistra e gli elementi maggiori del pivot alla sua destra. Se l'algoritmo sceglie casualmente come pivot un numero di grandezza media, l'algoritmo avrà migliori prestazioni e sarà più veloce.
Algoritmo Monte Carlo[modifica | modifica wikitesto]
Un Algoritmo randomizzato Monte Carlo è una procedura con passi casuali che a volte termina con un output sbagliato. Per sviare il problema l'algoreitmo viene eseguito piu' volta finchè non restituisce un output corretto.