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
70
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
Epithelial tissue
Morgan Morgan
IMPERFECT TENSE - French
T W
GCSE Maths Symbols, Equations & Formulae
Andrea Leyden
IB Economics SL: Microeconomics
Han Zhang
An Inspector Calls: Mr Arthur Birling
Rattan Bhorjee
GoConqr Quick Guide to Getting Started
Andrea Leyden
Top learning tips for students
Micheal Heffernan
Teaching Methods Every Educator Should Know
Micheal Heffernan
Cloud Data Integration Specialist Certification
James McLean
2PR101 1.test - 6. část
Nikola Truong
Browse Library