Copy and Edit

Algorithmik 2015

Description

MC-Test
Sara S
Quiz by Sara S, updated more than 1 year ago
Sara S
Created by Sara S over 9 years ago
72
0
0

Resource summary

Question 1

Question
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?
Answer
  • 2 Sek
  • 5 Min
  • 1/2 Min
  • 1 Std

Question 2

Question
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?
Answer
  • 2Min
  • 2 Sek
  • 2 Hundertstel Sek
  • 2 Tausendstel Sekunden

Question 3

Question
Welche dieser Aussagen ist korrekt?
Answer
  • 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

Question 4

Question
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.?
Answer
  • O (n^2 log n)
  • O (n log n)
  • O (log n)
  • O (n)

Question 5

Question
Es gelte: A => B ("aus Aussage A folgt Aussage B") B => C und aus A => D. Welche dieser Aussagen ist im Allgemeinen falsch?
Answer
  • B => C
  • Falls C nicht gilt, gilt A nicht.
  • B => D
  • A => C

Question 6

Question
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?
Answer
  • 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.

Question 7

Question
Folgende Frage bezieht sich auf das Thema Matching. Welche Aussage ist falsch?
Answer
  • 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

Question 8

Question
Welche dieser Aussagen ist falsch?
Answer
  • 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

Question 9

Question
Sei h: U -> T eine Hashfkt. mit |U| >> |T|. Welche dieser Aussagen ist falsch?
Answer
  • 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.

Question 10

Question
Rufen Sie sich die in der Vorlesung behandelte Datenstruktur Skiplisten in Erinnerung. Welche dieser Aussagen ist korrekt?
Answer
  • 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

Question 11

Question
Rufen Sie sich die in der Vorlesung behandelte Datenstruktur Skiplisten in Erinnerung. Welche dieser Aussagen ist korrekt?
Answer
  • 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.

Question 12

Question
Sei H eine c-universelle Familie von Hashfkt. U -> T. Welche dieser Aussagen ist korrekt?
Answer
  • 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|

Question 13

Question
Welche dieser Aussagen ist falsch?
Answer
  • 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.

Question 14

Question
Welche der Aussagen ist korrekt im Kontext des in der Vorlesung behandelten randomisierten QuickSort Alg.?
Answer
  • 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.

Question 15

Question
Folgende Frage bezieht sich auf das in der Vorlesung behandelte Thema "MinCut". Welche der Aussagen ist korrekt?
Answer
  • 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 .

Question 16

Question
Welche dieser Aussagen ist falsch?
Answer
  • 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)

Question 17

Question
Was ist das Graphisomorphieporblem?
Answer
  • 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

Question 18

Question
Was sind die ersten Schritte von Alice, wenn sie sich anderen gegenüber mittles eines Zero-Knowledge-Proof ausweisen möchte:
Answer
  • 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.

Question 19

Question
Folgende Frage bezieht sich auf den in der VL behandelten MinCut-Alg. Welche der Aussagen ist korrekt?
Answer
  • 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.

Question 20

Question
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?
Answer
  • <= 1
  • <= 2/i
  • <= 2/(i^2)
  • <= 2/(n^2)

Question 21

Question
Welche dieser Aussagen ist korrekt?
Answer
  • 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.

Question 22

Question
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?
Answer
  • O (n)
  • O (log n)
  • O (1), aber nur erwartet!
  • O (1)

Question 23

Question
Welche der folgenden Aussagen ist im Kontext des Zero-Knowledge-Proof-Verfahrens, welches in der VL vorgestellt wurde, korrekt?
Answer
  • 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

Question 24

Question
Folgende Fragen beziehen sich auf den randomisierten Closest-Pair-Alg. aus der VL. Welche dieser Aussagen ist falsch?
Answer
  • 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.

Question 25

Question
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)?
Answer
  • O (n)
  • O (1)
  • O (1/i)
  • O (log n)

Question 26

Question
Was ist die Anzahl der ZHK des obigen Graphen?
Image:
42154f20-5420-4cb6-96e8-44da6176580f.JPG (image/JPG)
Answer
  • 0
  • 1
  • 3
  • 2

Question 27

Question
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?
Answer
  • 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

Question 28

Question
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?
Answer
  • 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.

Question 29

Question
Welche dieser Aussagen ist korrekt?
Answer
  • 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.

Question 30

Question
Welchen Wert hat die Summe der Kantengewichte des MST des obigen Graph?
Image:
d69294ed-daf1-4af6-8b8d-8fca14adfa38.JPG (image/JPG)
Answer
  • 57
  • 55
  • 51
  • 44
Show full summary Hide full summary

Want to create your own Quizzes for free with GoConqr? Learn more.

Similar

Multiple Choice Fragen
Tobias Ranke
Acids and Bases
silviaod119
To Kill A Mockingbird Complete Notes
jessica.moscrip
01 Long Term causes of the French Revolution
Holly Lovering
Maths Revision- end of year test
hannahsquires
Apresentações em Inglês
miminoma
New Possibilities with ExamTime's Flashcard Maker
Andrea Leyden
5 Steps to Learning Success
Andrea Leyden
Checking out me History by John Agard
Eleanor Simmonds
Types of Learning Environment
Brandon Tuyuc
1PR101 2.test - Část 18.
Nikola Truong
Browse Library