Algorithmik 2015

2 Sek

5 Min

1/2 Min

1 Std

2Min

2 Sek

2 Hundertstel Sek

2 Tausendstel Sekunden

Die WS, im 25. Wurf einer Sequenz von 50 Würfen einer fairen Münze "Kopf" zu werfen ist geringer , wenn in den ersten 24 Würfen immer "Kopf" geworfen wurde.

Die Mächtigkeit des Schnitts zweier Mengen ist immer kleiner gleich den einzelnen Mächtigkeiten.

Die Ws, bei Abgabe eines Lottoscheins (nur ein Kästchen mit 6 Kreuzen ausgefüllt) nicht zu gewinnen, ist 1.1.

Die WS im Lotto zu gewinnen (6 Richtige) ist 6/49

O (n^2 log n)

O (n log n)

O (log n)

O (n)

B => C

Falls C nicht gilt, gilt A nicht.

B => D

A => C

Otto spinnt. Es gibt Graphen, in denen es Matchings gibt, sodass das optimale Vertex Cover Kardinalität zweimal Matchingkardinalität hat.

Otto spinnt. Vertex Cover ist NP-hard, deshlab kann es unter der Annahme, dass P nichtgleich NP keinen solchen Alg. geben.

Nicht schlecht, Otto. Zwar impliziert das nciht P = NP, aber eine bessere Approx.güte als 2 ist doch schon mal etwas.

Otto ist der Geilste, er hat P = NP gezeigt.

Es gilt |M| <= |V| /2

Für ein Matching M gilt für alle x,y Element M: X geschnitten y nicht gleich Leere Menge

Es gilt |M| = |V| / 2

Für ein Matching M gilt M echte Teilmenge von E

Die Größe des kleinsten Vertex Covers ist immer 2* Größe des größten Matchings.

Die Größe eines Matching in einem Graph ist immer eine untere Schranke für die Größe des kleinsten Vertex Cover dieses Graphen.

Für ein Vertex Cover gilt: C echte Teilmenge von V

Für ein Vertex Cover eines Graphen muss gelten: für alle e Element E: e geschnitten C ist ungleich der Leeren Menge

Es gibt ein t Element T, auf welches mind. |U| / |T| Elemente aus U gehasht werden.

Die Anzahl der möglichen Fkt. h beträgt |T|^|U|.

Es gibt keine Hashfkt., welche für jede Teilmenge S echte Teilmenge von U injektiv ist.

Es gibt eine perfekte Hashfkt., welche für jede Teilmenge S echte Teilmenge von U injektiv ist.

Mit Skiplisten können wir das Wörterbuchproblem in erwartet O (1) Zeit lösen.

Mit Skiplisten können wir das Wörterbuchproblem in worst-case O (log n) Zeit lösen

Mit Skiplisten können wir das Wörterbuchproblem in O (1) Zeit lösen

Mit Skiplisten können wir das Wörterbuchproblem in erwartet O (log n) Zeit lösen

Es gibt Eingaben, bei welchen die Suche in einer Skipliste immer Teta (n) Zeit benötigt.

Die Turmhöhe eines Elements einer Skipliste wird so gewählt, das die WS für die Höhe h genau 2^(-(h+1)) ist.

Eine Skipliste ist ein Baum, welcher immer Tiefe O (log n) ist.

Die Turmhöhe eines Elements einer Skipliste wird so gewählt, das die WS für die Höhe h gerade 1/2 ist.

Für S echte Teilmenge U und |S| <= |U| /2 ist jede Hashfkt. h Element H injektiv für S.

Für S echte Teilmenge U und |S| <= |U| /4 ist jede Hashfkt. h Element H injektiv für S

Für S echte Teilmenge U und |S| <= |U| /2 ist jede Hashfkt. h Element H surjektiv für S

Für x,y Element U, x nicht gleich y ist der Anteil an Hashfkt. h Element H mit h(x) = h(y) höchstens c/ |T|

Falls das Universum kleiner als die Hashtafelgröße ist, ist Hashing trivial.

(2,4)- Bäume können auch benutzt werden, um das Wörterbuchproblem zu lösen.

Wir können auf jedem geordneten Universum direkt die Technik des Hashing anwenden.

Skiplisten können auch benutzt werden, um das Wörterbuchproblem zu lösen.

Unabhänig von der Eingabe hat QS eine erwartete Lfz von O (n log n).

Es gibt Eingaben für welche QS immer Teta (n^2 log n) Schritte braucht.

Nur für zufällig permutierte Eingaben hat QS eine erwartete Lfz. von O (n log n).

Es gibt Eingaben für welche QS immer Teta (n^2) Schritte braucht.

Der in der VL behandelte MinCubt-Alg. ist ein Las Vegas Alg.

Die WS, dass der in der VL behandelte MinCut-Alg. das korrekte Erg. berechnet ist >= 1+ 1/n^2 .

Der Wert des MinCut eines nichtzusammenhängenden Graphen ist 0.

