Tobias Ranke
Test por , creado hace más de 1 año

Mögliche Algofragen

27
0
0
Tobias Ranke
Creado por Tobias Ranke hace alrededor de 9 años
Cerrar

Algorithmik Fragen MCT

Pregunta 1 de 22

1

Der CYK läuft in:

Selecciona una de las siguientes respuestas posibles:

  • n²

  • n³

  • n log(n)

Explicación

Pregunta 2 de 22

1

Welcher dieser Algorithmen ist nicht neidfrei?

Selecciona una de las siguientes respuestas posibles:

  • Succesive-Pairs-Algorithmus

  • Moving Knife

  • Trimming

Explicación

Pregunta 3 de 22

1

Folgende Frage bezieht sich auf das Thema Contraction Hierarchies, wie sie in
der Vorlesung behandelt wurden. Welche dieser Aussagen ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 4 de 22

1

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)?

Selecciona una de las siguientes respuestas posibles:

  • 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))

Explicación

Pregunta 5 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 6 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 7 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 8 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 9 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 200 g

  • 13EUR

  • 10EUR

  • 15EUR

Explicación

Pregunta 10 de 22

1

Folgende Frage bezieht sich auf das Thema (metrisches) TSP, wie es in der
Vorlesung behandelt wurde.
Welche dieser Aussagen ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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).

Explicación

Pregunta 11 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • Gi;j = max (Gi

  • Gi;j = max (Gi

  • Gi;j = min (Gi

  • Gi;j = min (Gi

Explicación

Pregunta 12 de 22

1

Folgende Frage bezieht sich auf das Thema Steinerbaum.
Welche dieser Aussagen ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 13 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 14 de 22

1

Welche dieser Aussagen ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 15 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • Wi;j = max (W-i

  • Wi;j = max (Wi

  • Wi;j = min (Wi-

  • Wi;j = min (Wi

Explicación

Pregunta 16 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 17 de 22

1

Folgende Frage bezieht sich auf das Thema Constrained Shortest Path (CSP),
wie es in der Vorlesung behandelt wurde.
Welche dieser Aussagen ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 18 de 22

1

Welche dieser Aussagen ist korrekt?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 19 de 22

1

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

Selecciona una de las siguientes respuestas posibles:

  • B => D

  • Falls C nicht gilt, gilt A nicht.

  • B=> C

  • A=> C

Explicación

Pregunta 20 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • 10 Tausendstel Sekunden

  • 10 Milliardstel Sekunden

  • 10 Hundertstel Sekunden

  • 10 Millionstel Sekunden

Explicación

Pregunta 21 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • etwa 8 Stunden

  • etwas mehr als eine halbe Stunde

  • ca. 90 Stunden

  • ca. 40 Tage

Explicación

Pregunta 22 de 22

1

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?

Selecciona una de las siguientes respuestas posibles:

  • O (n²)

  • O(n*log(n))

  • O(n)

  • O(log (n))

Explicación

Anterior
Siguiente