Randomisierte Algorithmen: Difference between revisions

From Alda
Jump to navigationJump to search
Line 5: Line 5:
'''Bsp.:''' Lösen des K-SAT-Problems durch RA
'''Bsp.:''' Lösen des K-SAT-Problems durch RA
     geg.: logischer Ausdruck in K-CNF (n Variablen, m Klauseln, k Variablen pro Klausel)
     geg.: logischer Ausdruck in K-CNF (n Variablen, m Klauseln, k Variablen pro Klausel)
     <math>\underbrace {\underbrace {\left(x_1 \vee x_3 \vee...\right)}_{k\; Variablen} \wedge \left( x_2 \vee x_4 \vee...\right)}_{m\;Klauseln}</math>
     <math>\underbrace {\underbrace {\left(x_1 \vee x_3 \vee...\right)}_{k\; Variablen} \wedge \left( x_2 \vee x_4 \vee...\right)}_{m\;Klauseln}</math>
    for i in range (trials):    #Anzahl der Versuche
        #Bestimme eine Zufallsbelegung des <math>\{ x_i \}</math>:

Revision as of 15:53, 3 July 2008

Randomisierte Algorithmen

Def.: Algorithmen, die bei Entscheidung oder bei der Wahl der Parameter Zufallszahlen benutzen

Bsp.: Lösen des K-SAT-Problems durch RA

   geg.: logischer Ausdruck in K-CNF (n Variablen, m Klauseln, k Variablen pro Klausel)
   <math>\underbrace {\underbrace {\left(x_1 \vee x_3 \vee...\right)}_{k\; Variablen} \wedge \left( x_2 \vee x_4 \vee...\right)}_{m\;Klauseln}</math>
   for i in range (trials):    #Anzahl der Versuche
        #Bestimme eine Zufallsbelegung des <math>\{ x_i \}</math>: