Randomisierte Algorithmen: Difference between revisions
From Alda
Jump to navigationJump to search
| Line 18: | Line 18: | ||
Eigenschaft: falls <math>k>2</math> : steps *trials <math>\in O\left(\Alpha^n \right) \Alpha >1</math> | Eigenschaft: falls <math>k>2</math> : steps *trials <math>\in O\left(\Alpha^n \right) \Alpha >1</math> | ||
z.B. <math>k=3</math> steps=3*n, trials=<math>\left(\frac{4}3\ | z.B. <math>k=3</math> steps=3*n, trials=<math>\left(\frac{4}3\right)^n</math> | ||
Revision as of 17:01, 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 :
for j in range (steps):
if erfüllt alle Klauseln: return
#wähle zufällig eine Klausel, die nicht erfüllt ist und negiere zufällig eine der Variablen in dieser Klausel
(die Klausel ist jetzt erfüllt)
return None
Eigenschaft: falls : steps *trials
z.B. steps=3*n, trials=
