Berechenbarkeitstheorie: Online-Quizze für Informatik-Studierende

Question 1

Welche Aussage beschreibt die Entscheidbarkeit von Problemen korrekt?

Accepted Answer

Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für jede Eingabe entscheidet, ob sie eine Lösung hat.

Answer

Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für jede Eingabe eine Lösung findet.

Answer

Ein Problem ist entscheidbar, wenn es eine Turingmaschine gibt, die für jede Eingabe anhält.

Answer

Ein Problem ist entscheidbar, wenn es eine rekursive Funktion gibt, die für jede Eingabe definiert ist.

Question 2

Welche Aussage beschreibt die Beziehung zwischen Turingmaschinen und anderen Modellen der Berechenbarkeit am besten?

Accepted Answer

Turingmaschinen können alle berechenbaren Funktionen berechnen.

Answer

Turingmaschinen sind immer effizienter als andere Algorithmen.

Answer

Endliche Zustandsmaschinen können alle Probleme lösen, die Turingmaschinen lösen können.

Answer

Nichtdeterministische Turingmaschinen sind immer mächtiger als deterministische Turingmaschinen.

Question 3

Welche der folgenden Aussagen fasst die Berechenbarkeitstheorie am umfassendsten zusammen?

Accepted Answer

Sie untersucht die Lösbarkeit von Problemen durch Algorithmen und die Klassifizierung ihrer Schwierigkeit.

Answer

Sie befasst sich ausschließlich mit der Lösbarkeit von Problemen, die nicht algorithmisch lösbar sind.

Answer

Sie konzentriert sich auf die Klassifizierung von Problemen nach ihrem Schwierigkeitsgrad.

Answer

Sie untersucht, welche Probleme in endlicher Zeit gelöst werden können.

Question 4

Welches Modell repräsentiert in der Berechenbarkeitstheorie die abstrakte Vorstellung eines Rechners?

Accepted Answer

Turingmaschine

Answer

Nichtdeterministischer Pushdown-Automat

Answer

Endlicher Automat

Answer

Neuronales Netzwerk

Question 5

Welche Komplexitätsklasse umfasst Probleme, die in polynomieller Zeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 6

Welches Verfahren dient der Prüfung, ob ein kontextfreier Ausdruck mehrdeutig ist?

Accepted Answer

CYK-Algorithmus

Answer

Parseranalyse

Answer

Breitensuche im Baum

Answer

Rekursive Deszensionsanalyse

Question 7

Welche Aussage trifft auf die Beziehung zwischen Rekursion und Berechenbarkeit zu?

Accepted Answer

Alle rekursiven Funktionen sind berechenbar.

Answer

Alle berechenbaren Funktionen sind rekursiv.

Answer

Rekursive Funktionen sind immer schneller als nicht-rekursive Funktionen.

Answer

Rekursion ist nur für einfache Funktionen geeignet.

Question 8

Wie tragen Komplexitätsklassen zur Klassifizierung von Problemen bei?

Accepted Answer

Sie ordnen Probleme nach ihrer Schwierigkeit.

Answer

Sie gelten nur für Probleme mit polynomialer Laufzeit.

Answer

Sie sind für die praktische Lösbarkeit von Problemen irrelevant.

Answer

Alle NP-Probleme sind auch P-Probleme.

Question 9

Welche Aussage beschreibt die Bedeutung der klassischen Unentscheidbarkeitsprobleme für die Berechenbarkeitstheorie?

Accepted Answer

Sie zeigten, dass es keine universelle Methode zur Lösung aller Entscheidungsprobleme gibt.

Answer

Sie bewiesen, dass alle Probleme algorithmisch lösbar sind.

Answer

Sie legten den Grundstein für die Theorie der NP-Vollständigkeit.

Answer

Sie etablierten die Turingmaschine als zentrales Konzept der Berechenbarkeitstheorie.

Question 10

Welches der folgenden Modelle ist **nicht** äquivalent zu einer Turingmaschine?

Accepted Answer

Quantencomputer

Answer

Registermaschine

Answer

Deterministischer endlicher Automat

Answer

Zweiseitiger endlicher Automat

Question 11

Welcher der folgenden Automatentypen ist NICHT in der Chomsky-Hierarchie enthalten?

Accepted Answer

Moore-Automaten

Answer

Endliche Automaten

Answer

Kellerautomaten

Question 12

Welche der folgenden Komplexitätsklassen repräsentiert Probleme, die in polynomialer Zeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

PSPACE

Question 13

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Rucksackproblem

Answer

Sortierung eines Arrays

Answer

Primzahltest

Question 14

Was ist das primäre Ziel der Berechenbarkeitstheorie?

Accepted Answer

Untersuchung der Grenzen algorithmischer Problemlösung

Answer

Entwicklung effizienter Algorithmen für komplexe Probleme

Answer

Analyse der Sicherheit von Computersystemen

Question 15

Welche der folgenden Sprachen ist nicht rekursiv?

Accepted Answer

{w | w enthält ein ungerades c}

Answer

{w | w ist ein Palindrom}

Answer

{w | w enthält mindestens ein a und ein b}

Question 16

Welcher der folgenden Beweise ist in der Berechenbarkeitstheorie üblich?

Accepted Answer

Diagonalisierungsbeweis

Answer

Induktionsbeweis

Answer

Kontradiktorischer Beweis

Question 17

Was ist das Halteproblem?

Accepted Answer

Das Problem, zu bestimmen, ob ein Programm mit einer bestimmten Eingabe jemals anhält

Answer

Das Problem, zu bestimmen, ob ein Programm eine bestimmte Ausgabe erzeugt

Answer

Das Problem, zu bestimmen, ob ein Programm syntaktisch korrekt ist

Question 18

Welche der folgenden Aussagen über die Church-Turing-These ist korrekt?

Accepted Answer

Beide Aussagen sind korrekt.

Answer

Sie besagt, dass alle berechenbaren Funktionen von einer Turing-Maschine berechnet werden können.

Answer

Sie besagt, dass alle Funktionen, die von einer Turing-Maschine berechnet werden können, berechenbar sind.

Question 19

Was ist die Bedeutung des Begriffes "Unentscheidbarkeit" in der Berechenbarkeitstheorie?

Accepted Answer

Es gibt Probleme, für die kein Algorithmus existiert, der sie für alle Eingaben lösen kann.

Answer

Es gibt Probleme, für die ein Algorithmus existiert, der sie für einige Eingaben lösen kann, aber nicht für alle.

Answer

Es gibt Probleme, für die kein effizienter Algorithmus existiert, der sie für alle Eingaben lösen kann.

Question 20

Welches der folgenden Probleme ist laut Halteproblem nicht entscheidbar?

Accepted Answer

Halteproblem

Answer

Primzahltest

Question 21

Turing-Berechenbarkeit: Welche der folgenden Sprachen ist nicht Turing-berechenbar?

Accepted Answer

{w | w ist eine Primzahl}

Answer

{w | w enthält ein ,a'}

Answer

{w | w enthält eine gerade Anzahl von ,a'}

Answer

{w | w ist eine Palindromzahl}

Question 22

Halting-Problem: Was ist die richtige Aussage über das Halting-Problem?

Accepted Answer

Das Halteproblem ist für alle Turingmaschinen unlösbar.

Answer

Für jedes Halteproblem gibt es einen Algorithmus, der es löst.

Answer

Das Halteproblem ist für alle deterministischen Turingmaschinen lösbar.

Answer

Das Halteproblem kann nur für nichtdeterministische Turingmaschinen gelöst werden.

Question 23

Komplexitätsklasse P: Welche Komplexitätsklasse enthält die Probleme, die in polynomialer Zeit lösbar sind?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

PSPACE

Question 24

coNP-Klasse: Welche der folgenden Sprachen gehört zur coNP-Klasse?

Accepted Answer

{w | w ist eine zusammengesetzte Zahl}

Answer

{w | w ist eine Primzahl}

Answer

{w | w ist eine gerade Zahl}

Answer

{w | w ist eine ungerade Zahl}

Question 25

Welches der folgenden Probleme ist unentscheidbar?

Accepted Answer

Halteproblem

Answer

Sortierproblem

Answer

Primzahltest

Question 26

Welche Komplexitätsklasse enthält alle Probleme, die in polynomieller Zeit lösbar sind?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

EXPTIME

Question 27

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

SAT-Problem

Answer

Sortierproblem

Answer

Primzahltest

Answer

Shortest Path-Problem

Question 28

Welche Aussage über die Reduktion ist richtig?

Accepted Answer

Sie ist transitiv.

Answer

Sie ist reflexiv.

Answer

Sie ist antireflexiv.

Answer

Sie ist symmetrisch.

Question 29

Welche der folgenden Aussagen über deterministische endliche Automaten (DFAs) ist richtig?

Accepted Answer

Sie erkennen reguläre Sprachen.

Answer

Sie können nur Probleme mit endlich vielen Eingaben lösen.

Answer

Sie können alle Sprachen erkennen.

Answer

Ihre Komplexität ist nur für nichtdeterministische Automaten definierbar.

Question 30

Welche Komplexitätsklasse enthält alle Probleme, die in exponentieller Zeit lösbar sind?

Accepted Answer

EXPTIME

Answer

NP

Answer

P

Answer

NP-vollständig

Question 31

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

Accepted Answer

Primzahltest

Answer

Teilmengenproblem

Answer

SAT-Problem

Answer

Hamiltonkreisproblem

Question 32

Welches Problem gilt nach der Church-Turing-These als unlösbar?

Accepted Answer

Entscheidungsproblem

Answer

Suche nach dem kleinsten gemeinsamen Teiler

Answer

Berechnung von Primzahlen

Answer

Sortierung einer Liste

Question 33

Welche Charakterisierung der Komplexitätsklasse NP ist korrekt?

Accepted Answer

Sie umfasst alle Probleme, bei denen Lösungen in polynomialer Zeit verifiziert werden können.

Answer

Sie umfasst alle Probleme, bei denen Lösungen in linearer Zeit gefunden werden können.

Answer

Sie umfasst alle Probleme, bei denen Lösungen in logarithmischer Zeit gefunden werden können.

Question 34

Welche Reduktionsart ist für den Nachweis der NP-Vollständigkeit von Bedeutung?

Accepted Answer

Polynomielle Reduktion

Answer

Konstante Reduktion

Answer

Lineare Reduktion

Answer

Logarithmische Reduktion

Question 35

Welche Eigenschaft ist für rekursive Funktionen charakteristisch?

Accepted Answer

Sie rufen sich selbst mindestens einmal auf.

Answer

Sie sind immer deterministisch.

Answer

Sie haben keine Basisfälle.

Question 36

Welche Annahme liegt dem Konzept einer deterministischen Turing-Maschine zugrunde?

Accepted Answer

Sie befindet sich immer in genau einem Zustand.

Answer

Sie verfügt über unendlich viel Speicher.

Answer

Sie kann nur eine begrenzte Anzahl von Operationen ausführen.

Question 37

In der Berechenbarkeitstheorie: Welches Problem ist unentscheidbar?

Accepted Answer

Haltproblem

Answer

Sortierproblem

Answer

Faktorisierungsproblem

Answer

Primzahltest

Question 38

Komplexitätsklassen: Welche Komplexitätsklasse umfasst Probleme, die in Polynomzeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 39

Beziehung zwischen P und NP: Welche Aussage ist korrekt?

Accepted Answer

P ≠ NP impliziert, dass nicht alle NP-Probleme in Polynomialzeit gelöst werden können.

Answer

NP ≠ P impliziert, dass alle NP-Probleme in Polynomialzeit gelöst werden können.

Answer

P = NP impliziert, dass alle NP-Probleme in Exponentialzeit gelöst werden können.

Question 40

Heuristische Algorithmen: Welcher Algorithmus ist ein heuristischer Algorithmus?

Accepted Answer

Genetischer Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Hash-Tabelle

Answer

Sortiernetzwerk

Question 41

Datenstrukturen: Welche Datenstruktur eignet sich am besten für die effiziente Suche nach dem nächsten größeren Element?

Accepted Answer

Segmentbaum

Answer

AVL-Baum

Answer

Binärer Suchbaum

Answer

Hash-Tabelle

Question 42

Welche Aussage beschreibt die Komplexitätsklasse BPP?

Accepted Answer

BPP beinhaltet Probleme, die mit hoher Wahrscheinlichkeit in Polynomialzeit lösbar sind.

Answer

BPP beinhaltet Probleme, die deterministisch in Polynomialzeit lösbar sind.

Question 43

Was trifft auf das Halteproblem zu?

Accepted Answer

Es ist unentscheidbar.

Answer

Es ist PSPACE-vollständig.

Answer

Es ist NP-vollständig.

Answer

Es ist in linearer Zeit lösbar.

Question 44

Welche der genannten Klassen von Sprachen ist rekursiv aufzählbar, aber nicht entscheidbar?

Accepted Answer

RE - R

Answer

R

Answer

NP

Question 45

Was besagt die Church-Turing-These?

Accepted Answer

Jede berechenbare Funktion kann von einer Turingmaschine berechnet werden.

Answer

Nur Funktionen, die in polynomialer Zeit berechenbar sind, können von einer Turingmaschine berechnet werden.

Answer

Nur Funktionen, die in exponentieller Zeit berechenbar sind, können von einer Turingmaschine berechnet werden.

Question 46

Welche Aussage zur Komplexitätsklasse NP ist korrekt?

Accepted Answer

NP beinhaltet Probleme, für die Lösungen in Polynomialzeit verifiziert werden können.

Answer

NP beinhaltet Probleme, für die Lösungen in linearer Zeit gefunden werden können.

Answer

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

Question 47

Was trifft auf die Komplexitätsklasse PSPACE zu?

Accepted Answer

PSPACE beinhaltet Probleme, für die Lösungen in polynomialem Speicherplatz gefunden werden können.

Answer

PSPACE beinhaltet Probleme, für die Lösungen in konstantem Speicherplatz gefunden werden können.

Answer

PSPACE beinhaltet Probleme, die in exponentiellem Speicherplatz lösbar sind.

Question 48

Welche Aussage zur Sprache {TM | TM ist eine Turingmaschine, die anhält} ist zutreffend?

Accepted Answer

Sie ist unentscheidbar.

Answer

Sie ist entscheidbar in exponentieller Zeit.

Answer

Sie ist entscheidbar in linearer Zeit.

Answer

Sie ist entscheidbar in polynomialer Zeit.

Question 49

Nennen Sie eine praktische Anwendung der Berechenbarkeitstheorie.

Accepted Answer

Kryptographie

Answer

Medizin

Answer

Soziologie

Answer

Architektur

Question 50

Was ist der zentrale Gegenstand der Berechenbarkeitstheorie?

Accepted Answer

Algorithmische Lösbarkeit und Komplexität von Problemen

Answer

Geschichte und Entwicklung von Computern

Answer

Entwurf und Analyse von Datenstrukturen

Question 51

Welche der folgenden Aufgaben kann nicht algorithmisch gelöst werden?

Accepted Answer

Entscheiden, ob ein beliebiges Programm terminieren wird

Answer

Berechnen des kleinsten gemeinsamen Vielfachen zweier Zahlen

Answer

Ermitteln der minimalen Anzahl von Münzen zum Wechseln eines Geldbetrags

Question 52

Was ist die wesentliche Eigenschaft einer Turing-Maschine?

Accepted Answer

Ein unendliches Band, ein Lese-/Schreibkopf und ein endlicher Satz von Zuständen

Answer

Eine physische Maschine zur Durchführung von Berechnungen

Question 53

Was ist ein charakteristisches Merkmal von NP-vollständigen Problemen?

Accepted Answer

Sie sind mindestens so schwer wie jedes andere NP-Problem

Answer

Sie sind in polynomieller Zeit lösbar

Answer

Sie sind abgeschlossen unter Reduktion

Question 54

Was besagt die Church-Turing-These?

Accepted Answer

Jede berechenbare Funktion kann von einer Turing-Maschine berechnet werden

Answer

Alle Algorithmen terminieren in einer endlichen Anzahl von Schritten

Answer

Jede Turing-Maschine kann eine Funktion berechnen

Question 55

Welche Eigenschaft haben nichtdeterministische Turing-Maschinen?

Accepted Answer

Sie können mehrere Berechnungszweige gleichzeitig erkunden

Answer

Sie sind immer effizienter als deterministische Turing-Maschinen

Answer

Sie haben nur eine endliche Anzahl von Zuständen

Question 56

Welche der folgenden Aussagen über das Halteproblem ist korrekt?

Accepted Answer

Es ist unentscheidbar.

Answer

Es kann in polynomialer Zeit gelöst werden.

Answer

Es ist äquivalent zum SAT-Problem.

Question 57

Welche der folgenden Sprachen gehört nicht zur Klasse RE (rekursiv aufzählbar)?

Accepted Answer

Die Sprache aller Primzahlen

Answer

Die Sprache aller Fibonacci-Zahlen

Answer

Die Sprache aller Quadratzahlen

Answer

Die Sprache aller Palindrome

Question 58

Welcher der folgenden Algorithmen kann nicht in polynomialer Zeit ausgeführt werden?

Accepted Answer

Faktorisierung großer Zahlen

Answer

Sortierung eines Arrays

Answer

Berechnung des größten gemeinsamen Teilers

Answer

Suche nach dem kürzesten Pfad in einem Graphen

Question 59

Welche Eigenschaft ist charakteristisch für eine kontextsensitive Sprache?

Accepted Answer

Sie kann durch eine kontextsensitive Grammatik erzeugt werden.

Answer

Sie ist regulär.

Answer

Sie ist kontextfrei.

Question 60

Welche Aussage über Pushdown-Automaten (PDA) ist nicht korrekt?

Accepted Answer

Sie können keine nicht-kontextsensitiven Sprachen erkennen.

Answer

Sie können deterministisch sein.

Answer

Sie verfügen über einen Stapelspeicher.

Question 61

Welche Aussage über die Berechenbarkeitstheorie ist nicht korrekt?

Accepted Answer

Alle berechenbaren Probleme können in logarithmischer Zeit gelöst werden.

Answer

Die Berechenbarkeitstheorie untersucht die Grundlagen der Berechenbarkeit.

Answer

Die Berechenbarkeitstheorie klassifiziert Probleme nach ihrer Schwierigkeit.

Question 62

Welche der folgenden Aussagen über Turingmaschinen ist falsch?

Accepted Answer

Turingmaschinen können keine Probleme mit unendlicher Eingabe lösen.

Answer

Turingmaschinen sind ein mathematisches Modell für Computer.

Answer

Turingmaschinen können Probleme mit endlicher Eingabe lösen.

Question 63

Welche der folgenden Aussagen über Entscheidbarkeit ist korrekt?

Accepted Answer

Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für alle Eingaben in endlicher Zeit korrekt entscheidet.

Answer

Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für alle Eingaben eine Lösung findet.

Answer

Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für alle Eingaben in polynomialer Zeit entscheidet.

Question 64

Welche der folgenden Aussagen über die Komplexitätsklasse NP ist korrekt?

Accepted Answer

NP ist die Klasse der Probleme, die von einer nichtdeterministischen Turingmaschine in polynomialer Zeit gelöst werden können.

Answer

NP ist die Klasse der Probleme, die von einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden können.

Answer

NP ist die Klasse der Probleme, die von einer Turingmaschine in exponentieller Zeit gelöst werden können.