Copy and Edit

Algorithmik Fragen MCT

Description

Mögliche Algofragen
Tobias Ranke
Quiz by Tobias Ranke, updated more than 1 year ago
Tobias Ranke
Created by Tobias Ranke almost 9 years ago
27
0
0

Resource summary

Question 1

Question
Der CYK läuft in:
Answer
  • n²
  • n³
  • n log(n)

Question 2

Question
Welcher dieser Algorithmen ist nicht neidfrei?
Answer
  • Succesive-Pairs-Algorithmus
  • Moving Knife
  • Trimming

Question 3

Question
Folgende Frage bezieht sich auf das Thema Contraction Hierarchies, wie sie in der Vorlesung behandelt wurden. Welche dieser Aussagen ist falsch?
Answer
  • Die Pfade, welche mittels der Contraction Hierarchies berechnet werden, sind immer auch kurzeste Pfade.
  • Die Pfade, welche mittels der Contraction Hierarchies berechnet werden, sind nicht unbedingt die kurzesten, allerdings maximal doppelt so lang wie die kurzesten.
  • Mittels Contraction Hierarchies kann der Suchraum bei einer kurzesten Wege Anfrage stark reduziert werden.
  • Contraction Hierarchies augmentieren den Graph um Shortcuts und ordnen jedem Knoten einen Level zu.

Question 4

Question
Betrachten Sie eine Implementierung von Dijkstras Algorithmus, in welchem die Prioritatswarteschlange mittels eines 'normalen' Binarheaps (alle Heapoperationen in O(log (n))) umgesetzt ist.Welche Aussage ist korrekt (beste Schranke)?
Answer
  • Diese Implementierung hat Laufzeit O(n + m)
  • Diese Implementierung hat Laufzeit O(n  log (n) + m)
  • Diese Implementierung hat Laufzeit O((n + m)  log (n))
  • Diese Implementierung hat Laufzeit O(n  log (n))

Question 5

Question
Betrachten Sie die Kontraktion eines Knotens v in der Vorverarbeitungsphase der Contraction Hierarchies, wie sie in der Vorlesung behandelt wurden. Welche dieser Aussagen ist falsch?
Answer
  • Ein Shortcut (u;w) muss in jedem Fall eingefugt werden, wenn (u; v) elementVon E und (v;w) elementVon E.
  • Ein Shortcut (u;w) muss nicht eingefugt werden, falls es einen kurzesten Weg von u nach w gibt, welcher nicht uber v verlauft.
  • Korrektheit geht nicht verloren, falls jeder Shortcut (u;w) eingefugt wird, falls (u; v) elementVon E und (v;w) elementVon E.
  • Ein Shortcut (u;w) muss eingefugt werden, falls (u; v) elementVon E und (v;w) elementVon E und uvw ist der einzige kurzeste Pfad von u nach w.

Question 6

Question
Wir betrachten das Rucksackproblem mit n Gegenstanden, ganzzahligen Gewichten gi und Werten wi, i = 1; : : : ; n, sowie einer Rucksackkapazitat G. Welche dieser Aussagen ist falsch?
Answer
  • Das Rucksackproblem kann in Zeit O(n Wopt) gelost werden, hierbei ist Wopt der Wert des optimalen Rucksacks.
  • Das Rucksackproblem kann in Zeit O(n  G) gelost werden.
  • Sind die Gewichte oder die Werte unar kodiert, ist das Rucksackproblem in Polynomialzeit losbar.
  • Da das Rucksackproblem in O(min (n  G; n Wopt)) gelost werden kann, ist das Rucksackproblem in P, hierbei ist Wopt der Wert des optimalen Rucksacks.

Question 7

Question
Folgende Frage bezieht sich auf das Thema Constrained Shortest Path (CSP), wie es in der Vorlesung behandelt wurde und insbesondere eine Formulierung als Dynamisches Programm, wobei die Zelle Ri;j den minimalen Ressourcenverbrauch eines Pfades von Knoten 1 zu Knoten i enthalt, welcher Kosten  j hat. ce bezeichnen die Kosten einer Kante e, re deren Ressourcenverbrauch. Welche dieser Aussagen ist korrekt?
Answer
  • Ri;j = min e=(v;i) Rv;j
  • Ri;j = min e=(v;i) Rv;j
  • Ri;j = max e=(v;i) Rv;j
  • Ri;j = max e=(v;i) Rv;j

Question 8

Question
Folgende Frage bezieht sich auf die Dyn.Prog. Formulierung fur das Rucksackproblem, wie sie in der VL behandelt wurde. Welche der folgenden Aussagen ist falsch?
Answer
  • Aus einem vervollstandigten Dynamischen Programm konnen alle optimalen Rucksackpackungen ermittelt werden.
  • Fur die Anwendung der Technik des Dynamischen Programmierens mussen die Gewichte oder die Werte ganzzahlig sein.
  • Mittels Dynamischen Programmierens konnen wir auch folgendes Problem losen: Gibt es eine Rucksackpackung mit Wert mindestens W und Gewicht hochstens G?
  • Fur eine gegebene Instanz des Rucksackproblems gibt es genau einen optimalen Rucksack.

Question 9

Question
Sie sind beim Juwelier eingebrochen und haben einen Rucksack mit Tragekapazit at 333 g dabei. Was sollten Sie mitnehmen, wenn Sie den maximalen Wert erzielen, jedoch nicht Ihre Rucksackkapazitat uberschreiten wollen? Es liegen 7 Gegenstande herum mit Gewichten 169g, 188g, 200g, 300g, 423g, 500g, 165g und Werten 9 EUR, 10 EUR, 4 EUR, 2 EUR, 3 EUR, 1 EUR, 5 EUR. Was ist der Wert des wertvollsten Rucksacks, den Sie packen konnen?
Answer
  • 200 g
  • 13EUR
  • 10EUR
  • 15EUR

Question 10

Question
Folgende Frage bezieht sich auf das Thema (metrisches) TSP, wie es in der Vorlesung behandelt wurde. Welche dieser Aussagen ist falsch?
Answer
  • Die Kosten einer optimalen Losung fur eine TSP-Instanz G(V;E; c), mit zu besuchenden Knoten C  V kann beliebig weit unter den Kosten des Minimum Spanning Trees fur G(V;E; c) liegen.
  • Die Kosten einer optimalen Losung fur eine TSP-Instanz G(V;E; c), mit zu besuchenden Knoten C  V sind immer zweimal die Kosten des Minimum Spanning Trees fur G(V;E; c).
  • Die optimale Losung fur eine TSP-Instanz besucht moglicherweise einige Knoten in V mehrfach.
  • Die Kosten einer optimalen Losung fur eine TSP-Instanz G(V;E; c) sind nie groer als zweimal die Kosten des Minimum Spanning Trees fur G(V;E; c).

Question 11

