Մասնակից:I1indra/Ավազարկղ

Պատահականացված ալգորիթմ

Պատահականացված ալգորիթմը ալգորիթմ է, որը օգտագործում է որոշակի աստիճանի պատահականության որպես իր տրամաբանության կամ ընթացակարգի. Ալգորիթմը սովորաբար օգտագործում է միատեսակ պատահական bits որպես օժանդակ մուտքային տվյալներ, իրենց վարքագիծը կառավարելու համար, հույս ունենալով "միջին դեպքում" լավ կատարման հասնելու համար, պատահական ընտրության բոլոր հնարավոր տարբերակները, որոնք որոշվում են պատահական բիտերով. Այսպիսով, կամ կատարման ժամանակը կամ ելքային տվյալները (կամ երկուսն էլ) պատահական արժեքներ են:

Պետք է տարբերակել ալգորիթմներ, որոնք օգտագործում են պատահական մուտքագրում, Որպեսզի նրանք միշտ ավարտվում է ճիշտ պատասխան, բայց որտեղ ակնկալվող ժամանակը կատարման սահմանափակ է (Las Vegas ալգորիթմներ, օրինակ, արագ տեսակավորման [1]), եւ ալգորիթմներ, որոնք ունեն հնարավորություն ստանալու սխալ արդյունքի (ալգորիթմներ Monte Carlo, օրինակ, Monte Carlo ալգորիթմը համար mfas խնդրի[2]), կամ չի տալիս արդյունք, կամ ազդանշանային ձախողման, կամ առանց ավարտելու աշխատանքը: Որոշ դեպքերում հավանական ալգորիթմները խնդրի լուծման միակ գործնական միջոցն են:[3]

Սովորական պրակտիկայում, randomized ալգորիթմները մոտավորվում են կեղծ թվերի գեներատորի օգտագործմամբ, պատահական bits-ի իրական աղբյուրի փոխարեն. նման իրականացումը կարող է շեղվել ակնկալվող տեսական վարքագծից եւ մաթեմատիկական երաշխիքներից, որոնք կարող են կախված լինել կատարյալ պատահական թվերի գեներատորի առկայությունից:

Մոտիվացիա

Որպես մոտիվացիոն օրինակ, դիտարկենք խնդիրը գտնելու" Ա " զանգված n տարրերի.

Մուտք: զանգված n ≥ 2 տարրերի, որի կեսը - "a", իսկ մյուս կեսը - "b".

Եզրակացություն: գտնել' A ' զանգված.

Մենք ներկայացնում ենք ալգորիթմի երկու տարբերակ, Լաս Վեգասի մեկ ալգորիթմ եւ Մոնտե Կառլոյի մեկ ալգորիթմ:

Լաս Վեգասի Ալգորիթմը:

findingA_LV(array  A, n)
begin
     repeat
         Պատահականորեն ընտրել մեկ տարր n տարրերից.
     until'a'  is found
 end

Այս ալգորիթմը հաջող է հավանականությունը 1. Իտերացիաների քանակը տատանվում է եւ կարող է լինել, քանի որ շատ, բայց ակնկալվող իտերացիաների քանակը հավասար

Քանի որ այն անընդհատ, ակնկալվող կատարման ժամանակ շատ մարտահրավերների հավասար. (Տես մեծ մետա-նոտացիա)

Մոնտե Կառլո Ալգորիթմ:

findingA_MC(array  A, n, k)
begin
     i := 0
     repeat
         Պատահականորեն ընտրել մեկ տարր n տարրերից.
        i := i + 1
    , մինչեւ  i = k  կամ  a'is չի գտնվի end  

Եթե A ' հայտնաբերվել է, ալգորիթմը հաջող է աշխատում, Հակառակ դեպքում ալգորիթմը չի հաջողվում. Հետո k iterations հավանականությունը գտնելու ' a ' հավասար:

Այս ալգորիթմը չի երաշխավորում հաջողություն, բայց կատարման ժամանակը սահմանափակ է: Միավորների քան-iterations միշտ փոքր կամ հավասար k. հաշվի առնելով k մշտական, Runtime (ակնկալվող եւ բացարձակ) հավասար .

