Theoretische Informatik lernen: Quizfragen und Übungen für Klasse 13

Question 1

Vergleicht deterministische endliche Automaten (DFA) und nichtdeterministische endliche Automaten (NFA). Erläutert ihre Funktionsweise, Akzeptanzfähigkeit und die wichtigsten Unterschiede.

Accepted Answer

DFA:

- Lesen von links nach rechts
- Immer in einem Zustand

NFA:

- Beliebige Leserichtung
- Kann in mehreren Zuständen sein

Unterschiede:

- Akzeptanz: DFA: reguläre Sprachen, NFA: auch nichtreguläre
- Konstruktion: DFA: einfacher
- Effizienz: NFA: ggf. mehr Zustände für gleiche Sprache

Answer

Falsch: DFAs akzeptieren nicht alle Sprachen.

Answer

Falsch: Es gibt Unterschiede in der Funktionsweise.

Answer

Falsch: NFAs sind nicht immer effizienter.

Question 2

Welche Bedeutung haben formale Sprachen in der Informatik? Nenne ihre Vorteile und Grenzen bei der Darstellung und Verarbeitung von Informationen.

Accepted Answer

Formale Sprachen ermöglichen eine klare und eindeutige Darstellung von Informationen, was die Verarbeitung durch Computer erleichtert.

Accepted Answer

Formale Sprachen sind nicht geeignet, um natürliche Sprache und menschliche Kommunikation darzustellen.

Answer

Formale Sprachen sind nur für die theoretische Analyse von Algorithmen nützlich.

Answer

Formale Sprachen können alle Arten von Informationen darstellen, unabhängig von ihrer Komplexität.

Question 3

Erläutern Sie, wie Turingmaschinen die Berechenbarkeit von Problemen definieren. Begründen Sie, warum eine Turingmaschine jedes berechenbare Problem lösen kann.

Accepted Answer

Turingmaschinen sind abstrakte Rechenmodelle, die jedes Problem lösen können, für das ein Algorithmus existiert.

Answer

Turingmaschinen sind auf Probleme beschränkt, die in einer bestimmten Programmiersprache formuliert sind.

Answer

Die Berechenbarkeit eines Problems hängt von der Anzahl der verwendeten Turingmaschinen ab.

Answer

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

Question 4

Welche Strategie ist **ungeeignet** zur Beweissteigerung formaler Sprachen?

Accepted Answer

Analogie

Answer

Induktion

Answer

Widerspruch

Question 5

Was versteht man in der Theoretischen Informatik unter Berechenbarkeit und welche Bedeutung hat sie für die Entwicklung und Analyse von Algorithmen?

Accepted Answer

Berechenbarkeit bedeutet, dass ein Problem durch einen Algorithmus in endlich vielen Schritten gelöst werden kann.

Answer

Berechenbarkeit garantiert, dass ein Algorithmus immer das beste Ergebnis liefert.

Answer

Berechenbarkeit misst die Effizienz eines Algorithmus.

Answer

Berechenbarkeit ist nur für theoretische Probleme relevant.

Question 6

Wie tragen formale Sprachen zum Verständnis und zur Verarbeitung menschlicher Sprache in Bereichen wie künstliche Intelligenz und Verarbeitung natürlicher Sprache bei?

Accepted Answer

Formale Sprachen sind Regelwerke, die Computern die Analyse und Generierung von Struktur und Bedeutung menschlicher Sprache ermöglichen.

Answer

Formale Sprachen haben keine praktische Anwendung außerhalb der theoretischen Informatik.

Answer

Formale Sprachen sind nur für die Entwicklung von Compilern und Interpretern relevant.

Answer

Formale Sprachen sind ausschließlich für linguistische Analysen relevant und haben keine Bedeutung für die Informatik.

Question 7

Wie werden formale Sprachen in der Datenbanktheorie eingesetzt? Erläutern Sie insbesondere die praktische Anwendung regulärer Ausdrücke in Abfragesprachen wie SQL.

