NP-Vollständigkeit: Interaktive Lernquizzes für Algorithmen und Datenstrukturen

Question 1

Welches der folgenden Probleme ist NP-vollständig: Ermitteln des kürzesten Pfades in einem gewichteten, ungerichteten Graphen?

Accepted Answer

Ermittlung des kürzesten Pfades in einem gewichteten, ungerichteten Graphen

Answer

Sortierung einer Liste von Zahlen in aufsteigender Reihenfolge

Answer

Berechnung des kleinsten gemeinsamen Vielfachen zweier natürlicher Zahlen

Answer

Prüfung, ob eine gegebene Zahl eine Primzahl ist

Question 2

Welche der folgenden Aussagen zu Approximationsalgorithmen ist korrekt?

Accepted Answer

Sie finden in polynomieller Zeit eine Lösung, die innerhalb eines bestimmten Faktors der optimalen Lösung liegt.

Answer

Sie finden immer eine optimale Lösung.

Answer

Sie sind immer genauer als exakte Algorithmen.

Answer

Sie können nur für bestimmte Arten von Problemen verwendet werden.

Question 3

Welches der folgenden Probleme ist ein Beispiel für ein NP-vollständiges Problem?

Accepted Answer

Traveling Salesman Problem

Answer

Sortierung eines Arrays

Answer

Suche nach dem kürzesten Pfad in einem Graphen

Answer

Matrixmultiplikation

Question 4

Welcher Beweisansatz wird verwendet, um zu zeigen, dass ein Problem NP-vollständig ist?

Accepted Answer

Indirekter Beweis (Reduktion)

Answer

Direkter Beweis

Answer

Konstruktionsbeweis

Answer

Statistischer Nachweis

Question 5

Welche der folgenden Aussagen ist korrekt in Bezug auf NP-Vollständigkeit?

Accepted Answer

Ein Problem ist NP-vollständig, wenn es mindestens so schwierig ist wie jedes andere NP-Problem.

Answer

Ein Problem ist NP-vollständig, wenn es in polynomialer Zeit gelöst werden kann.

Answer

Alle NP-vollständigen Probleme sind miteinander äquivalent.

Answer

Die NP-Vollständigkeit eines Problems ist unabhängig von der verwendeten Reduktionsmethode.

Question 6

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Sortierung eines Arrays

Answer

Primzahltest

Answer

Berechnung der Primzahlen kleiner als eine bestimmte Zahl

Question 7

Welche der folgenden Aussagen beschreibt Approximationsalgorithmen?

Accepted Answer

Sie liefern Lösungen, die möglicherweise nicht optimal, aber nahe am Optimum sind.

Answer

Sie liefern exakte Lösungen für NP-vollständige Probleme.

Answer

Sie reduzieren die Komplexität von NP-vollständigen Problemen auf P.

Answer

Sie sind nur für kleine Instanzen von NP-vollständigen Problemen anwendbar.

Question 8

Welche der folgenden Aussagen ist eine Folge der NP-Vollständigkeit?

Accepted Answer

Es gibt keine effizienten Algorithmen zur Lösung aller NP-vollständigen Probleme.

Answer

Es ist unmöglich, zu beweisen, dass ein gegebenes Problem NP-vollständig ist.

Answer

Die NP-Vollständigkeit eines Problems impliziert, dass es keine heuristischen Algorithmen für dieses Problem gibt.

Answer

Approximationsalgorithmen sind für alle NP-vollständigen Probleme wirkungslos.

Question 9

Welche Aussage beschreibt die Cook-Levin-Transformation zutreffend?

Accepted Answer

Sie wandelt jedes NP-Problem in ein SAT-Problem um.

Answer

Sie wandelt jedes SAT-Problem in ein NP-Problem um.

Answer

Sie beweist die polynomiale Äquivalenz aller NP-Probleme.

Answer

Sie widerlegt die Vermutung P = NP.

Question 10

Welche Aussage zu Reduktionen zwischen Problemen ist richtig?

Accepted Answer

Eine Reduktion wandelt die Lösung eines Problems in die Lösung eines anderen Problems um.

Answer

Eine Reduktion wandelt ein beliebiges Problem in ein NP-vollständiges Problem um.

Answer

Eine Reduktion darf die Laufzeit des Problems nicht verändern.

Answer

Eine Reduktion ist immer ein Beweis dafür, dass das Problem NP-vollständig ist.

Question 11

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Primzahltest

Answer

Sortierproblem

Answer

Lineare Regression