Question
Folgende Frage bezieht sich auf das Rucksackproblem, wie es in der Vorlesung behandelt wurde und insbesondere eine Formulierung als Dynamisches Programm, wobei die Zelle Gi;j das minimale Gewicht eines Rucksacks enthalt, welcher Elemente aus f1; : : : ; ig enthalten kann, und Wert genau j hat. wi bezeichnet den Wert von Gegenstand i, gi sein Gewicht. Welche dieser Aussagen ist korrekt?
Answer
  • Gi;j = max (Gi
  • Gi;j = max (Gi
  • Gi;j = min (Gi
  • Gi;j = min (Gi

Question 12

Question
Folgende Frage bezieht sich auf das Thema Steinerbaum. Welche dieser Aussagen ist falsch?
Answer
  • Die Kosten einer optimalen Losung fur eine Steinerbauminstanz G(V;E; c) mit Terminalmenge T  V sind immer zweimal die Kosten des Minimum Spanning Trees fur G(V;E; c).
  • Die Kosten einer optimalen Losung fur eine Steinerbauminstanz G(V;E; c) mit Terminalmenge T  V sind sind nie groer als die Kosten des Minimum Spanning Trees fur G(V;E; c).
  • Die optimale Losung einer Steinerbauminstanz ist immer ein Baum.
  • Die Kosten einer optimalen Losung fur eine Steinerbauminstanz G(V;E; c) mit Terminalmenge T  V kann beliebig weit

Question 13

Question
Folgende Frage bezieht sich auf das Thema Constrained Shortest Path (CSP), wie es in der Vorlesung behandelt wurde und insbesondere eine Formulierung als Dynamisches Programm, wobei die Zelle Ci;j die minimalen Kosten eines Pfades von Knoten 1 zu Knoten i enthalt, welcher Ressourcenverbrauch  j hat. ce bezeichnen die Kosten einer Kante e, re deren Ressourcenverbrauch. Welche dieser Aussagen ist korrekt?
Answer
  • Ci;j = min e=(v;i) Cv;j
  • Ci;j = min e=(v;i) Cv;j
  • Ci;j = max e=(v;i) Cv;j
  • Ci;j = max e=(v;i) Cv;j

Question 14

Question
Welche dieser Aussagen ist falsch?
Answer
  • Es gibt nicht mehr als 2n viele verschiedene Rucksackinhalte.
  • Fur beliebiges  > 0 kann in Zeit polynomiell in n und 1  ein Rucksackinhalt bestimmt werden, dessen Wert  (1
  • Falls jemand einen Polynomzeitalgorithmus zur exakten Losung des Rucksackproblems ndet, gilt P = NP.
  • Fur beliebiges  > 0 kann in Zeit polynomiell in n und 1  ein Rucksackinhalt bestimmt werden, dessen Wert  (1 + ) mal dem Optimalwert ist.

Question 15

Question
Folgende Frage bezieht sich auf das Rucksackproblem, wie es in der Vorlesung behandelt wurde und insbesondere eine Formulierung als Dynamisches Programm, wobei die Zelle Wi;j den maximalen Wert eines Rucksacks enthalt, welcher Elemente aus f1; : : : ; ig enthalten kann, und Gewicht genau j hat. wi bezeichnet den Wert von Gegenstand i, gi sein Gewicht. Welche dieser Aussagen ist korrekt?
Answer
  • Wi;j = max (W-i
  • Wi;j = max (Wi
  • Wi;j = min (Wi-
  • Wi;j = min (Wi

Question 16

Question
Folgende Frage bezieht sich auf das Thema Constrained Shortest Path (CSP), wie es in der Vorlesung behandelt wurde und insbesondere auf das Approximationsschema. Welche dieser Aussagen ist korrekt?
Answer
  • Fur das Approximationsschema ist die Dyn.Prog. Formulierung, welche links den Ressourcenverbrauch stehen hat, besser geeignet.
  • Fur das Approximationsschema ist die Dyn.Prog. Formulierung, welche links die Kosten stehen hat, besser geeignet.
  • Das von uns behandelte Approximationsschema benotigt keine Dyn.Prog. Formulierung.
  • Fur das Approximationsschema sind beide Dyn.Prog. Formulierung gleichermaßen geeignet.

Question 17

Question
Folgende Frage bezieht sich auf das Thema Constrained Shortest Path (CSP), wie es in der Vorlesung behandelt wurde. Welche dieser Aussagen ist falsch?
Answer
  • Falls jemand einen Polynomzeitalgorithmus zur exakten Losung des CSP Problems ndet, gilt P = NP.
  • Das CSP Problem ist in NP.
  • Fur beliebiges  > 0 kann in Zeit polynomiell in n und 1  ein s-t Pfad bestimmt werden, dessen Kosten maximal  (1
  • Fur beliebiges  > 0 kann in Zeit polynomiell in n und 1  ein s-t Pfad bestimmt werden, dessen Kosten maximal  (1 + ) mal dem Optimalwert sind und der den Ressourcenconstraint erfullt.

Question 18

Question
Welche dieser Aussagen ist korrekt?
Answer
  • DieWahrscheinlichkeit, bei der Abgabe eines Lottoscheins (nur ein Kastchen mit 6 Kreuzen ausgefullt) nicht zu gewinnen, ist 1:1.
  • Die Wahrscheinlichkeit, im 25. Wurf einer Sequenz von 50 Wurfen einer fairen Munze 'Kopf' zu werfen, ist geringer, wenn in den ersten 24Wurfen immer 'Kopf' geworfen wurde.
  • Die Wahrscheinlichkeit, im Lotto zu gewinnen (6 Richtige) ist 6 49
  • Die Machtigkeit des Schnitts zweier Mengen ist immer kleiner gleich den einzelnen Machtigkeiten.

Question 19

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

Question 20

Question
Wir haben einen 1 GHz Rechner, der pro Takt eine Instruktion ausfuhren kann. Unsere Anfragedatenstruktur mit n = 10 Milliarde Elementen, fuhrt pro Anfrage log10 (n) Operationen aus. Wie lange dauert es in etwa, bis eine Anfrage beantwortet ist?
Answer
  • 10 Tausendstel Sekunden
  • 10 Milliardstel Sekunden
  • 10 Hundertstel Sekunden
  • 10 Millionstel Sekunden

Question 21

Question
Wir haben einen 3 MHz Rechner, der pro Takt eine Instruktion ausfuhren kann. Wir lassen einen Sortieralgorithmus, der n2 Operationen benotigt, auf einer Eingabe von 1 Million Elementen laufen. Wie lange dauert es in etwa, bis der Algorithmus fertig ist?
Answer
  • etwa 8 Stunden
  • etwas mehr als eine halbe Stunde
  • ca. 90 Stunden
  • ca. 40 Tage

Question 22

Question
Ein Algorithmus braucht zur Bearbeitung einer Probleminstanz der Groe n zunachst n Zeitschritte und ruft sich dann (falls n > 1) selber rekursiv mit einer Probleminstanz der Groe n 2 auf. Was ist die beste obere Schranke fur die Laufzeit dieses Algorithmus?
Answer
  • O (n²)
  • O(n*log(n))
  • O(n)
  • O(log (n))
Show full summary Hide full summary

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

Similar

KPOL-Fragen
Lisa-Maria Hauschild
KPOL-Fragen (sofort überprüfbar)
Tim Schröder
IKA-Theoriefragen Serie 01 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 02 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 03 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 16 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 04 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 20 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 18 (15 Fragen)
IKA ON ICT GmbH
IKA-Theoriefragen Serie 19 (15 Fragen)
IKA ON ICT GmbH
AOW - Psych
Aydan Altuner
Browse Library