Պատահականացված ալգորիթմը հատկապես օգտակար է, երբ բախվում են վնասակար "հակառակորդ" կամ հարձակվող, որը միտումնավոր փորձում է կերակրել վատ ալգորիթմ մուտքը (տես բարդությունը վատթարագույն դեպքում եւ մրցակցային վերլուծություն (առցանց ալգորիթմ))), օրինակ, մի երկընտրանքի բանտարկյալի. Հենց այդ պատճառով է, որ պատահականությունը համատարած է կրիպտոգրաֆիայի մեջ ։ Ծածկագրային հավելվածներում կեղծ թվերը չեն կարող օգտագործվել, քանի որ հակառակորդը կարող է կանխատեսել դրանք, դարձնելով ալգորիթմը արդյունավետ դետերմինացված: Հետեւաբար, պահանջվում է կամ աղբյուր, իրոք, պատահական թվերի, կամ cryptographically պաշտպանված aliased թվերի գեներատոր. Մեկ այլ տարածք, որտեղ բնորոշ է պատահականությունը, քվանտային հաշվարկներն են:

Վերը նշված օրինակում Լաս Վեգասի ալգորիթմը միշտ ճիշտ պատասխան է տալիս, բայց դրա կատարման ժամանակը Պատահական մեծություն է: Մոնտե Կառլոյի ալգորիթմը (կապված Մոնտե Կառլոյի մեթոդի հետ մոդելավորման համար) երաշխավորվում է ժամանակի ընթացքում, որը կարող է սահմանափակվել մուտքային չափի գործառույթով եւ դրա k պարամետրով, սակայն թույլ է տալիս սխալի փոքր հավանականություն: Նշենք, որ ցանկացած Լաս Վեգասի ալգորիթմը կարող է վերածվել Մոնտե Կառլոյի ալգորիթմի (Մարկովի անհավասարության միջոցով), եթե այն դուրս բերի կամայական, գուցե սխալ պատասխան, եթե այն չի ավարտվել նշված ժամանակահատվածում: Եվ հակառակը, եթե կա արդյունավետ ընթացակարգ ստուգելու ճշտությունը պատասխանի, ապա Monte Carlo ալգորիթմը կարող է ձեւափոխվել է Լաս Վեգասում ալգորիթմի միջոցով բազմակի գործարկման Monte Carlo ալգորիթմի մինչեւ ստանալու ճիշտ պատասխան.

Հաշվողական բարդությունը

Տեսությունը հաշվողական բարդության simulates randomized ալգորիթմներ որպես հավանականության մեքենաներ Turing. Ուսումնասիրվել են Լաս Վեգասի և Մոնտե Կառլոյի ալգորիթմները, ուսումնասիրվել են բարդության մի քանի դասեր ։ Բարդության առավել հիմնական randomized դասը RP-ն է, որը լուծման առաջադրանքների դաս է, որի համար կա արդյունավետ (բազմաբնույթ ժամանակ) randomized ալգորիթմ (կամ Turing-ի հավանականության մեքենա), որը ճանաչում է No-օրինակները բացարձակ վստահությամբ եւ ճանաչում է YES-օրինակները առնվազն 1/2-ի հավանականության հետ: The լրացում դաս RP է co-RP. Առաջադրանքների դասեր, որոնք ունեն (հնարավոր է, ոչ-ականացիոն) ալգորիթմներ, որոնք ունեն պոլիոմիալային ժամանակի միջին կատարման ժամանակ, որոնց եզրակացությունը միշտ ճիշտ է, կոչվում են ZPP-ում:

Առաջադրանքների դասը, որի համար YES-ի եւ NO-ի օրինակների որոշ սխալներով նույնականացումը թույլատրվում է, կոչվում է BPP: Այս դասի հանդես է գալիս որպես randomized համարժեք P, այսինքն BPP ներկայացնում է մի դաս արդյունավետ randomized ալգորիթմներ.

Պատմություն

Թվերի տեսության մեջ Պատահականացված ալգորիթմների հետազոտության կարեւոր ուղղությունը թվագրվում է 1917-ի Poklington ալգորիթմի, որը գտնում է քառակուսի արմատներ պարզ թվերի մոդուլի վրա:[4] ուսումնասիրությունը randomized ալգորիթմներ թվերի տեսության էր խթանել բացման 1977 թ. randomized քննության պարզությամբ (Այսինքն, սահմանելով պարզություն) Ռոբերտ Մ. Solovey եւ փայլաթիթեղի Strassen. Դրանից կարճ ժամանակ անց Մայքլ Օ. Ռաբինը ցույց տվեց, որ 1976-ի Միլլերի պարզության թեստը կարելի է վերածել randomized ալգորիթմի: Այդ ժամանակ պարզության համար ոչ մի գործնական դետերմինացված ալգորիթմ հայտնի չէր ։

Միլլեր–Ռաբինի պարզության թեստը հիմնված է երկու դրական k-ի եւ n-ի ամբողջ թվերի միջեւ երկուական վերաբերմունքի վրա, որը կարող է արտահայտվել, ասելով, որ k-ն "վկան է" n-ը: կարելի է ցույց տալ, որ

