Difference between revisions of "Randomisierte Algorithmen"
From Alda
(→Randomisierte Algorithmen) |
(→Randomisierte Algorithmen) |
||
| 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 16: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)
for i in range (trials): #Anzahl der Versuche
#Bestimme eine Zufallsbelegung des 
:
