Hazardigita algoritmo

Hazardigita algoritmo aŭ probableca algoritmo estas algoritmo kiu uzas iun gradon de hazardon kiel parto de sia logiko. En komuna praktiko, ĉi tio signifas ke la maŝino realiganta la algoritmon havas atingon al kvazaŭstokasta generilo. Por ĉi tiuj algoritmoj la plej malbona okazo estas tipe malverŝajna kaj tiel povas esti ignorita.

Motivado

Konsideru problemon de trovo de valoro a en tabelo de n eroj, se duono de la eroj estas a' kaj la alia duono estas b' La evidenta maniero estas trarigardi ĉiu eron de la tabelo ekde komenco, sed ĉi tio prenas n/2 operaciojn se la tabelo estas ordigita tiel ke b estas unuaj. Eblas kontroli en la rea ordo, aŭ kontroli ĉiun duan eron, sed por ĉiu ĉi tia strategio ekzistas ordo de eroj en la tabelo je kiu bazonatas n/2 operaciojn. Do kun determinisma algoritmo, se malica atakanto kiu intence penas nutri malbonan enigon al la algoritmo, oni ne povas garantii pli bonan tempon ol n/2.

Aliflanke, se kontroli tabelajn erojn hazarde, tiam oni rapide trovas na a kun alta probablo.

En ĉifrikaj aplikoj, pseŭdo-stokastoj ne povas esti uzataj, pro tio ke la atakanto povas antaŭdiri ilin, farante la algoritmon efike determinisman. Pro ĉi tio fonto de veraj stokastoj aŭ ĉifrike sekura pseŭdo-stokasta generilo estas bezonata. Alia tereno en kiu hazardo estas nepra estas kvantumo komputado.

En la ekzemplo pli supre, la hazardigita algoritmo ĉiam donas korektan respondon, sed estas malgranda probablo de preno de longa tempo por ruliĝi. Ĉi tiu speco estas algoritmo de Las Vegas. Iam oni bezonas algoritmon kiu ĉiam ruliĝas rapide, sed permesas malgrandan probablon de eraro. Ĉi tiu speco estas montekarla algoritmo. Algoritmo de Las Vegas povas esti konvertita en montekarlan algoritmon, per haltigo de ĝi post certa tempo kaj rezultigo de ajna, eble malĝusta, respondo.

Hazardigita montekarla maniero estadas uzata por integralado.

Plej popularaj primeco-testoj estas hazardigitaj algoritmoj. Ĉi tiuj testoj uzas, krom la testata nombro n, iujn aliajn nombrojn a kiuj estas elektataj je hazarde de iu aro. La probablo de eraro povas reduktiĝas per ripetado de la testo kun multaj sendepende elektitaj a; por du kutime uzataj testoj, por ĉiu komponita n almenaŭ duono de la a detektas komponitecon de n. Tiel k ripetadoj reduktas la eraran probablon al maksimume 2^−k, kiu povas esti farita sufiĉe malgranda per pligrandiĝo de k.

La baza strukturo de hazardigita primeco-testo estas jena:

Ripeti certan kvanton da fojoj:
- Hazarde preni nombron a.
- Kontroli iun egaleco kun a kaj la donita nombro n. Se la egaleco ne veras, do n estas komponita nombro, kaj la testo haltas.
Se la testo ankoraŭ ne haltiĝis kun rezulto ke n estas komponita, do nun rezultigi ke n estas primo.

En praktiko, taŭgas akcepti malgrandan probablon de eraro, kiu povas esti farita astronomie malgrandan. Kaj, eĉ kvankam determinismaj polinomo-tempaj primeco-testoj estas ellaboritaj, ili ne anstataŭigas la pli malnovajn probablecajn testojn en ĉifrika programaro, kaj ĉi tiu anstataŭigo ne estas atendata por la antaŭvidebla estonto.

Se la probablo de eraro de hazardigita maniero estas ekzemple 2⁻¹⁰⁰⁰, ĝi estas klare pli malgranda ol la probablo de eraro en la aparataro ruliganta ĝin.

Rapida ordigo estas familiara, kutime uzita algoritmo en kiu hazardo povas esti utila. La determinisma, versio de ĉi tiu algoritmo postulas tempon O(n²) por ordigi n nombrojn por iu degenera enigoj. En la plej simpla varianto, temas pri tabelo kies eroj estas jam en ordigitaj, kaj en ĉiu okazo atakanto povas krei ĉi tian tabelon. Tamen, se la algoritmo elektas erojn hazarde, ĝi havas tre altan probablon de ruliĝo en tempo O(n log n).

Vidu ankaŭ

Eksteraj ligiloj

"La esperindeco de hazardigitaj algoritmoj, Don Fallis 2000, Brita Ĵurnalo por la Filozofio de Scienco 51:255-71.
[1] R. Motwani kaj P. Raghavan. Hazardigitaj algoritmoj.