Theoretische Informatik lernen: Online-Quizze und Übungen

Question 1

Welches der folgenden Probleme kann von keinem Computer gelöst werden?

Accepted Answer

Prüfen, ob ein Turing-Maschinenprogramm anhält

Answer

Prüfen, ob eine natürliche Zahl gerade ist

Answer

Prüfen, ob eine Zeichenkette ein Palindrom ist

Question 2

Ist die folgende Sprache regulär? {w | w enthält eine gerade Anzahl von a's und eine ungerade Anzahl von b's}

Accepted Answer

Ja, denn sie kann durch einen endlichen Automaten beschrieben werden, der die Anzahl der a's und b's zählt.

Answer

Nein, denn sie kann nicht durch einen endlichen Automaten beschrieben werden.

Question 3

Welche Aussage beschreibt die Chomsky-Hierarchie formaler Sprachen am treffendsten?

Accepted Answer

Eine Hierarchie, die formale Sprachen nach der Komplexität ihrer erzeugenden Grammatiken einteilt.

Answer

Eine Klassifizierung formaler Sprachen nach ihrer syntaktischen Struktur.

Answer

Eine Menge von Regeln, die die Gültigkeit formaler Sprachen festlegen.

Answer

Eine Methode zur Konstruktion formaler Sprachen aus regulären Ausdrücken.

Question 4

Welche grundlegenden Prinzipien der Algorithmentheorie sind für die Entwicklung effizienter Algorithmen in der Praxis von Bedeutung?

Accepted Answer

Analyse der Effizienz von Algorithmen und Entwicklung neuer Algorithmen mit verbesserter Leistung

Answer

Konzentration auf die Entwicklung theoretisch optimaler Algorithmen

Answer

Keine praktische Relevanz, beschränkt auf theoretische Studien

Answer

Schwerpunkt auf der Implementierung von Algorithmen in verschiedenen Programmiersprachen

Question 5

Erörtern Sie die Bedeutung des Halteproblems für die theoretischen Grundlagen der Informatik. Wie hat das Halteproblem unser Verständnis von Berechenbarkeit und Entscheidbarkeit beeinflusst?

Accepted Answer

Das Halteproblem hat unser Verständnis von Berechenbarkeit und Entscheidbarkeit grundlegend geprägt.

Answer

Das Halteproblem ist ein unbedeutendes Problem, das keine Auswirkungen auf die Informatik hat.

Answer

Das Halteproblem hat bewiesen, dass alle Probleme in der Informatik lösbar sind.

Question 6

Erläutern Sie, wie die Grammatik einer formalen Sprache die Menge der Wörter bestimmt, die von einem endlichen Automaten akzeptiert werden kann.

Accepted Answer

Die Grammatik definiert die Regeln, nach denen gültige Wörter gebildet werden, und der Automat überprüft, ob ein gegebenes Wort diesen Regeln entspricht.

Answer

Die Grammatik ist irrelevant für die Akzeptanz durch einen Automaten.

Answer

Die Grammatik beeinflusst lediglich die Komplexität des Automaten.

Answer

Die Grammatik legt die Anzahl der Zustände im Automaten fest.

Question 7

Welche Aussage zum Entscheidungsproblem trifft zu?

Accepted Answer

Das Entscheidungsproblem teilt formale Sprachen in entscheidbare, nicht-entscheidbare und semi-entscheidbare Sprachen.

Answer

Das Entscheidungsproblem ist für alle formalen Sprachen lösbar.

Answer

Das Entscheidungsproblem hat keine Auswirkungen auf die Praxis der Informatik.

Answer

Das Entscheidungsproblem kann nur für reguläre Sprachen gelöst werden.

Question 8

Was besagt die Church-Turing-These und welche Bedeutung hat sie für die Informatik?

Accepted Answer

Sie besagt, dass jede berechenbare Funktion von einer Turingmaschine berechnet werden kann.

Answer

Sie besagt, dass alle Algorithmen in jeder Programmiersprache implementiert werden können.

Answer

Sie wurde von John von Neumann formuliert.

Question 9

Welcher der folgenden Bereiche ist ein aktueller Forschungstrend in der Theoretischen Informatik?

Accepted Answer

Quanteninformatik

Answer

Maschinelles Lernen

Answer

Datenbanken

Answer

Softwareentwicklung

Question 10

Welche formale Beschreibung definiert eine formale Sprache?

Accepted Answer

Eine formale Grammatik

Answer

Eine begrenzte Sammlung von Zeichen

Answer

Ein Lexikon

Question 11

Welche der folgenden Aussagen über die Turingmaschine ist richtig?

Accepted Answer

Die Turingmaschine ist ein Modell für eine universelle Rechenmaschine.

Answer

Die Turingmaschine kann nicht-entscheidbare Probleme lösen.

Answer

Die Turingmaschine hat eine unbegrenzte Anzahl von Befehlen.

Answer

Die Turingmaschine kann nur binäre Eingaben verarbeiten.

Question 12

Welche der folgenden Aussagen über formale Beweise ist richtig?

Accepted Answer

Ein formaler Beweis verwendet axiomatische Regeln, um Aussagen abzuleiten.

Answer

Ein formaler Beweis ist ein Beweis, der in Alltagssprache geschrieben ist.

Answer

Ein formaler Beweis kann keine Fehler enthalten.

Answer

Ein formaler Beweis kann nur auf konkrete Fälle beschränkt sein.

Question 13

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

Accepted Answer

Die Church-Turing-These besagt, dass alle berechenbaren Funktionen von einer Turingmaschine oder einem äquivalenten Modell berechnet werden können.

Answer

Die Church-Turing-These wurde von Alan Turing bewiesen.

Answer

Die Church-Turing-These ist falsch, da es Funktionen gibt, die von keinem Berechnungsmodell berechnet werden können.

Answer

Die Church-Turing-These ist eine Hypothese, die noch nicht bewiesen wurde.

Question 14

Welche der folgenden Kontextfreien Grammatiken erzeugt die Sprache aller Palindrome?

Accepted Answer

S -> aSa | ε

Answer

S -> aa | ε

Answer

S -> aS | ab

Answer

S -> aS | εS

Question 15

Welche Aussage trifft auf endliche Zustandsmaschinen (FSA) zu?

Accepted Answer

Eine FSA akzeptiert eine Sprache genau dann, wenn sie für die Eingabezeichenfolge einen Pfad vom Start- zum Endzustand aufweist.

Answer

Eine FSA kann unendlich viele Eingabestrings verarbeiten.

Question 16

Welche der folgenden Definitionen beschreibt formale Sprachen axiomatisch?

Accepted Answer

Eine formale Sprache ist eine Menge von Zeichenfolgen, die nach bestimmten Regeln aus einem Alphabet erzeugt werden können.

Answer

Eine formale Sprache ist eine Menge von Zeichenfolgen, die in einer bestimmten Reihenfolge angeordnet sind.

Question 17

Welche der folgenden Sprachen ist nicht kontextfrei?

Accepted Answer

Die Menge aller Zeichenfolgen mit einer geraden Anzahl von 'a' und einer ungeraden Anzahl von 'b'.

Answer

Die Menge aller Zeichenfolgen, die mit 'a' beginnen und mit 'b' enden.

Question 18

Welches der folgenden Probleme ist rekursiv?

Accepted Answer

Das Problem des Turms von Hanoi.

Answer

Das Problem der Bin-Packung.

Answer

Das Problem der kürzesten Wege.

Answer

Das Problem des Handlungsreisenden.

Question 19

Welche der folgenden Funktionen ist nicht berechenbar?

Accepted Answer

Das Halteproblem

Answer

Die Primzahlfunktion

Answer

Die Fibonacci-Funktion

Answer

Die Fakultätsfunktion

Question 20

Welche der folgenden Sprachen ist nicht regulär?

Accepted Answer

{w ∈ {a, b}* | w enthält die Teilfolge "abbaba"}

Answer

Die Sprache aller Palindrome über dem Alphabet {a, b}

Answer

Die Sprache aller Binärzahlen, die eine gerade Anzahl von Nullen enthalten

Answer

Die Sprache aller Wörter über dem Alphabet {a, b} ungerader Länge

Question 21

Welcher der folgenden Automatentypen ist der mächtigste?

Accepted Answer

Turingmaschine

Answer

Nichtdeterministischer endlicher Automat

Answer

Deterministischer endlicher Automat

Question 22

Welche der folgenden Sprachen ist eine reguläre Sprache? Eine reguläre Sprache ist eine Sprache, die von einem deterministischen endlichen Automaten erkannt werden kann.

Accepted Answer

a*b*

Answer

a^b

Answer

{a, b}

Answer

a|b