Եթե կա N-ի կազմի վկայագիր, ապա n-ը բարդ է (այսինքն N-ը պարզ չէ), եւ

Եթե n-ը կոմպոզիտային է, ապա N-ի փոքր բնական թվերի առնվազն երեք քառորդը դրա բաղադրության ականատեսն է, եւ

Կա արագ ալգորիթմ, որը, հաշվի առնելով k-ն եւ n-ը, սահմանում է, թե արդյոք k-ն n-Ի կոմպոզիտորական վկան է:

Նշենք, որ դա նշանակում է, որ առաջնային խնդիրը գտնվում է Co-RP.

Եթե պատահականորեն ընտրենք n-ի ավելի փոքր թվով 100 թվեր, ապա նման "վկա" գտնելու անկարողության հավանականությունը հավասար է (1/4) 100-ի, այնպես որ գործնական նպատակների մեծամասնության համար դա պարզության լավ փորձություն է: Եթե n մեծ է, չի կարող լինել որեւէ այլ գործնական փորձություն. Սխալի հավանականությունը կարող է կրճատվել կամայական աստիճանի ' բավարար քանակությամբ անկախ թեստեր կատարելով:

Հետեւաբար, գործնականում չկա տուգանք, որը կապված է սխալի փոքր հավանականության ընդունման հետ, քանի որ փոքր զգուշությամբ, սխալի հավանականությունը կարող է աստղագիտական փոքր լինել: Իսկապես, չնայած այն հանգամանքին, որ այդ ժամանակից ի վեր հայտնաբերվել է դետերմինացված թեստը բազմաբնույթ ժամանակի պարզության համար, այն չի փոխարինել հին հավանական թեստերը cryptographic ծրագրային ապահովման եւ չի ակնկալվում, որ դա կանի տեսանելի ապագայում:

Դերանդոմացում

Պատահականություն կարելի է համարել որպես ռեսուրս, քանի որ տարածության եւ ժամանակի. Դերանդոմիզացիան պատահականության հեռացման գործընթաց է (կամ այն հնարավորինս քիչ օգտագործելը): Ներկայումս հայտնի չէ, թե արդյոք հնարավոր է դերանդոմիզացնել բոլոր ալգորիթմները ՝ առանց դրանց կատարման ժամանակի զգալի ավելացման ։ Օրինակ, հաշվողական բարդության անհայտ է, P = BPP, Այսինքն, մենք չգիտենք, թե արդյոք մենք կարող ենք վերցնել կամայական randomized ալգորիթմ, որը աշխատում է polyinomial ժամանակ մի փոքր հավանականության սխալի, եւ դերանդոմիզացնել այն աշխատում է polyinomial ժամանակ, առանց օգտագործման պատահական.

Կան հատուկ մեթոդներ, որոնք կարող են օգտագործվել դերանդոմացման կոնկրետ randomized ալգորիթմներ:

պայմանական հավանականությունների մեթոդը և Դրա ընդհանրացումը, հոռետեսական գնահատականները

անհամապատասխանության տեսություն (որն օգտագործվում է երկրաչափական ալգորիթմների դերանդոմացման համար)

սահմանափակ անկախության օգտագործումը պատահական քանակությամբ օգտագործվում է ալգորիթմի կողմից, ինչպիսիք են ընդհանուր անկախությունը, որն օգտագործվում է համընդհանուր hashing-ում

օգտագործելով count extenders (կամ dispersant ընդհանրապես) բարձրացնել սահմանափակ քանակությամբ նախնական պատահականության (այս վերջին մոտեցումը կոչվում է նաեւ առաջացնում կեղծ պատահական bits պատահական աղբյուրի եւ հանգեցնում է համապատասխան թեմայի pseudosbuilding)

փոփոխությունը randomized ալգորիթմի օգտագործման համար հաշ ֆունկցիա որպես աղբյուր պատահական համար ալգորիթմի խնդիրների, եւ ապա derandomization ալգորիթմի կողմից busting բոլոր հնարավոր պարամետրերի (սերմերի) հաշ գործառույթը. Այս մեթոդը սովորաբար օգտագործվում է ընտրանքային տարածքի սպառիչ որոնման համար եւ ալգորիթմը դարձնում է դետերմինացված (օրինակ, randomized գրաֆների ալգորիթմները)

Որտեղ է պատահականությունը օգնում