Die WS, dass der in der VL behandelte MinCut-Alg das falsche Erg. berechnet ist >= 1+ 1/n^2 .

Für eine ZV X ist die WS, mehr als Faktor 4 über dem Erwartungswert zu liegen <= 1/4

Für eine diskrete ZV X gilt: E(X) = Summe aus Pr(X = i) * i

Für eine pos. ZV X ist die WS, mehr als Faktor 5 über dem Erwartungswert zu liegen <= 1/5 .

Für ZV X,Y gilt: E(X+Y) = E(X) + E(Y)

Geg. Graphen G1(V1,E1), G2(V2,E2), gilt |V1| = |V2| und |E1| = |E2|

Geg. Graphen G1(V1,E1), G2(V2,E2), gilt |V1| = |V2|

Geg. Graphen G1(V1,E1), G2(V2,E2), gilt |E1| = |E2|

Geg. Graphen G1(V1,E1), G2(V2,E2) mit |V1| = |V2| existiert ein Phi: V1 -> V2 sodass (v,w) Element E1 <=> (Phi(v), Phi(w)) Element E2

A generiert 2 isomorphe Graphen und stellt diese öffentlich z.B. auf ihre Webseite für alle sichtbar zur Verfügung.

A generiert 2 große zufällige Primzahlen q und r und stellt die Zahl q mod r auf ihre Webseite.

A generiert 2 isomorphe Graphen, hält einen für sich geheim und stellt den anderen öffentlich z.B. auf ihre Webseite.

A generiert einen isomorphen Graph und gibt nur dessen Knoten- und Kantenanzahl auf ihrer Webseite bekannt.

In jeder Runde wählt der Alg. eine Kante zufällig aus und kontahiert diese.

Der Alg. wählt in jeder Runde eine beliebige Kante aus, nimmt beide Endknoten dieser Kante un den Cut.

Der Alg. berechnet genau dann den MinCut,wenn in jeder Runde eine Kante des MinCuts kontrahiert wird.

Der Alg. berechnet den kürzesten Pfad zwischen s und t und kontrahiert die Kanten auf diesem Pfad.

<= 1

<= 2/i

<= 2/(i^2)

<= 2/(n^2)

Ein LV-Alg. kann ohne weiteres in einen MC-Alg. gewandelt werden.

Ein MC-Alg. kann ohne weiteres in einen LV-Alg. gewandelt werden.

LV-Alg liefern manchmal ein inkorrektes Ergebnis.

MC-Alg. liefern immer das korrekte Ergebnis.

O (n)

O (log n)

O (1), aber nur erwartet!

O (1)

Falls Alice das Geheimnis nicht kennt, findet Bob dies heraus.

Mit jeder Runde des ZKP-Verfahrens lernt Bob mehr über das Geheimnis von Alice.

Die Sicherheit des ZKP-Verfahrens basiert auf der Annahme, dass die Fakorisierung großer Zahlen schwierig ist.

Falls Alice das Geheimnis nicht kennt, ist in jeder Runde des ZKP-Verfahrens die WS, dass Bob dies erkennt >= 1/2

Bei jeder Einführung muss der neu hinzugenommene Punkt mit O (1) bereits eingeführten Punkten verglichen werden.

Ohne Randomisierung des CP-Alg. gibt es eine Eingabe und eine Einfügereihenfolge, welche Teta (n^2) Schritte benötigt.

Es gibt für Einfügereihenfolgen, bei denen das Gitter nie neu aufgebaut werden muss.

Für den randomisierten CP-Alg. aus der VL gibt es Eingaben, sodass der Alg. immer Teta (n^2) Schitte macht.

O (n)

O (1)

O (1/i)

O (log n)

Die Anzahl der Kanten mit Gewicht 2 im MST von G ist c^(1) +1

Die Anzahl der Kanten mit Gewicht 2 im MST von G ist c^(1) -1

Die Anzahl der Kanten mit Gewicht 2 im MST von G ist c^(1)

Die Anzahl der Kanten mit Gewicht 2 im MST von G ist c^(1) +2

Der MST von G enthält n-12 Kanten mit Gewicht 1.

Falls G genau 12 Kanten mit Gewicht 2 hat, ist das Gewicht des MST von G genau n-1+12 .

Der MST von G hat Gewicht 12(n-1) .

Die Anzahl der Kanten mit Gewicht 2 im MST von G ist 12.

Ein Graph mit Max.grad D hat höchstens n/D ZHK.

Ein Graph mit Max.grad D hat mindestens n/D ZHK.

Wir können in einem Graph mit Max.grad D in erwarteter Zeit O ((D/pe^2) log n) mit WS >= 1-p die Anzahl der ZHK bis auf einen additiven Fehler von e*n schätzen.

Es gibt einen deterministischen Alg., welcher in Zeit o (|V| + |E|) die Anzahl der ZHK eines Graphen G berechnen kann.