Anki Deck Changes

Note 1: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: #vrtD+3u4N

added

Note did not exist

New Note

Front

Fehlerreduktion Las-Vegas
Sei $A$ ein randomisierter Algorithmus, der nie eine falsche Antwort gibt, aber zuweilen '???' ausgibt, mit $\Pr[A(I) \text{ korrekt}] \geq \varepsilon$.

Sei $A_\delta$ der Algorithmus, der $A$ solange aufruft, bis entweder ein Wert verschieden von '???' ausgegeben wird (und diesen Wert dann ebenfalls ausgibt) oder bis
\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\] mal '???' ausgegeben wurde (und dann '???' ausgibt). Dann gilt:
\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]

Back

Beweisskizze: Pr[$A_\delta$ gibt '???' aus] $\leq (1-\varepsilon)^N \leq e^{-\varepsilon N} \leq \delta$ für $N \geq \varepsilon^{-1} \ln \delta^{-1}$, via $1 - x \leq e^{-x}$.

Field-by-field Comparison

Field	Before	After
Text		<b>Fehlerreduktion Las-Vegas</b> <br>Sei $A$ ein randomisierter Algorithmus, der nie eine falsche Antwort gibt, aber zuweilen '???' ausgibt, mit $\Pr[A(I) \text{ korrekt}] \geq \varepsilon$.<br><br>Sei $A_\delta$ der Algorithmus, der $A$ solange aufruft, bis entweder ein Wert verschieden von '???' ausgegeben wird (und diesen Wert dann ebenfalls ausgibt) oder bis <br>\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\] mal '???' ausgegeben wurde (und dann '???' ausgibt). Dann gilt:<br>\[\Pr[A_\delta(I) \text{ korrekt}] \geq {{c2::1 - \delta}}.\]
Extra		Beweisskizze: Pr[$A_\delta$ gibt '???' aus] $\leq (1-\varepsilon)^N \leq e^{-\varepsilon N} \leq \delta$ für $N \geq \varepsilon^{-1} \ln \delta^{-1}$, via $1 - x \leq e^{-x}$.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit

Note 2: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: +N@/D$lVm_

added

Note did not exist

New Note

Front

Selektionsproblem: Bestimme in einer Folge $(A[1], \ldots, A[n])$ paarweise verschiedener Zahlen den $k$-kleinsten Wert.

Naiver Ansatz: Sortieren + Index, Laufzeit $O(n \log n)$.

Schneller geht es mit QuickSelect (erwartet $O(n)$):

QuickSelect(A, ℓ, r, k):
  p ← Uniform({ℓ, ℓ+1, ..., r})
  t ← Partition(A, ℓ, r, p)
  if t = ℓ + k - 1: return A[t]    # gefunden
  else if t > ℓ + k - 1:
    return QuickSelect(A, ℓ, t-1, k)     # links
  else:
    return QuickSelect(A, t+1, r, k - t) # rechts

Back

QuickSelect(A, ℓ, r, k):
  p ← Uniform({ℓ, ℓ+1, ..., r})
  t ← Partition(A, ℓ, r, p)
  if t = ℓ + k - 1: return A[t]    # gefunden
  else if t > ℓ + k - 1:
    return QuickSelect(A, ℓ, t-1, k)     # links
  else:
    return QuickSelect(A, t+1, r, k - t) # rechts

Im Gegensatz zu QuickSort rekursiert QuickSelect nur in eine der beiden Hälften (oder gibt direkt zurück, falls Pivot bereits an der gesuchten Position liegt). Das macht den Unterschied zwischen $O(n \log n)$ und $O(n)$ erwartet.

Bei einem Aufruf von QuickSelect ist die Anzahl Vergleiche $T = \sum_{i=1}^{N} (r_i - \ell_i)$, wobei $N$ die Anzahl Partition-Aufrufe ist.

Field-by-field Comparison

Field	Before	After
Text		<b>Selektionsproblem:</b> Bestimme in einer Folge $(A[1], \ldots, A[n])$ paarweise verschiedener Zahlen den {{c1::$k$-kleinsten Wert}}.<br><br>Naiver Ansatz: Sortieren + Index, Laufzeit {{c2::$O(n \log n)$}}.<br><br>Schneller geht es mit <b>QuickSelect</b> (erwartet {{c3::$O(n)$}}):<pre>QuickSelect(A, ℓ, r, k): p ← Uniform({ℓ, ℓ+1, ..., r}) t ← Partition(A, ℓ, r, p) if t = ℓ + k - 1: return A[t] # gefunden else if t > ℓ + k - 1: return QuickSelect(A, ℓ, t-1, k) # links else: return QuickSelect(A, t+1, r, k - t) # rechts</pre>
Extra		Im Gegensatz zu QuickSort rekursiert QuickSelect nur in <b>eine</b> der beiden Hälften (oder gibt direkt zurück, falls Pivot bereits an der gesuchten Position liegt). Das macht den Unterschied zwischen $O(n \log n)$ und $O(n)$ erwartet.<br><br>Bei einem Aufruf von QuickSelect ist die Anzahl Vergleiche $T = \sum_{i=1}^{N} (r_i - \ell_i)$, wobei $N$ die Anzahl Partition-Aufrufe ist.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren

Note 3: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: /,nT@jP#V6

added

Note did not exist

New Note

Front

Randomisierter Algorithmus für Optimierungsprobleme
Sei $\varepsilon > 0$ und $A$ ein randomisierter Algorithmus, der immer eine zulässige Lösung liefert, mit\[\Pr[A(I) \geq f(I)] \geq \varepsilon\]für eine Zielschwelle $f(I)$. Sei $A_\delta$ der Algorithmus, der\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\]Aufrufe von $A$ macht und die beste der erhaltenen Antworten ausgibt. Dann gilt:\[\Pr[A_\delta(I) \geq f(I)] \geq 1 - \delta.\]

Back

Selbe Iterationsschranke wie bei Las-Vegas und MC mit einseitigem Fehler. Die Idee ist analog: ein einziger Aufruf, der die Schwelle überschreitet, genügt, da das Maximum mehrerer Aufrufe genommen wird.

Typischerweise ist $f(I) = \mathbb{E}[A(I)]$, d.h. man möchte mit hoher Wahrscheinlichkeit mindestens den Erwartungswert erreichen.

Field-by-field Comparison

Field	Before	After
Text		<b>Randomisierter Algorithmus für Optimierungsprobleme</b> <br>Sei $\varepsilon > 0$ und $A$ ein randomisierter Algorithmus, der immer eine zulässige Lösung liefert, mit\[\Pr[A(I) \geq f(I)] \geq \varepsilon\]für eine Zielschwelle $f(I)$. Sei $A_\delta$ der Algorithmus, der\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\]Aufrufe von $A$ macht und {{c2::die beste der erhaltenen Antworten}} ausgibt. Dann gilt:\[\Pr[A_\delta(I) \geq f(I)] \geq 1 - \delta.\]
Extra		Selbe Iterationsschranke wie bei Las-Vegas und MC mit einseitigem Fehler. Die Idee ist analog: ein einziger Aufruf, der die Schwelle überschreitet, genügt, da das Maximum mehrerer Aufrufe genommen wird.<br><br>Typischerweise ist $f(I) = \mathbb{E}[A(I)]$, d.h. man möchte mit hoher Wahrscheinlichkeit mindestens den Erwartungswert erreichen.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit

Note 4: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 1c]P8!r+kY

added

Note did not exist

New Note

Front

Für die Anwendung in der RSA-Kryptographie möchte man zufällige grosse Primzahlen erzeugen (z.B. mit $1000$ Bits, also $n \approx 2^{1000}$). Man erzeugt zufällig Zahlen mit $1000$ Bits und testet sie auf prim.

Dass das funktioniert, garantiert der Primzahlsatz:
\[\pi(x) := |\{n \in \mathbb{N} \mid n \leq x,\, n \text{ prim}\}| \sim {{c1::\frac{x}{\ln x} }}.\]Daraus folgt für $1000$-Bit-Zahlen eine Erfolgsrate von etwa {{c2::$\frac{1}{1000 \ln 2} \approx \frac{1}{693}$}}.

Back

Die RSA-Verschlüsselung beruht auf der Asymmetrie: Ob $n$ prim ist, kann man schnell entscheiden (randomisiert), aber einen nicht-trivialen Teiler von $n$ effizient zu finden ist nicht bekannt. Quantencomputer können das via Shor-Algorithmus.

Field-by-field Comparison

Field	Before	After
Text		Für die Anwendung in der RSA-Kryptographie möchte man zufällige grosse Primzahlen erzeugen (z.B. mit $1000$ Bits, also $n \approx 2^{1000}$). Man erzeugt zufällig Zahlen mit $1000$ Bits und testet sie auf prim.<br><br>Dass das funktioniert, garantiert der <b>Primzahlsatz</b>:<br>\[\pi(x) := \|\{n \in \mathbb{N} \mid n \leq x,\, n \text{ prim}\}\| \sim {{c1::\frac{x}{\ln x} }}.\]Daraus folgt für $1000$-Bit-Zahlen eine Erfolgsrate von etwa {{c2::$\frac{1}{1000 \ln 2} \approx \frac{1}{693}$}}.
Extra		Die RSA-Verschlüsselung beruht auf der <b>Asymmetrie</b>: Ob $n$ prim ist, kann man schnell entscheiden (randomisiert), aber einen nicht-trivialen Teiler von $n$ effizient zu finden ist nicht bekannt. Quantencomputer können das via Shor-Algorithmus.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest

Note 5: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 2k)Z={{#13

added

Note did not exist

New Note

Front

Sei $PB_n := \{a \in [n-1] \mid a^{n-1} \equiv_n 1\} = \{a \in \mathbb{Z}_n^* \mid a^{n-1} \equiv_n 1\}$ die Menge der Pseudoprimzahlbasen von $n$.

$n$ heisst Carmichael-Zahl, falls {{c1::$n$ nicht prim ist und $PB_n = \mathbb{Z}_n^*$}}.

Kleinste Beispiele: $561 = 3 \cdot 11 \cdot 17,\ 1105 = 5 \cdot 13 \cdot 17,\ 1729 = 7 \cdot 13 \cdot 19$.

Back

Auf Carmichael-Zahlen versagt der Fermat-Test komplett: Jede Pseudoprimzahlbasis täuscht "Primzahl" vor, und $PB_n$ ist die ganze multiplikative Gruppe $\mathbb{Z}_n^*$. Die Fehlerwahrscheinlichkeit $|PB_n|/(n-1) = \varphi(n)/(n-1)$ ist nahe $1$.

Genau hier setzt der Miller-Rabin-Test an.

Field-by-field Comparison

Field	Before	After
Text		Sei $PB_n := \{a \in [n-1] \mid a^{n-1} \equiv_n 1\} = \{a \in \mathbb{Z}_n^* \mid a^{n-1} \equiv_n 1\}$ die Menge der <b>Pseudoprimzahlbasen</b> von $n$.<br><br>$n$ heisst <b>Carmichael-Zahl</b>, falls {{c1::$n$ nicht prim ist und $PB_n = \mathbb{Z}_n^*$}}.<br><br>Kleinste Beispiele: ${{c2::561 = 3 \cdot 11 \cdot 17,\ 1105 = 5 \cdot 13 \cdot 17,\ 1729 = 7 \cdot 13 \cdot 19}}$.
Extra		Auf Carmichael-Zahlen versagt der Fermat-Test komplett: Jede Pseudoprimzahlbasis täuscht "Primzahl" vor, und $PB_n$ ist die ganze multiplikative Gruppe $\mathbb{Z}_n^*$. Die Fehlerwahrscheinlichkeit $\|PB_n\|/(n-1) = \varphi(n)/(n-1)$ ist nahe $1$.<br><br>Genau hier setzt der Miller-Rabin-Test an.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest

Note 6: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 5]{}ADU2JV

added

Note did not exist

New Note

Front

Sei $n > 2$ ungerade, schreibe $n - 1 = 2^k d$ mit $d$ ungerade.

Vorüberlegung: Für $n$ prim ist $(\mathbb{Z}_n, +, \cdot)$ ein Körper, und in einem Körper hat $x^2 = 1$ genau zwei Lösungen: ${{c2::x = 1\ \text{und}\ x = n - 1\ (= -1)}}$.

Ist $n$ prim und $a \in [n-1]$, dann gilt:

$a^{2^k d} = a^{n-1} \equiv_n 1$ (kleiner Fermat),
also $a^{2^{k-1}d} \equiv_n 1$ oder $n - 1$,
falls $\equiv_n 1$: wieder Quadratwurzel ziehen, $a^{2^{k-2}d} \equiv_n 1$ oder $n-1$,
... bis: falls $a^{2d} \equiv_n 1$, dann $a^d \equiv_n 1$ oder $n - 1$.

Miller-Rabin-Bedingung: für $n$ prim und alle $a$ gilt
\[{{c3::a^d \equiv_n 1 \quad \text{oder} \quad \exists\, i \in \{0, 1, \ldots, k-1\}: a^{2^i d} \equiv_n n - 1.}}\]

Back

$a^{2^k d} = a^{n-1} \equiv_n 1$ (kleiner Fermat),
also $a^{2^{k-1}d} \equiv_n 1$ oder $n - 1$,
falls $\equiv_n 1$: wieder Quadratwurzel ziehen, $a^{2^{k-2}d} \equiv_n 1$ oder $n-1$,
... bis: falls $a^{2d} \equiv_n 1$, dann $a^d \equiv_n 1$ oder $n - 1$.

Miller-Rabin-Bedingung: für $n$ prim und alle $a$ gilt
\[{{c3::a^d \equiv_n 1 \quad \text{oder} \quad \exists\, i \in \{0, 1, \ldots, k-1\}: a^{2^i d} \equiv_n n - 1.}}\]

Idee: aus $a^{n-1} \equiv_n 1$ wiederholt Quadratwurzeln ziehen, solange das Ergebnis noch $1$ ist. Im Körper sind die einzigen Quadratwurzeln von $1$ genau $\pm 1$, daher muss man irgendwann auf $n-1$ treffen oder bei $a^d \equiv_n 1$ landen.

Ein $a$, das diese Bedingung verletzt, ist ein Miller-Rabin-Zertifikat dafür, dass $n$ nicht prim ist.

Field-by-field Comparison

Field	Before	After
Text		Sei $n > 2$ ungerade, schreibe $n - 1 = 2^k d$ mit $d$ ungerade.<br><br>Vorüberlegung: Für $n$ prim ist $(\mathbb{Z}_n, +, \cdot)$ ein {{c1::Körper}}, und in einem Körper hat $x^2 = 1$ genau zwei Lösungen: ${{c2::x = 1\ \text{und}\ x = n - 1\ (= -1)}}$.<br><br>Ist $n$ prim und $a \in [n-1]$, dann gilt:<ul><li>$a^{2^k d} = a^{n-1} \equiv_n 1$ (kleiner Fermat),</li><li>also $a^{2^{k-1}d} \equiv_n 1$ oder $n - 1$,</li><li>falls $\equiv_n 1$: wieder Quadratwurzel ziehen, $a^{2^{k-2}d} \equiv_n 1$ oder $n-1$,</li><li>... bis: falls $a^{2d} \equiv_n 1$, dann $a^d \equiv_n 1$ oder $n - 1$.</li></ul><b>Miller-Rabin-Bedingung</b>: für $n$ prim und alle $a$ gilt<br>\[{{c3::a^d \equiv_n 1 \quad \text{oder} \quad \exists\, i \in \{0, 1, \ldots, k-1\}: a^{2^i d} \equiv_n n - 1.}}\]
Extra		Idee: aus $a^{n-1} \equiv_n 1$ wiederholt Quadratwurzeln ziehen, solange das Ergebnis noch $1$ ist. Im Körper sind die einzigen Quadratwurzeln von $1$ genau $\pm 1$, daher muss man irgendwann auf $n-1$ treffen oder bei $a^d \equiv_n 1$ landen.<br><br>Ein $a$, das diese Bedingung verletzt, ist ein <b>Miller-Rabin-Zertifikat</b> dafür, dass $n$ nicht prim ist.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest

Note 7: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:

7js:~


            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Bei einem Las-Vegas-Algorithmus ist die Laufzeit eine Zufallsvariable, die Korrektheit hingegen nicht vom Zufall abhängig.

Ziel: immer korrekt/gut, meistens schnell.

Alternative Sichtweise: Algorithmus, der manchmal '???' statt eines Ergebnisses ausgibt. Man kann ihn dann entweder wiederholen, bis ein Ergebnis kommt, oder nach fester Laufzeit abbrechen.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Bei einem Las-Vegas-Algorithmus ist die Laufzeit eine Zufallsvariable, die Korrektheit hingegen nicht vom Zufall abhängig.

Ziel: immer korrekt/gut, meistens schnell.

Alternative Sichtweise: Algorithmus, der manchmal '???' statt eines Ergebnisses ausgibt. Man kann ihn dann entweder wiederholen, bis ein Ergebnis kommt, oder nach fester Laufzeit abbrechen.
    
    
    
    Die alternative Sichtweise ist die Brücke zum Monte-Carlo-Algorithmus: Lässt man den Las-Vegas-Algorithmus nach fester Laufzeit abbrechen, wird daraus ein Monte-Carlo-Algorithmus mit einseitigem Fehler.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Bei einem <b>Las-Vegas-Algorithmus</b> ist {{c1::die Laufzeit}} eine Zufallsvariable, die {{c1::Korrektheit}} hingegen nicht vom Zufall abhängig.<br><br>Ziel: {{c2::immer korrekt/gut, meistens schnell}}.<br><br><b>Alternative Sichtweise:</b> Algorithmus, der manchmal {{c3::'???' statt eines Ergebnisses}} ausgibt. Man kann ihn dann entweder {{c4::wiederholen, bis ein Ergebnis kommt}}, oder {{c4::nach fester Laufzeit abbrechen}}.
                        
                        
                        
                            Extra
                            
                            Die alternative Sichtweise ist die Brücke zum Monte-Carlo-Algorithmus: Lässt man den Las-Vegas-Algorithmus nach fester Laufzeit abbrechen, wird daraus ein Monte-Carlo-Algorithmus mit einseitigem Fehler.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit

Field	Before	After
Text		Bei einem <b>Las-Vegas-Algorithmus</b> ist {{c1::die Laufzeit}} eine Zufallsvariable, die {{c1::Korrektheit}} hingegen nicht vom Zufall abhängig.<br><br>Ziel: {{c2::immer korrekt/gut, meistens schnell}}.<br><br><b>Alternative Sichtweise:</b> Algorithmus, der manchmal {{c3::'???' statt eines Ergebnisses}} ausgibt. Man kann ihn dann entweder {{c4::wiederholen, bis ein Ergebnis kommt}}, oder {{c4::nach fester Laufzeit abbrechen}}.
Extra		Die alternative Sichtweise ist die Brücke zum Monte-Carlo-Algorithmus: Lässt man den Las-Vegas-Algorithmus nach fester Laufzeit abbrechen, wird daraus ein Monte-Carlo-Algorithmus mit einseitigem Fehler.


        
        
            Note 8: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: :UEQ*@nnq1
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Üppige-Auswahl-Problem (gegeben \(x_1, \ldots, x_n \in \{0, 1\}\) mit \(n/2\) Einsen, finde \(i\) mit \(x_i = 1\)):

Was ist die Laufzeit des schnellsten deterministischen Algorithmus, was die erwartete Laufzeit des schnellsten Las-Vegas-Algorithmus?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Üppige-Auswahl-Problem (gegeben \(x_1, \ldots, x_n \in \{0, 1\}\) mit \(n/2\) Einsen, finde \(i\) mit \(x_i = 1\)):

Was ist die Laufzeit des schnellsten deterministischen Algorithmus, was die erwartete Laufzeit des schnellsten Las-Vegas-Algorithmus?
    
    Deterministisch: \(\Theta(n)\) (Worst Case).
Las-Vegas: \(O(1)\) erwartet, unabhängig von \(n\).

Das ist ein dramatischer Unterschied und ein Paradebeispiel für den Vorteil von Randomisierung: der Las-Vegas-Algorithmus probiert wiederholt zufällige Indizes und stoppt, sobald er eine \(1\) findet. Da die Hälfte der Bits \(1\) ist, ist die erwartete Anzahl Versuche \(\mathbb{E}[T] = 2\).

Die deterministische untere Schranke folgt aus einem Adversary-Argument: gegen jeden festen Algorithmus kann man eine Instanz konstruieren, auf der er \(n/2 + 1\) Bits lesen muss.
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Üppige-Auswahl-Problem (gegeben \(x_1, \ldots, x_n \in \{0, 1\}\) mit \(n/2\) Einsen, finde \(i\) mit \(x_i = 1\)):<br><br>Was ist die Laufzeit des schnellsten <b>deterministischen</b> Algorithmus, was die <b>erwartete</b> Laufzeit des schnellsten <b>Las-Vegas</b>-Algorithmus?
                        
                        
                        
                            Back
                            
                            Deterministisch: \(\Theta(n)\) (Worst Case).<br>Las-Vegas: \(O(1)\) erwartet, unabhängig von \(n\).<br><br>Das ist ein dramatischer Unterschied und ein Paradebeispiel für den Vorteil von Randomisierung: der Las-Vegas-Algorithmus probiert wiederholt zufällige Indizes und stoppt, sobald er eine \(1\) findet. Da die Hälfte der Bits \(1\) ist, ist die erwartete Anzahl Versuche \(\mathbb{E}[T] = 2\).<br><br>Die deterministische untere Schranke folgt aus einem Adversary-Argument: gegen jeden festen Algorithmus kann man eine Instanz konstruieren, auf der er \(n/2 + 1\) Bits lesen muss.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
                    
                
            
            
        
        
        
            Note 9: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: ;gVJQ/IG6*
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Im Beweis der QuickSort-Schranke \(t_n \leq 2(n+1) \ln n + O(n)\) startet man mit der Rekursion \(n \cdot t_n = \sum_{i=0}^{n-1}(n - 1 + t_i + t_{n-i-1})\).

Wie kommt man von dort zur einfachen Ungleichung \(t_n \leq \tfrac{n+1}{n} t_{n-1} + 2\)?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Im Beweis der QuickSort-Schranke \(t_n \leq 2(n+1) \ln n + O(n)\) startet man mit der Rekursion \(n \cdot t_n = \sum_{i=0}^{n-1}(n - 1 + t_i + t_{n-i-1})\).

Wie kommt man von dort zur einfachen Ungleichung \(t_n \leq \tfrac{n+1}{n} t_{n-1} + 2\)?
    
    Trick: Schreibe dieselbe Rekursion für \(n - 1\) auf:
\[(n-1) \cdot t_{n-1} = \sum_{i=0}^{n-2} (n - 2 + t_i + t_{n-i-2})\]und subtrahiere von der ursprünglichen:
\[n t_n - (n-1) t_{n-1} = 2(n-1) + 2 t_{n-1}.\]Umstellen liefert exakt
\[t_n = \tfrac{n+1}{n} t_{n-1} + \tfrac{2(n-1)}{n} \leq \tfrac{n+1}{n} t_{n-1} + 2.\]Per Induktion folgt \(t_n \leq 2 \sum_{i=3}^{n+1} \tfrac{n+1}{i}\), und mit der harmonischen Reihe \(H_n = \ln n + O(1)\) folgt das Resultat.
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Im Beweis der QuickSort-Schranke \(t_n \leq 2(n+1) \ln n + O(n)\) startet man mit der Rekursion \(n \cdot t_n = \sum_{i=0}^{n-1}(n - 1 + t_i + t_{n-i-1})\).<br><br>Wie kommt man von dort zur einfachen Ungleichung \(t_n \leq \tfrac{n+1}{n} t_{n-1} + 2\)?
                        
                        
                        
                            Back
                            
                            <b>Trick:</b> Schreibe dieselbe Rekursion für \(n - 1\) auf:<br>\[(n-1) \cdot t_{n-1} = \sum_{i=0}^{n-2} (n - 2 + t_i + t_{n-i-2})\]und subtrahiere von der ursprünglichen:<br>\[n t_n - (n-1) t_{n-1} = 2(n-1) + 2 t_{n-1}.\]Umstellen liefert exakt<br>\[t_n = \tfrac{n+1}{n} t_{n-1} + \tfrac{2(n-1)}{n} \leq \tfrac{n+1}{n} t_{n-1} + 2.\]Per Induktion folgt \(t_n \leq 2 \sum_{i=3}^{n+1} \tfrac{n+1}{i}\), und mit der harmonischen Reihe \(H_n = \ln n + O(1)\) folgt das Resultat.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
                    
                
            
            
        
        
        
            Note 10: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: @3P8r}IW5w
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Wann (und von wem) wurde der erste deterministische Primzahltest mit Polynomial-Laufzeit gefunden?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Wann (und von wem) wurde der erste deterministische Primzahltest mit Polynomial-Laufzeit gefunden?
    
    2002 von Agrawal, Kayal und Saxena (AKS-Test).

Davor: nur randomisierte Polynomialzeit-Tests bekannt:1976 Miller-Rabin: Monte-Carlo, einseitiger Fehler (immer korrekt für Primzahlen)
1977 Solovay-Strassen: alternativer Monte-Carlo-Test
1987 Adleman-Huang: einseitiger Fehler (immer korrekt für Nicht-Primzahlen)
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Wann (und von wem) wurde der erste <b>deterministische</b> Primzahltest mit Polynomial-Laufzeit gefunden?
                        
                        
                        
                            Back
                            
                            <b>2002</b> von Agrawal, Kayal und Saxena (<b>AKS-Test</b>).<br><br>Davor: nur randomisierte Polynomialzeit-Tests bekannt:<ul><li>1976 Miller-Rabin: Monte-Carlo, einseitiger Fehler (immer korrekt für Primzahlen)</li><li>1977 Solovay-Strassen: alternativer Monte-Carlo-Test</li><li>1987 Adleman-Huang: einseitiger Fehler (immer korrekt für Nicht-Primzahlen)</li></ul>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 11: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: @Id@]fUyPJ
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Monte-Carlo, Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\) 
Sei \(\varepsilon > 0\) und \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\Pr[A(I) \text{ korrekt}] \geq \tfrac{1}{2} + \varepsilon.\]Sei \(A_\delta\) der Algorithmus, der\[N = {{c1::\left\lceil 4\varepsilon^{-2} \ln \delta^{-1} \right\rceil}}\]Aufrufe von \(A\) macht und die Mehrheit der erhaltenen Antworten ausgibt. Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Monte-Carlo, Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\) 
Sei \(\varepsilon > 0\) und \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\Pr[A(I) \text{ korrekt}] \geq \tfrac{1}{2} + \varepsilon.\]Sei \(A_\delta\) der Algorithmus, der\[N = {{c1::\left\lceil 4\varepsilon^{-2} \ln \delta^{-1} \right\rceil}}\]Aufrufe von \(A\) macht und die Mehrheit der erhaltenen Antworten ausgibt. Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]
    
    
    
    Achtung: \(N\) skaliert hier quadratisch in \(\varepsilon^{-1}\) (statt linear wie bei einseitigem Fehler oder Las-Vegas) und nutzt nicht die erste richtige Antwort, sondern den Mehrheitsentscheid.

Beweis nutzt die Chernoff-Schranke \(\Pr[X \leq (1-\eta)\mathbb{E}[X]] \leq e^{-\eta^2 \mathbb{E}[X]/2}\) auf die Anzahl korrekter Aufrufe.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Monte-Carlo, Fehlerwahrscheinlichkeit </b>\(&lt; \tfrac{1}{2}\)&nbsp;<br>Sei \(\varepsilon &gt; 0\) und \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\Pr[A(I) \text{ korrekt}] \geq \tfrac{1}{2} + \varepsilon.\]Sei \(A_\delta\) der Algorithmus, der\[N = {{c1::\left\lceil 4\varepsilon^{-2} \ln \delta^{-1} \right\rceil}}\]Aufrufe von \(A\) macht und {{c2::die Mehrheit der erhaltenen Antworten}} ausgibt. Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]
                        
                        
                        
                            Extra
                            
                            Achtung: \(N\) skaliert hier <b>quadratisch</b> in \(\varepsilon^{-1}\) (statt linear wie bei einseitigem Fehler oder Las-Vegas) und nutzt nicht die erste richtige Antwort, sondern den Mehrheitsentscheid.<br><br>Beweis nutzt die Chernoff-Schranke \(\Pr[X \leq (1-\eta)\mathbb{E}[X]] \leq e^{-\eta^2 \mathbb{E}[X]/2}\) auf die Anzahl korrekter Aufrufe.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 12: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: BEp+Di
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Für \(\mathrm{QuickSelect}(A, 1, n, k)\) mit zufälligem Pivot gilt:\[\mathbb{E}[T] \leq 8n,\]also \(\mathbb{E}[T] = O(n)\) erwartet, wobei \(T\) die Anzahl Vergleiche bezeichnet.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Für \(\mathrm{QuickSelect}(A, 1, n, k)\) mit zufälligem Pivot gilt:\[\mathbb{E}[T] \leq 8n,\]also \(\mathbb{E}[T] = O(n)\) erwartet, wobei \(T\) die Anzahl Vergleiche bezeichnet.
    
    
    
    Proof Included.