Question 12

Welche Aussage beschreibt die Komplexitätsklasse NP treffend?

Accepted Answer

Probleme, deren Lösungen in polynomialer Zeit überprüfbar sind.

Answer

Probleme, die in polynomialer Zeit lösbar sind.

Answer

Probleme, die mittels Brute-Force-Methoden effizient lösbar sind.

Answer

Probleme, für die keine effizienten Algorithmen bekannt sind.

Question 13

Welche Technik wird eingesetzt, um das Hamiltonkreisproblem annähernd zu lösen?

Accepted Answer

Simulated Annealing

Answer

Lineare Programmierung

Answer

Zufallssuche

Answer

Dynamische Programmierung

Question 14

Welche Aussage beschreibt den Zusammenhang zwischen NP-Vollständigkeit und Approximationsalgorithmen?

Accepted Answer

Approximationsalgorithmen können NP-vollständige Probleme nur innerhalb einer bestimmten Approximationsgarantie lösen.

Answer

NP-vollständige Probleme können immer durch Approximationsalgorithmen effizient gelöst werden.

Answer

NP-vollständige Probleme können niemals durch Approximationsalgorithmen effizient gelöst werden.

Answer

Approximationsalgorithmen können NP-vollständige Probleme stets besser als eine bestimmte Approximationsgarantie lösen.

Question 15

Welche Aussage über das SAT-Problem ist korrekt?

Accepted Answer

Es ist NP-vollständig.

Answer

Es lässt sich in quadratischer Zeit lösen.

Answer

Es ist ein Spezialfall des Graphfärbungsproblems.

Answer

Es kann durch einen Greedy-Algorithmus effizient gelöst werden.

Question 16

Welche Aussage über NP-optimale Probleme ist richtig?

Accepted Answer

Sie haben keine bekannte effiziente Lösung.

Answer

Sie lassen sich effizient durch Brute-Force-Methoden lösen.

Answer

Ihre Zeitkomplexität ist polynomial.

Answer

Approximationsalgorithmen können sie beliebig genau lösen.

Question 17

Wie verhält sich die Laufzeit von Heuristiken bei NP-vollständigen Problemen?

Accepted Answer

Die Laufzeit von Heuristiken hängt von der Größe der Eingabe ab.

Answer

Heuristiken lösen NP-vollständige Probleme immer in polynomialer Zeit.

Answer

Heuristiken finden immer optimale Lösungen für NP-vollständige Probleme.

Answer

Heuristiken sind immer langsamer als exakte Algorithmen.

Question 18

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Sortierproblem

Answer

Minimales Spannbaumproblem

Answer

Dijkstra-Algorithmus

Question 19

Was ist das Hauptmerkmal von Approximationsalgorithmen?

Accepted Answer

Sie liefern Lösungen mit nachweisbaren Approximationsgarantien.

Answer

Sie liefern immer exakte Lösungen.

Answer

Sie sind nur für kleine Problemgrößen geeignet.

Answer

Sie sind für alle NP-vollständigen Probleme anwendbar.

Question 20

Welcher der folgenden Algorithmen ist ein Approximationsalgorithmus für das Traveling Salesman Problem?

Accepted Answer

Nearest Neighbor Heuristik

Answer

Dijkstra-Algorithmus

Answer

Prim-Algorithmus

Answer

Kruskal-Algorithmus

Question 21

Was besagt die Approximationsgarantie einer 2-Approximation?

Accepted Answer

Die Lösung ist höchstens doppelt so schlecht wie das Optimum.

Answer

Die Lösung ist mindestens doppelt so gut wie das Optimum.

Answer

Die Lösung ist im Durchschnitt doppelt so gut wie das Optimum.

Answer

Die Lösung ist immer gleich dem Optimum.

Question 22

Welche der folgenden Reduktionen ist eine polynomielle Reduktion?

Accepted Answer

Von 3-SAT zu Subset-Sum

Answer

Von Hamiltonkreisproblem zu Teilmengenproblem

Answer

Von Sortierproblem zu Binärunterteilung

Answer

Von Rucksackproblem zu Traveling Salesman Problem

Question 23

Welcher der folgenden Algorithmen ist ein probabilistischer Algorithmus?

Accepted Answer

Randomized QuickSort

Answer

Dijkstra-Algorithmus

Answer

Prim-Algorithmus

Answer

Kruskal-Algorithmus

Question 24

Was ist das Ziel eines Approximationsalgorithmus?

Accepted Answer

Eine ungefähre Lösung für ein NP-vollständiges Problem zu finden

Answer

Eine exakte Lösung für ein NP-vollständiges Problem zu finden

Answer

Die Komplexität eines NP-vollständigen Problems zu reduzieren

Answer

Ein NP-vollständiges Problem in ein polynomialzeitlösbares Problem umzuwandeln

Question 25

Wie wird die Güte eines Approximationsalgorithmus gemessen?

Accepted Answer

Durch seinen Approximationsfaktor

Answer

Durch seine Laufzeit

Answer

Durch seinen Speicherbedarf

Answer

Durch seine Genauigkeit

Question 26

Welches der folgenden Verfahren ist kein Heuristiksverfahren?

Accepted Answer

Dynamische Programmierung

Answer

Tabu-Suche

Answer

Simulated Annealing

Answer

Lokale Suche

Question 27

Welche der folgenden Aussagen beschreibt am besten die Entscheidungsversion eines NP-Problems?

Accepted Answer

Ein Problem, bei dem eine gegebene Lösung in Polynomialzeit überprüft werden kann.

Answer

Ein Problem, bei dem eine Lösung in Polynomialzeit gefunden werden kann.

Answer

Ein Problem, für das eine Lösung in Polynomialzeit existiert, aber nicht unbedingt gefunden werden kann.

Answer

Ein Problem, das sowohl in Polynomialzeit gelöst als auch überprüft werden kann.

Question 28

Welche der folgenden Aussagen über NP-vollständige Probleme ist korrekt?

Accepted Answer

Sie können nicht in polynomialer Zeit exakt gelöst werden.

Answer

Sie können in exponentieller Zeit exakt gelöst werden.

Answer

Sie können nur näherungsweise gelöst werden.

Question 29

Welches der folgenden Probleme ist NP-schwer?

Accepted Answer

Hamiltonkreis

Answer

Kürzester Weg

Answer

Minimales Spannbaumproblem

Answer

Dijkstra-Algorithmus

Question 30

Welches der folgenden Probleme ist ein Beispiel für ein Optimierungsproblem?

Accepted Answer

Rucksackproblem

Answer

Subgraph-Isomorphismus

Answer

SAT-Problem

Answer

Hamiltonkreis

Question 31

Welches der folgenden Probleme ist ein Beispiel für ein graphentheoretisches Problem?

Accepted Answer

Hamilton-Kreis

Answer

SAT-Problem

Answer

Primfaktorzerlegung

Answer

Rucksackproblem

Question 32

Welche der folgenden Aussagen über NP-Vollständigkeit ist falsch?

Accepted Answer

Jedes NP-vollständige Problem kann in polynomialer Zeit gelöst werden.

Answer

NP-Vollständigkeit ist ein Hinweis darauf, dass ein Problem nur sehr schwer zu lösen ist.

Answer

Wenn ein Problem NP-vollständig ist, sind alle anderen Probleme in NP auch NP-vollständig.

Question 33

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Das Erfüllbarkeitsproblem der Aussagenlogik (SAT)

Answer

Die Berechnung der Primzahlen bis zu einer bestimmten Grenze

Answer

Die Sortierung eines Arrays in aufsteigender Reihenfolge

Answer

Die Suche nach dem kürzesten Weg in einem gewichteten Graphen

Question 34

Was ist die allgemeine Charakterisierung von NP-vollständigen Problemen?

Accepted Answer

Sie können in polynomialer Zeit durch einen nichtdeterministischen Turingmaschine gelöst werden, sind aber nichtdeterministisch in polynomialer Zeit entscheidbar

Answer

Sie können in polynomialer Zeit durch eine deterministische Turingmaschine gelöst werden

Question 35

Welcher der folgenden Algorithmen ist ein Approximationsalgorithmus für das Problem des Handlungsreisenden?

Accepted Answer

Der 2-Opt-Algorithmus

Answer

Der Floyd-Warshall-Algorithmus

Answer

Der Kruskal-Algorithmus

Answer

Der Dijkstra-Algorithmus

Question 36

Was ist der Hauptvorteil der Verwendung von Approximationsalgorithmen für NP-vollständige Probleme?

Accepted Answer

Sie liefern schnell eine ungefähre Lösung, die in der Praxis oft ausreichend ist

Answer

Sie garantieren immer eine optimale Lösung

Answer

Sie können in polynomialer Zeit genaue Lösungen liefern

Question 37

Welches der folgenden Probleme ist nicht NP-vollständig?

Accepted Answer