Question 23

Welche Art von Automat kann alle regulären Sprachen erkennen? Ein deterministischer endlicher Automat ist ein Automat, der sich in einem endlichen Zustand befindet und Zeichen für Zeichen liest.

Accepted Answer

Deterministischer endlicher Automat

Answer

Turingmaschine

Answer

Pushdown-Automat

Answer

Nichtdeterministischer endlicher Automat

Question 24

Welche der folgenden Beweismethoden verwendet die Widerspruchstechnik? Bei der Widerspruchstechnik wird angenommen, dass die Aussage falsch ist, und dann wird gezeigt, dass dies zu einem Widerspruch führt.

Accepted Answer

Beweis durch Widerspruch

Answer

Existenzbeweis

Answer

Induktionsbeweis

Answer

Konstruktionsbeweis

Question 25

Welche Art von Automat kann alle kontextfreien Sprachen erkennen? Ein nichtdeterministischer Pushdown-Automat ist ein Automat, der einen Stapel verwenden kann, um Informationen zu speichern.

Accepted Answer

Nichtdeterministischer Pushdown-Automat

Answer

Deterministischer endlicher Automat

Answer

Turingmaschine

Answer

Linear beschränkter Automat

Question 26

Welche der folgenden Aussagen über die Berechenbarkeit ist korrekt? Die Berechenbarkeitstheorie beschäftigt sich mit der Frage, welche Probleme von Computern gelöst werden können.

Accepted Answer

Das Halteproblem ist nicht berechenbar.

Answer

Die Menge der berechenbaren Funktionen ist endlich.

Answer

Alle Turingmaschinen halten für alle Eingaben an.

Answer

Alle Funktionen sind berechenbar.

Question 27

Welche der folgenden Beweismethoden verwendet die Induktionstechnik? Bei der Induktionstechnik wird bewiesen, dass eine Aussage für einen Basisfall gilt und dass sie für jeden nachfolgenden Fall gilt, wenn sie für den vorhergehenden Fall gilt.

Accepted Answer

Beweis durch vollständige Induktion

Answer

Konstruktionsbeweis

Answer

Existenzbeweis

Answer

Beweis durch Widerspruch

Question 28

Welche der folgenden Aussagen zur Chomsky-Hierarchie ist korrekt? Die Chomsky-Hierarchie ist eine Klassifizierung von formalen Sprachen.

Accepted Answer

Die regulären Sprachen sind eine Teilmenge der kontextfreien Sprachen.

Answer

Die rekursiv aufzählbaren Sprachen sind eine Teilmenge der kontextsensitiven Sprachen.

Answer

Die kontextfreien Sprachen sind eine Teilmenge der regulären Sprachen.

Question 29

Welche der folgenden Aussagen zum Halteproblem trifft zu?

Accepted Answer

Es ist nicht entscheidbar, ob eine Turingmaschine mit einer gegebenen Eingabe anhält.

Answer

Es ist entscheidbar, ob eine Turingmaschine mit einer gegebenen Eingabe anhält.

Answer

Wenn eine Turingmaschine anhält, kann man immer einen Beweis dafür liefern.

Question 30

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

Accepted Answer

P

Answer

NP-vollständig

Answer

NP

Answer

NP-schwer

Question 31

Welche Datenstruktur ermöglicht die Implementierung eines Stacks?

Accepted Answer

Verkettete Liste

Answer

Hashtabelle

Answer

Array

Answer

Baum

Question 32

Formale Sprachen werden definiert als:

Accepted Answer

Menge von Zeichenfolgen über einem definierten Alphabet

Answer

Menge von Regeln für die Satzbildung

Answer

Menge von Sätzen in einer natürlichen Sprache.

Answer

Menge von Berechnungen

Question 33

Welche Aussage über endliche Automaten ist korrekt?

Accepted Answer

Sie repräsentieren begrenzte Modelle für Berechnungen.

Answer

Sie sind nichtdeterministisch.

Answer

Sie können beliebige Sprachen akzeptieren.

Question 34

Der Satz von Church-Turing besagt:

Accepted Answer

Jede berechenbare Funktion kann von einer Turingmaschine berechnet werden.

Answer

Jede Turingmaschine kann durch einen endlichen Automaten simuliert werden.

Answer

Es existieren unberechenbare Funktionen.

Question 35

Welche Grammatik generiert die Sprache {aⁿbⁿ | n ≥ 0}?