Beweisidee (siehe separate Karte zur \(N_j\)-Konstruktion): Man partitioniert die Aufrufe nach Grössenklassen und nutzt, dass mit Wahrscheinlichkeit \(\geq 1/2\) ein Aufruf das Intervall um Faktor \(3/4\) verkleinert. Die geometrische Reihe \(\sum_{j \geq 1} (3/4)^{j-1} = 4\) zusammen mit \(\mathbb{E}[N_j] \leq 2\) liefert \(\mathbb{E}[T] \leq 2n \cdot 4 = 8n\).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Für \(\mathrm{QuickSelect}(A, 1, n, k)\) mit zufälligem Pivot gilt:\[\mathbb{E}[T] \leq {{c1::8n}},\]also \(\mathbb{E}[T] = {{c2::O(n)}}\) erwartet, wobei \(T\) die Anzahl Vergleiche bezeichnet.
                        
                        
                        
                            Extra
                            
                            Proof Included.<br><br>Beweisidee (siehe separate Karte zur \(N_j\)-Konstruktion): Man partitioniert die Aufrufe nach Grössenklassen und nutzt, dass mit Wahrscheinlichkeit \(\geq 1/2\) ein Aufruf das Intervall um Faktor \(3/4\) verkleinert. Die geometrische Reihe \(\sum_{j \geq 1} (3/4)^{j-1} = 4\) zusammen mit \(\mathbb{E}[N_j] \leq 2\) liefert \(\mathbb{E}[T] \leq 2n \cdot 4 = 8n\).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
                    
                
            
            
        
        
        
            Note 13: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: CR2my^EB=I
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Ein klassischer Algorithmus \(A\) erhält Eingabe \(I\) und liefert Ausgabe \(A(I)\). Es gilt:\(A(I)\) ist immer genau und korrekt,
bei gleicher Eingabe immer dieselbe Ausgabe (\(A\) ist eine Funktion),
dieselbe Laufzeit.
Ein randomisierter Algorithmus erhält zusätzlich eine Zufallsquelle \(R\) und liefert Ausgabe \(A(I, R)\). Die Ausgabe ist manchmal richtig, manchmal fast richtig, manchmal schnell, das Verhalten ist nicht reproduzierbar. \(A\) ist nach wie vor eine Funktion auf den Paaren \((I, R)\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Ein klassischer Algorithmus \(A\) erhält Eingabe \(I\) und liefert Ausgabe \(A(I)\). Es gilt:\(A(I)\) ist immer genau und korrekt,
bei gleicher Eingabe immer dieselbe Ausgabe (\(A\) ist eine Funktion),
dieselbe Laufzeit.
Ein randomisierter Algorithmus erhält zusätzlich eine Zufallsquelle \(R\) und liefert Ausgabe \(A(I, R)\). Die Ausgabe ist manchmal richtig, manchmal fast richtig, manchmal schnell, das Verhalten ist nicht reproduzierbar. \(A\) ist nach wie vor eine Funktion auf den Paaren \((I, R)\).
    
    
    
    Reproduzierbarkeit ist die zentrale Eigenschaft, die beim Übergang zum randomisierten Algorithmus verloren geht.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Ein <b>klassischer</b> Algorithmus \(A\) erhält Eingabe \(I\) und liefert Ausgabe \(A(I)\). Es gilt:<ul><li>\(A(I)\) ist immer {{c1::genau und korrekt}},</li><li>bei gleicher Eingabe immer {{c2::dieselbe Ausgabe (\(A\) ist eine Funktion)}},</li><li>{{c3::dieselbe Laufzeit}}.</li></ul>Ein <b>randomisierter</b> Algorithmus erhält zusätzlich eine Zufallsquelle \(R\) und liefert Ausgabe \(A(I, R)\). Die Ausgabe ist {{c4::manchmal richtig, manchmal fast richtig, manchmal schnell}}, das Verhalten ist {{c5::nicht reproduzierbar}}. \(A\) ist nach wie vor eine Funktion auf den Paaren \((I, R)\).
                        
                        
                        
                            Extra
                            
                            Reproduzierbarkeit ist die zentrale Eigenschaft, die beim Übergang zum randomisierten Algorithmus verloren geht.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 14: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: FiE@x{E.i3
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Skizziere den Beweis von \(\mathbb{E}[T] \leq 8n\) für QuickSelect.

Wie wird \(T\) zerlegt, und wieso gilt \(\mathbb{E}[N_j] \leq 2\)?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Skizziere den Beweis von \(\mathbb{E}[T] \leq 8n\) für QuickSelect.

Wie wird \(T\) zerlegt, und wieso gilt \(\mathbb{E}[N_j] \leq 2\)?
    
    Zerlegung: Definiere \(N_j\) als Anzahl Aufrufe von QuickSelect mit\[(3/4)^j n < r_i - \ell_i + 1 \leq (3/4)^{j-1} n.\]Da jeder Partition-Aufruf \(r_i - \ell_i\) Vergleiche braucht:\[T \leq \sum_{j=1}^{\infty} N_j \cdot (3/4)^{j-1} n.\]Schlüsselbeobachtung für \(\mathbb{E}[N_j] \leq 2\): Wählt man als Pivot eines der mittleren \(\tfrac{1}{2}(r_i - \ell_i + 1)\) Elemente, so wird die Intervallgrösse mindestens um Faktor \(3/4\) reduziert. Die Wahrscheinlichkeit dafür ist \(\geq 1/2\), pro Pivot-Wahl unabhängig.

Also ist \(N_j\) durch eine geometrisch verteilte Variable mit \(p = 1/2\) dominiert, woraus \(\mathbb{E}[N_j] \leq 2\) folgt.

Zusammen:\[\mathbb{E}[T] \leq n \sum_{j=1}^{\infty} \mathbb{E}[N_j] \cdot (3/4)^{j-1} \leq 2n \sum_{j=1}^{\infty} (3/4)^{j-1} = 8n.\]
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Skizziere den Beweis von \(\mathbb{E}[T] \leq 8n\) für QuickSelect.<br><br>Wie wird \(T\) zerlegt, und wieso gilt \(\mathbb{E}[N_j] \leq 2\)?
                        
                        
                        
                            Back
                            
                            <b>Zerlegung:</b> Definiere \(N_j\) als Anzahl Aufrufe von QuickSelect mit\[(3/4)^j n &lt; r_i - \ell_i + 1 \leq (3/4)^{j-1} n.\]Da jeder Partition-Aufruf \(r_i - \ell_i\) Vergleiche braucht:\[T \leq \sum_{j=1}^{\infty} N_j \cdot (3/4)^{j-1} n.\]<b>Schlüsselbeobachtung für \(\mathbb{E}[N_j] \leq 2\):</b> Wählt man als Pivot eines der <b>mittleren \(\tfrac{1}{2}(r_i - \ell_i + 1)\)</b> Elemente, so wird die Intervallgrösse mindestens um Faktor \(3/4\) reduziert. Die Wahrscheinlichkeit dafür ist \(\geq 1/2\), pro Pivot-Wahl unabhängig.<br><br>Also ist \(N_j\) durch eine geometrisch verteilte Variable mit \(p = 1/2\) dominiert, woraus \(\mathbb{E}[N_j] \leq 2\) folgt.<br><br><b>Zusammen:</b>\[\mathbb{E}[T] \leq n \sum_{j=1}^{\infty} \mathbb{E}[N_j] \cdot (3/4)^{j-1} \leq 2n \sum_{j=1}^{\infty} (3/4)^{j-1} = 8n.\]
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
                    
                
            
            
        
        
        
            Note 15: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: GUSRKOlJ(I
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Miller-Rabin-Primzahltest (für \(n > 1\) ungerade):1. Schreibe n - 1 = 2^k · d mit d ungerade
2. Wähle a ∈ [n-1] zufällig gleichverteilt
3. if a^d mod n = 1 oder ∃i ∈ {0,...,k-1}: a^(2^i·d) mod n = n-1:
     return 'Primzahl'
   else:
     return 'keine Primzahl'
Korrektheit:Falls \(n\) prim: Ausgabe immer korrekt.
Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\), tatsächlich sogar \(\leq \tfrac{1}{4}\)}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Miller-Rabin-Primzahltest (für \(n > 1\) ungerade):1. Schreibe n - 1 = 2^k · d mit d ungerade
2. Wähle a ∈ [n-1] zufällig gleichverteilt
3. if a^d mod n = 1 oder ∃i ∈ {0,...,k-1}: a^(2^i·d) mod n = n-1:
     return 'Primzahl'
   else:
     return 'keine Primzahl'
Korrektheit:Falls \(n\) prim: Ausgabe immer korrekt.
Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\), tatsächlich sogar \(\leq \tfrac{1}{4}\)}}.
    
    
    
    Im Gegensatz zum Fermat-Test funktioniert Miller-Rabin auch für Carmichael-Zahlen.

Beispiel \(n = 561\) mit \(a = 2\): \(n - 1 = 560 = 2^4 \cdot 35\), und \(2^{280} \equiv_{561} 1\), aber \(2^{140} \equiv_{561} 67 \notin \{1, 560\}\). Also ist \(2\) ein Miller-Rabin-Zertifikat dafür, dass \(561\) nicht prim ist.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Miller-Rabin-Primzahltest</b> (für \(n &gt; 1\) ungerade):<pre>1. Schreibe n - 1 = 2^k · d mit d ungerade
2. Wähle a ∈ [n-1] zufällig gleichverteilt
3. if a^d mod n = 1 oder ∃i ∈ {0,...,k-1}: a^(2^i·d) mod n = n-1:
     return 'Primzahl'
   else:
     return 'keine Primzahl'</pre>Korrektheit:<ul><li>Falls \(n\) prim: {{c1::Ausgabe immer korrekt}}.</li><li>Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\), tatsächlich sogar \(\leq \tfrac{1}{4}\)}}.</li></ul>
                        
                        
                        
                            Extra
                            
                            Im Gegensatz zum Fermat-Test funktioniert Miller-Rabin auch für Carmichael-Zahlen.<br><br>Beispiel \(n = 561\) mit \(a = 2\): \(n - 1 = 560 = 2^4 \cdot 35\), und \(2^{280} \equiv_{561} 1\), aber \(2^{140} \equiv_{561} 67 \notin \{1, 560\}\). Also ist \(2\) ein Miller-Rabin-Zertifikat dafür, dass \(561\) nicht prim ist.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 16: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: MH1KRE1DzH
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Las-Vegas-Algorithmus für das Üppige-Auswahl-Problemrepeat:
    i := Uniform({1, ..., n})
    if x_i = 1: return i
Sei \(T\) die Anzahl an Wiederholungen. Da \(\Pr[x_i = 1] = \Pr[x_i = 0] = \tfrac{1}{2}\) für einen zufälligen Index \(i\), gilt:\[\Pr[T > k] = {{c1::\left(\tfrac{1}{2}\right)^k}}.\]Folglich:\[\Pr[T \leq k] = {{c2::1 - \left(\tfrac{1}{2}\right)^k}}.\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Las-Vegas-Algorithmus für das Üppige-Auswahl-Problemrepeat:
    i := Uniform({1, ..., n})
    if x_i = 1: return i
Sei \(T\) die Anzahl an Wiederholungen. Da \(\Pr[x_i = 1] = \Pr[x_i = 0] = \tfrac{1}{2}\) für einen zufälligen Index \(i\), gilt:\[\Pr[T > k] = {{c1::\left(\tfrac{1}{2}\right)^k}}.\]Folglich:\[\Pr[T \leq k] = {{c2::1 - \left(\tfrac{1}{2}\right)^k}}.\]
    
    
    
    \(T\) ist geometrisch verteilt mit Parameter \(p = \tfrac{1}{2}\).

Konkrete Werte: \(\Pr[T > 10] = 1/1024 < 0{,}001\), also \(\Pr[T \leq 10] > 0{,}999\). Mit \(\leq 20\) Wiederholungen erreicht man Wahrscheinlichkeit \(> 0{,}999999\).

Wichtig: \(T\) hängt nicht von \(n\) ab, weil die Erfolgswahrscheinlichkeit pro Versuch konstant \(\tfrac{1}{2}\) ist (genau die Hälfte der Bits sind \(1\)).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Las-Vegas-Algorithmus für das Üppige-Auswahl-Problem</b><pre>repeat:
    i := Uniform({1, ..., n})
    if x_i = 1: return i</pre>Sei \(T\) die Anzahl an Wiederholungen. Da \(\Pr[x_i = 1] = \Pr[x_i = 0] = \tfrac{1}{2}\) für einen zufälligen Index \(i\), gilt:\[\Pr[T &gt; k] = {{c1::\left(\tfrac{1}{2}\right)^k}}.\]Folglich:\[\Pr[T \leq k] = {{c2::1 - \left(\tfrac{1}{2}\right)^k}}.\]
                        
                        
                        
                            Extra
                            
                            \(T\) ist geometrisch verteilt mit Parameter \(p = \tfrac{1}{2}\).<br><br>Konkrete Werte: \(\Pr[T &gt; 10] = 1/1024 &lt; 0{,}001\), also \(\Pr[T \leq 10] &gt; 0{,}999\). Mit \(\leq 20\) Wiederholungen erreicht man Wahrscheinlichkeit \(&gt; 0{,}999999\).<br><br>Wichtig: \(T\) hängt <b>nicht von \(n\)</b> ab, weil die Erfolgswahrscheinlichkeit pro Versuch konstant \(\tfrac{1}{2}\) ist (genau die Hälfte der Bits sind \(1\)).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
                    
                
            
            
        
        
        
            Note 17: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: Pa^@bE6s8n
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Üppige-Auswahl-Problem
Gegeben sind \(x_1, \ldots, x_n \in \{0, 1\}\), von denen genau die Hälfte gleich \(1\) sind (\(n\) gerade).
Berechne einen Index \(i\) mit \(x_i = 1\).

Trivialer deterministischer Algorithmus (in Zeit \(O(n)\)):for i = 1, ..., n:
    if x_i = 1: return i
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Üppige-Auswahl-Problem
Gegeben sind \(x_1, \ldots, x_n \in \{0, 1\}\), von denen genau die Hälfte gleich \(1\) sind (\(n\) gerade).
Berechne einen Index \(i\) mit \(x_i = 1\).

Trivialer deterministischer Algorithmus (in Zeit \(O(n)\)):for i = 1, ..., n:
    if x_i = 1: return i
    
    
    
    Das Problem heisst üppig, weil es sehr viele gültige Antworten gibt (genau \(n/2\)). Trotzdem braucht jeder deterministische Algorithmus im Worst Case \(\Omega(n)\) Zeit, während ein einfacher Las-Vegas-Algorithmus mit erwartet \(O(1)\) auskommt.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Üppige-Auswahl-Problem<br></b>Gegeben sind \(x_1, \ldots, x_n \in \{0, 1\}\), von denen {{c1::genau die Hälfte}} gleich \(1\) sind (\(n\) gerade).<br>Berechne {{c2::einen Index \(i\) mit \(x_i = 1\)}}.<br><br>Trivialer deterministischer Algorithmus (in Zeit \(O({{c3::n}})\)):<pre>for i = 1, ..., n:
    if x_i = 1: return i</pre>
                        
                        
                        
                            Extra
                            
                            Das Problem heisst <i>üppig</i>, weil es sehr viele gültige Antworten gibt (genau \(n/2\)). Trotzdem braucht jeder deterministische Algorithmus im Worst Case \(\Omega(n)\) Zeit, während ein einfacher Las-Vegas-Algorithmus mit erwartet \(O(1)\) auskommt.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
                    
                
            
            
        
        
        
            Note 18: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: T+YN#N>,$x
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Im Allgemeinen ist die Fehlerreduktion bei Monte-Carlo-Algorithmen nicht möglich.
(Gegenbeispiel: Algorithmus, der mit Wahrscheinlichkeit \(\tfrac{1}{2}\) JA bzw. NEIN antwortet, unabhängig von der Eingabe.)

Möglich ist sie aber bei:einseitigem Fehler, oder
{{c2::Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\)}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Im Allgemeinen ist die Fehlerreduktion bei Monte-Carlo-Algorithmen nicht möglich.
(Gegenbeispiel: Algorithmus, der mit Wahrscheinlichkeit \(\tfrac{1}{2}\) JA bzw. NEIN antwortet, unabhängig von der Eingabe.)

Möglich ist sie aber bei:einseitigem Fehler, oder
{{c2::Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\)}}.
    
    
    
    Bei einseitigem Fehler genügt eine einzige korrekte Antwort, um die Wahrheit zu kennen (Wiederholung + erste eindeutige Antwort).
Bei Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\) hilft Mehrheitsentscheid (Chernoff-Argument).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Im Allgemeinen ist die Fehlerreduktion bei Monte-Carlo-Algorithmen <b>nicht möglich</b>.<br>(Gegenbeispiel: Algorithmus, der mit Wahrscheinlichkeit \(\tfrac{1}{2}\) JA bzw. NEIN antwortet, unabhängig von der Eingabe.)<br><br>Möglich ist sie aber bei:<ul><li>{{c1::einseitigem Fehler}}, oder</li><li>{{c2::Fehlerwahrscheinlichkeit \(&lt; \tfrac{1}{2}\)}}.</li></ul>
                        
                        
                        
                            Extra
                            
                            Bei einseitigem Fehler genügt eine einzige korrekte Antwort, um die Wahrheit zu kennen (Wiederholung + erste eindeutige Antwort).<br>Bei Fehlerwahrscheinlichkeit \(&lt; \tfrac{1}{2}\) hilft Mehrheitsentscheid (Chernoff-Argument).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 19: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: VKeMFH&qvc
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Bei einem Monte-Carlo-Algorithmus ist die Korrektheit (bzw. Qualität) eine Zufallsvariable, die Laufzeit hingegen nicht vom Zufall abhängig.

Ziel: immer schnell, meistens korrekt/gut.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Bei einem Monte-Carlo-Algorithmus ist die Korrektheit (bzw. Qualität) eine Zufallsvariable, die Laufzeit hingegen nicht vom Zufall abhängig.

Ziel: immer schnell, meistens korrekt/gut.
    
    
    
    Merksatz: Monte-Carlo ist schnell und vielleicht falsch, Las-Vegas ist korrekt und vielleicht langsam.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Bei einem <b>Monte-Carlo-Algorithmus</b> ist {{c1::die Korrektheit (bzw. Qualität)}}&nbsp;eine Zufallsvariable, die {{c1::Laufzeit}}&nbsp;hingegen nicht vom Zufall abhängig.<br><br>Ziel: {{c2::immer schnell, meistens korrekt/gut}}.
                        
                        
                        
                            Extra
                            
                            Merksatz: Monte-Carlo ist <i>schnell und vielleicht falsch</i>, Las-Vegas ist <i>korrekt und vielleicht langsam</i>.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 20: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: a+AQXsL|IC
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Monte-Carlo, einseitiger Fehler
Sei \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\begin{gathered}\Pr[A(I) = \text{JA}] = 1, \text{ falls } I \text{ JA-Instanz},\\ \Pr[A(I) = \text{NEIN}] \geq \varepsilon, \text{ falls } I \text{ NEIN-Instanz}.\end{gathered}\]Sei \(A_\delta\) der Algorithmus, der \(A\) solange aufruft, bis entweder NEIN ausgegeben wird (dann selbst NEIN) oder bis\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\]mal JA ausgegeben wurde (dann selbst JA). Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Monte-Carlo, einseitiger Fehler
Sei \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\begin{gathered}\Pr[A(I) = \text{JA}] = 1, \text{ falls } I \text{ JA-Instanz},\\ \Pr[A(I) = \text{NEIN}] \geq \varepsilon, \text{ falls } I \text{ NEIN-Instanz}.\end{gathered}\]Sei \(A_\delta\) der Algorithmus, der \(A\) solange aufruft, bis entweder NEIN ausgegeben wird (dann selbst NEIN) oder bis\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\]mal JA ausgegeben wurde (dann selbst JA). Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]
    
    
    
    Selbe Iterationsschranke wie bei Las-Vegas: \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\). Tatsächlich ist das hier äquivalent zur Las-Vegas-Sicht: man kann den einseitig-fehlerhaften MC-Algorithmus als Las-Vegas-Algorithmus auffassen, der '???' (alias 'JA') ausgibt, wenn er nicht sicher ist.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Monte-Carlo, einseitiger Fehler<br></b>Sei \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\begin{gathered}\Pr[A(I) = \text{JA}] = 1, \text{ falls } I \text{ JA-Instanz},\\ \Pr[A(I) = \text{NEIN}] \geq \varepsilon, \text{ falls } I \text{ NEIN-Instanz}.\end{gathered}\]Sei \(A_\delta\) der Algorithmus, der \(A\) solange aufruft, bis entweder NEIN ausgegeben wird (dann selbst NEIN) oder bis\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\]mal JA ausgegeben wurde (dann selbst JA). Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq {{c2::1 - \delta}}.\]
                        
                        
                        
                            Extra
                            
                            Selbe Iterationsschranke wie bei Las-Vegas: \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\). Tatsächlich ist das hier äquivalent zur Las-Vegas-Sicht: man kann den einseitig-fehlerhaften MC-Algorithmus als Las-Vegas-Algorithmus auffassen, der '???' (alias 'JA') ausgibt, wenn er nicht sicher ist.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 21: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: andmV{gT6%
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Fermat-Primzahltest:Fermat-Primzahltest(n):
  wähle a ∈ [n-1] zufällig gleichverteilt
  if a^(n-1) mod n = 1: return 'Primzahl'
  else: return 'keine Primzahl'
(Berechnung von \(a^{n-1} \bmod n\) schnell mit binärer Exponentiation.)

Korrektheit:Falls \(n\) prim: Ausgabe immer korrekt (kleiner Fermat).
Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\)}}, es sei denn \(n\) ist eine Carmichael-Zahl.
Durch \(k\)-faches Wiederholen lässt sich die Fehlerwahrscheinlichkeit auf {{c4::\(\leq \tfrac{1}{2^k}\)}} drücken.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Fermat-Primzahltest:Fermat-Primzahltest(n):
  wähle a ∈ [n-1] zufällig gleichverteilt
  if a^(n-1) mod n = 1: return 'Primzahl'
  else: return 'keine Primzahl'
(Berechnung von \(a^{n-1} \bmod n\) schnell mit binärer Exponentiation.)

Korrektheit:Falls \(n\) prim: Ausgabe immer korrekt (kleiner Fermat).
Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\)}}, es sei denn \(n\) ist eine Carmichael-Zahl.
Durch \(k\)-faches Wiederholen lässt sich die Fehlerwahrscheinlichkeit auf {{c4::\(\leq \tfrac{1}{2^k}\)}} drücken.
    
    
    
    Wir machen einen Fehler genau dann, wenn \(n\) nicht prim und \(a^{n-1} \equiv_n 1\). Ein solches \(a\) heisst Pseudoprimzahlbasis von \(n\).

Achtung: Die \(\tfrac{1}{2}\)-Schranke greift nicht für Carmichael-Zahlen, dort ist die Fehlerrate effektiv \(1\) (siehe nächste Karte).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Fermat-Primzahltest:</b><pre>Fermat-Primzahltest(n):
  wähle a ∈ [n-1] zufällig gleichverteilt
  if a^(n-1) mod n = 1: return 'Primzahl'
  else: return 'keine Primzahl'</pre>(Berechnung von \(a^{n-1} \bmod n\) schnell mit binärer Exponentiation.)<br><br>Korrektheit:<ul><li>Falls \(n\) prim: {{c1::Ausgabe immer korrekt}} (kleiner Fermat).</li><li>Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\)}}, es sei denn \(n\) ist eine {{c3::Carmichael-Zahl}}.</li></ul>Durch \(k\)-faches Wiederholen lässt sich die Fehlerwahrscheinlichkeit auf {{c4::\(\leq \tfrac{1}{2^k}\)}} drücken.
                        
                        
                        
                            Extra
                            
                            Wir machen einen Fehler genau dann, wenn \(n\) nicht prim und \(a^{n-1} \equiv_n 1\). Ein solches \(a\) heisst <b>Pseudoprimzahlbasis</b> von \(n\).<br><br>Achtung: Die \(\tfrac{1}{2}\)-Schranke greift nicht für Carmichael-Zahlen, dort ist die Fehlerrate effektiv \(1\) (siehe nächste Karte).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 22: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: j21wCKqyxl
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Im Beweis von \(\mathbb{E}[T_{1,n}] \leq 2(n+1) \ln n + O(n)\) für QuickSort beobachtet man, dass \(\mathbb{E}[T_{\ell, r}]\) nur von \(r - \ell + 1\) abhängt, also nur von der Anzahl zu sortierender Elemente.

Dies motiviert die rekursive Definition von Zahlen \(t_n\) mit \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\):
\[t_n = {{c2::\begin{cases} 0, & \text{falls } n \leq 1, \\ \frac{1}{n} \sum_{i=0}^{n-1} (n - 1 + t_i + t_{n-i-1}), & \text{falls } n \geq 2. \end{cases} }}\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Im Beweis von \(\mathbb{E}[T_{1,n}] \leq 2(n+1) \ln n + O(n)\) für QuickSort beobachtet man, dass \(\mathbb{E}[T_{\ell, r}]\) nur von \(r - \ell + 1\) abhängt, also nur von der Anzahl zu sortierender Elemente.

Dies motiviert die rekursive Definition von Zahlen \(t_n\) mit \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\):
\[t_n = {{c2::\begin{cases} 0, & \text{falls } n \leq 1, \\ \frac{1}{n} \sum_{i=0}^{n-1} (n - 1 + t_i + t_{n-i-1}), & \text{falls } n \geq 2. \end{cases} }}\]
    
    
    
    Herleitung: \(\mathbb{E}[T_{\ell, r}] = \sum_{i=\ell}^{r} \Pr[t = i] \cdot (r - \ell + \mathbb{E}[T_{\ell, i-1}] + \mathbb{E}[T_{i+1, r}])\) (Linearität des Erwartungswerts + Satz über bedingten Erwartungswert), wobei \(t\) auf \(\{\ell, \ldots, r\}\) gleichverteilt ist (paarweise verschiedene Elemente). Daraus folgt durch Induktion über \(r - \ell\), dass \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Im Beweis von \(\mathbb{E}[T_{1,n}] \leq 2(n+1) \ln n + O(n)\) für QuickSort beobachtet man, dass \(\mathbb{E}[T_{\ell, r}]\) {{c1::nur von \(r - \ell + 1\) abhängt}}, also nur von der Anzahl zu sortierender Elemente.<br><br>Dies motiviert die rekursive Definition von Zahlen \(t_n\) mit \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\):<br>\[t_n = {{c2::\begin{cases} 0, &amp; \text{falls } n \leq 1, \\ \frac{1}{n} \sum_{i=0}^{n-1} (n - 1 + t_i + t_{n-i-1}), &amp; \text{falls } n \geq 2. \end{cases} }}\]
                        
                        
                        
                            Extra
                            
                            Herleitung: \(\mathbb{E}[T_{\ell, r}] = \sum_{i=\ell}^{r} \Pr[t = i] \cdot (r - \ell + \mathbb{E}[T_{\ell, i-1}] + \mathbb{E}[T_{i+1, r}])\) (Linearität des Erwartungswerts + Satz über bedingten Erwartungswert), wobei \(t\) auf \(\{\ell, \ldots, r\}\) gleichverteilt ist (paarweise verschiedene Elemente). Daraus folgt durch Induktion über \(r - \ell\), dass \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
                    
                
            
            
        
        
        
            Note 23: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: k!;R/,m=ac
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Designziel für Primzahltests: Laufzeit polynomiell in \(\log n\) (Darstellungsgrösse). Naives Trial-Division bis \(\sqrt{n}\) ist zu langsam für \(n \approx 2^{1000}\).

Der \(\mathrm{ggT}\) zweier Zahlen \(m, n\) lässt sich mit dem Euklid-Algorithmus in \(O((\log nm)^3)\) berechnen. Damit:Euklid-Primzahltest(n):
  wähle a ∈ [n-1] zufällig gleichverteilt
  if ggT(a, n) = 1: return 'Primzahl'
  else: return 'keine Primzahl'
Korrektheit:Falls \(n\) prim: Ausgabe immer korrekt (alle \(a \in [n-1]\) sind teilerfremd zu \(n\)).
Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c3::\(\frac{|\mathbb{Z}_n^*|}{n-1}\)}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Designziel für Primzahltests: Laufzeit polynomiell in \(\log n\) (Darstellungsgrösse). Naives Trial-Division bis \(\sqrt{n}\) ist zu langsam für \(n \approx 2^{1000}\).

Der \(\mathrm{ggT}\) zweier Zahlen \(m, n\) lässt sich mit dem Euklid-Algorithmus in \(O((\log nm)^3)\) berechnen. Damit:Euklid-Primzahltest(n):
  wähle a ∈ [n-1] zufällig gleichverteilt
  if ggT(a, n) = 1: return 'Primzahl'
  else: return 'keine Primzahl'
Korrektheit:Falls \(n\) prim: Ausgabe immer korrekt (alle \(a \in [n-1]\) sind teilerfremd zu \(n\)).
Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c3::\(\frac{|\mathbb{Z}_n^*|}{n-1}\)}}.
    
    
    
    Trivialerweise gilt: \(\mathrm{ggT}(a, n) > 1\) für ein \(a \in [n-1]\) \(\Rightarrow\) \(n\) nicht prim. Der Test sucht also einen kleinen gemeinsamen Faktor mit zufälligem \(a\).

Problem: für \(n = p^2\) ist die Fehlerrate \(\approx 1 - 1/\sqrt{n}\), also fast \(1\). Der Test ist deshalb in der Praxis nutzlos.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Designziel für Primzahltests: Laufzeit polynomiell in \(\log n\) (Darstellungsgrösse). Naives Trial-Division bis \(\sqrt{n}\) ist zu langsam für \(n \approx 2^{1000}\).<br><br>Der \(\mathrm{ggT}\) zweier Zahlen \(m, n\) lässt sich mit dem Euklid-Algorithmus in \(O({{c1::(\log nm)^3}})\)&nbsp;berechnen. Damit:<pre>Euklid-Primzahltest(n):
  wähle a ∈ [n-1] zufällig gleichverteilt
  if ggT(a, n) = 1: return 'Primzahl'
  else: return 'keine Primzahl'</pre>Korrektheit:<ul><li>Falls \(n\) prim: {{c2::Ausgabe immer korrekt (alle \(a \in [n-1]\) sind teilerfremd zu \(n\))}}.</li><li>Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c3::\(\frac{|\mathbb{Z}_n^*|}{n-1}\)}}.</li></ul>
                        
                        
                        
                            Extra
                            
                            Trivialerweise gilt: \(\mathrm{ggT}(a, n) &gt; 1\) für ein \(a \in [n-1]\) \(\Rightarrow\) \(n\) nicht prim. Der Test sucht also einen kleinen gemeinsamen Faktor mit zufälligem \(a\).<br><br>Problem: für \(n = p^2\) ist die Fehlerrate \(\approx 1 - 1/\sqrt{n}\), also fast \(1\). Der Test ist deshalb in der Praxis nutzlos.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 24: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: m;emJ<(X_K
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega(n)\).

Beweisidee (Adversary-Argument): 
Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens \(n/2 + 1\) Eingabezahlen, bevor er eine \(1\) sieht.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega(n)\).

Beweisidee (Adversary-Argument): 
Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens \(n/2 + 1\) Eingabezahlen, bevor er eine \(1\) sieht.
    
    
    
    Das ist ein typisches Adversary-Argument: Der "Gegenspieler" entscheidet die Eingabe erst während der Ausführung, immer so, dass der Algorithmus möglichst lange braucht. Da der Algorithmus deterministisch ist, weiss der Adversary genau, welche Position als nächstes gelesen wird, und kann sie auf \(0\) setzen.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega({{c1::n}})\).<br><br><b>Beweisidee (Adversary-Argument):</b> <br>Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit&nbsp;{{c2::\(0\)}}, solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens {{c3::\(n/2 + 1\)}} Eingabezahlen, bevor er eine \(1\) sieht.
                        
                        
                        
                            Extra
                            
                            Das ist ein typisches <b>Adversary-Argument</b>: Der "Gegenspieler" entscheidet die Eingabe erst während der Ausführung, immer so, dass der Algorithmus möglichst lange braucht. Da der Algorithmus deterministisch ist, weiss der Adversary genau, welche Position als nächstes gelesen wird, und kann sie auf \(0\) setzen.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
                    
                
            
            
        
        
        
            Note 25: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: p,MlVR+5|=
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Welche Anteile von \(a \in [n-1]\) sind Zertifikate dafür, dass \(n\) nicht prim ist?

Zertifikat Bedingung an \(a\) Anteil
Trivial \(a \geq 2\) und \(a \mid n\) \({{c1::> \tfrac{1}{n}}}\)
Euklid \(\mathrm{ggT}(a, n) > 1\) \({{c2::> \tfrac{1}{\sqrt{n}}}}\)
Fermat \(a^{n-1} \not\equiv_n 1\) {{c3::\(\geq \tfrac{1}{2}\), ausser \(n\) Carmichael}}
Miller-Rabin verletzt MR-Bedingung {{c4::\(\geq \tfrac{3}{4}\) (\(n\) ungerade)}}

  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Welche Anteile von \(a \in [n-1]\) sind Zertifikate dafür, dass \(n\) nicht prim ist?

Zertifikat Bedingung an \(a\) Anteil
Trivial \(a \geq 2\) und \(a \mid n\) \({{c1::> \tfrac{1}{n}}}\)
Euklid \(\mathrm{ggT}(a, n) > 1\) \({{c2::> \tfrac{1}{\sqrt{n}}}}\)
Fermat \(a^{n-1} \not\equiv_n 1\) {{c3::\(\geq \tfrac{1}{2}\), ausser \(n\) Carmichael}}
Miller-Rabin verletzt MR-Bedingung {{c4::\(\geq \tfrac{3}{4}\) (\(n\) ungerade)}}

    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Welche Anteile von \(a \in [n-1]\) sind <b>Zertifikate</b> dafür, dass \(n\) <b>nicht prim</b> ist?<br><br><table style="border-collapse:collapse;border:1px solid;"><thead><tr><th style="border:1px solid;padding:4px;">Zertifikat</th><th style="border:1px solid;padding:4px;">Bedingung an \(a\)</th><th style="border:1px solid;padding:4px;">Anteil</th></tr></thead><tbody><tr><td style="border:1px solid;padding:4px;">Trivial</td><td style="border:1px solid;padding:4px;">\(a \geq 2\) und \(a \mid n\)</td><td style="border:1px solid;padding:4px;">\({{c1::&gt; \tfrac{1}{n}}}\)</td></tr><tr><td style="border:1px solid;padding:4px;">Euklid</td><td style="border:1px solid;padding:4px;">\(\mathrm{ggT}(a, n) &gt; 1\)</td><td style="border:1px solid;padding:4px;">\({{c2::&gt; \tfrac{1}{\sqrt{n}}}}\)</td></tr><tr><td style="border:1px solid;padding:4px;">Fermat</td><td style="border:1px solid;padding:4px;">\(a^{n-1} \not\equiv_n 1\)</td><td style="border:1px solid;padding:4px;">{{c3::\(\geq \tfrac{1}{2}\), ausser \(n\) Carmichael}}<br></td></tr><tr><td style="border:1px solid;padding:4px;">Miller-Rabin</td><td style="border:1px solid;padding:4px;">verletzt MR-Bedingung</td><td style="border:1px solid;padding:4px;">{{c4::\(\geq \tfrac{3}{4}\) (\(n\) ungerade)}}<br></td></tr></tbody></table>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 26: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: pt-ci_M_
            

            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::7._Abschätzen_von_Wahrscheinlichkeiten::2._Die_Ungleichung_von_Chernoff
  
  
    Seien \(X_1, \ldots, X_n\) unabhängige Bernoulli-verteilte Zufallsvariablen mit \(\Pr[X_i = 1] = p_i\) und \(\Pr[X_i = 0] = 1 - p_i\).