Das Problem der Sortierung eines Arrays in absteigender Reihenfolge

Answer

Das Problem des Handlungsreisenden

Answer

Das Problem der Teilmengenaufsummierung

Question 38

Welche Art von Aufzählung liegt vor, wenn alle möglichen Lösungen eines NP-vollständigen Problems implizit berücksichtigt werden?

Accepted Answer

Brute-Force-Suche nach allen möglichen Lösungen

Answer

Zufällige Suche

Answer

Greedy-Suche

Answer

Informierte Suche

Question 39

Welches der folgenden Probleme ist NP-vollständig, kann aber in polynomialer Zeit durch eine deterministische Turingmaschine gelöst werden, wenn die Eingabegröße beschränkt ist?

Accepted Answer

Das Problem der Teilmengenaufsummierung für eine feste Teilmengengröße

Answer

Das Problem des Rucksackproblems

Answer

Das Problem der Cliquenfindung

Answer

Das Problem des Handlungsreisenden

Question 40

Was ist der wesentliche Unterschied zwischen NP-Vollständigkeit und PSPACE-Vollständigkeit?

Accepted Answer

NP-vollständige Probleme können in polynomialer Zeit durch eine nichtdeterministische Turingmaschine gelöst werden, während PSPACE-vollständige Probleme in polynomialer Speicherplatzkomplexität durch eine nichtdeterministische Turingmaschine gelöst werden können.

Answer

PSPACE-vollständige Probleme sind immer auch NP-vollständig

Answer

NP-vollständige Probleme sind immer auch PSPACE-vollständig

Question 41

Welches der folgenden Probleme ist ein klassisches NP-vollständiges Problem?

Accepted Answer

SAT

Answer

Sortierung

Answer

Suche in einem sortierten Array

Answer

Primzahltest

Question 42

Welches der folgenden Probleme ist NP-schwer?

Accepted Answer

3-SAT

Answer

Bubblesort

Answer

Binäres Suchproblem

Answer

Kürzester Weg

Question 43

Was ist der Hauptgedanke eines Beweises durch Widerspruch?

Accepted Answer

Die Annahme, dass eine Aussage falsch ist, führt zu einem Widerspruch.

Answer

Eine Lösung wird direkt konstruiert.

Question 44

Welche der folgenden Aussagen trifft auf die Beziehung zwischen NP-Vollständigkeit und NP-Schwere zu?

Accepted Answer

Es gibt keine Probleme, die NP-vollständig, aber nicht NP-schwer sind.

Answer

SAT ist NP-vollständig, aber nicht NP-schwer.

Question 45

Welche der folgenden Aussagen zu Approximationsproblemen ist korrekt?

Accepted Answer

Sie können sowohl Minimierungs- als auch Maximierungsprobleme sein.

Answer

Sie können nur für NP-vollständige Probleme formuliert werden.

Answer

Ihre Approximationsrate ist immer 1.

Question 46

Welches der folgenden Probleme ist nachweislich NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Breitensuche

Answer

Sortierung

Answer

Suche des kleinsten gemeinsamen Vielfachen

Question 47

Welche Aussage ist bezüglich NP-vollständiger Probleme zutreffend?

Accepted Answer

Sie können nicht exakt in Polynomialzeit gelöst werden.

Answer

Sie sind immer leicht zu lösen.

Answer

Sie können nur durch Brute-Force-Suche gelöst werden.

Question 48

Welche Reduktionsart ist von entscheidender Bedeutung, um die NP-Vollständigkeit zu beweisen?

Accepted Answer

Polynomzeitreduktion

Answer

Logarithmische Reduktion

Answer

Exponentielle Reduktion

Answer

Linearkonstantenreduktion

Question 49

Welches der folgenden Probleme ist NP-vollständig, aber nicht in polynomieller Zeit lösbar, außer es sei denn, P = NP?

Accepted Answer

Das Problem zu entscheiden, ob ein Graph einen Hamiltonschen Kreis enthält.

Answer

Das Problem zu entscheiden, ob ein Graph azyklisch ist.

Answer

Das Problem zu entscheiden, ob ein Graph planar ist.

Question 50

Welche der folgenden Aussagen über Approximationsalgorithmen ist korrekt?

Accepted Answer

Sie liefern Lösungen, die möglicherweise nicht optimal sind, aber oft nahe am Optimum liegen.

Answer

Sie sind immer effizienter als exakte Algorithmen.

Answer

Sie können immer exakte Lösungen liefern.

