Komplexitätstheorie: Online-Quiz für Informatik-Studierende

Question 1

Welches Problem ist NP-vollständig?

Accepted Answer

SAT

Answer

Sortierung

Answer

Primzahltest

Answer

Lineare Algebra

Question 2

Was ist die Konsequenz, wenn ein NP-vollständiges Problem in polynomialer Zeit gelöst werden kann?

Accepted Answer

P = NP

Answer

NP = PSPACE

Answer

PSPACE = NP

Answer

Es gibt keine Konsequenzen.

Question 3

Welcher der folgenden Algorithmen ist ein heuristischer Algorithmus?

Accepted Answer

Genetischer Algorithmus

Answer

Quicksort

Answer

Breadth-First-Suche

Answer

Dijkstra-Algorithmus

Question 4

Welche der folgenden Definitionen von **NP-Vollständigkeit** ist korrekt?

Accepted Answer

Ein Problem ist NP-vollständig, wenn es in **NP** ist und jedes andere Problem in **NP** polynomial darauf reduziert werden kann.

Answer

Ein Problem ist NP-vollständig, wenn es in **P** ist und jedes andere Problem in **P** polynomial darauf reduziert werden kann.

Answer

Ein Problem ist NP-vollständig, wenn es in **NP** ist, aber nicht in **P**.

Answer

Ein Problem ist NP-vollständig, wenn es in **P** ist, aber nicht in **NP**.

Question 5

Welche Technik wird verwendet, um zu beweisen, dass ein Problem **NP-vollständig** ist?

Accepted Answer

Polynomiale Reduktion

Answer

Induktionsbeweis

Answer

Diagonalisierungsargument

Answer

Approximationsalgorithmus

Question 6

Welche Art von Reduktion wird verwendet, um **NP-Vollständigkeit** zu beweisen?

Accepted Answer

Polynomiale Reduktion

Answer

Lineare Reduktion

Answer

Logarithmische Reduktion

Answer

Exponentielle Reduktion

Question 7

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

Accepted Answer

Das Problem, zu entscheiden, ob eine ganzzahlige Matrix invertierbar ist

Answer

Das Graphfärbungsproblem

Answer

Das Hamiltonkreisproblem

Answer

Das Cliquenproblem

Question 8

Welche Aussage über die Beziehung zwischen den Komplexitätsklassen **NP** und **P** ist korrekt?

Accepted Answer

Es ist unbekannt, ob **NP** gleich **P** ist.

Answer

NP ist eine Teilmenge von P.

Answer

P ist eine Teilmenge von NP.

Answer

NP und P sind disjunkte Mengen.

Question 9

Welche Aussage über die Komplexitätsklasse P trifft zu?

Accepted Answer

Sie beinhaltet alle Probleme, die in polynomialer Zeit lösbar sind.

Answer

Sie beinhaltet alle Probleme, die in exponentieller Zeit lösbar sind.

Answer

Sie ist eine echte Teilmenge von NP.

Answer

Sie ist identisch mit NP.

Question 10

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreis-Problem

Answer

Sortierproblem

Answer

Primzahltest

Answer

Berechnung der Determinante einer Matrix

Question 11

Welcher der folgenden Algorithmen ist ein randomisierter Algorithmus?

Accepted Answer

Monte-Carlo-Algorithmus

Answer

Quicksort

Answer

Binärsuche

Answer

Dijkstra-Algorithmus

Question 12

Welcher der folgenden Begriffe beschreibt die asymptotische Laufzeit eines Algorithmus, dessen Laufzeit linear mit der Anzahl der Eingaben wächst?

Accepted Answer

Lineare Komplexität

Answer

Quadratische Komplexität

Answer

Exponentielle Komplexität

Answer

Logarithmische Komplexität

Question 13

Welcher der folgenden Algorithmen ist ein heuristischer Algorithmus?

Accepted Answer

Greedy

Answer

Branch-and-Bound

Answer

Quicksort

Answer

Dijkstra

Question 14

Welche Aussage über die Turingmaschine ist korrekt?

Accepted Answer

Sie ist ein abstraktes Rechenmodell, das alle berechenbaren Probleme lösen kann.

Answer

Sie ist ein physisches Gerät, das zur Durchführung von Berechnungen verwendet wird.

Answer

Sie ist eine effiziente Möglichkeit, große Datenmengen zu verarbeiten.

Answer

Sie wurde von Charles Babbage erfunden.

Question 15

Welcher Begriff beschreibt die Anzahl der Rechenschritte, die ein Algorithmus für ein gegebenes Problem durchführt?

Accepted Answer

Laufzeitkomplexität

Answer

Speicherkomplexität

Answer

Algorithmische Effizienz

Answer

Berechenbarkeit

Question 16

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Sortierung eines Arrays

Answer

Primzahltest

Answer

Berechnung des kleinsten gemeinsamen Vielfachen

Question 17

Welche Problemklasse ist eine Teilmenge aller Probleme, die in Polynomialzeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NPC

Answer

EXPTIME

Question 18

Welches Problem ist undefinierbar?

Accepted Answer

Das Halteproblem

Answer

Das Diagonalisierungsproblem

Answer

Das Färbungsproblem

Answer

Das Primzahlproblem

Question 19

Welche Aussage über die Komplexitätstheorie ist **nicht** korrekt?

Accepted Answer

Sie kann die beste Lösung für ein Problem finden.

Answer

Sie untersucht die Klassifizierung von Problemen nach ihrer Schwierigkeit.

Answer

Sie kann bestimmen, ob ein Problem überhaupt lösbar ist.

Answer

Sie kann keine neuen Algorithmen entwickeln.

Question 20

Welches ist das zentrale Ziel der Komplexitätstheorie?

Accepted Answer

Probleme nach ihrer Schwierigkeit zu klassifizieren

Answer

Effiziente Algorithmen zu entwerfen

Answer

Unlösbare Probleme zu identifizieren

Answer

Die Anzahl der Ausführungsschritte eines Algorithmus zu minimieren

Question 21

Welche Komplexitätsklasse vereint Probleme, die in polynomieller Zeit lösbar sind?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

EXP

Question 22

Was besagt das P-gegen-NP-Problem?

Accepted Answer

Sind alle NP-Probleme auch in P lösbar?

Answer

Sind alle P-Probleme auch in NP lösbar?

Answer

Sind alle EXP-Probleme auch in P lösbar?

Answer

Sind alle NP-vollständigen Probleme auch in P lösbar?

Question 23

Welche Eigenschaft trifft auf die Komplexitätsklasse EXP zu?

Accepted Answer

Sie umfasst Probleme, die in exponentieller Zeit lösbar sind

Answer

Sie ist eine Teilmenge von NP

Answer

Sie enthält alle NP-vollständigen Probleme

Answer

Sie ist identisch mit der Klasse P

Question 24

Worin unterscheiden sich deterministische von nicht-deterministischen Turingmaschinen?

Accepted Answer

Eine deterministische Turingmaschine wählt bei jedem Schritt nur einen Pfad, während eine nicht-deterministische mehrere Pfade wählen kann

Answer

Eine nicht-deterministische Turingmaschine wählt bei jedem Schritt nur einen Pfad, während eine deterministische mehrere Pfade wählen kann

Answer

Deterministische Turingmaschinen sind stets effizienter als nicht-deterministische

Answer

Nicht-deterministische Turingmaschinen sind stets effizienter als deterministische

Question 25

Welche Aussage zu NP-Problemen ist korrekt?

Accepted Answer

Ihre Lösungen können in polynomieller Zeit verifiziert werden

Answer

Sie sind in polynomieller Zeit lösbar

Answer

Sie sind in exponentieller Zeit lösbar

Answer

Ihre Lösungen erfordern stets eine vollständige Suche

Question 26

Welches der folgenden Probleme ist ein NP-vollständiges Problem, das sich auf die Überprüfung der Erfüllbarkeit einer booleschen Formel bezieht?

Accepted Answer

SAT-Problem

Answer

Primzahltest

Answer

Suche nach dem kürzesten Pfad

Answer

Sortierung von Zahlen

Question 27

Welche Aussage über P-Probleme ist korrekt?

Accepted Answer

P-Probleme können in polynomialer Zeit deterministisch gelöst werden.

Answer

P-Probleme sind nicht NP-schwer.

Answer

P-Probleme sind NP-vollständig.

Answer

P-Probleme sind immer in linearer Zeit lösbar.

Question 28

Was ist das zentrale Ziel der Komplexitätstheorie?

Accepted Answer

Klassifizierung von Problemen nach ihrer rechnerischen Schwierigkeit

Answer

Analyse und Verbesserung bestehender Algorithmen

Answer

Entwicklung effizienter Algorithmen für bestimmte Aufgaben

Question 29

Welche der Komplexitätsklassen beschreibt die Menge aller Probleme, die in deterministischer polynomialer Zeit gelöst werden können?

Accepted Answer

P

Answer

NP-schwer

Answer

NP

Answer

NP-vollständig

Question 30

Welche Bedeutung hat das Konzept der Turingmaschine in der Komplexitätstheorie?

Accepted Answer

Es bietet ein abstraktes Modell für Berechnungen und die Untersuchung ihrer Komplexität.

Answer

Es bildet die Grundlage für die Entwicklung neuer Programmiersprachen.

Answer

Es ermöglicht die präzise Vorhersage der Laufzeit bestimmter Algorithmen.

Answer

Es dient als Simulationsplattform für reale Computer.

Question 31

Welche Aussage über die Komplexitätsklasse NP ist korrekt?

Accepted Answer

NP-Probleme können in nichtdeterministischer polynomialer Zeit gelöst werden.

Answer

NP-Probleme sind immer in polynomialer Zeit lösbar.

Answer

NP-Probleme sind alle NP-vollständig.

Question 32

Was besagt das Cook-Levin-Theorem?

Accepted Answer

Es beweist, dass das SAT-Problem NP-vollständig ist und somit eine Basis für andere NP-vollständige Probleme bildet.

Answer

Es liefert einen effizienten Algorithmus zur Lösung aller NP-vollständigen Probleme.

Answer

Es beweist, dass P = NP ist.

Question 33

Welches der folgenden Probleme ist ein Beispiel für ein NP-schweres Problem?

Accepted Answer

Hamiltonkreisproblem

Answer

Suche nach dem kürzesten Pfad

Answer

Sortierung von Zahlen

Answer

Primzahltest

Question 34

Was bedeutet es, wenn ein Problem als NP-vollständig klassifiziert wird?

Accepted Answer

Es ist mindestens so schwierig wie jedes andere NP-Problem, d. h., jedes NP-Problem kann darauf reduziert werden.

Answer

Es kann nur durch Brute-Force-Suche gelöst werden.

Answer

Es kann in linearer Zeit gelöst werden.

Question 35

Welche Aussage über NP-vollständige Probleme ist korrekt?

Accepted Answer

Sie sind nicht in polynomialer Zeit lösbar, es sei denn, P = NP.

Answer

Sie sind immer in exponentieller Zeit lösbar.

Answer

Sie sind immer in quadratischer Zeit lösbar.

Question 36

Welche Aussage über Polynomzeitreduktionen ist korrekt?

Accepted Answer

Sie transformieren ein Problem in ein anderes Problem, wobei die Lösungen in polynomialer Zeit überprüft werden können.

Answer

Sie transformieren ein Problem in ein anderes Problem, wobei die Lösungen in exponentieller Zeit überprüft werden können.

Question 37

Welche Aussage über das Halteproblem ist korrekt?

Accepted Answer

Es ist unentscheidbar.

Answer

Es ist NP-vollständig.

Answer

Es ist in linearer Zeit lösbar.

Answer

Es ist entscheidbar, aber nur von Quantencomputern.

Question 38

Welche Aussage über Zufallsalgorithmen ist korrekt?

Accepted Answer

Sie liefern nicht immer die richtige Antwort, aber sie liefern sie mit einer gewissen Wahrscheinlichkeit.

Answer

Sie liefern immer die richtige Antwort, aber sie benötigen viel Zeit.

Question 39

Welche Aussage über die asymptotische Notation ist korrekt?

Accepted Answer

Sie beschreibt das Verhalten einer Funktion für große Eingaben.

Answer

Sie ist nur für lineare Funktionen anwendbar.

Answer

Sie beschreibt das genaue Verhalten einer Funktion für alle Eingaben.

Question 40

Welche Aussage über NP-schwere Probleme ist korrekt?

Accepted Answer

Es gibt keine bekannte polynomielle Zeitlösung für sie.

Answer

Sie sind immer in exponentieller Zeit lösbar.

Answer

Sie können in polynomialer Zeit von Quantencomputern gelöst werden.

Question 41

Welche Aussage über Approximationsalgorithmen ist korrekt?

Accepted Answer

Sie liefern eine Lösung, die innerhalb eines bestimmten Faktors von der optimalen Lösung abweicht.

Answer

Sie liefern immer die optimale Lösung.

Answer

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

Question 42

Welche Aussage über die Turingmaschine ist korrekt?

Accepted Answer

Sie ist ein theoretisches Modell für einen Computer, das alle berechenbaren Funktionen berechnen kann.

Answer

Sie ist ein praktischer Computer, der in realen Anwendungen eingesetzt wird.

Question 43

Welche Aussage über die Church-Turing-These ist korrekt?

Accepted Answer

Sie besagt, dass alle berechenbaren Funktionen von einer Turingmaschine berechnet werden können.

Answer

Sie besagt, dass alle Funktionen, die von einer Turingmaschine berechnet werden können, auch von einem menschlichen Gehirn berechnet werden können.

Answer

Sie besagt, dass alle Funktionen, die von einem Computer berechnet werden können, von einer Turingmaschine berechnet werden können.

Question 44

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

Accepted Answer

**Hamiltonkreisproblem**

Answer

Sortierproblem

Answer

Primzahltest

Question 45

**Welche Aussage über NP-Probleme ist zutreffend?**

Accepted Answer

**Es existiert kein bekannter Algorithmus, der sie in polynomialer Zeit löst.**

Answer

Sie sind immer in linearer Zeit lösbar.

Answer

Sie sind immer in exponentieller Zeit lösbar.

Question 46

**Welche Laufzeitklasse beschreibt Probleme, die in logarithmischer Zeit gelöst werden können?**

Accepted Answer

**L**

Answer

EXPTIME

Answer

P

Answer

NP

Question 47

**Welches Reduktionsverfahren wird verwendet, um NP-Probleme auf andere NP-Probleme zurückzuführen?**

Accepted Answer

**Polynomiale Reduktion**

Answer

Lineare Reduktion

Answer

Logarithmische Reduktion

Answer

Exponentielle Reduktion

Question 48

**Was bedeutet die Aussage, dass ein Problem NP-schwer ist?**

Accepted Answer

**Es kann nicht in polynomialer Zeit gelöst werden, es sei denn, P = NP.**

Answer

Es kann nur in exponentieller Zeit gelöst werden.

Answer

Es kann nur in linearer Zeit gelöst werden.

Question 49

**Welcher Algorithmus wird zur Approximation von NP-Problemen verwendet?**

Accepted Answer

**Approximationsalgorithmus**

Answer

Exakter Algorithmus

Answer

Zufälliger Algorithmus

Answer

Heuristischer Algorithmus

Question 50

**Welcher Satz besagt, dass jedes NP-Problem in polynomialer Zeit durch ein nichtdeterministisches Turing-Modell gelöst werden kann?**

Accepted Answer

**Satz von Cook-Levin**

Answer

Satz von Gödel

Answer

Satz von Church-Turing

Answer

Satz von Turing

Question 51

**Welches Problem ist NP-äquivalent zum Hamiltonkreisproblem?**

Accepted Answer

**Traveling-Salesman-Problem**

Answer

Primzahltest

Answer

Dijkstra-Algorithmus

Answer

Satisfiability-Problem

Question 52

**Was ist das Ziel der Komplexitätstheorie?**

Accepted Answer

**Klassifizierung von Problemen nach ihrer Schwierigkeit**

Answer

Optimierung von Algorithmen

Answer

Entwicklung neuer Programmiersprachen

Question 53

Welche der folgenden Aussagen beschreibt das oberste Ziel der Komplexitätstheorie?

Accepted Answer

Zu untersuchen, welche Probleme effizient lösbar sind und welche nicht.

Answer

Algorithmen für spezifische Probleme zu entwerfen.

Answer

Zu bestimmen, wie viele Ressourcen für die Problemlösung optimal sind.

Question 54

Welche Komplexitätsklasse umfasst Probleme, die in polynomieller Zeit lösbar sind?

Accepted Answer

P

Answer

NP-schwer

Answer

NP-vollständig

Answer

NP

Question 55

Welche der folgenden Aussagen beschreibt die Zeitkomplexität der binären Suche?

Accepted Answer

O(log n)

Answer

O(2^n)

Answer

O(n)

Answer

O(n^2)

Question 56

Welche Reduktionsmethode wird verwendet, um die NP-Vollständigkeit eines Problems nachzuweisen?

Accepted Answer

Polynomielle Reduktion

Answer

Logarithmische Reduktion

Answer

Exponentielle Reduktion

Answer

Lineare Reduktion

Question 57

Für welchen Zweck wird die P-NP-Frage gestellt?

Accepted Answer

Zu bestimmen, ob alle Probleme, die effizient überprüfbar sind, auch effizient lösbar sind.

Answer

Um die Entwicklung von Algorithmen für neue Probleme zu vereinfachen.

Answer

Um die Grenzen der Computerberechnung zu ermitteln.

Question 58

Welches Merkmal ist charakteristisch für Approximationsalgorithmen?

Accepted Answer

Sie liefern Lösungen, die sich einer optimalen Lösung annähern.

Answer

Ihre Genauigkeit ist immer mit exakten Algorithmen vergleichbar.

Answer

Sie sind nur für bestimmte Problemtypen geeignet.

Question 59

Was ist das entscheidende Unterscheidungsmerkmal zwischen deterministischen und nichtdeterministischen Turingmaschinen?

Accepted Answer

Nichtdeterministische Turingmaschinen können mehrere Berechnungszweige gleichzeitig erkunden.

Answer

Deterministische Turingmaschinen sind effizienter als nichtdeterministische.

Answer

Nichtdeterministische Turingmaschinen benötigen mehr Speicher als deterministische.

Question 60

Was ist das Halteproblem in der Komplexitätstheorie?

Accepted Answer

Das Problem zu ermitteln, ob ein gegebenes Programm für eine bestimmte Eingabe jemals beendet.

Answer

Das Problem zu bestimmen, wie lange ein gegebenes Programm für eine bestimmte Eingabe benötigt.

Answer

Das Problem zu finden, den optimalen Algorithmus für ein gegebenes Problem zu entwickeln.