Accepted Answer

Reguläre Ausdrücke in SQL ermöglichen die effiziente Suche und Bearbeitung von Textmustern und vereinfachen so die Datenabfrage.

Answer

Formale Sprachen dienen nur der theoretischen Untersuchung und haben keine praktische Bedeutung für Datenbanken.

Answer

Formale Sprachen werden in Datenbanken nur zur Modellierung von Datenstrukturen verwendet, ohne Auswirkungen auf die Abfrageleistung.

Answer

Der Einsatz formaler Sprachen in Datenbanken beschränkt sich auf reguläre Ausdrücke.

Question 8

Welche Eigenschaft unterscheidet **endliche Automaten** von unendlichen Automaten?

Accepted Answer

Endliche Automaten haben eine begrenzte Anzahl von Zuständen und Übergängen.

Answer

Endliche Automaten können unendlich viele Zustände haben.

Answer

Endliche Automaten können unendlich viele Eingaben verarbeiten.

Question 9

Welche dieser Aussagen über formale Sprachen ist korrekt?

Accepted Answer

Formale Sprachen werden durch eine Grammatik definiert.

Answer

Formale Sprachen sind begrenzte Mengen von Wörtern.

Answer

Formale Sprachen können sowohl Wörter als auch Sätze beinhalten.

Answer

Formale Sprachen sind immer kontextsensitiv.

Question 10

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

Accepted Answer

Jedes berechenbare Problem kann von einer Turingmaschine gelöst werden.

Answer

Es gibt Probleme, die von keiner Turingmaschine gelöst werden können.

Answer

Die Church-Turing-These besagt, dass das menschliche Gehirn ein universeller Computer ist.

Answer

Die Church-Turing-These ist eine unbewiesene Hypothese.

Question 11

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Bestimmung, ob ein Graph einen Hamilton-Zyklus besitzt

Answer

Sortierung einer Liste von Zahlen

Answer

Suche nach dem kürzesten Pfad in einem Graphen

Answer

Berechnung der kleinsten gemeinsamen Vielfachen von zwei Zahlen

Question 12

Welche der folgenden Grammatiken ist eine kontextsensitive Grammatik?

Accepted Answer

{ -> , -> | a, -> | b, -> | ε}

Answer

{ ~~-> a ~~b, ~~-> ε}~~~~~~

Answer

{<S> -> S S | a}

Answer

{ ~~-> a ~~b | ~~a }~~~~~~

Question 13

Welche Aussage über Berechenbarkeit ist korrekt?

Accepted Answer

Es existieren Probleme, die nicht berechenbar sind.

Answer

Alle Probleme sind berechenbar.

Answer

Das Halteproblem ist berechenbar.

Answer

Die Berechnung eines Problems benötigt immer endlich viele Schritte.

Question 14

Welche der folgenden Maschinen ist die mächtigste?

Accepted Answer

Turingmaschine

Answer

Nichtdeterministischer Pushdown-Automat

Answer

Deterministischer endlicher Automat

Answer

Kellerautomat

Question 15

Welcher der folgenden Algorithmen verwendet Backtracking?

Accepted Answer

Depth-First-Search

Answer

Dijkstra-Algorithmus

Answer

Primscher Algorithmus

Answer

Kruskalscher Algorithmus

Question 16

Wie hängen Turingmaschinen mit der Entscheidbarkeit von Problemen zusammen?

Accepted Answer

Turingmaschinen können alle berechenbaren Probleme lösen und sind damit ein Modell für Entscheidbarkeit.

Answer

Turingmaschinen können nur Probleme lösen, die in endlich vielen Schritten lösbar sind.

Answer

Die Entscheidbarkeit eines Problems ist unabhängig vom verwendeten Berechnungsmodell.

Question 17

Welche Technik zur Analyse der Zeitkomplexität von Algorithmen erleichtert die Analyse rekursiver Algorithmen?

