¡GoConqr estrena diseño! Cuéntanos qué te parece.

Regístrate gratis

Test

Algorithmik Fragen MCT

Tobias Ranke 22 preguntas

Hacer el test

Preguntas del test (22)

  1. 1Der CYK läuft in:
    1. An²
    2. Bn³
    3. Cn log(n)
  2. 2Welcher dieser Algorithmen ist nicht neidfrei?
    1. ASuccesive-Pairs-Algorithmus
    2. BMoving Knife
    3. CTrimming
  3. 3Folgende Frage bezieht sich auf das Thema Contraction Hierarchies, wie sie in
    der Vorlesung behandelt wurden. Welche dieser Aussagen ist falsch?
    1. ADie Pfade, welche mittels der Contraction Hierarchies berechnet werden,
      sind immer auch kurzeste Pfade.
    2. BDie Pfade, welche mittels der Contraction Hierarchies berechnet werden,
      sind nicht unbedingt die kurzesten, allerdings maximal doppelt so lang
      wie die kurzesten.
    3. CMittels Contraction Hierarchies kann der Suchraum bei einer kurzesten
      Wege Anfrage stark reduziert werden.
    4. DContraction Hierarchies augmentieren den Graph um Shortcuts und ordnen
      jedem Knoten einen Level zu.
  4. 4Betrachten 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)?
    1. ADiese Implementierung hat Laufzeit O(n + m)
    2. BDiese Implementierung hat Laufzeit O(n  log (n) + m)
    3. CDiese Implementierung hat Laufzeit O((n + m)  log (n))
    4. DDiese Implementierung hat Laufzeit O(n  log (n))
  5. 5Betrachten Sie die Kontraktion eines Knotens v in der Vorverarbeitungsphase
    der Contraction Hierarchies, wie sie in der Vorlesung behandelt wurden. Welche
    dieser Aussagen ist falsch?
    1. AEin Shortcut (u;w) muss in jedem Fall eingefugt werden, wenn (u; v) elementVon E
      und (v;w) elementVon E.
    2. BEin Shortcut (u;w) muss nicht eingefugt werden, falls es einen kurzesten
      Weg von u nach w gibt, welcher nicht uber v verlauft.
    3. CKorrektheit geht nicht verloren, falls jeder Shortcut (u;w) eingefugt wird,
      falls (u; v) elementVon E und (v;w) elementVon E.
    4. DEin 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.
  6. 6Wir betrachten das Rucksackproblem mit n Gegenstanden, ganzzahligen Gewichten
    gi und Werten wi, i = 1; : : : ; n, sowie einer Rucksackkapazitat G.
    Welche dieser Aussagen ist falsch?
    1. ADas Rucksackproblem kann in Zeit O(n Wopt) gelost werden, hierbei ist
      Wopt der Wert des optimalen Rucksacks.
    2. BDas Rucksackproblem kann in Zeit O(n  G) gelost werden.
    3. CSind die Gewichte oder die Werte unar kodiert, ist das Rucksackproblem
      in Polynomialzeit losbar.
    4. DDa 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.
  7. 7Folgende 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?
    1. ARi;j = min
      e=(v;i)
      Rv;j
    2. BRi;j = min
      e=(v;i)
      Rv;j
    3. CRi;j = max
      e=(v;i)
      Rv;j
    4. DRi;j = max
      e=(v;i)
      Rv;j
  8. 8Folgende Frage bezieht sich auf die Dyn.Prog. Formulierung fur das Rucksackproblem,
    wie sie in der VL behandelt wurde.
    Welche der folgenden Aussagen ist falsch?
    1. AAus einem vervollstandigten Dynamischen Programm konnen alle optimalen
      Rucksackpackungen ermittelt werden.
    2. BFur die Anwendung der Technik des Dynamischen Programmierens mussen
      die Gewichte oder die Werte ganzzahlig sein.
    3. CMittels Dynamischen Programmierens konnen wir auch folgendes Problem
      losen: Gibt es eine Rucksackpackung mit Wert mindestens W und
      Gewicht hochstens G?
    4. DFur eine gegebene Instanz des Rucksackproblems gibt es genau einen
      optimalen Rucksack.
  9. 9Sie 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?
    1. A200 g
    2. B13EUR
    3. C10EUR
    4. D15EUR
  10. 10Folgende Frage bezieht sich auf das Thema (metrisches) TSP, wie es in der
    Vorlesung behandelt wurde.
    Welche dieser Aussagen ist falsch?
    1. ADie 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.
    2. BDie 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).
    3. CDie optimale Losung fur eine TSP-Instanz besucht moglicherweise einige
      Knoten in V mehrfach.
    4. DDie 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).

Información

Descripción
Mögliche Algofragen
Idioma
Deutsch
Visitas
31
Valoración
Aún sin valoraciones
Valora este test
Valora este test

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué te parece el nuevo diseño?

¿Te gusta?