Theoretische Informatik für Klasse 12: Online-Quizze und Übungen

Question 1

Welcher Automatentyp ist deterministisch und erkennt reguläre Sprachen?

Accepted Answer

Deterministischer endlicher Automat

Answer

Nichtdeterministischer endlicher Automat

Answer

Nichtdeterministischer Pushdown-Automat

Answer

Deterministische Turingmaschine

Question 2

Welches Merkmal ist ein zentrales Charakteristikum von Turingmaschinen?

Accepted Answer

Sie können jedes berechenbare Problem lösen.

Answer

Sie verarbeiten nur deterministische Eingaben.

Answer

Sie benötigen nur begrenzten Speicherplatz.

Answer

Sie können keine rekursiven Funktionen verarbeiten.

Question 3

Welcher Automatentyp ist besonders geeignet, um verschachtelte Strukturen wie Klammerfolgen oder arithmetische Ausdrücke zu erkennen?

Accepted Answer

PDA (Nicht-deterministischer Pushdown-Automat)

Answer

DFA (Deterministischer endlicher Automat)

Answer

Turingmaschine

Answer

Mealy-Automat

Question 4

Welche Aussage über eine deterministische, eindeutige, bandbeschränkte lineare Eingabe-Ausgabe-Turingmaschine ist richtig?

Accepted Answer

Sie erkennt jede reguläre Sprache.

Answer

Sie kann nur eine endliche Anzahl von Zuständen haben.

Answer

Sie kann alle berechenbaren Funktionen berechnen.

Answer

Sie kann jede Sprache erkennen.

Question 5

Welche Eigenschaft trifft auf nichtdeterministische Turingmaschinen (NDTMs) zu?

Accepted Answer

Sie können Probleme lösen, die für deterministische Turingmaschinen unlösbar sind.

Answer

Sie können immer in deterministische Turingmaschinen umgewandelt werden.

Answer

Sie benötigen für eine bestimmte Eingabe weniger Bandspeicher als deterministische Turingmaschinen.

Answer

Sie sind für praktische Anwendungen gut geeignet.

Question 6

Welche Eigenschaft ist entscheidend für die Berechnungsfähigkeit einer Turing-Maschine?

Accepted Answer

Unbegrenzter Speicher

Answer

Begrenzte Zustände

Answer

Deterministische Arbeitsweise

Answer

Unfähigkeit, auf ein leeres Band zu schreiben

Question 7

Welche Eigenschaft ist grundlegend für endliche Automaten (EA)?

Accepted Answer

EA bestimmen den nächsten Zustand mithilfe einer Übergangsfunktion.

Answer

EA können unendlich viele Zustände haben.

Answer

EA können beliebig lange Eingaben verarbeiten.

Answer

EA können rekursiv definiert werden.

Question 8

Welche der folgenden Eigenschaften trifft auf endliche Automaten zu?

Accepted Answer

Sie haben eine begrenzte Anzahl von Zuständen.

Accepted Answer

Sie erkennen nur reguläre Sprachen.

Answer

Sie sind immer deterministisch.

Answer

Sie können auch nicht-reguläre Sprachen erkennen.

Question 9

Welche Aussage über das Verhältnis zwischen kontextfreien und regulären Sprachen ist korrekt?

Accepted Answer

Reguläre Sprachen sind eine Teilmenge der kontextfreien Sprachen.

Answer

Kontextfreie Sprachen sind eine Teilmenge der regulären Sprachen.

Answer

Reguläre und kontextfreie Sprachen sind disjunkt.

Answer

Reguläre und kontextfreie Sprachen sind identisch.

Question 10

Welche der folgenden Aussagen trifft auf die Beziehung zwischen endlichen Automaten (EA) und regulären Sprachen zu?

Accepted Answer

Alle von endlichen Automaten erkannten Sprachen sind reguläre Sprachen.

Accepted Answer

Alle regulären Sprachen können von endlichen Automaten erkannt werden.

Answer

Endliche Automaten können nur Sprachen mit einer begrenzten Anzahl von Zuständen erkennen.

Answer

Reguläre Sprachen sind immer kontextfrei.

Question 11

Welche Eigenschaften treffen auf die Prädikatenlogik zu?

Accepted Answer

Verwendung von Variablen zur Beschreibung von Objekten

Accepted Answer

Ermöglichung von Aussagen über Beziehungen zwischen Objekten

Accepted Answer

Ableitung von Schlussfolgerungen aus gegebenen Annahmen

Answer

Formale Sprache zur Softwarebeschreibung

Question 12

Welche Datenstruktur ermöglicht es, das kleinste Element mit den wenigsten Vergleichen zu finden?

Accepted Answer

Binärheap

Answer

Verkettete Liste

Answer

Binärbaum

Answer

Hashtabelle

Question 13

Welche Eigenschaft trifft auf endliche Automaten zu?

Accepted Answer

Ihre Anzahl an Zuständen ist begrenzt.

Answer

Sie können alle Funktionen berechnen.

Answer

Sie verarbeiten nur Eingaben begrenzter Länge.

Answer

Sie erkennen Fehler in Eingaben.

Question 14

Welche Aussage beschreibt die universelle Eigenschaft von Turingmaschinen?

Accepted Answer

Sie können jedes Problem lösen, für das ein Algorithmus existiert.

Answer

Sie können nur Probleme lösen, die in endlicher Zeit lösbar sind.

Answer

Sie können nur Probleme lösen, die in endlicher Zeit lösbar sind und für die ein Algorithmus existiert.

Answer

Sie können jedes Problem lösen, das in endlicher Zeit lösbar ist.

Question 15

Welche Datenstruktur eignet sich am besten, um bei der Tiefensuche eines Graphen die besuchten Knoten zu verfolgen?

Accepted Answer

Stapel

Answer

Warteschlange

Answer

Verkettete Liste

Question 16

Welche Datenstruktur folgt dem Prinzip 'Last-in-First-out' (LIFO)?

Accepted Answer

Stapel

Answer

Hashtabelle

Answer

Warteschlange

Answer

Baum

Question 17

Welche Aussage über die Turingmaschine ist korrekt?

Accepted Answer

Sie ist ein universelles Rechenmodell, das alle berechenbaren Funktionen berechnen kann.

Answer

Sie kann nur endlich viele Zustände haben.

Answer

Sie kann nur endlich viele Symbole auf dem Band haben.

Answer

Sie kann nur endlich viele Übergänge haben.

Question 18

Welche Aussage zur Analyse der Laufzeit von Algorithmen ist korrekt?

Accepted Answer

Die Laufzeit ergibt sich aus der Summe der Laufzeiten der Teilaufgaben.

Answer

Die Laufzeit ist immer unabhängig von der Eingabegröße.

Answer

Die Laufzeit wächst immer linear.

Answer

Die Laufzeit ist unabhängig von der Programmiersprache.

Question 19

Welches Merkmal unterscheidet Deduktionssysteme der Prädikatenlogik von denen der Aussagenlogik?

Accepted Answer

Zusätzliche Regeln für Objekte und Beziehungen

Answer

Beschränkung auf gültige Schlussfolgerungen

Answer

Vereinfachte Anwendung ohne Quantoren

Question 20

Welche Aussage beschreibt die Chomsky-Hierarchie treffend?

Accepted Answer

Eine hierarchische Einteilung formaler Sprachen nach der Komplexität ihrer erzeugenden Grammatiken.

Answer

Eine vollständige Auflistung aller Programmiersprachen, geordnet nach ihrer Beliebtheit.

Answer

Eine Sammlung von Regeln zur Bestimmung gültiger Zeichenfolgen in einer formalen Sprache.

Question 21

Welche der folgenden Aussagen beschreibt die Komplexitätsklassen P und NP korrekt?

Accepted Answer

P enthält alle Probleme, die in polynomialer Zeit gelöst werden können.

Accepted Answer

NP enthält alle Probleme, die von einer nicht-deterministischen Turingmaschine in polynomialer Zeit gelöst werden können.

Answer

P und NP sind gleich.

Answer

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

Question 22

Welche der folgenden Sprachen kann von keiner Turingmaschine entschieden werden?

Accepted Answer

Die Sprache aller Konfigurationen von Turingmaschinen, die anhalten

Answer

Die Sprache aller Palindrome mit den Zeichen 0 und 1

Answer

Die Sprache aller Primzahlen

Answer

Die Sprache aller endlichen Teilmengen der natürlichen Zahlen

Question 23

Welches Merkmal trifft am ehesten auf ein unentscheidbares Problem zu?

Accepted Answer

Es gibt keinen Algorithmus, der garantiert eine korrekte Lösung liefert.

Answer

Es kann von einem Algorithmus in endlicher Zeit gelöst werden.

Answer

Eine Turingmaschine liefert immer eine eindeutige Antwort.

Answer

Die Lösung hängt von den Eingabedaten ab.

Question 24

Welche Eigenschaft trifft **nicht** auf reguläre Sprachen in der Chomsky-Hierarchie zu?

Accepted Answer

Erzeugbar durch kontextfreie Grammatiken

Answer

Erkennbar durch endliche Automaten

Answer

Beschreibbar durch reguläre Ausdrücke

Question 25

Welche Eigenschaft zeichnet Turingmaschinen aus?

Accepted Answer

Sie können alle berechenbaren Funktionen berechnen.

Answer

Sie sind ausschließlich deterministisch.

Answer

Ihr Bandkopf kann sich nur in eine Richtung bewegen.

Answer

Sie verfügen über eine begrenzte Anzahl von Bandzellen.

Question 26

Welche Aussage beschreibt korrekt die Beziehung zwischen den Komplexitätsklassen P und NP?

Accepted Answer

Alle Probleme in P sind auch in NP enthalten.

Answer

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

Answer

NP-Probleme sind immer leichter zu lösen als P-Probleme.

Question 27

Welche der folgenden Sprachen ist **keine** reguläre Sprache?

Accepted Answer

Eine Sprache, die Schleifen oder Funktionen enthält

Answer

Eine Sprache, die durch einen endlichen Automaten erkannt werden kann

Answer

Eine Sprache, die alle Zeichenfolgen über einem endlichen Alphabet umfasst

Answer

Eine Sprache, die durch eine reguläre Grammatik definiert ist

Question 28

Was beschreibt die Chomsky-Hierarchie?

Accepted Answer

Eine Klassifizierung formaler Sprachen nach der Verschachtelungsebene ihrer Grammatiken

Answer

Eine Hierarchie von Automaten zur Erkennung formaler Sprachen

Answer

Eine Sammlung unlösbarer Probleme in der Informatik

Answer

Eine Methode zur Messung der Algorithmuskomplexität

Question 29

Welche der folgenden Sprachen ist **nicht** regulär? Begründe deine Antwort.

Accepted Answer

a^n b^n, wobei n ≥ 1

Answer

((a + b)*)*

Question 30

Wie lässt sich die Struktur eines Graphen am besten beschreiben?

Accepted Answer

Eine Menge von Punkten (Knoten), die paarweise durch Linien (Kanten) verbunden sind.

Answer

Ein Baum aus verbundenen Punkten ohne Schleifen.

Answer

Die Anzahl der Linien in einem Graphen ist immer kleiner oder gleich der Anzahl der Punkte.

Question 31

Welche der folgenden Aussagen beschreibt die Rolle regulärer Ausdrücke in der Informatik am besten?

Accepted Answer

Reguläre Ausdrücke sind formale Sprachen zur Beschreibung und Verarbeitung von Textdaten.

Answer

Reguläre Ausdrücke sind ein Datentyp zur Speicherung von Textzeichenfolgen.

Answer

Reguläre Ausdrücke sind ein Algorithmus zur Datenkomprimierung.

Question 32

Welche Eigenschaft schränkt die Erkennungsfähigkeit endlicher Automaten ein?

Accepted Answer

Sie können nur reguläre Sprachen erkennen.

Answer

Sie können jede Sprache erkennen.

Answer

Sie können nur Strings mit einer bestimmten Länge erkennen.

Answer

Sie können alle nichtregulären Sprachen erkennen.

Question 33

Frage: Nenne die Stärken und Grenzen regulärer Ausdrücke in der Informatik.

Accepted Answer

Stärken:
* Einfache Definition komplexer Muster
* Effiziente Ausführung für einfache Ausdrücke
* Vielseitig einsetzbar

Grenzen:
* Beschränkt auf reguläre Sprachen
* Kann ressourcenintensiv sein

Answer

Reguläre Ausdrücke können jede beliebige Sprache beschreiben.

Answer

Reguläre Ausdrücke werden nur zur Suche und zum Ersetzen von Zeichenfolgen verwendet.

Question 34

Erläutere die Bedeutung der Turing-Maschine als universelles Rechenmodell. Wie prägt sie unser Verständnis von Berechenbarkeit?

Accepted Answer

Die Turing-Maschine kann jede berechenbare Funktion berechnen, was sie universell macht.

Answer

Die Turing-Maschine ist begrenzt, da sie nur eine begrenzte Anzahl von Symbolen speichern kann.

Answer

Die Turing-Maschine ist deterministisch, da sie für jede Eingabe immer die gleiche Berechnung durchführt.

Answer

Die Turing-Maschine ist parallel, da sie mehrere Operationen gleichzeitig ausführen kann.

Question 35

Welche der folgenden Aussagen beschreibt das Potenzial der Quanteninformatik am besten?

Accepted Answer

Quantencomputer können alle Probleme lösen, die klassische Computer nicht lösen können.

Answer

Option 1: Die Quanteninformatik hat in letzter Zeit kaum Fortschritte gemacht.

Question 36

Welche Stärke der Church-Turing-These wird in der folgenden Aussage beschrieben: "Sie definiert Berechenbarkeit präzise"?

Accepted Answer

Präzise Definition von Berechenbarkeit

Answer

Universell anwendbar

Answer

Leicht verständlich

Answer

Historisch bedeutend

Question 37

Welcher der folgenden Automatentypen kann eine Sprache genau dann akzeptieren, wenn sie regulär ist?

Accepted Answer

Deterministischer endlicher Automat (DFA)

Answer

Nichtdeterministischer endlicher Automat (NFA)

Answer

Nichtdeterministischer Stapelautomat (PDA)

Answer

Turing-Maschine

Question 38

Welche Aussage über das Halteproblem ist korrekt?

Accepted Answer

Es gibt einen Algorithmus, der für jede Turing-Maschine und jedes Eingabewort bestimmt, ob die Turing-Maschine mit der Eingabe anhält.

Answer

Das Halteproblem ist nur für nichtdeterministische Turing-Maschinen unlösbar.

Answer

Das Halteproblem ist nur für deterministische Turing-Maschinen lösbar.

Answer

Das Halteproblem ist für alle Turing-Maschinen lösbar.

Question 39

Welche der folgenden Komplexitätsklassen enthält alle Probleme, die von einer deterministischen Turing-Maschine in polynomialer Zeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 40

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

Accepted Answer

NP enthält alle Probleme, die in nichtdeterministischer polynomialer Zeit gelöst werden können.

Answer

NP enthält alle Probleme, die in deterministischer polynomialer Zeit gelöst werden können.

Answer

NP enthält alle Probleme, die in exponentieller Zeit gelöst werden können.

Answer

NP enthält alle Probleme, die in konstanter Zeit gelöst werden können.

Question 41

Welche der folgenden Sprachen ist eine reguläre Sprache?

Accepted Answer

Die Menge aller Wörter über dem Alphabet {a, b} mit gleicher Anzahl an a und b

Answer

Die Menge aller Wörter über dem Alphabet {a, b} mit ungleicher Anzahl an a und b

Answer

Die Menge aller Wörter über dem Alphabet {a, b, c} mit ungleicher Anzahl an a, b und c

Answer

Die Menge aller Wörter über dem Alphabet {a, b, c} mit mindestens einem Vorkommen von a, b und c

Question 42

Welches Komplexitätsmaß gibt die Laufzeit eines Algorithmus als Funktion der Eingabelänge an?

Accepted Answer

Zeitkomplexität

Answer

Raumkomplexität

Answer

Komplexität

Answer

Speicherkomplexität

Question 43

Welche der folgenden Sprachen ist **nicht** rekursiv aufzählbar?

Accepted Answer

Die Sprache aller Primzahlen

Answer

Die Sprache aller Palindrome

Answer

Die Sprache aller Quadratzahlen

Answer

Die Sprache aller Fibonacci-Zahlen

Question 44

Welche Aussage über das Halteproblem ist korrekt?

Accepted Answer

Das Halteproblem ist unentscheidbar.

Answer

Das Halteproblem ist entscheidbar.

Answer

Das Halteproblem ist semientcheidbar.

Answer

Das Halteproblem ist ein NP-vollständiges Problem.

Question 45

Inwiefern ist Logik für die Theoretische Informatik von Bedeutung? Erläutern Sie, wie Logik zur Entwicklung formaler Modelle und zum Beweisen von Aussagen in diesem Bereich eingesetzt wird.

Accepted Answer

Logik dient dazu, formale Modelle von Berechnungsprozessen zu erstellen und deren Eigenschaften zu beweisen.

Answer

Logik wird verwendet, um Algorithmen zu entwerfen und zu optimieren.

Answer

Logik hat keine direkte Anwendung in der Theoretischen Informatik.

Question 46

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

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 47

Welche Aussage über das P-NP-Problem ist korrekt?

Accepted Answer

Es ist ein ungelöstes Problem in der Informatik.

Answer

Es ist bewiesen, dass P = NP.

Answer

Es ist bewiesen, dass P ≠ NP.

Answer

Es ist bekannt, dass P ⊃ NP.

Question 48

Welche der folgenden Techniken wird zur Analyse der Komplexität von Algorithmen verwendet?

Accepted Answer

Asymptotische Analyse

Answer

Experimentelle Analyse

Answer

Heuristische Analyse

Answer

Statistische Analyse

Question 49

Welche Aussage über formale Sprachen ist korrekt?

Accepted Answer

Eine formale Sprache ist eine Menge von Zeichenfolgen über einem Alphabet.

Answer

Alle natürlichen Sprachen sind formale Sprachen.

Answer

Formale Sprachen können nur verwendet werden, um Computerprogramme zu beschreiben.

Answer

Formale Sprachen haben keine theoretische Bedeutung.

Question 50

Welche Aussage über kontextfreie Grammatiken ist korrekt?

Accepted Answer

Kontextfreie Grammatiken können alle regulären Sprachen erzeugen.

Answer

Kontextfreie Grammatiken können alle Sprachen erzeugen.

Answer

Kontextfreie Grammatiken haben eine begrenzte Anzahl an Regeln.

Answer

Kontextfreie Grammatiken sind immer nichtdeterministisch.

Question 51

Welche Aussage beschreibt das Halteproblem am zutreffendsten?

Accepted Answer

Es gibt keinen Algorithmus, der für jedes Programm bestimmen kann, ob es terminiert.

Answer

Jedes Programm terminiert innerhalb einer endlichen Zeitspanne.

Answer

Für jedes Programm kann ein Algorithmus die genaue Laufzeit vorhersagen.

Question 52

Welches Komplexitätsmaß gibt die worst-case Zeitkomplexität eines Algorithmus an?

Accepted Answer

O-Notation

Answer

Sigma-Notation

Answer

Omega-Notation

Answer

Theta-Notation

Question 53

Welche Aussage beschreibt das Pumping-Lemma für reguläre Sprachen korrekt?

Accepted Answer

Jede genügend lange Zeichenkette in einer regulären Sprache kann in kleinere Abschnitte zerlegt werden, sodass der mittlere Abschnitt beliebig oft wiederholt werden kann, ohne dass die Zugehörigkeit zur Sprache verloren geht.

Answer

Jede reguläre Sprache kann durch einen endlichen Automaten beschrieben werden.

Question 54

Welcher Automatentyp ist ein Spezialfall eines Pushdown-Automaten?

Accepted Answer

Endlicher Automat

Answer

Kontextfreie Grammatik

Answer

Turing-Maschine

Answer

Nichtdeterministischer Automat

Question 55

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Sortierproblem

Answer

Dijkstra-Algorithmus

Answer

Primzahltest

Question 56

Was ist das Ziel einer Reduktion in der Komplexitätstheorie?

Accepted Answer

Probleme in Beziehung zu setzen, um die Komplexität eines Problems auf die eines anderen Problems zurückzuführen.

Answer

Algorithmen zu optimieren.

Question 57

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

Accepted Answer

P

Answer

NP

Answer

EXP

Question 58

Mit welchem Argument wird die Unentscheidbarkeit des Halteproblems bewiesen?

Accepted Answer

Diagonalisierungsargument

Answer

Gödelscher Unvollständigkeitssatz

Answer

Turingmaschine

Question 59

Welche der folgenden Aussagen über Turingmaschinen ist korrekt?

Accepted Answer

Eine Turingmaschine kann alle berechenbaren Funktionen berechnen.

Answer

Eine Turingmaschine benötigt unendlich viel Band.

Answer

Eine Turingmaschine ist ein deterministischer Automat.

Question 60

Welche Aussage zur Halteproblematik ist zutreffend?

Accepted Answer

Für jedes Programm kann kein Programm geschrieben werden, das feststellt, ob das erste Programm für alle Eingaben anhält.

Answer

Das Halteproblem ist für deterministische Programme lösbar.

Question 61

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

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Question 62

Welche Aussage über reguläre Sprachen ist korrekt?

Accepted Answer

Sie lassen sich durch reguläre Ausdrücke beschreiben.

Answer

Endliche Automaten können sie nicht erkennen.

Answer

Sie sind immer auch kontextfrei.

Question 63

Welche der folgenden Sprachen ist kontextfrei?

Accepted Answer

{a^n b^n | n >= 0}

Answer

{a^n | n ist ungerade}

Answer

{a^n | n ist eine Primzahl}

Answer

{a^n b^m | m > n}

Question 64

Welche Aussage zur Church-Turing-These ist zutreffend?

Accepted Answer

Sie besagt, dass alle berechenbaren Probleme von einer Turingmaschine gelöst werden können.

Answer

Sie besagt, dass alle Turingmaschinen äquivalent sind.

Answer

Sie besagt, dass alle algorithmischen Probleme von einer Turingmaschine gelöst werden können.