Accepted Answer

Master-Theorem

Answer

Amortisierte Analyse

Answer

Experimentelle Analyse

Answer

Erschöpfende Auflistung aller möglichen Eingaben

Question 18

Welche der folgenden Aussagen beschreibt korrekt die Einsatzmöglichkeiten endlicher Automaten?

Accepted Answer

Endliche Automaten können verwendet werden, um zu überprüfen, ob eine Zeichenkette zu einer regulären Sprache gehört.

Answer

Endliche Automaten können jede beliebige Sprache akzeptieren.

Answer

Die Anzahl der Zustände eines endlichen Automaten ist immer geringer als die Anzahl der Zeichen im Eingabealphabet.

Question 19

Was ist das grundlegende Prinzip einer rekursiven Funktionsdefinition?

Accepted Answer

Eine rekursive Funktion ruft sich selbst auf.

Answer

Rekursive Funktionen haben eine begrenzte Anzahl von Aufrufen.

Answer

Die erste Anweisung einer rekursiven Funktion ist die Basisbedingung.

Answer

Rekursive Funktionen sind immer schneller als iterative Funktionen.

Question 20

Welche Aussage über formale Sprachen ist korrekt?

Accepted Answer

Formale Sprachen sind Mengen von Wörtern über einem Alphabet.

Answer

Formale Sprachen sind Mengen geordneter Paare.

Answer

Formale Sprachen sind immer endlich.

Answer

Formale Sprachen sind immer deterministisch.

Question 21

Was ist das Halteproblem?

Accepted Answer

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

Answer

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

Answer

Das Problem, zu bestimmen, ob ein bestimmtes Programm frei von Fehlern ist.

Answer

Das Problem, zu bestimmen, ob ein bestimmtes Programm effizient ist.

Question 22

Welche Aussage über Turingmaschinen ist korrekt?

Accepted Answer

Turingmaschinen können jede berechenbare Funktion berechnen.

Answer

Turingmaschinen sind äquivalent zu PDAs.

Answer

Turingmaschinen sind immer deterministisch.

Answer

Turingmaschinen haben eine unendliche Anzahl von Zuständen.

Question 23

Was ist die Chomsky-Normalform?

Accepted Answer

Eine kanonische Darstellung kontextfreier Grammatiken.

Answer

Eine kanonische Darstellung regulärer Ausdrücke.

Answer

Eine Methode zur Umwandlung von NFAs in DFAs.

Answer

Eine Methode zur Minimierung von endlichen Automaten.

Question 24

Welche Aussage über Komplexitätstheorie ist korrekt?

Accepted Answer

Komplexitätstheorie untersucht die Ressourcenbeschränkungen von Algorithmen.

Answer

Die Komplexitätsklassen P und NP sind gleich.

Answer

NP-vollständige Probleme lassen sich in logarithmischer Zeit lösen.

Answer

Alle Probleme in der Klasse P sind auch in der Klasse NP enthalten.

Question 25

Was ist ein endlicher Automat?

Accepted Answer

Ein mathematisches Modell, das die Entscheidbarkeit einer Sprache beschreibt.

Answer

Ein Algorithmus, der eine bestimmte Aufgabe in einer unendlichen Anzahl von Schritten löst.

Answer

Eine Datenstruktur, die zur Speicherung von Daten in einer linearen Struktur verwendet wird.

Answer

Ein Computerprogramm, das eine bestimmte Aufgabe ausführt.

Question 26

Welches der folgenden Modelle ist ein endlicher Automat?

Accepted Answer

Zustandsautomat

Answer

Petrinetz

Answer

Entscheidungsbaum

Question 27

Welche Sprache wird durch den regulären Ausdruck (01)* beschrieben?

Accepted Answer

Menge aller Folgen, die aus beliebig vielen sich abwechselnden 0en und 1en bestehen

Answer

Menge aller Folgen, die mit 0 beginnen

Answer

Menge aller Folgen, die gerade Länge haben