Երբ հաշվողական մոդելը սահմանափակված է Turing մեքենաների կողմից, ներկայումս բաց է մնում այն հարցը, թե արդյոք հնարավորություն է տալիս պատահական ընտրություն կատարել, լուծել պոլիոմիալային ժամանակի որոշ խնդիրներ, որոնք չեն կարող լուծվել պոլիոմիալային ժամանակի համար, առանց այդ ունակության. դա այն հարցն է, թե արդյոք P = BPP: Սակայն, այլ համատեքստերում կան կոնկրետ օրինակներ խնդիրների, որտեղ randomization տալիս խիստ բարելավումներ.

Հաշվի առնելով էքսպոնենտալ երկար տողը 2 k նիշից, կես A եւ կես b-ից, կամայական մուտք ունեցող մեքենան պահանջում է 2 k−1 որոնում վատագույն դեպքում ' գտնել A ցուցանիշը; եթե թույլատրվում է պատահական ընտրություն կատարել, ապա դա կարող է լուծել այս խնդիրը ակնկալվող բազմաբնույթ որոնման մեջ:

Ներկառուցված համակարգերում կամ կիբեռֆիզիկական համակարգերում թվային հաշվարկներ կատարելու բնական եղանակը այն արդյունքն է, որը բարձր հավանականությամբ մոտենում է ճիշտ (կամ, հավանաբար, մոտավորապես ճիշտ հաշվարկին (PACC)): Բարդ խնդիրը, որը կապված է մոտավոր եւ ճիշտ հաշվարկի միջեւ անհամապատասխանության կորստի գնահատման հետ, կարող է արդյունավետ կերպով լուծվել randomization-ի դիմելու միջոցով[7]

Ի բարդության կապի հավասարությունը երկու շարքերում կարող է ստուգվել ինչ-որ հուսալիության օգտագործելով {\displaystyle \log n} \ log pbit կապի հետ randomized արձանագրության. Ցանկացած determinated արձանագրությունը պահանջում է {\displaystyle \Theta (n)}\Theta (n)bits, երբ պաշտպանվում է ուժեղ մրցակցի.[8]

Ուռուցիկ մարմնի ծավալը կարելի է գնահատել պոլիոմիալային ժամանակի համար պատահական ճշգրտությամբ randomized ալգորիթմ:[9] Barani եւ Furad պարզվել է, որ ոչ մի determinated ալգորիթմը կարող է անել նույնը.[10] դա ճիշտ է անվերապահորեն, այսինքն, առանց որեւէ տեսական եւ բարդ ենթադրությունների հենման, ենթադրելով, որ ուռուցիկ մարմինը կարող է պահանջվել միայն որպես սեւ արկղ:

Ավելի բարդ տեսական օրինակ է այն վայրում, որտեղ պատահականությունը, ըստ երեւույթին, օգնում է, այն է, որ IP դաս. IP-ն բաղկացած է բոլոր լեզուներից, որոնք կարող են ընդունվել (բարձր հավանականությամբ) պոլիոմիալ երկար փոխազդեցություն Ամենակարող ստուգման եւ ստուգման միջեւ, որը իրականացնում է BPP ալգորիթմը: IP = PSPACE.[11] Սակայն, եթե պահանջվում է, որ ստուգման էր determinated, ապա IP = NP.

Քիմիական ռեակցիաների ցանցում (ռեակցիաների վերջնական հավաքածու, ինչպիսիք են A + B → 2C + D-ը, որոնք աշխատում են մոլեկուլների վերջնական թվին), նախնական վիճակից կանխորոշված նպատակային վիճակի հասնելու ունակությունը թույլ է տալիս, նույնիսկ մոտավորելով կանխորոշված նպատակային վիճակի հասնելու հավանականությունը (օգտագործելով համակենտրոնացման վրա ստանդարտ հիմնված հավանականությունը, որի համար արձագանքը տեղի կունենա հաջորդ) անլուծելի է: Ավելի կոնկրետ, Turing-ի սահմանափակ մեքենան կարող է ձեւավորված լինել ամբողջ ժամանակի ընթացքում կամայական բարձր հավանականությամբ, միայն այն դեպքում, եթե օգտագործվում է քիմիական ռեակցիաների պատահական Ցանց: Քիմիական ռեակցիաների պարզ չեթերմինացված ցանցի (այսուհետ կարող է տեղի ունենալ ցանկացած հնարավոր ռեակցիա) օգտագործման դեպքում հաշվողական հզորությունը սահմանափակված է պարզունակ ռեկուրսիվ գործառույթներով[12] ։

• A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow and Network Design Problems, Mathematics of Operations Research, 24(2):383-413, 1999.