2842956
Frage 1
Frage
Wir haben eine 3 GHz Rechner, der pro Takt eine Instruktion ausführen kann. Wir lassen einen Sortieralg., der n^2 Operationen benötigt auf einer Eingabe von 1 Million Elementen laufen. Wie lange dauert es in etwa, bis der Alg. fertig ist?
Antworten
-
2 Sek
-
5 Min
-
1/2 Min
-
1 Std
Frage 2
Frage
Wir haben eine 3 GHz Rechner, der pro Takt eine Instruktion ausführen kann. Wir lassen einen Alg., der n log n Operationen benötigt, auf einer Eingabe von 10 Million Elementen laufen. Wie lange dauert es in etwa, bis der Alg. fertig ist?
Antworten
-
2Min
-
2 Sek
-
2 Hundertstel Sek
-
2 Tausendstel Sekunden
Frage 3
Frage
Welche dieser Aussagen ist korrekt?
Antworten
-
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
Frage 4
Frage
Ein Alg. braucht zur Bearbeitung einer Probleminstanz der Größe n zunächst n Zeitschritte und ruft sich dann (falls n > 1) selber rekursiv mit 2 Probleminstanzen der Größe n/2 auf. Was ist die beste obere Schranke für die Laufzeit dieses Alg.?
Antworten
-
O (n^2 log n)
-
O (n log n)
-
O (log n)
-
O (n)
Frage 5
Frage
Es gelte: A => B ("aus Aussage A folgt Aussage B") B => C und aus A => D. Welche dieser Aussagen ist im Allgemeinen falsch?
Antworten
-
B => C
-
Falls C nicht gilt, gilt A nicht.
-
B => D
-
A => C
Frage 6
Frage
Otto hat einen neuen Polynomzeitalg. gefunden, welcher für einen Eingabegraph G (V,E) ein Vertex Cover C bestimmt mit |C| <= 1.3|M|, wobei M echte Teilmenge von E ein Matching aus G ist, welches Ottos Alg. mitberechnet. Was sagen Sie korrekterweise dazu?
Antworten
-
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.
Frage 7
Frage
Folgende Frage bezieht sich auf das Thema Matching. Welche Aussage ist falsch?
Antworten
-
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
Frage 8
Frage
Welche dieser Aussagen ist falsch?
Antworten
-
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
Frage 9
Frage
Sei h: U -> T eine Hashfkt. mit |U| >> |T|. Welche dieser Aussagen ist falsch?
Antworten
-
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.
Frage 10
Frage
Rufen Sie sich die in der Vorlesung behandelte Datenstruktur Skiplisten in Erinnerung. Welche dieser Aussagen ist korrekt?
Antworten
-
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
Frage 11
Frage
Rufen Sie sich die in der Vorlesung behandelte Datenstruktur Skiplisten in Erinnerung. Welche dieser Aussagen ist korrekt?
Antworten
-
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.
Frage 12
Frage
Sei H eine c-universelle Familie von Hashfkt. U -> T. Welche dieser Aussagen ist korrekt?
Antworten
-
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|
Frage 13
Frage
Welche dieser Aussagen ist falsch?
Antworten
-
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.
Frage 14
Frage
Welche der Aussagen ist korrekt im Kontext des in der Vorlesung behandelten randomisierten QuickSort Alg.?
Antworten
-
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.
Frage 15
Frage
Folgende Frage bezieht sich auf das in der Vorlesung behandelte Thema "MinCut". Welche der Aussagen ist korrekt?
Antworten
-
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 .
Frage 16
Frage
Welche dieser Aussagen ist falsch?
Antworten
-
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)
Frage 17
Frage
Was ist das Graphisomorphieporblem?
Antworten
-
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
Frage 18
Frage
Was sind die ersten Schritte von Alice, wenn sie sich anderen gegenüber mittles eines Zero-Knowledge-Proof ausweisen möchte:
Antworten
-
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.
Frage 19
Frage
Folgende Frage bezieht sich auf den in der VL behandelten MinCut-Alg. Welche der Aussagen ist korrekt?
Antworten
-
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.
Frage 20
Frage
Folgende Fragen beziehen sich auf den randomisierten Closest-Pair-Alg. aus der VL. Was ist die genaueste Abschätzung für die WS, dass wir nach Einführung des i-ten Punkts das Gitter neu aufbauen müssen?
Antworten
-
<= 1
-
<= 2/i
-
<= 2/(i^2)
-
<= 2/(n^2)
Frage 21
Frage
Welche dieser Aussagen ist korrekt?
Antworten
-
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.
Frage 22
Frage
Folgende Fragen beziehen sich auf den randomisierten Closest-Pair-Alg. aus der VL. Was ist die beste Schranke für die worst-case Kosten um für den i-ten Punkt festzustellen, ob dieser ein neues Clostest Pair definiert?
Antworten
-
O (n)
-
O (log n)
-
O (1), aber nur erwartet!
-
O (1)
Frage 23
Frage
Welche der folgenden Aussagen ist im Kontext des Zero-Knowledge-Proof-Verfahrens, welches in der VL vorgestellt wurde, korrekt?
Antworten
-
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
Frage 24
Frage
Folgende Fragen beziehen sich auf den randomisierten Closest-Pair-Alg. aus der VL. Welche dieser Aussagen ist falsch?
Antworten
-
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.
Frage 25
Frage
Folgende Fragen beziehen sich auf den randomisierten Closest-Pair-Alg. aus der VL. Was ist die schärfste Schranke für die erwarteten Kosten für die Einfügung des i-ten Punkts (inkl. Neuaufbau des Gitters)?
Antworten
-
O (n)
-
O (1)
-
O (1/i)
-
O (log n)
Frage 26
Frage
Was ist die Anzahl der ZHK des obigen Graphen?
Antworten
-
0
-
1
-
3
-
2
Frage 27
Frage
Betrachten wir einen zusammenhängenden, ungerichteten, gewichteten Graph G (V,E) mit c: E -> {1,2}, |V| = n. Sei c^(1) die Anzahl an ZHK des Graphen induziert durch Kanten mit Gewicht 1. Welche der folgenden Aussagen ist korrekt?
Antworten
-
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
Frage 28
Frage
Betrachten wir einen zusammenhängenden, ungerichteten, gewichteten Graph G (V,E) mit c: E -> {1,2}, |V| = n. Sei c^(1) die Anzahl an ZHK des Graphen induziert durch Kanten mit Gewicht 1. Welche der folgenden Aussagen ist korrekt?
Antworten
-
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.
Frage 29
Frage
Welche dieser Aussagen ist korrekt?
Antworten
-
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.
Frage 30
Frage
Welchen Wert hat die Summe der Kantengewichte des MST des obigen Graph?
Antworten
-
57
-
55
-
51
-
44
Möchten Sie mit GoConqr kostenlos Ihre eigenen Quiz erstellen? eigenen Mehr erfahren.