Accepted Answer

S → aSb | ε

Answer

S → aS | bS

Answer

S → a | b

Answer

S → Sa | Sb

Question 36

Welche Aussage über Boolesche Algebra ist korrekt?

Accepted Answer

Sie ist eine algebraische Struktur, die die Operationen UND, ODER und NICHT definiert.

Answer

Sie ist ein Modell für die Berechnung von Wahrscheinlichkeiten.

Answer

Sie ist eine Menge an Regeln für die Satzbildung in natürlicher Sprache.

Question 37

Welche Eigenschaft besitzen Codewörter nach der Anwendung des Huffman-Algorithmus?

Accepted Answer

Sie sind präfixfrei und minimieren die durchschnittliche Länge.

Answer

Sie sind möglichst kurz und eindeutig.

Answer

Sie sind alle gleich lang.

Question 38

Was ist das Ziel des Halteproblems?

Accepted Answer

Zu bestimmen, ob eine beliebige Turingmaschine für eine beliebige Eingabe zum Stillstand kommt.

Answer

Einen allgemeinen Algorithmus zur Problemlösung zu finden.

Answer

Die Komplexität von Berechnungen zu messen.

Question 39

Was versteht man unter einer Komplexitätsklasse?

Accepted Answer

Eine Menge von Problemen mit ähnlicher Laufzeitkomplexität.

Answer

Eine Menge von Problemen mit ähnlichem Speicherbedarf.

Answer

Eine Menge von Problemen, die mit demselben Algorithmus gelöst werden können.

Question 40

Welches Problem ist NP-vollständig?

Accepted Answer

SAT (Boolesche Erfüllbarkeit)

Answer

Primzahltest

Answer

Sortierung

Question 41

Welche Aufgabe erfüllt eine Grammatik in der Theorie der formalen Sprachen?

Accepted Answer

Sie definiert eine Sprache durch Regeln, die gültige Zeichenfolgen erzeugen.

Answer

Sie stellt Beziehungen zwischen Objekten dar.

Answer

Sie speichert Daten in einer strukturierten Form.

Question 42

Welche der folgenden Aussagen über rekursive Funktionen ist richtig?

Accepted Answer

Sie können komplexe Probleme durch Aufteilung in kleinere Instanzen derselben Art lösen.

Answer

Sie können nur einfache arithmetische Operationen ausführen.

Answer

Sie können nur endliche Mengen verarbeiten.

Question 43

Was ist der Halteproblem?

Accepted Answer

Das Problem, zu bestimmen, ob eine Turingmaschine bei einer bestimmten Eingabe anhält oder nicht.

Answer

Das Problem, zu bestimmen, ob zwei Sprachen gleich sind.

Answer

Das Problem, zu bestimmen, ob eine bestimmte Zeichenfolge in einer Sprache ist.

Question 44

Welche der folgenden Aussagen über endliche Automaten ist FALSCH?

Accepted Answer

Ein endlicher Automat kann eine beliebig große Anzahl von Zuständen haben.

Answer

Ein endlicher Automat kann nur eine begrenzte Anzahl von Zuständen haben.

Answer

Ein endlicher Automat kann Eingaben verarbeiten und basierend auf diesen Eingaben seinen Zustand ändern.

Question 45

Welche der folgenden Sprachen ist NICHT regulär?

Accepted Answer

{a^n b^n | n ≥ 0}

Answer

{a^n b^m | n, m ≥ 0}

Answer

{a^n | n ≥ 0}

Answer

{a, b}

Question 46

Welcher Typ von Grammatik kann alle regulären Sprachen generieren?

Accepted Answer

Reguläre Grammatik

Answer

Kontextsensitive Grammatik

Answer

Unbeschränkte Grammatik

Answer

Kontextfreie Grammatik

Question 47

Welche der folgenden Aussagen über die Turing-Maschine ist RICHTIG?

Accepted Answer

Eine Turing-Maschine kann jedes berechenbare Problem lösen.

Answer

Eine Turing-Maschine ist eine Maschine, die endliche Automaten simuliert.

Answer

Eine Turing-Maschine kann nur reguläre Sprachen erkennen.

Question 48

Was ist die Church-Turing-These?

Accepted Answer

Die Church-Turing-These besagt, dass alles, was algorithmisch berechenbar ist, von einer Turing-Maschine berechnet werden kann.

Answer