Dann gilt für \(X = \sum_{i=1}^{n} X_i\)
\(\Pr[X \geq (1+\delta)\,\mathbb{E}[X]] \;\leq\; {{c1::e^{-\frac{1}{3}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \leq (1-\delta)\,\mathbb{E}[X]] \;\geq\; {{c2::e^{-\frac{1}{2}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \geq t] \;\leq\; {{c3::2^{-t} }}\) für alle \(t \geq 2e\,\mathbb{E}[X]\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::7._Abschätzen_von_Wahrscheinlichkeiten::2._Die_Ungleichung_von_Chernoff
  
  
    Seien \(X_1, \ldots, X_n\) unabhängige Bernoulli-verteilte Zufallsvariablen mit \(\Pr[X_i = 1] = p_i\) und \(\Pr[X_i = 0] = 1 - p_i\).

Dann gilt für \(X = \sum_{i=1}^{n} X_i\)
\(\Pr[X \geq (1+\delta)\,\mathbb{E}[X]] \;\leq\; {{c1::e^{-\frac{1}{3}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \leq (1-\delta)\,\mathbb{E}[X]] \;\geq\; {{c2::e^{-\frac{1}{2}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \geq t] \;\leq\; {{c3::2^{-t} }}\) für alle \(t \geq 2e\,\mathbb{E}[X]\).
    
    
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::7._Abschätzen_von_Wahrscheinlichkeiten::2._Die_Ungleichung_von_Chernoff
  
  
    Seien \(X_1, \ldots, X_n\) unabhängige Bernoulli-verteilte Zufallsvariablen mit \(\Pr[X_i = 1] = p_i\) und \(\Pr[X_i = 0] = 1 - p_i\).

Dann gilt für \(X = \sum_{i=1}^{n} X_i\)
\(\Pr[X \geq (1+\delta)\,\mathbb{E}[X]] \;\leq\; {{c1::e^{-\frac{1}{3}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \leq (1-\delta)\,\mathbb{E}[X]] \;\leq\; {{c2::e^{-\frac{1}{2}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \geq t] \;\leq\; {{c3::2^{-t} }}\) für alle \(t \geq 2e\,\mathbb{E}[X]\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::7._Abschätzen_von_Wahrscheinlichkeiten::2._Die_Ungleichung_von_Chernoff
  
  
    Seien \(X_1, \ldots, X_n\) unabhängige Bernoulli-verteilte Zufallsvariablen mit \(\Pr[X_i = 1] = p_i\) und \(\Pr[X_i = 0] = 1 - p_i\).

Dann gilt für \(X = \sum_{i=1}^{n} X_i\)
\(\Pr[X \geq (1+\delta)\,\mathbb{E}[X]] \;\leq\; {{c1::e^{-\frac{1}{3}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \leq (1-\delta)\,\mathbb{E}[X]] \;\leq\; {{c2::e^{-\frac{1}{2}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 < \delta \leq 1\)
\(\Pr[X \geq t] \;\leq\; {{c3::2^{-t} }}\) für alle \(t \geq 2e\,\mathbb{E}[X]\).
    
    
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            Seien \(X_1, \ldots, X_n\) unabhängige Bernoulli-verteilte Zufallsvariablen mit \(\Pr[X_i = 1] = p_i\) und \(\Pr[X_i = 0] = 1 - p_i\).<br>
Dann gilt für \(X = \sum_{i=1}^{n} X_i\)<br><ol><li>\(\Pr[X \geq (1+\delta)\,\mathbb{E}[X]] \;\leq\; {{c1::e^{-\frac{1}{3}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 &lt; \delta \leq 1\)</li><li>\(\Pr[X \leq (1-\delta)\,\mathbb{E}[X]] \;\geq\; {{c2::e^{-\frac{1}{2}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 &lt; \delta \leq 1\)</li><li>\(\Pr[X \geq t] \;\leq\; {{c3::2^{-t} }}\) für alle \(t \geq 2e\,\mathbb{E}[X]\).</li></ol>
                            Seien \(X_1, \ldots, X_n\) unabhängige Bernoulli-verteilte Zufallsvariablen mit \(\Pr[X_i = 1] = p_i\) und \(\Pr[X_i = 0] = 1 - p_i\).<br>
Dann gilt für \(X = \sum_{i=1}^{n} X_i\)<br><ol><li>\(\Pr[X \geq (1+\delta)\,\mathbb{E}[X]] \;\leq\; {{c1::e^{-\frac{1}{3}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 &lt; \delta \leq 1\)</li><li>\(\Pr[X \leq (1-\delta)\,\mathbb{E}[X]] \;\leq\; {{c2::e^{-\frac{1}{2}\delta^2\,\mathbb{E}[X]} }}\) für alle \(0 &lt; \delta \leq 1\)</li><li>\(\Pr[X \geq t] \;\leq\; {{c3::2^{-t} }}\) für alle \(t \geq 2e\,\mathbb{E}[X]\).</li></ol>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::7._Abschätzen_von_Wahrscheinlichkeiten::2._Die_Ungleichung_von_Chernoff
                    
                    
                    
                
            
            
        

        
        
            Note 27: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: s=]4*X3Fbz
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Kleiner fermatscher Satz 
Ist \(n \in \mathbb{N}\) prim, so gilt für alle \(a \in [n-1]\):\[a^{n-1} \equiv_n 1\quad\text{(bzw.} a^{n-1} = 1 \text{ in } \mathbb{Z}_n^*).\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Kleiner fermatscher Satz 
Ist \(n \in \mathbb{N}\) prim, so gilt für alle \(a \in [n-1]\):\[a^{n-1} \equiv_n 1\quad\text{(bzw.} a^{n-1} = 1 \text{ in } \mathbb{Z}_n^*).\]
    
    
    
    Folgt aus dem Satz von Lagrange: für die Gruppe \(\mathbb{Z}_n^*\) gilt \(a^{|\mathbb{Z}_n^*|} = 1\) für alle \(a \in \mathbb{Z}_n^*\). Da \(n\) prim, ist \(|\mathbb{Z}_n^*| = \varphi(n) = n - 1\).

Allgemeiner gilt für jedes \(n\) und jedes \(a \in \mathbb{Z}_n^*\): \(a^{\varphi(n)} \equiv_n 1\) (Satz von Euler).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Kleiner fermatscher Satz</b>&nbsp;<br>Ist \(n \in \mathbb{N}\) prim, so gilt für alle \(a \in [n-1]\):\[a^{n-1} \equiv_n {{c1::1}}\quad\text{(bzw.} a^{n-1} = 1 \text{ in } \mathbb{Z}_n^*).\]
                        
                        
                        
                            Extra
                            
                            Folgt aus dem Satz von Lagrange: für die Gruppe \(\mathbb{Z}_n^*\) gilt \(a^{|\mathbb{Z}_n^*|} = 1\) für alle \(a \in \mathbb{Z}_n^*\). Da \(n\) prim, ist \(|\mathbb{Z}_n^*| = \varphi(n) = n - 1\).<br><br>Allgemeiner gilt für jedes \(n\) und jedes \(a \in \mathbb{Z}_n^*\): \(a^{\varphi(n)} \equiv_n 1\) (Satz von Euler).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 28: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: t&2cm[5&m<
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Beim Las-Vegas-Algorithmus für das Üppige-Auswahl-Problem ist \(T\) die Anzahl an Wiederholungen mit \(\Pr[T > k] = (1/2)^k\).

Was ist \(\mathbb{E}[T]\)? Gib zwei Herleitungen an.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Beim Las-Vegas-Algorithmus für das Üppige-Auswahl-Problem ist \(T\) die Anzahl an Wiederholungen mit \(\Pr[T > k] = (1/2)^k\).

Was ist \(\mathbb{E}[T]\)? Gib zwei Herleitungen an.
    
    \[\mathbb{E}[T] = 2.\]Erwartete Laufzeit des Algorithmus: \(O(1)\), unabhängig von \(n\).

Direkter Ansatz (über \(\mathbb{E}[T] = \sum_{k \geq 1} \Pr[T \geq k]\)):
\[\begin{gathered}\mathbb{E}[T] = \sum_{k=1}^{\infty} \Pr[T \geq k] = \sum_{k=1}^{\infty} \Pr[T > k - 1] = \sum_{k=1}^{\infty} \left(\tfrac{1}{2}\right)^{k-1}\\= 1 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8} + \cdots = 2.\end{gathered}\]Indirekter Ansatz (Rekursion via Fallunterscheidung im ersten Versuch):
\[\mathbb{E}[T] = \Pr[x_i = 1] \cdot 1 + \Pr[x_i = 0] \cdot (1 + \mathbb{E}[T']),\]wobei \(T'\) die Anzahl an weiteren Wiederholungen ist, falls die erste fehlschlägt. Da \(T'\) und \(T\) gleichverteilt sind:
\[\mathbb{E}[T] = \tfrac{1}{2} \cdot 1 + \tfrac{1}{2}(1 + \mathbb{E}[T]) = 1 + \tfrac{1}{2}\mathbb{E}[T] \;\Longrightarrow\; \mathbb{E}[T] = 2.\]
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Beim Las-Vegas-Algorithmus für das Üppige-Auswahl-Problem ist \(T\) die Anzahl an Wiederholungen mit \(\Pr[T &gt; k] = (1/2)^k\).<br><br>Was ist \(\mathbb{E}[T]\)? Gib zwei Herleitungen an.
                        
                        
                        
                            Back
                            
                            \[\mathbb{E}[T] = 2.\]Erwartete Laufzeit des Algorithmus: \(O(1)\), unabhängig von \(n\).<br><br><b>Direkter Ansatz</b> (über \(\mathbb{E}[T] = \sum_{k \geq 1} \Pr[T \geq k]\)):<br>\[\begin{gathered}\mathbb{E}[T] = \sum_{k=1}^{\infty} \Pr[T \geq k] = \sum_{k=1}^{\infty} \Pr[T &gt; k - 1] = \sum_{k=1}^{\infty} \left(\tfrac{1}{2}\right)^{k-1}\\= 1 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8} + \cdots = 2.\end{gathered}\]<b>Indirekter Ansatz</b> (Rekursion via Fallunterscheidung im ersten Versuch):<br>\[\mathbb{E}[T] = \Pr[x_i = 1] \cdot 1 + \Pr[x_i = 0] \cdot (1 + \mathbb{E}[T']),\]wobei \(T'\) die Anzahl an weiteren Wiederholungen ist, falls die erste fehlschlägt. Da \(T'\) und \(T\) gleichverteilt sind:<br>\[\mathbb{E}[T] = \tfrac{1}{2} \cdot 1 + \tfrac{1}{2}(1 + \mathbb{E}[T]) = 1 + \tfrac{1}{2}\mathbb{E}[T] \;\Longrightarrow\; \mathbb{E}[T] = 2.\]
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
                    
                
            
            
        
        
        
            Note 29: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: tgqE9:PFcm
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Ein klassisches Beispiel für einen Las-Vegas-Algorithmus ist QuickSort: der Algorithmus sortiert immer richtig, aber die konkrete Laufzeit hängt von der zufälligen Wahl der Pivot-Elemente ab.

Mit \(\mathrm{Partition}(A, \ell, r, p)\) sei eine Prozedur bezeichnet, die mit \(r - \ell\) Vergleichen \(A[\ell], \ldots, A[r]\) so umsortiert, dass links von \(A[p]\) alle kleineren und rechts alle grösseren Elemente stehen, und die Endposition \(t\) zurückgibt.QuickSort(A, ℓ, r):
  if ℓ < r:
    p ← Uniform({ℓ, ℓ+1, ..., r})    # Pivot zufällig
    t ← Partition(A, ℓ, r, p)
    QuickSort(A, ℓ, t-1)
    QuickSort(A, t+1, r)
Sei \(T_{\ell, r}\) die zufällige Anzahl an Vergleichen bei \(\mathrm{QuickSort}(A, \ell, r)\). Dann:
\[\mathbb{E}[T_{1,n}] \leq 2(n+1) \ln n + O(n).\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
  
  
    Ein klassisches Beispiel für einen Las-Vegas-Algorithmus ist QuickSort: der Algorithmus sortiert immer richtig, aber die konkrete Laufzeit hängt von der zufälligen Wahl der Pivot-Elemente ab.

Mit \(\mathrm{Partition}(A, \ell, r, p)\) sei eine Prozedur bezeichnet, die mit \(r - \ell\) Vergleichen \(A[\ell], \ldots, A[r]\) so umsortiert, dass links von \(A[p]\) alle kleineren und rechts alle grösseren Elemente stehen, und die Endposition \(t\) zurückgibt.QuickSort(A, ℓ, r):
  if ℓ < r:
    p ← Uniform({ℓ, ℓ+1, ..., r})    # Pivot zufällig
    t ← Partition(A, ℓ, r, p)
    QuickSort(A, ℓ, t-1)
    QuickSort(A, t+1, r)
Sei \(T_{\ell, r}\) die zufällige Anzahl an Vergleichen bei \(\mathrm{QuickSort}(A, \ell, r)\). Dann:
\[\mathbb{E}[T_{1,n}] \leq 2(n+1) \ln n + O(n).\]
    
    
    
    Im Worst Case ist die Laufzeit \(\Theta(n^2)\) (z.B. wenn das Pivot stets minimal oder maximal ist). Erwartet aber nur \(O(n \log n)\), und das unabhängig von der Eingabe, weil das Pivot zufällig gewählt wird.

Annahme im Beweis: alle Elemente von \(A\) sind paarweise verschieden, sodass \(t\) eindeutig ist.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Ein klassisches Beispiel für einen <b>Las-Vegas-Algorithmus</b> ist <b>QuickSort</b>: der Algorithmus sortiert {{c1::immer richtig}}, aber die konkrete Laufzeit hängt von der zufälligen Wahl der Pivot-Elemente ab.<br><br>Mit \(\mathrm{Partition}(A, \ell, r, p)\) sei eine Prozedur bezeichnet, die mit \(r - \ell\) Vergleichen \(A[\ell], \ldots, A[r]\) so umsortiert, dass links von \(A[p]\) alle kleineren und rechts alle grösseren Elemente stehen, und die Endposition \(t\) zurückgibt.<pre>QuickSort(A, ℓ, r):
  if ℓ &lt; r:
    p ← Uniform({ℓ, ℓ+1, ..., r})    # Pivot zufällig
    t ← Partition(A, ℓ, r, p)
    QuickSort(A, ℓ, t-1)
    QuickSort(A, t+1, r)</pre>Sei \(T_{\ell, r}\) die zufällige Anzahl an Vergleichen bei \(\mathrm{QuickSort}(A, \ell, r)\). Dann:<br>\[\mathbb{E}[T_{1,n}] \leq {{c2::2(n+1) \ln n + O(n)}}.\]
                        
                        
                        
                            Extra
                            
                            Im Worst Case ist die Laufzeit \(\Theta(n^2)\) (z.B. wenn das Pivot stets minimal oder maximal ist). Erwartet aber nur \(O(n \log n)\), und das unabhängig von der Eingabe, weil das Pivot zufällig gewählt wird.<br><br>Annahme im Beweis: alle Elemente von \(A\) sind paarweise verschieden, sodass \(t\) eindeutig ist.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::2._Sortieren_und_Selektieren
                    
                
            
            
        
        
        
            Note 30: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: tw5dhN|-*-
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    \(PB_n\) ist eine {{c1::Untergruppe von \(\mathbb{Z}_n^*\)}}, denn\[a^{n-1} \equiv_n 1 \;\wedge\; b^{n-1} \equiv_n 1 \;\Longrightarrow\; (ab)^{n-1} \equiv_n 1.\]Folglich: ist \(n\) nicht Carmichael, dann ist \(|PB_n|\) ein {{c2::echter Teiler von \(|\mathbb{Z}_n^*|\)}}, also\[|PB_n| \leq {{c3::\frac{\varphi(n)}{2} \leq \frac{n-1}{2} }}.\]
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    \(PB_n\) ist eine {{c1::Untergruppe von \(\mathbb{Z}_n^*\)}}, denn\[a^{n-1} \equiv_n 1 \;\wedge\; b^{n-1} \equiv_n 1 \;\Longrightarrow\; (ab)^{n-1} \equiv_n 1.\]Folglich: ist \(n\) nicht Carmichael, dann ist \(|PB_n|\) ein {{c2::echter Teiler von \(|\mathbb{Z}_n^*|\)}}, also\[|PB_n| \leq {{c3::\frac{\varphi(n)}{2} \leq \frac{n-1}{2} }}.\]
    
    
    
    Genau diese Schranke liefert die Fehlerwahrscheinlichkeit \(\leq \tfrac{1}{2}\) des Fermat-Tests für Nicht-Carmichael-Zahlen: \(\Pr[\text{Fehler}] = |PB_n|/(n-1) \leq \tfrac{1}{2}\).

Der Beweis nutzt den Satz von Lagrange: jede echte Untergruppe einer endlichen Gruppe hat höchstens halb so viele Elemente wie die Gruppe selbst.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            \(PB_n\) ist eine {{c1::Untergruppe von \(\mathbb{Z}_n^*\)}}, denn\[a^{n-1} \equiv_n 1 \;\wedge\; b^{n-1} \equiv_n 1 \;\Longrightarrow\; (ab)^{n-1} \equiv_n 1.\]Folglich: ist \(n\) <b>nicht</b> Carmichael, dann ist \(|PB_n|\) ein {{c2::echter Teiler von \(|\mathbb{Z}_n^*|\)}}, also\[|PB_n| \leq {{c3::\frac{\varphi(n)}{2} \leq \frac{n-1}{2} }}.\]
                        
                        
                        
                            Extra
                            
                            Genau diese Schranke liefert die Fehlerwahrscheinlichkeit \(\leq \tfrac{1}{2}\) des Fermat-Tests für Nicht-Carmichael-Zahlen: \(\Pr[\text{Fehler}] = |PB_n|/(n-1) \leq \tfrac{1}{2}\).<br><br>Der Beweis nutzt den Satz von Lagrange: jede echte Untergruppe einer endlichen Gruppe hat höchstens halb so viele Elemente wie die Gruppe selbst.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 31: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: w;X(,bh1:N
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Die multiplikative Gruppe modulo \(n\) ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod \(n\). Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:\(n\) prim: \(\mathbb{Z}_n^* = [n-1]\) und \(\varphi(n) = n - 1\).
\(n = p^2\), \(p\) prim: \(\varphi(n) = p(p-1) = n - \sqrt{n}\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
  
  
    Die multiplikative Gruppe modulo \(n\) ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod \(n\). Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:\(n\) prim: \(\mathbb{Z}_n^* = [n-1]\) und \(\varphi(n) = n - 1\).
\(n = p^2\), \(p\) prim: \(\varphi(n) = p(p-1) = n - \sqrt{n}\).
    
    
    
    Beispiele: \(\mathbb{Z}_9^* = \{1, 2, 4, 5, 7, 8\}\), \(\varphi(9) = 6\). \(\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}\), \(\varphi(7) = 6\).

Konsequenz für den \(p^2\)-Fall beim Euklid-Test: \(\frac{|\mathbb{Z}_n^*|}{n-1} \approx 1 - \frac{1}{\sqrt{n}}\), die Fehlerrate ist also fast \(1\).
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Die <b>multiplikative Gruppe modulo \(n\)</b> ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod \(n\). Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:<ul><li>\(n\) prim: \(\mathbb{Z}_n^* = [n-1]\) und \(\varphi(n) = {{c3::n - 1}}\).</li><li>\(n = p^2\), \(p\) prim: \(\varphi(n) = {{c4::p(p-1) = n - \sqrt{n}}}\).</li></ul>
                        
                        
                        
                            Extra
                            
                            Beispiele: \(\mathbb{Z}_9^* = \{1, 2, 4, 5, 7, 8\}\), \(\varphi(9) = 6\). \(\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}\), \(\varphi(7) = 6\).<br><br>Konsequenz für den \(p^2\)-Fall beim Euklid-Test: \(\frac{|\mathbb{Z}_n^*|}{n-1} \approx 1 - \frac{1}{\sqrt{n}}\), die Fehlerrate ist also fast \(1\).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest
                    
                
            
            
        
        
        
            Note 32: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: |2|f7e7DL}
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Eine Zufallsquelle liefert nach vorgegebener Verteilung zufällige unabhängige Zufallsbits oder -zahlen. Zwei Typen:Physikalische Zufallsgeneratoren: Lottozahlen, Geigerzähler, Rauschen, Quantenexperimente.
Deterministische (Pseudo-)Zufallsgeneratoren: liefern, basierend auf einem Startwert (seed) \(s\), eine Folge \(s \to r_0(s), r_1(s), r_2(s), \ldots\) Das ermöglicht Reproduzierbarkeit, wenn man sich den Startwert merkt.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Eine Zufallsquelle liefert nach vorgegebener Verteilung zufällige unabhängige Zufallsbits oder -zahlen. Zwei Typen:Physikalische Zufallsgeneratoren: Lottozahlen, Geigerzähler, Rauschen, Quantenexperimente.
Deterministische (Pseudo-)Zufallsgeneratoren: liefern, basierend auf einem Startwert (seed) \(s\), eine Folge \(s \to r_0(s), r_1(s), r_2(s), \ldots\) Das ermöglicht Reproduzierbarkeit, wenn man sich den Startwert merkt.
    
    
    
    In der Analyse geht man von idealen Zufallsgeneratoren aus. Bei der Anwendung muss man aber berücksichtigen, dass Pseudo-Zufallsgeneratoren das nur näherungsweise leisten.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Eine <b>Zufallsquelle</b> liefert nach vorgegebener Verteilung zufällige unabhängige Zufallsbits oder -zahlen. Zwei Typen:<ul><li><b>Physikalische Zufallsgeneratoren</b>: {{c1::Lottozahlen, Geigerzähler, Rauschen, Quantenexperimente::Beispiele?}}.</li><li><b>Deterministische (Pseudo-)Zufallsgeneratoren</b>: liefern, basierend auf einem {{c2::Startwert (seed)}} \(s\), eine Folge \(s \to r_0(s), r_1(s), r_2(s), \ldots\) Das ermöglicht {{c3::Reproduzierbarkeit, wenn man sich den Startwert merkt}}.</li></ul>
                        
                        
                        
                            Extra
                            
                            In der Analyse geht man von idealen Zufallsgeneratoren aus. Bei der Anwendung muss man aber berücksichtigen, dass Pseudo-Zufallsgeneratoren das nur näherungsweise leisten.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 33: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Classic

                GUID: ~d57MCW=Q9
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Bei der Fehlerreduktion eines Las-Vegas-Algorithmus mit Erfolgswahrscheinlichkeit \(\geq \varepsilon\) genügen \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\) Wiederholungen, um \(\Pr[\text{korrekt}] \geq 1 - \delta\) zu erreichen.

Wie skaliert \(N\) in \(\delta\)? Was bedeutet das praktisch?
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
  
  
    Bei der Fehlerreduktion eines Las-Vegas-Algorithmus mit Erfolgswahrscheinlichkeit \(\geq \varepsilon\) genügen \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\) Wiederholungen, um \(\Pr[\text{korrekt}] \geq 1 - \delta\) zu erreichen.

Wie skaliert \(N\) in \(\delta\)? Was bedeutet das praktisch?
    
    \(N\) skaliert logarithmisch in \(\delta^{-1}\).

Praktisch: Um die Fehlerwahrscheinlichkeit um einen konstanten Faktor (z.B. von \(10^{-2}\) auf \(10^{-3}\)) zu reduzieren, sind nur konstant viele zusätzliche Iterationen nötig.

Beispiel \(\varepsilon = 0{,}25\): \(\delta = 10^{-1} \Rightarrow N = 10\), \(\delta = 10^{-2} \Rightarrow N = 19\), \(\delta = 10^{-3} \Rightarrow N = 28\), \(\ldots\) (jeweils \(+9\)).
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            Bei der Fehlerreduktion eines Las-Vegas-Algorithmus mit Erfolgswahrscheinlichkeit \(\geq \varepsilon\) genügen \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\) Wiederholungen, um \(\Pr[\text{korrekt}] \geq 1 - \delta\) zu erreichen.<br><br>Wie skaliert \(N\) in \(\delta\)? Was bedeutet das praktisch?
                        
                        
                        
                            Back
                            
                            \(N\) skaliert <b>logarithmisch</b> in \(\delta^{-1}\).<br><br>Praktisch: Um die Fehlerwahrscheinlichkeit um einen <b>konstanten Faktor</b> (z.B. von \(10^{-2}\) auf \(10^{-3}\)) zu reduzieren, sind nur <b>konstant viele zusätzliche Iterationen</b> nötig.<br><br>Beispiel \(\varepsilon = 0{,}25\): \(\delta = 10^{-1} \Rightarrow N = 10\), \(\delta = 10^{-2} \Rightarrow N = 19\), \(\delta = 10^{-3} \Rightarrow N = 28\), \(\ldots\) (jeweils \(+9\)).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::1._Reduktion_der_Fehlerwahrscheinlichkeit
                    
                
            
            
        
        
        
            Note 34: ETH::2. Semester::Analysis
            
                Deck: ETH::2. Semester::Analysis

                Note Type: Horvath Cloze

                GUID: CuzVNVUfwp
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
  
  
    Das Maximum, geschrieben \(\max(X)\), ist ein Element \(x_0 \in X\) mit der folgenden Eigenschaft: \(\forall x \in X\) \(x \leq x_0\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
  
  
    Das Maximum, geschrieben \(\max(X)\), ist ein Element \(x_0 \in X\) mit der folgenden Eigenschaft: \(\forall x \in X\) \(x \leq x_0\).
    
    
    
    Das Minimum, geschrieben \(\min(X)\), ist entsprechend mit \(\geq\) definiert.
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
  
  
    Das Maximum, geschrieben \(\max(X)\), ist ein Element \(x_0 \in X\) mit der folgenden Eigenschaft: \(\forall x \in X : x \leq x_0\) .
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
  
  
    Das Maximum, geschrieben \(\max(X)\), ist ein Element \(x_0 \in X\) mit der folgenden Eigenschaft: \(\forall x \in X : x \leq x_0\) .
    
    
    
    Das Minimum, geschrieben \(\min(X)\), ist entsprechend mit \(\geq\) definiert.
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            <div>Das {{c1::<b>Maximum</b>}}, geschrieben {{c1::\(\max(X)\)}}, ist ein Element \(x_0 \in X\) mit der folgenden Eigenschaft: {{c2::\(\forall x \in X\) \(x \leq x_0\)}}.</div>
                            <div>Das {{c1::<b>Maximum</b>}}, geschrieben {{c1::\(\max(X)\)}}, ist ein Element \(x_0 \in X\) mit der folgenden Eigenschaft: {{c2::\(\forall x \in X : x \leq x_0\) }}.</div>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
                    
                    
                    
                
            
            
        
        
        
            Note 35: ETH::2. Semester::Analysis
            
                Deck: ETH::2. Semester::Analysis

                Note Type: Horvath Cloze

                GUID: NA&O,x/IQT
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f : X = \mathbb{D}(f) \subset \mathbb{R} \to \mathbb{R}\). Wir nennen \(f\):

monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) \geq f(x_2)\)
streng monoton wachsend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\)
streng monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) > f(x_2)\)
(streng) monoton, falls \(f\) (streng) monoton wachsend oder (streng) monoton fallend ist.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f : X = \mathbb{D}(f) \subset \mathbb{R} \to \mathbb{R}\). Wir nennen \(f\):

monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) \geq f(x_2)\)
streng monoton wachsend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\)
streng monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) > f(x_2)\)
(streng) monoton, falls \(f\) (streng) monoton wachsend oder (streng) monoton fallend ist.
    
    
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f : X = \mathbb{D}(f) \subset \mathbb{R} \to \mathbb{R}\). Wir nennen \(f\):
monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) \geq f(x_2)\)
streng monoton wachsend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\)
streng monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) > f(x_2)\)
(streng) monoton, falls \(f\) (streng) monoton wachsend oder (streng) monoton fallend ist.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f : X = \mathbb{D}(f) \subset \mathbb{R} \to \mathbb{R}\). Wir nennen \(f\):
monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) \geq f(x_2)\)
streng monoton wachsend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\)
streng monoton fallend, falls \(\forall x_1, x_2 \in X: \;x_1 < x_2 \Rightarrow f(x_1) > f(x_2)\)
(streng) monoton, falls \(f\) (streng) monoton wachsend oder (streng) monoton fallend ist.
    
    
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            Sei \(f : X = \mathbb{D}(f) \subset \mathbb{R} \to \mathbb{R}\). Wir nennen \(f\):<br><br><ul><li><i>monoton fallend</i>, falls \(\forall x_1, x_2 \in X: \;{{c1::x_1 &lt; x_2 \Rightarrow f(x_1) \geq f(x_2)}}\)</li><li><i>streng monoton wachsend</i>, falls \(\forall x_1, x_2 \in X: \;{{c2::x_1 &lt; x_2 \Rightarrow f(x_1) &lt; f(x_2)}}\)</li><li><i>streng monoton fallend</i>, falls \(\forall x_1, x_2 \in X: \;{{c3::x_1 &lt; x_2 \Rightarrow f(x_1) &gt; f(x_2)}}\)</li><li><i>(streng) monoton</i>, falls \(f\) {{c4::(streng) monoton wachsend <i>oder</i> (streng) monoton fallend}} ist.</li></ul>
                            Sei \(f : X = \mathbb{D}(f) \subset \mathbb{R} \to \mathbb{R}\). Wir nennen \(f\):<br><ul><li><i>monoton fallend</i>, falls \(\forall x_1, x_2 \in X: \;{{c1::x_1 &lt; x_2 \Rightarrow f(x_1) \geq f(x_2)}}\)</li><li><i>streng monoton wachsend</i>, falls \(\forall x_1, x_2 \in X: \;{{c1::x_1 &lt; x_2 \Rightarrow f(x_1) &lt; f(x_2)}}\)</li><li><i>streng monoton fallend</i>, falls \(\forall x_1, x_2 \in X: \;{{c1::x_1 &lt; x_2 \Rightarrow f(x_1) &gt; f(x_2)}}\)</li><li><i>(streng) monoton</i>, falls \(f\) {{c2::(streng) monoton wachsend <i>oder</i> (streng) monoton fallend}} ist.</li></ul>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
                    
                    
                    
                
            
            
        
        
        
            Note 36: ETH::2. Semester::Analysis
            
                Deck: ETH::2. Semester::Analysis

                Note Type: Horvath Cloze

                GUID: d`:*hpWRF9
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f: \mathbb{D}(f) \to \mathbb{R}\) mit \(\mathbb{D}(f) \neq \emptyset\).

\(f\) heisst nach unten beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(f(x) \geq M\) \(\forall x \in \mathbb{D}(f)\)}}.
\(f\) heisst beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c2::\(|f(x)| \leq M\) \(\forall x \in \mathbb{D}(f)\)}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f: \mathbb{D}(f) \to \mathbb{R}\) mit \(\mathbb{D}(f) \neq \emptyset\).

\(f\) heisst nach unten beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(f(x) \geq M\) \(\forall x \in \mathbb{D}(f)\)}}.
\(f\) heisst beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c2::\(|f(x)| \leq M\) \(\forall x \in \mathbb{D}(f)\)}}.
    
    
    
    Äquivalent: \(f\) ist beschränkt gdw. \(f\) ist sowohl nach oben als auch nach unten beschränkt.
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f: \mathbb{D}(f) \to \mathbb{R}\) mit \(\mathbb{D}(f) \neq \emptyset\).
\(f\) heisst nach unten beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(f(x) \geq M\) \(\forall x \in \mathbb{D}(f)\)}}.
\(f\) heisst beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(|f(x)| \leq M\) \(\forall x \in \mathbb{D}(f)\)}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
  
  
    Sei \(f: \mathbb{D}(f) \to \mathbb{R}\) mit \(\mathbb{D}(f) \neq \emptyset\).
\(f\) heisst nach unten beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(f(x) \geq M\) \(\forall x \in \mathbb{D}(f)\)}}.
\(f\) heisst beschränkt, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(|f(x)| \leq M\) \(\forall x \in \mathbb{D}(f)\)}}.
    
    
    
    Äquivalent: \(f\) ist beschränkt gdw. \(f\) ist sowohl nach oben als auch nach unten beschränkt.
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            Sei \(f: \mathbb{D}(f) \to \mathbb{R}\) mit \(\mathbb{D}(f) \neq \emptyset\).<br><br><ul><li>\(f\) heisst <i>nach unten beschränkt</i>, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(f(x) \geq M\) \(\forall x \in \mathbb{D}(f)\)}}.</li><li>\(f\) heisst <i>beschränkt</i>, falls \(M \in \mathbb{R}\) existiert mit {{c2::\(|f(x)| \leq M\) \(\forall x \in \mathbb{D}(f)\)}}.</li></ul>
                            Sei \(f: \mathbb{D}(f) \to \mathbb{R}\) mit \(\mathbb{D}(f) \neq \emptyset\).<br><ul><li>\(f\) heisst <i>nach unten beschränkt</i>, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(f(x) \geq M\) \(\forall x \in \mathbb{D}(f)\)}}.</li><li>\(f\) heisst <i>beschränkt</i>, falls \(M \in \mathbb{R}\) existiert mit {{c1::\(|f(x)| \leq M\) \(\forall x \in \mathbb{D}(f)\)}}.</li></ul>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::2._Semester::Analysis::4._Funktionen::1._Grundlagen
                    
                    
                    
                
            
            
        
        
        
            Note 37: ETH::2. Semester::Analysis
            
                Deck: ETH::2. Semester::Analysis

                Note Type: Horvath Cloze

                GUID: MtKk|s)sx.
            
            deleted
            

            
            
            
                
                    Deleted Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::Analysis::0._Nützliches
  
  
    \(1 + x \le e^x\) oft nützlich.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::Analysis::0._Nützliches
  
  
    \(1 + x \le e^x\) oft nützlich.
    
    
  



                        
                    
                    
                
                
                    Current
                    Note has been deleted
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            \(1 + x \le {{c1::e^x::Exponential}}\)&nbsp;oft nützlich.
                            
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    ETH::2._Semester::Analysis::0._Nützliches

Field	Before	After
Front		Beim Las-Vegas-Algorithmus für das Üppige-Auswahl-Problem ist \(T\) die Anzahl an Wiederholungen mit \(\Pr[T > k] = (1/2)^k\).<br><br>Was ist \(\mathbb{E}[T]\)? Gib zwei Herleitungen an.
Back		\[\mathbb{E}[T] = 2.\]Erwartete Laufzeit des Algorithmus: \(O(1)\), unabhängig von \(n\).<br><br><b>Direkter Ansatz</b> (über \(\mathbb{E}[T] = \sum_{k \geq 1} \Pr[T \geq k]\)):<br>\[\begin{gathered}\mathbb{E}[T] = \sum_{k=1}^{\infty} \Pr[T \geq k] = \sum_{k=1}^{\infty} \Pr[T > k - 1] = \sum_{k=1}^{\infty} \left(\tfrac{1}{2}\right)^{k-1}\\= 1 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8} + \cdots = 2.\end{gathered}\]<b>Indirekter Ansatz</b> (Rekursion via Fallunterscheidung im ersten Versuch):<br>\[\mathbb{E}[T] = \Pr[x_i = 1] \cdot 1 + \Pr[x_i = 0] \cdot (1 + \mathbb{E}[T']),\]wobei \(T'\) die Anzahl an weiteren Wiederholungen ist, falls die erste fehlschlägt. Da \(T'\) und \(T\) gleichverteilt sind:<br>\[\mathbb{E}[T] = \tfrac{1}{2} \cdot 1 + \tfrac{1}{2}(1 + \mathbb{E}[T]) = 1 + \tfrac{1}{2}\mathbb{E}[T] \;\Longrightarrow\; \mathbb{E}[T] = 2.\]

Field	Before	After
Text		Sei \(PB_n := \{a \in [n-1] \mid a^{n-1} \equiv_n 1\} = \{a \in \mathbb{Z}_n^* \mid a^{n-1} \equiv_n 1\}\) die Menge der <b>Pseudoprimzahlbasen</b> von \(n\).<br><br>\(n\) heisst <b>Carmichael-Zahl</b>, falls {{c1::\(n\) nicht prim ist und \(PB_n = \mathbb{Z}_n^*\)}}.<br><br>Kleinste Beispiele: \({{c2::561 = 3 \cdot 11 \cdot 17,\ 1105 = 5 \cdot 13 \cdot 17,\ 1729 = 7 \cdot 13 \cdot 19}}\).
Extra		Auf Carmichael-Zahlen versagt der Fermat-Test komplett: Jede Pseudoprimzahlbasis täuscht "Primzahl" vor, und \(PB_n\) ist die ganze multiplikative Gruppe \(\mathbb{Z}_n^*\). Die Fehlerwahrscheinlichkeit \(\|PB_n\|/(n-1) = \varphi(n)/(n-1)\) ist nahe \(1\).<br><br>Genau hier setzt der Miller-Rabin-Test an.

Field	Before	After
Text		Sei \(n > 2\) ungerade, schreibe \(n - 1 = 2^k d\) mit \(d\) ungerade.<br><br>Vorüberlegung: Für \(n\) prim ist \((\mathbb{Z}_n, +, \cdot)\) ein {{c1::Körper}}, und in einem Körper hat \(x^2 = 1\) genau zwei Lösungen: \({{c2::x = 1\ \text{und}\ x = n - 1\ (= -1)}}\).<br><br>Ist \(n\) prim und \(a \in [n-1]\), dann gilt:<ul><li>\(a^{2^k d} = a^{n-1} \equiv_n 1\) (kleiner Fermat),</li><li>also \(a^{2^{k-1}d} \equiv_n 1\) oder \(n - 1\),</li><li>falls \(\equiv_n 1\): wieder Quadratwurzel ziehen, \(a^{2^{k-2}d} \equiv_n 1\) oder \(n-1\),</li><li>... bis: falls \(a^{2d} \equiv_n 1\), dann \(a^d \equiv_n 1\) oder \(n - 1\).</li></ul><b>Miller-Rabin-Bedingung</b>: für \(n\) prim und alle \(a\) gilt<br>\[{{c3::a^d \equiv_n 1 \quad \text{oder} \quad \exists\, i \in \{0, 1, \ldots, k-1\}: a^{2^i d} \equiv_n n - 1.}}\]
Extra		Idee: aus \(a^{n-1} \equiv_n 1\) wiederholt Quadratwurzeln ziehen, solange das Ergebnis noch \(1\) ist. Im Körper sind die einzigen Quadratwurzeln von \(1\) genau \(\pm 1\), daher muss man irgendwann auf \(n-1\) treffen oder bei \(a^d \equiv_n 1\) landen.<br><br>Ein \(a\), das diese Bedingung verletzt, ist ein <b>Miller-Rabin-Zertifikat</b> dafür, dass \(n\) nicht prim ist.

Field	Before	After
Front		Üppige-Auswahl-Problem (gegeben \(x_1, \ldots, x_n \in \{0, 1\}\) mit \(n/2\) Einsen, finde \(i\) mit \(x_i = 1\)):<br><br>Was ist die Laufzeit des schnellsten <b>deterministischen</b> Algorithmus, was die <b>erwartete</b> Laufzeit des schnellsten <b>Las-Vegas</b>-Algorithmus?
Back		Deterministisch: \(\Theta(n)\) (Worst Case).<br>Las-Vegas: \(O(1)\) erwartet, unabhängig von \(n\).<br><br>Das ist ein dramatischer Unterschied und ein Paradebeispiel für den Vorteil von Randomisierung: der Las-Vegas-Algorithmus probiert wiederholt zufällige Indizes und stoppt, sobald er eine \(1\) findet. Da die Hälfte der Bits \(1\) ist, ist die erwartete Anzahl Versuche \(\mathbb{E}[T] = 2\).<br><br>Die deterministische untere Schranke folgt aus einem Adversary-Argument: gegen jeden festen Algorithmus kann man eine Instanz konstruieren, auf der er \(n/2 + 1\) Bits lesen muss.

Field	Before	After
Front		Im Beweis der QuickSort-Schranke \(t_n \leq 2(n+1) \ln n + O(n)\) startet man mit der Rekursion \(n \cdot t_n = \sum_{i=0}^{n-1}(n - 1 + t_i + t_{n-i-1})\).<br><br>Wie kommt man von dort zur einfachen Ungleichung \(t_n \leq \tfrac{n+1}{n} t_{n-1} + 2\)?
Back		<b>Trick:</b> Schreibe dieselbe Rekursion für \(n - 1\) auf:<br>\[(n-1) \cdot t_{n-1} = \sum_{i=0}^{n-2} (n - 2 + t_i + t_{n-i-2})\]und subtrahiere von der ursprünglichen:<br>\[n t_n - (n-1) t_{n-1} = 2(n-1) + 2 t_{n-1}.\]Umstellen liefert exakt<br>\[t_n = \tfrac{n+1}{n} t_{n-1} + \tfrac{2(n-1)}{n} \leq \tfrac{n+1}{n} t_{n-1} + 2.\]Per Induktion folgt \(t_n \leq 2 \sum_{i=3}^{n+1} \tfrac{n+1}{i}\), und mit der harmonischen Reihe \(H_n = \ln n + O(1)\) folgt das Resultat.

Field	Before	After
Front		Wann (und von wem) wurde der erste <b>deterministische</b> Primzahltest mit Polynomial-Laufzeit gefunden?
Back		<b>2002</b> von Agrawal, Kayal und Saxena (<b>AKS-Test</b>).<br><br>Davor: nur randomisierte Polynomialzeit-Tests bekannt:<ul><li>1976 Miller-Rabin: Monte-Carlo, einseitiger Fehler (immer korrekt für Primzahlen)</li><li>1977 Solovay-Strassen: alternativer Monte-Carlo-Test</li><li>1987 Adleman-Huang: einseitiger Fehler (immer korrekt für Nicht-Primzahlen)</li></ul>

Field	Before	After
Text		<b>Monte-Carlo, Fehlerwahrscheinlichkeit </b>\(< \tfrac{1}{2}\) <br>Sei \(\varepsilon > 0\) und \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\Pr[A(I) \text{ korrekt}] \geq \tfrac{1}{2} + \varepsilon.\]Sei \(A_\delta\) der Algorithmus, der\[N = {{c1::\left\lceil 4\varepsilon^{-2} \ln \delta^{-1} \right\rceil}}\]Aufrufe von \(A\) macht und {{c2::die Mehrheit der erhaltenen Antworten}} ausgibt. Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq 1 - \delta.\]
Extra		Achtung: \(N\) skaliert hier <b>quadratisch</b> in \(\varepsilon^{-1}\) (statt linear wie bei einseitigem Fehler oder Las-Vegas) und nutzt nicht die erste richtige Antwort, sondern den Mehrheitsentscheid.<br><br>Beweis nutzt die Chernoff-Schranke \(\Pr[X \leq (1-\eta)\mathbb{E}[X]] \leq e^{-\eta^2 \mathbb{E}[X]/2}\) auf die Anzahl korrekter Aufrufe.

Field	Before	After
Text		Für \(\mathrm{QuickSelect}(A, 1, n, k)\) mit zufälligem Pivot gilt:\[\mathbb{E}[T] \leq {{c1::8n}},\]also \(\mathbb{E}[T] = {{c2::O(n)}}\) erwartet, wobei \(T\) die Anzahl Vergleiche bezeichnet.
Extra		Proof Included.<br><br>Beweisidee (siehe separate Karte zur \(N_j\)-Konstruktion): Man partitioniert die Aufrufe nach Grössenklassen und nutzt, dass mit Wahrscheinlichkeit \(\geq 1/2\) ein Aufruf das Intervall um Faktor \(3/4\) verkleinert. Die geometrische Reihe \(\sum_{j \geq 1} (3/4)^{j-1} = 4\) zusammen mit \(\mathbb{E}[N_j] \leq 2\) liefert \(\mathbb{E}[T] \leq 2n \cdot 4 = 8n\).

Field	Before	After
Text		Ein <b>klassischer</b> Algorithmus \(A\) erhält Eingabe \(I\) und liefert Ausgabe \(A(I)\). Es gilt:<ul><li>\(A(I)\) ist immer {{c1::genau und korrekt}},</li><li>bei gleicher Eingabe immer {{c2::dieselbe Ausgabe (\(A\) ist eine Funktion)}},</li><li>{{c3::dieselbe Laufzeit}}.</li></ul>Ein <b>randomisierter</b> Algorithmus erhält zusätzlich eine Zufallsquelle \(R\) und liefert Ausgabe \(A(I, R)\). Die Ausgabe ist {{c4::manchmal richtig, manchmal fast richtig, manchmal schnell}}, das Verhalten ist {{c5::nicht reproduzierbar}}. \(A\) ist nach wie vor eine Funktion auf den Paaren \((I, R)\).
Extra		Reproduzierbarkeit ist die zentrale Eigenschaft, die beim Übergang zum randomisierten Algorithmus verloren geht.

Field	Before	After
Front		Skizziere den Beweis von \(\mathbb{E}[T] \leq 8n\) für QuickSelect.<br><br>Wie wird \(T\) zerlegt, und wieso gilt \(\mathbb{E}[N_j] \leq 2\)?
Back		<b>Zerlegung:</b> Definiere \(N_j\) als Anzahl Aufrufe von QuickSelect mit\[(3/4)^j n < r_i - \ell_i + 1 \leq (3/4)^{j-1} n.\]Da jeder Partition-Aufruf \(r_i - \ell_i\) Vergleiche braucht:\[T \leq \sum_{j=1}^{\infty} N_j \cdot (3/4)^{j-1} n.\]<b>Schlüsselbeobachtung für \(\mathbb{E}[N_j] \leq 2\):</b> Wählt man als Pivot eines der <b>mittleren \(\tfrac{1}{2}(r_i - \ell_i + 1)\)</b> Elemente, so wird die Intervallgrösse mindestens um Faktor \(3/4\) reduziert. Die Wahrscheinlichkeit dafür ist \(\geq 1/2\), pro Pivot-Wahl unabhängig.<br><br>Also ist \(N_j\) durch eine geometrisch verteilte Variable mit \(p = 1/2\) dominiert, woraus \(\mathbb{E}[N_j] \leq 2\) folgt.<br><br><b>Zusammen:</b>\[\mathbb{E}[T] \leq n \sum_{j=1}^{\infty} \mathbb{E}[N_j] \cdot (3/4)^{j-1} \leq 2n \sum_{j=1}^{\infty} (3/4)^{j-1} = 8n.\]

Field	Before	After
Text		<b>Miller-Rabin-Primzahltest</b> (für \(n > 1\) ungerade):<pre>1. Schreibe n - 1 = 2^k · d mit d ungerade 2. Wähle a ∈ [n-1] zufällig gleichverteilt 3. if a^d mod n = 1 oder ∃i ∈ {0,...,k-1}: a^(2^i·d) mod n = n-1: return 'Primzahl' else: return 'keine Primzahl'</pre>Korrektheit:<ul><li>Falls \(n\) prim: {{c1::Ausgabe immer korrekt}}.</li><li>Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\), tatsächlich sogar \(\leq \tfrac{1}{4}\)}}.</li></ul>
Extra		Im Gegensatz zum Fermat-Test funktioniert Miller-Rabin auch für Carmichael-Zahlen.<br><br>Beispiel \(n = 561\) mit \(a = 2\): \(n - 1 = 560 = 2^4 \cdot 35\), und \(2^{280} \equiv_{561} 1\), aber \(2^{140} \equiv_{561} 67 \notin \{1, 560\}\). Also ist \(2\) ein Miller-Rabin-Zertifikat dafür, dass \(561\) nicht prim ist.

Field	Before	After
Text		<b>Las-Vegas-Algorithmus für das Üppige-Auswahl-Problem</b><pre>repeat: i := Uniform({1, ..., n}) if x_i = 1: return i</pre>Sei \(T\) die Anzahl an Wiederholungen. Da \(\Pr[x_i = 1] = \Pr[x_i = 0] = \tfrac{1}{2}\) für einen zufälligen Index \(i\), gilt:\[\Pr[T > k] = {{c1::\left(\tfrac{1}{2}\right)^k}}.\]Folglich:\[\Pr[T \leq k] = {{c2::1 - \left(\tfrac{1}{2}\right)^k}}.\]
Extra		\(T\) ist geometrisch verteilt mit Parameter \(p = \tfrac{1}{2}\).<br><br>Konkrete Werte: \(\Pr[T > 10] = 1/1024 < 0{,}001\), also \(\Pr[T \leq 10] > 0{,}999\). Mit \(\leq 20\) Wiederholungen erreicht man Wahrscheinlichkeit \(> 0{,}999999\).<br><br>Wichtig: \(T\) hängt <b>nicht von \(n\)</b> ab, weil die Erfolgswahrscheinlichkeit pro Versuch konstant \(\tfrac{1}{2}\) ist (genau die Hälfte der Bits sind \(1\)).

Field	Before	After
Text		<b>Üppige-Auswahl-Problem<br></b>Gegeben sind \(x_1, \ldots, x_n \in \{0, 1\}\), von denen {{c1::genau die Hälfte}} gleich \(1\) sind (\(n\) gerade).<br>Berechne {{c2::einen Index \(i\) mit \(x_i = 1\)}}.<br><br>Trivialer deterministischer Algorithmus (in Zeit \(O({{c3::n}})\)):<pre>for i = 1, ..., n: if x_i = 1: return i</pre>
Extra		Das Problem heisst <i>üppig</i>, weil es sehr viele gültige Antworten gibt (genau \(n/2\)). Trotzdem braucht jeder deterministische Algorithmus im Worst Case \(\Omega(n)\) Zeit, während ein einfacher Las-Vegas-Algorithmus mit erwartet \(O(1)\) auskommt.

Field	Before	After
Text		Im Allgemeinen ist die Fehlerreduktion bei Monte-Carlo-Algorithmen <b>nicht möglich</b>.<br>(Gegenbeispiel: Algorithmus, der mit Wahrscheinlichkeit \(\tfrac{1}{2}\) JA bzw. NEIN antwortet, unabhängig von der Eingabe.)<br><br>Möglich ist sie aber bei:<ul><li>{{c1::einseitigem Fehler}}, oder</li><li>{{c2::Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\)}}.</li></ul>
Extra		Bei einseitigem Fehler genügt eine einzige korrekte Antwort, um die Wahrheit zu kennen (Wiederholung + erste eindeutige Antwort).<br>Bei Fehlerwahrscheinlichkeit \(< \tfrac{1}{2}\) hilft Mehrheitsentscheid (Chernoff-Argument).

Field	Before	After
Text		Bei einem <b>Monte-Carlo-Algorithmus</b> ist {{c1::die Korrektheit (bzw. Qualität)}} eine Zufallsvariable, die {{c1::Laufzeit}} hingegen nicht vom Zufall abhängig.<br><br>Ziel: {{c2::immer schnell, meistens korrekt/gut}}.
Extra		Merksatz: Monte-Carlo ist <i>schnell und vielleicht falsch</i>, Las-Vegas ist <i>korrekt und vielleicht langsam</i>.

Field	Before	After
Text		<b>Monte-Carlo, einseitiger Fehler<br></b>Sei \(A\) ein randomisierter Algorithmus, der immer JA oder NEIN ausgibt, mit\[\begin{gathered}\Pr[A(I) = \text{JA}] = 1, \text{ falls } I \text{ JA-Instanz},\\ \Pr[A(I) = \text{NEIN}] \geq \varepsilon, \text{ falls } I \text{ NEIN-Instanz}.\end{gathered}\]Sei \(A_\delta\) der Algorithmus, der \(A\) solange aufruft, bis entweder NEIN ausgegeben wird (dann selbst NEIN) oder bis\[N = {{c1::\left\lceil \varepsilon^{-1} \ln \delta^{-1} \right\rceil}}\]mal JA ausgegeben wurde (dann selbst JA). Dann gilt:\[\Pr[A_\delta(I) \text{ korrekt}] \geq {{c2::1 - \delta}}.\]
Extra		Selbe Iterationsschranke wie bei Las-Vegas: \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\). Tatsächlich ist das hier äquivalent zur Las-Vegas-Sicht: man kann den einseitig-fehlerhaften MC-Algorithmus als Las-Vegas-Algorithmus auffassen, der '???' (alias 'JA') ausgibt, wenn er nicht sicher ist.

Field	Before	After
Text		<b>Fermat-Primzahltest:</b><pre>Fermat-Primzahltest(n): wähle a ∈ [n-1] zufällig gleichverteilt if a^(n-1) mod n = 1: return 'Primzahl' else: return 'keine Primzahl'</pre>(Berechnung von \(a^{n-1} \bmod n\) schnell mit binärer Exponentiation.)<br><br>Korrektheit:<ul><li>Falls \(n\) prim: {{c1::Ausgabe immer korrekt}} (kleiner Fermat).</li><li>Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c2::\(\leq \tfrac{1}{2}\)}}, es sei denn \(n\) ist eine {{c3::Carmichael-Zahl}}.</li></ul>Durch \(k\)-faches Wiederholen lässt sich die Fehlerwahrscheinlichkeit auf {{c4::\(\leq \tfrac{1}{2^k}\)}} drücken.
Extra		Wir machen einen Fehler genau dann, wenn \(n\) nicht prim und \(a^{n-1} \equiv_n 1\). Ein solches \(a\) heisst <b>Pseudoprimzahlbasis</b> von \(n\).<br><br>Achtung: Die \(\tfrac{1}{2}\)-Schranke greift nicht für Carmichael-Zahlen, dort ist die Fehlerrate effektiv \(1\) (siehe nächste Karte).

Field	Before	After
Text		Im Beweis von \(\mathbb{E}[T_{1,n}] \leq 2(n+1) \ln n + O(n)\) für QuickSort beobachtet man, dass \(\mathbb{E}[T_{\ell, r}]\) {{c1::nur von \(r - \ell + 1\) abhängt}}, also nur von der Anzahl zu sortierender Elemente.<br><br>Dies motiviert die rekursive Definition von Zahlen \(t_n\) mit \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\):<br>\[t_n = {{c2::\begin{cases} 0, & \text{falls } n \leq 1, \\ \frac{1}{n} \sum_{i=0}^{n-1} (n - 1 + t_i + t_{n-i-1}), & \text{falls } n \geq 2. \end{cases} }}\]
Extra		Herleitung: \(\mathbb{E}[T_{\ell, r}] = \sum_{i=\ell}^{r} \Pr[t = i] \cdot (r - \ell + \mathbb{E}[T_{\ell, i-1}] + \mathbb{E}[T_{i+1, r}])\) (Linearität des Erwartungswerts + Satz über bedingten Erwartungswert), wobei \(t\) auf \(\{\ell, \ldots, r\}\) gleichverteilt ist (paarweise verschiedene Elemente). Daraus folgt durch Induktion über \(r - \ell\), dass \(\mathbb{E}[T_{\ell, r}] = t_{r - \ell + 1}\).

Field	Before	After
Text		Designziel für Primzahltests: Laufzeit polynomiell in \(\log n\) (Darstellungsgrösse). Naives Trial-Division bis \(\sqrt{n}\) ist zu langsam für \(n \approx 2^{1000}\).<br><br>Der \(\mathrm{ggT}\) zweier Zahlen \(m, n\) lässt sich mit dem Euklid-Algorithmus in \(O({{c1::(\log nm)^3}})\) berechnen. Damit:<pre>Euklid-Primzahltest(n): wähle a ∈ [n-1] zufällig gleichverteilt if ggT(a, n) = 1: return 'Primzahl' else: return 'keine Primzahl'</pre>Korrektheit:<ul><li>Falls \(n\) prim: {{c2::Ausgabe immer korrekt (alle \(a \in [n-1]\) sind teilerfremd zu \(n\))}}.</li><li>Falls \(n\) nicht prim: Falsche Ausgabe 'Primzahl' mit Wahrscheinlichkeit {{c3::\(\frac{\|\mathbb{Z}_n^*\|}{n-1}\)}}.</li></ul>
Extra		Trivialerweise gilt: \(\mathrm{ggT}(a, n) > 1\) für ein \(a \in [n-1]\) \(\Rightarrow\) \(n\) nicht prim. Der Test sucht also einen kleinen gemeinsamen Faktor mit zufälligem \(a\).<br><br>Problem: für \(n = p^2\) ist die Fehlerrate \(\approx 1 - 1/\sqrt{n}\), also fast \(1\). Der Test ist deshalb in der Praxis nutzlos.

Field	Before	After
Text		Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega({{c1::n}})\).<br><br><b>Beweisidee (Adversary-Argument):</b> <br>Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit {{c2::\(0\)}}, solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens {{c3::\(n/2 + 1\)}} Eingabezahlen, bevor er eine \(1\) sieht.
Extra		Das ist ein typisches <b>Adversary-Argument</b>: Der "Gegenspieler" entscheidet die Eingabe erst während der Ausführung, immer so, dass der Algorithmus möglichst lange braucht. Da der Algorithmus deterministisch ist, weiss der Adversary genau, welche Position als nächstes gelesen wird, und kann sie auf \(0\) setzen.

Zertifikat	Bedingung an \(a\)	Anteil
Trivial	\(a \geq 2\) und \(a \mid n\)	\({{c1::> \tfrac{1}{n}}}\)
Euklid	\(\mathrm{ggT}(a, n) > 1\)	\({{c2::> \tfrac{1}{\sqrt{n}}}}\)
Fermat	\(a^{n-1} \not\equiv_n 1\)	{{c3::\(\geq \tfrac{1}{2}\), ausser \(n\) Carmichael}}
Miller-Rabin	verletzt MR-Bedingung	{{c4::\(\geq \tfrac{3}{4}\) (\(n\) ungerade)}}

Field	Before	After
Text		<b>Kleiner fermatscher Satz</b> <br>Ist \(n \in \mathbb{N}\) prim, so gilt für alle \(a \in [n-1]\):\[a^{n-1} \equiv_n {{c1::1}}\quad\text{(bzw.} a^{n-1} = 1 \text{ in } \mathbb{Z}_n^*).\]
Extra		Folgt aus dem Satz von Lagrange: für die Gruppe \(\mathbb{Z}_n^\) gilt \(a^{\|\mathbb{Z}_n^\|} = 1\) für alle \(a \in \mathbb{Z}_n^\). Da \(n\) prim, ist \(\|\mathbb{Z}_n^\| = \varphi(n) = n - 1\).<br><br>Allgemeiner gilt für jedes \(n\) und jedes \(a \in \mathbb{Z}_n^*\): \(a^{\varphi(n)} \equiv_n 1\) (Satz von Euler).

Field	Before	After
Text		Ein klassisches Beispiel für einen <b>Las-Vegas-Algorithmus</b> ist <b>QuickSort</b>: der Algorithmus sortiert {{c1::immer richtig}}, aber die konkrete Laufzeit hängt von der zufälligen Wahl der Pivot-Elemente ab.<br><br>Mit \(\mathrm{Partition}(A, \ell, r, p)\) sei eine Prozedur bezeichnet, die mit \(r - \ell\) Vergleichen \(A[\ell], \ldots, A[r]\) so umsortiert, dass links von \(A[p]\) alle kleineren und rechts alle grösseren Elemente stehen, und die Endposition \(t\) zurückgibt.<pre>QuickSort(A, ℓ, r): if ℓ < r: p ← Uniform({ℓ, ℓ+1, ..., r}) # Pivot zufällig t ← Partition(A, ℓ, r, p) QuickSort(A, ℓ, t-1) QuickSort(A, t+1, r)</pre>Sei \(T_{\ell, r}\) die zufällige Anzahl an Vergleichen bei \(\mathrm{QuickSort}(A, \ell, r)\). Dann:<br>\[\mathbb{E}[T_{1,n}] \leq {{c2::2(n+1) \ln n + O(n)}}.\]
Extra		Im Worst Case ist die Laufzeit \(\Theta(n^2)\) (z.B. wenn das Pivot stets minimal oder maximal ist). Erwartet aber nur \(O(n \log n)\), und das unabhängig von der Eingabe, weil das Pivot zufällig gewählt wird.<br><br>Annahme im Beweis: alle Elemente von \(A\) sind paarweise verschieden, sodass \(t\) eindeutig ist.

Field	Before	After
Text		\(PB_n\) ist eine {{c1::Untergruppe von \(\mathbb{Z}_n^\)}}, denn\[a^{n-1} \equiv_n 1 \;\wedge\; b^{n-1} \equiv_n 1 \;\Longrightarrow\; (ab)^{n-1} \equiv_n 1.\]Folglich: ist \(n\) <b>nicht</b> Carmichael, dann ist \(\|PB_n\|\) ein {{c2::echter Teiler von \(\|\mathbb{Z}_n^\|\)}}, also\[\|PB_n\| \leq {{c3::\frac{\varphi(n)}{2} \leq \frac{n-1}{2} }}.\]
Extra		Genau diese Schranke liefert die Fehlerwahrscheinlichkeit \(\leq \tfrac{1}{2}\) des Fermat-Tests für Nicht-Carmichael-Zahlen: \(\Pr[\text{Fehler}] = \|PB_n\|/(n-1) \leq \tfrac{1}{2}\).<br><br>Der Beweis nutzt den Satz von Lagrange: jede echte Untergruppe einer endlichen Gruppe hat höchstens halb so viele Elemente wie die Gruppe selbst.

Field	Before	After
Text		Die <b>multiplikative Gruppe modulo \(n\)</b> ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod \(n\). Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::\|\mathbb{Z}_n^\|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:<ul><li>\(n\) prim: \(\mathbb{Z}_n^ = [n-1]\) und \(\varphi(n) = {{c3::n - 1}}\).</li><li>\(n = p^2\), \(p\) prim: \(\varphi(n) = {{c4::p(p-1) = n - \sqrt{n}}}\).</li></ul>
Extra		Beispiele: \(\mathbb{Z}_9^* = \{1, 2, 4, 5, 7, 8\}\), \(\varphi(9) = 6\). \(\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}\), \(\varphi(7) = 6\).<br><br>Konsequenz für den \(p^2\)-Fall beim Euklid-Test: \(\frac{\|\mathbb{Z}_n^*\|}{n-1} \approx 1 - \frac{1}{\sqrt{n}}\), die Fehlerrate ist also fast \(1\).

Field	Before	After
Text		Eine <b>Zufallsquelle</b> liefert nach vorgegebener Verteilung zufällige unabhängige Zufallsbits oder -zahlen. Zwei Typen:<ul><li><b>Physikalische Zufallsgeneratoren</b>: {{c1::Lottozahlen, Geigerzähler, Rauschen, Quantenexperimente::Beispiele?}}.</li><li><b>Deterministische (Pseudo-)Zufallsgeneratoren</b>: liefern, basierend auf einem {{c2::Startwert (seed)}} \(s\), eine Folge \(s \to r_0(s), r_1(s), r_2(s), \ldots\) Das ermöglicht {{c3::Reproduzierbarkeit, wenn man sich den Startwert merkt}}.</li></ul>
Extra		In der Analyse geht man von idealen Zufallsgeneratoren aus. Bei der Anwendung muss man aber berücksichtigen, dass Pseudo-Zufallsgeneratoren das nur näherungsweise leisten.

Field	Before	After
Front		Bei der Fehlerreduktion eines Las-Vegas-Algorithmus mit Erfolgswahrscheinlichkeit \(\geq \varepsilon\) genügen \(N = \lceil \varepsilon^{-1} \ln \delta^{-1} \rceil\) Wiederholungen, um \(\Pr[\text{korrekt}] \geq 1 - \delta\) zu erreichen.<br><br>Wie skaliert \(N\) in \(\delta\)? Was bedeutet das praktisch?
Back		\(N\) skaliert <b>logarithmisch</b> in \(\delta^{-1}\).<br><br>Praktisch: Um die Fehlerwahrscheinlichkeit um einen <b>konstanten Faktor</b> (z.B. von \(10^{-2}\) auf \(10^{-3}\)) zu reduzieren, sind nur <b>konstant viele zusätzliche Iterationen</b> nötig.<br><br>Beispiel \(\varepsilon = 0{,}25\): \(\delta = 10^{-1} \Rightarrow N = 10\), \(\delta = 10^{-2} \Rightarrow N = 19\), \(\delta = 10^{-3} \Rightarrow N = 28\), \(\ldots\) (jeweils \(+9\)).