Algoritm randomizat
Un algoritm randomizat este un algoritm care include un anumit grad de aleatorie în logica sa. De obicei, algoritmul utilizează variabile aleatorii ca intrare auxiliară pentru a-și ghida comportamentul cu scopul de a obține, în medie , performanțe bune. Performanța algoritmului, inclusiv timpul de execuție sau ieșirea, va fi, de asemenea, aleatorie.
Pe baza utilizării variabilelor aleatorii, algoritmul poate fi conceput pentru a returna întotdeauna răspunsul corect ( algoritmul Las Vegas ), în detrimentul timpului de calcul sau pentru a prezice, de asemenea, că rezultatul calculat poate fi greșit cu o anumită probabilitate ( Monte Algoritmul Carlo ).
Algoritmii randomizați sunt deosebit de utili în fața utilizatorilor rău intenționați și, prin urmare, sunt folosiți pe scară largă cu aplicațiile criptografice ; în aceste cazuri, totuși, sunt necesare măsuri pentru a preveni prezicerea numerelor pseudo-aleatorii , făcând algoritmul în mod substanțial determinist.
Un exemplu tipic de algoritm randomizat este rapidul rapid [1] .
În unele cazuri, algoritmii probabilistici sunt singurul mijloc practic de rezolvare a unei probleme [2] .
Notă
- ^ CAR Hoare, Algoritm 64: Quicksort , în Commun. ACM , voi. 4, nr. 7, iulie 1961, pp. 321–, DOI : 10.1145 / 366622.366644 , ISSN 0001-0782 .
- ^ Hal Abelson și Gerald J. Sussman, Structura și interpretarea programelor de calculator , MIT Press , 1996.
