Metode ransfdomizaţi, în Computation
Source: http://www.wisdom.weizmann.ac.il/~oded/rnd-sum.html
(Notele de curs - Rezumate)
Oded Goldreich
Curs 1:. Probabilitatea şi metoda probabilistica După o introducere generală la curs, ne amintim câteva dintre noţiunile de bază ale teoriei probabilitatilor, cum ar fi aşteptări, şi a varianţei unei variabile aleatoare, inegalitatea Chebyshev şi prima lege a numerelor mari. Va prezentam, de asemenea, metoda probabiliste si de a demonstra o cerere a acesteia (în special, la problema Max3SAT). În cele din urmă, vom dezvolta un algoritm simplu că, având o formulă 3CNF, constată o misiune care îndeplineşte multe dintre clauzele sale.
Curs 2: Legile numerelor mari şi Existenţa expandat. Ne concentrăm pe diferite legi a numerelor mari. Aceste legi legat probabilitatea ca o variabilă aleatoare se abate de la ceea ce se aşteaptă. Motivat de problema de a aproxima medie a unei funcţii, vom prezenta limitele mai puternică decât inegalitatea Chebyshev lui: trecerea de la prelevare de probe independente luate două câte două până la $ 2k $-înţelept prelevare de probe independente şi apoi la prelevarea de probe total independent face ca probabilitatea erorii exponenţial dispare (în suma de de independenţă). Am defini, de asemenea familiile de grafice numite expandere, şi să dovedească existenţa unei familii de 3-regulat extindere (folosind metoda probabilistică).
Curs 3:. Mici, luate două câte două-Independent Spatii de propoziţii Deseori, în aplicaţiile care utilizează aleatoriu (de exemplu, aruncă monede), nu avem nevoie de toate aceste aruncă să fie independent, în schimb ar fi suficient ca acestea să fie $ k $ independente pentru unele $ k $. În cazul variabilelor aleatoare complet independente spaţiul probabilitatea este de cel puţin de dimensiunea $ | S | ^ m $, unde $ $ m este numărul de variabile în secvenţa şi $ S $ este spaţiul pentru o variabila proba individuală. În schimb, vă prezentăm o pereche de construcţie pentru spaţiu eşantion independent de dimensiunea $ \ max (| S |, m) ^ 2 $ şi extinderea acestuia la k $ $-înţelept caz independent. Acest lucru ne va permite să {\-l derandomize} algoritmul (prezentate pe prima lectură), care constată sarcini pentru 3CNF care îndeplineşte cel puţin 7 / 8 clauze. Algoritmul de rezultat va efectua o căutare exhaustivă a relativ mici 3-înţelept spaţiu eşantion independent (de misiuni boolean).
Curs 4:. Mici, luate două câte două-Independent de spaţii de propoziţii (continuare) şi Hash Funcţii O construcţie bună de $ k $-înţelept spaţiu probă independent ar trebui să fie mici şi uşor de utilizat in aplicatii. De construcţie prezentate în prelegerea anterioară îndeplineşte prima condiţie (de exemplu, este mic), dar este destul de complexă, de instituire a unui număr de probleme tehnice în aplicare. În această prelegere o construcţie al doilea, mult mai convenabil este prezentat, pe baza transformări afine. Această construcţie randamentele spaţii mici probă, dar numai pentru independenţă perechi ($ k = 2 $). Vom începe, de asemenea, discutăm funcţii hash, arătând relaţia lor la spaţiile de mici proba luate două câte două-independent, şi care prezintă un Lema hashing. Acesta din urmă afirmă că luate două câte două-independent de distribuire hartă funcţii stabileşte într-un mod `` buna''(de exemplu, fiecare imagine obţine aproximativ acelaşi număr de preimages).
Curs 5:. Counting aproximata Vom discuta probleme cantitative legate de NP-relaţiilor. Concret, având în vedere un element într-o limbă-NP, ne întrebăm câţi martori acestui element a fost. Noi folosim funcţiile Hash, în scopul de a prezenta o procedură eficientă randomizat, care a dat un exemplu, un într-un acces NP-limbă şi Oracle la NP, aproximează numărul de martori în acest exemplu.
Curs 6: Generation uniforme. Acest curs continua discuţia de numărare şi aproximative generaţie uniform folosind un NP-oracol a început în curs anterior, în cazul în care am văzut un algoritm aproximative de numărare. Aici vom vedea echivalenţa (până la Turing reduceri) de numărare aproximative pentru generarea de uniforme NP-martori. Împreună cu algoritmul de aproximativ începând prelegere trecut, acest lucru produce un algoritm de generare uniform cu ajutorul unui NP-oracol. Am încheia cu o alternativă (directe) algoritm de generare uniformă, care foloseste $ $ n-înţelept funcţii independente hash (spre deosebire de funcţiile pereche independent hash utilizate pentru numărarea aproximative).
Curs 7:. Spaţii mici de propoziţii Bias (partea 1) În această prelegere vom introduce noţiunea de $ spatii eşantion \ e $-părtinire. Neoficial, o variabilă aleatoare de peste $ \ bitset ^ n $ este $ \ $ e-părtinire în cazul în care pentru fiecare subset de biţi, diferenţa dintre probabilitatea ca paritatea de biţi este zero, iar probabilitatea este unul este cel mult $ \ e $. Ne arată o legătură între $ \ $ e-părtinire şi distanţa statistice pentru a distributie uniforma. În continuare, vom prezenta o cerere de $ \ $ e-prejudecata locuri de probă pentru generarea de aproximativ''`` $ $ k-înţelept distribuţii independent (de exemplu, distribuţii de peste $ \ n $ ^ bitset în care biţi fiecare $ k $ arata aproape uniform distribuite peste $ \ bitset ^ n $).
. Curs 8: spatii mici de propoziţii Bias (partea 2) În această prelegere vom prezenta unei constructii de spatii mici eşantion prejudecată, adică, vom prezenta un algoritm că, având în $ n $ şi $ \ e $ ieşiri o reprezentare explicită a unei $ \ $ e-părtinire spaţiu eşantion de peste $ \ n $ ^ bitset şi face acest lucru în termen de $ \ poli (n / \ e) $. Vă prezentăm, de asemenea, o cerere a unei astfel de construcţii pentru a dovedi un rezultat strâns în ceea ce priveşte duritatea de aproximare MaxQE (în cazul în care unuia îi este dat o secvenţă de ecuaţii pătratice peste $ GF (2) $ şi i se cere să găsească o misiune care satisface cât mai multe din aceste ecuatii).
Curs 9:. Extinderea şi valorilor proprii Acest curs este de aproximativ graficele extensorul, care sunt foarte utile în multe aplicaţii probabilistic. În primul rând, ne-ar descrie câteva dintre definiţiile combinatoriale şi proprietăţile unui Graficul extensor. În al doilea rând, am vedea o singură cerere, care utilizează graficele expandor, şi în cele din urmă, ne-ar discuta despre unele dintre proprietăţile algebrice de grafice astfel.
Curs 10:. Merge pe la Întâmplare expandat În această prelegere ne arată că ţinând seama de o L $ $-pas mers aleator într-un extensor Graficul este într-un mod similar de a alege nodurile $ l $ la întâmplare. Avantajul de a folosi la o plimbare de peste aleatoare a lua o probă de independent este ca o plimbare aleator pe un d $ $-regulat Graficul necesită $ \ log_2 d $ biţi aleatorii pentru fiecare pas, fiecare nod întrucât selectarea aleatoare a unui N $ $-vertex Graficul necesită $ \ log_2 N $ biţi aleatorii. Ca un warm up, ne arată că satring la orice nod într-un N $ $ vertex-expandor şi luând $ O (\ log N) $ pasi aleator, se ajunge la aproximativ distribuţie uniformă (pe nodurile). Ne amintim, de asemenea, relaţia dintre două definiţii de expansiune şi să descrie unele construcţii cunoscute de expansiune.
Curs 11:. Testarea Primality (prin extracţie SQRT) În această prelegere vom prezenta doi algoritmi randomizaţi în teoria numerelor. Algoritmul de aşteptat în primul constată polinomial timp o rădăcină pătrată a unui număr în Z_p $ ^ $ * pentru orice număr prim p $ $. Noi folosim atunci acest algoritm pentru a construi un algoritm de timp polinomial cu faţă-verso erori pentru testarea primality.
Curs 12:. Hitters si de probe un sampler este un oracol masina Turing că estimările media cu privire la orice funcţie $ f: \ {0,1 \} ^ n \ to [0,1] $ cu deviaţie delimitate şi mărginită de probabilitatea eşecului. Un Hitter este un oracol masina Turing că, având în vedere o funcţie boolean $ f: \ {0,1 \} ^ n \ a \ {0,1 \} $, constată $ x $ st ~ $ f (x) = 1 $ cu o probabilitate mărginită de eşec în cazul în $ f $ are valoarea 1 pe cel puţin o fracţiune constantă de $ \ {0,1 \} ^ n $. Acestea sunt probleme fundamentale şi utile. Noi considerăm complexitatea aleatoriu şi interogare hitters prelevatoarelor şi a căror funcţionare este polynomially timp mărginit, şi amintesc limitele inferioare pentru fiecare. Arătăm mai multe constructii simplu pentru ambele, precum şi construcţiile îmbunătăţit pe baza spaţiile eşantion luate două câte două-independent, şi pe plimbari aleatorii pe graficele extensor. Ne arată apoi constructii ale căror complexitatea meci limitele inferioare.
Curs 13:. Rotunjire randomizat unor algoritmi de programare liniară apropierea utilizează pe o varianta a problemei originale. Soluţiile de o problemă de programare liniară sunt non-integrantă, în cazul general, în timp ce soluţii la problemele legitime originale sunt numere întregi numai. O idee care poate fi folosit pentru a transforma numerele reale în soluţii întreg, este de a folosi liniar de programare (non-integer) soluţii ca parametri de probabilitate de selecţie (întreg), soluţii pentru problema originală. În această prelegere vom prezenta această idee şi să demonstreze că în două cazuri.
Înapoi la pagina de start Oded Goldreich lui.
Copyright (simbolul C) 2001 de Goldreich Oded. Permisiunea de a face copii digitale sau tare de o parte sau în întregime acest lucru pentru uz personal sau de clasă este acordat fără taxă, cu condiţia ca copii nu sunt realizate sau distribuite de avantaj sau profit comercial şi noi copii care poartă acest anunţ şi citare complete privind prima pagina. Abstractizare cu credit este permisă.
Acest lucru ar putea fi publicate sau poate fi o bază pentru publicarea în viitor. Drepturi de autor pot fi transferate fără o notificare ulterioară şi această versiune ar putea să nu mai fie accesibil.