Question 51

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Das Problem des Handlungsreisenden (TSP)

Answer

Das Finden des kürzesten Pfades in einem Graphen

Answer

Das Berechnen des größten gemeinsamen Teilers zweier Zahlen

Answer

Das Sortieren einer Liste von Zahlen

Question 52

Welche der folgenden Aussagen über NP-vollständige Probleme ist FALSCH?

Accepted Answer

NP-vollständige Probleme können in polynomieller Zeit gelöst werden.

Answer

NP-vollständige Probleme sind in NP enthalten.

Answer

Wenn ein NP-vollständiges Problem in polynomieller Zeit gelöst werden kann, dann können alle Probleme in NP in polynomieller Zeit gelöst werden.

Question 53

Welche der folgenden Techniken wird häufig verwendet, um NP-vollständige Probleme zu lösen?

Accepted Answer

Approximationsalgorithmen

Answer

Divide-and-Conquer

Answer

Dynamische Programmierung

Answer

Greedy-Algorithmen

Question 54

Welche der folgenden Eigenschaften ist NICHT charakteristisch für einen Approximationsalgorithmus?

Accepted Answer

Er findet immer die optimale Lösung.

Answer

Er findet eine Lösung in polynomieller Zeit.

Answer

Er ist besonders nützlich für NP-vollständige Probleme.

Answer

Er liefert eine Lösung, die innerhalb einer bestimmten Toleranz von der optimalen Lösung liegt.

Question 55

Welche der folgenden Aussagen über Approximationsalgorithmen für NP-vollständige Probleme ist RICHTIG?

Accepted Answer

Sie bieten oft eine gute Balance zwischen Laufzeit und Lösungsqualität.

Answer

Sie sind nur für bestimmte NP-vollständige Probleme geeignet.

Answer

Sie finden immer die optimale Lösung.

Question 56

Welcher der folgenden Algorithmen ist ein Approximationsalgorithmus für das Problem des Handlungsreisenden (TSP)?

Accepted Answer

Nearest-Neighbor-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 57

Was ist die Komplexitätsklasse von Problemen, die in polynomieller Zeit verifiziert werden können?

Accepted Answer

NP

Answer

P

Answer

EXPTIME

Answer

NP-vollständig

Question 58

Was bedeutet es, wenn ein Problem NP-hart ist?

Accepted Answer

Jedes Problem in NP kann auf das Problem in polynomieller Zeit reduziert werden.

Answer

Das Problem ist nicht in NP enthalten.

Answer

Das Problem kann in polynomieller Zeit gelöst werden.

Question 59

Welche der folgenden Aussagen über NP-vollständige Probleme ist RICHTIG?

Accepted Answer

Es gibt keine bekannte effiziente Lösung für alle NP-vollständigen Probleme.

Answer

Es gibt effiziente Algorithmen für alle NP-vollständigen Probleme.

Answer

NP-vollständige Probleme sind in der Praxis selten anzutreffen.

Question 60

Welches Problem ist nachweislich NP-vollständig?

Accepted Answer

Das Traveling Salesperson Problem

Answer

Das Berechnen der Fakultät einer Zahl

Answer

Das Suchen eines Elements in einem sortierten Array

Answer

Das Sortieren einer Liste von Zahlen

Question 61

Was ist eine Eigenschaft von NP-vollständigen Problemen?

Accepted Answer

Es ist nicht bekannt, ob sie in polynomieller Zeit gelöst werden können.

Answer

Sie sind immer leicht zu lösen.

Answer

Sie können nur durch Approximationsalgorithmen gelöst werden.

Question 62

Was bedeutet es, wenn ein Problem auf ein anderes reduziert werden kann?

Accepted Answer

Eine Lösung für das erste Problem kann verwendet werden, um das zweite Problem zu lösen.

Answer

Das erste Problem ist schwieriger als das zweite Problem.

Answer

Die beiden Probleme sind identisch.

Question 63

Was ist ein Beispiel für einen Approximationsalgorithmus?

Accepted Answer

Der Nearest-Neighbor-Algorithmus für das Traveling Salesperson Problem

Answer

Der binäre Suchalgorithmus

Answer

Der Bubblesort-Algorithmus

Question 64

Was ist das Ziel eines Approximationsalgorithmus für ein NP-vollständiges Problem?

Accepted Answer

Eine in polynomieller Zeit berechenbare Lösung zu finden, die möglichst nah an der optimalen Lösung liegt.

Answer

Die optimale Lösung in exponentieller Zeit zu finden.