Die Church-Turing-These besagt, dass alle Turing-Maschinen gleich leistungsstark sind.

Question 49

Welches der folgenden Probleme ist UNENTScheidbar?

Accepted Answer

Das Halteproblem

Answer

Das Sortierungsproblem

Answer

Das Suchproblem

Question 50

Welche der folgenden Aussagen über Chomsky-Hierarchien ist RICHTIG?

Accepted Answer

Die Chomsky-Hierarchie klassifiziert Sprachen anhand ihrer Grammatiktypen.

Answer

Die Chomsky-Hierarchie klassifiziert Sprachen anhand ihrer Anwendungen.

Answer

Die Chomsky-Hierarchie klassifiziert Sprachen anhand ihrer Komplexität.

Question 51

Was ist der Unterschied zwischen einem deterministischen endlichen Automaten (DFA) und einem nicht-deterministischen endlichen Automaten (NFA)?

Accepted Answer

Ein DFA hat für jeden Zustand und jede Eingabe genau einen Folgezustand, während ein NFA mehrere Folgezustände für einen Zustand und eine Eingabe haben kann.

Answer

Ein DFA kann nur eine begrenzte Anzahl von Zuständen haben, während ein NFA eine beliebig große Anzahl von Zuständen haben kann.

Question 52

Welche der folgenden Aussagen beschreibt am besten die Chomsky-Hierarchie?

Accepted Answer

Die Chomsky-Hierarchie klassifiziert formale Sprachen nach ihrer Komplexität, wobei die Klasse 0 die mächtigsten und die Klasse 3 die am wenigsten mächtigen Sprachen enthält.

Answer

Die Chomsky-Hierarchie ist ein System zur Klassifizierung von Automaten nach ihrer Fähigkeit, Sprachen zu erkennen.

Question 53

Welcher Typ von Automat kann jede reguläre Sprache erkennen?

Accepted Answer

Endlicher Automat (DFA)

Answer

Turingmaschine

Answer

Kellerautomat (PDA)

Answer

Linear beschränkter Automat

Question 54

Welche der folgenden Sprachen ist nicht regulär?

Accepted Answer

{a^n b^n | n ≥ 0}

Answer

{a b | n ≥ 0}

Answer

{a^n b^m | n, m ≥ 0}

Answer

{a^n | n ≥ 0}

Question 55

Welches Problem ist bekanntlich unentscheidbar?

Accepted Answer

Das Halteproblem

Answer

Das Primzahlproblem

Answer

Das kürzeste Pfadproblem

Answer

Das Sortierproblem

Question 56

Wie viele Zustände benötigt ein minimaler DFA, um die Sprache {a^n b^n | n ≥ 0} zu erkennen?

Accepted Answer

Unendlich viele

Answer

1

Answer

2

Question 57

Welches Konzept beschreibt die Fähigkeit eines Algorithmus, ein Problem in endlicher Zeit zu lösen?

Accepted Answer

Berechenbarkeit

Answer

Komplexität

Answer

Effizienz

Answer

Korrektheit

Question 58

Welche der folgenden ist keine Eigenschaft von Kontextfreien Grammatiken?

Accepted Answer

Sie können alle regulären Sprachen erzeugen.

Answer

Sie können rekursive Sprachen erzeugen.

Answer

Sie können Sprachen mit verschachtelten Strukturen erzeugen.

Question 59

Welche der folgenden Aussagen ist FALSCH in Bezug auf die Turingmaschine?

Accepted Answer

Eine Turingmaschine kann jedes Problem in endlicher Zeit lösen.

Answer

Eine Turingmaschine kann beliebig viel Speicherplatz verwenden.

Answer

Eine Turingmaschine ist ein universelles Berechnungsmodell.

Question 60

Welche der folgenden Sprachen kann von einem endlichen Automaten erkannt werden?

Accepted Answer

{a^n b^m | n, m ≥ 0}

Answer

{a^n b^n c^n | n ≥ 0}

Answer

{a^n b^2n | n ≥ 0}

Answer

{a^n b^n | n ≥ 0}

Question 61

Was ist der Unterschied zwischen einem DFA und einem NFA?

Accepted Answer

Ein DFA hat genau einen Übergang für jedes Eingabezeichen in jedem Zustand, während ein NFA mehrere Übergänge für ein Eingabezeichen haben kann.

Answer

Ein DFA kann beliebig viel Speicherplatz verwenden, während ein NFA begrenzt ist.