Randomisierte Algorithmen: Difference between revisions
From Alda
Jump to navigationJump to search
(New page: == 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....) |
|||
| Line 1: | Line 1: | ||
== Randomisierte Algorithmen == | == Randomisierte Algorithmen == | ||
'''Def.:'''Algorithmen, die bei Entscheidung oder bei der Wahl der Parameter Zufallszahlen benutzen | '''Def.:''' Algorithmen, die bei Entscheidung oder bei der Wahl der Parameter Zufallszahlen benutzen | ||
'''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> | |||
Revision as of 15:51, 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>