Question 28

Welches Problem ist Turing-vollständig?

Accepted Answer

Halteproblem

Answer

Sortierproblem

Answer

Primzahltest

Answer

Rucksackproblem

Question 29

Welche der folgenden Aussagen ist über formale Sprachen richtig?

Accepted Answer

Sie sind abstrakte Systeme, die die Syntax von Sprachen beschreiben

Answer

Sie haben keine praktische Bedeutung in der Informatik

Answer

Sie werden in der Regel in natürlicher Sprache ausgedrückt

Question 30

Welcher Automatentyp akzeptiert Sprachen, die durch kontextfreie Grammatiken beschrieben werden können?

Accepted Answer

Kellerautomat

Answer

Turingmaschine

Answer

Deterministischer endlicher Automat

Answer

Nichtdeterministischer endlicher Automat

Question 31

Welche der folgenden Aussagen ist über Turingmaschinen richtig?

Accepted Answer

Sie sind universelle Rechenmodelle, die jedes berechenbare Problem lösen können

Answer

Sie sind nur für die Verarbeitung von Zahlenfolgen geeignet

Answer

Sie sind nicht in der Lage, rekursive Funktionen zu berechnen

Question 32

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Primzahltest

Answer

Sortierproblem

Question 33

Welche der folgenden Aussagen ist über die Chomsky-Hierarchie richtig?

Accepted Answer

Sie definiert eine Hierarchie von Sprachklassen nach ihrer Grammatik

Answer

Sie ist nur für natürliche Sprachen relevant

Answer

Sie wurde von Alan Turing entwickelt

Question 34

Welche der folgenden Aussagen ist über die Komplexitätstheorie richtig?

Accepted Answer

Sie untersucht die Ressourcen, die für die Lösung von Problemen benötigt werden

Answer

Sie wurde von Charles Babbage entwickelt

Answer

Sie ist nur für die theoretische Informatik relevant

Question 35

Welcher Automatentyp erkennt genau die regulären Sprachen?

Accepted Answer

Deterministischer endlicher Automat (DFA)

Answer

Nichtdeterministischer endlicher Automat (NFA)

Answer

Pushdown-Automat (PDA)

Answer

Turing-Maschine (TM)

Question 36

Welche Aussage über Turing-Maschinen ist korrekt?

Accepted Answer

Turing-Maschinen sind universell berechenbar.

Answer

Turing-Maschinen sind immer deterministisch.

Answer

Turing-Maschinen sind nichtdeterministisch.

Answer

Turing-Maschinen können nur endliche Eingaben verarbeiten.

Question 37

Welcher Automatentyp kann alle und nur die kontextfreien Sprachen erkennen?

Accepted Answer

Nichtdeterministischer Pushdown-Automat (NPDA)

Answer

Turing-Maschine (TM)

Answer

Deterministischer Pushdown-Automat (DPDA)

Answer

Deterministischer endlicher Automat (DFA)

Question 38

Welche Sprache ist nicht rekursiv aufzählbar?

Accepted Answer

Die Menge aller Terme, die mindestens eine freie Variable aufweisen.

Answer

Die Menge aller Primzahlen.

Answer

Die Menge aller Binärzahlen.

Question 39

Welche Schreibweise definiert die Menge aller Wörter über {a, b} der Länge 3?

Accepted Answer

{a, b}^{3}

Answer

{a, b}+

Answer

{a, b}?

Answer

{a, b}*

Question 40

Welcher Satz besagt, dass es kein Algorithmus gibt, der bestimmen kann, ob eine Turingmaschine bei einer gegebenen Eingabe anhält?

Accepted Answer

Das Halteproblem

Answer

Das Äquivalenzproblem für reguläre Ausdrücke

Answer

Das Erreichbarkeitsproblem für Petrinetze

Answer

Das Erfüllbarkeitsproblem für boolesche Formeln

Question 41

Was ist der Hauptunterschied zwischen einer regulären Sprache und einer kontextfreien Sprache?

Accepted Answer

Eine reguläre Sprache kann durch einen endlichen Automaten akzeptiert werden, während eine kontextfreie Sprache durch einen Pushdown-Automaten akzeptiert werden kann.

Answer

Eine reguläre Sprache verwendet nur einfache Operationen wie Konjunktion und Disjunktion, während eine kontextfreie Sprache Rekursion verwenden kann.

Question 42

Welche der folgenden Eigenschaften trifft auf berechenbare Probleme zu?

Accepted Answer

Sie können von einer Turingmaschine in einer endlichen Anzahl von Schritten gelöst werden.

Answer

Sie sind immer in polynomialer Zeit lösbar.

Answer

Sie sind immer lösbar durch menschliche Intelligenz.

Question 43

Was ist das vorrangige Ziel der Theoretischen Informatik?

Accepted Answer

Die Untersuchung grundlegender theoretischer Konzepte, die die Informatik prägen.

Answer

Die Entwicklung praktischer Anwendungen für die Informatik.

Answer

Die Bereitstellung historischer Einblicke in die Entwicklung der Informatik.

Question 44

Welches Anwendungsgebiet ist ein Beispiel für die praktische Anwendung theoretischer Informatik-Konzepte?

Accepted Answer

Fehlerkorrektur und Datenkomprimierung

Answer

Webdesign

Answer

Datenbankverwaltungssysteme

Question 45

Wer gilt allgemein als der Vater der Theoretischen Informatik?

Accepted Answer

Alan Turing

Answer

Claude Shannon

Answer

John von Neumann

Answer

Richard Feynman

Question 46

Welche der folgenden Aussagen über reguläre Ausdrücke beschreibt deren Wesensmerkmal treffend?

Accepted Answer

Sie definieren eine formale Sprache zum Beschreiben von Zeichenfolgen.

Answer

Sie bilden eine Programmiersprache zur Steuerung von Computern.

Answer

Sie repräsentieren einen Datentyp zur Speicherung von Text.

Question 47

Welche Aussage über die Turingmaschine ist zutreffend?

Accepted Answer

Sie verkörpert ein universelles Berechnungsmodell.

Answer

Sie stellt ein besonders effizientes Berechnungsmodell dar.

Answer

Ihre Eingabe muss zwingend endlich sein.

Answer

Ihr Verhalten ist deterministisch.

Question 48

Welche der folgenden Aussagen gibt die Church-Turing-These korrekt wieder?

Accepted Answer

Jede berechenbare Funktion lässt sich von einer Turingmaschine berechnen.

Answer

Jede Turingmaschine berechnet eine berechenbare Funktion.

Answer

Die Turingmaschine ist das einzig mögliche Berechnungsmodell.

Question 49

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

Accepted Answer

P

Answer

NP

Answer

NEXPTIME

Answer

EXP

Question 50

Welche Datenstruktur zeichnet sich durch effiziente Suche und Einfügung von Elementen aus?

Accepted Answer

Hashtabelle

Answer

Binärbaum

Answer

Array

Answer

Verkettete Liste

Question 51

Welche Programmiersprache ist ihrem Wesen nach deklarativ?

Accepted Answer

Prolog

Answer

Java

Answer

Python

Answer

C++

Question 52

Welcher der folgenden regulären Ausdrücke beschreibt die Menge aller Wörter über dem Alphabet {a, b}, die mit 'ab' beginnen und mit 'ba' enden?

Accepted Answer

ab(a|b)*ba

Answer

(ab)*ba

Answer

ab(a|b)+ba

Question 53

Welche der folgenden Aussagen über Turingmaschinen trifft zu?

Accepted Answer

Eine Turingmaschine kann jede berechenbare Funktion berechnen.

Answer

Jede Sprache kann von einer Turingmaschine entschieden werden.

Answer

Eine Turingmaschine hat immer beschränkten Speicherplatz.

Question 54

Was versteht man unter dem Halteproblem?

Accepted Answer

Die Frage, ob ein gegebenes Programm mit einer gegebenen Eingabe jemals zum Stillstand kommt.

Answer

Die Frage, ob ein gegebenes Programm effizient implementiert werden kann.

Answer

Die Frage, ob ein gegebenes Programm für alle Eingaben das korrekte Ergebnis berechnet.

Question 55

Was ist die Chomsky-Hierarchie?

Accepted Answer

Eine Hierarchie formaler Grammatiken, die Sprachklassen nach ihrer generativen Komplexität klassifiziert.

Answer

Eine Hierarchie von Datenstrukturen, die Daten nach ihrer Speicherkomplexität klassifiziert.

Answer

Eine Hierarchie von Algorithmen, die Probleme nach ihrer Laufzeit klassifiziert.

Question 56

Welche der folgenden Aussagen über kontextfreie Sprachen ist korrekt?

Accepted Answer

Jede kontextfreie Sprache kann von einem nichtdeterministischen Kellerautomaten erkannt werden.

Answer

Jede kontextfreie Sprache ist auch eine reguläre Sprache.

Answer

Die Menge der kontextfreien Sprachen ist unter Komplementbildung abgeschlossen.

Question 57

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

Accepted Answer

Das Erfüllbarkeitsproblem der Aussagenlogik (SAT).

Answer

Überprüfung, ob ein Graph zusammenhängend ist.

Answer

Sortierung einer Liste von Zahlen.

Answer

Suche des größten gemeinsamen Teilers zweier Zahlen.

Question 58

Welche Art von Reduktion impliziert, dass Problem A mindestens so schwierig ist wie Problem B?

Accepted Answer

Eine Polynomialzeitreduktion von Problem B auf Problem A.

Answer

Eine Exponentialzeitreduktion von Problem B auf Problem A.

Answer

Eine Polynomialzeitreduktion von Problem A auf Problem B.

Question 59

Welche Aussage über die Turingmaschine ist korrekt?

Accepted Answer

Eine Turingmaschine kann jede berechenbare Funktion ausführen.

Answer

Eine Turingmaschine ist auf die Berechnung von Funktionen beschränkt, die sich durch eine endliche Anzahl von Zuständen darstellen lassen.

Answer

Eine Turingmaschine kann ausschließlich reelle Zahlen verarbeiten.

Question 60

Welcher Automatentyp kann die Sprache aller Wörter mit einer geraden Anzahl von 'a' erkennen?

Accepted Answer

Endlicher Automat

Answer

Pushdown-Automat

Answer

Turingmaschine

Answer

Kellerautomat

Question 61

Was ist ein Pumping-Lemma?

Accepted Answer

Ein Werkzeug, um nachzuweisen, dass eine Sprache nicht regulär ist.

Answer

Ein Algorithmus, der reguläre Sprachen in kontextfreie Sprachen umwandelt.

Answer

Ein Werkzeug, um nachzuweisen, dass eine Sprache kontextfrei ist.

Question 62

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Das Travelling-Salesman-Problem

Answer

Die Berechnung der Summe aller Elemente in einer Liste.

Answer

Das Suchen nach einem bestimmten Element in einer Liste.

Answer

Das Sortieren einer Liste von Zahlen.

Question 63

Was bedeutet es, wenn ein Problem entscheidbar ist?

Accepted Answer

Es gibt einen Algorithmus, der in endlicher Zeit entscheiden kann, ob eine Eingabe zu dem Problem gehört.

Answer

Das Problem kann nur von einer Turingmaschine gelöst werden.

Question 64

Welches der folgenden Probleme ist unentscheidbar?

Accepted Answer

Das Halteproblem

Answer

Das Sortieren einer Liste von Zahlen.

Answer

Die Berechnung der Summe aller Elemente in einer Liste.

Answer

Das Suchen nach einem bestimmten Element in einer Liste.