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

Question 1

Beschreibe die Chomsky-Hierarchie formaler Sprachen und ihre Bedeutung für die Informatik.

Accepted Answer

Die Chomsky-Hierarchie ist eine Klassifizierung formaler Sprachen nach ihrer Komplexität. Sie umfasst reguläre, kontextfreie, kontextsensitive und rekursiv aufzählbare Sprachen.

Answer

Die Chomsky-Hierarchie ist eine Hierarchie von Automatenmodellen, die zur Erkennung formaler Sprachen verwendet werden.

Answer

Die Chomsky-Hierarchie hat keine praktische Bedeutung für die Informatik.

Answer

Die Chomsky-Hierarchie ist eine Klassifizierung formaler Sprachen nach ihrer lexikalischen Struktur.

Question 2

Was versteht man unter semantischer Äquivalenz formaler Sprachen? Wie lässt sich feststellen, ob zwei formale Sprachen semantisch äquivalent sind?

Accepted Answer

Semantisch äquivalente formale Sprachen erzeugen unabhängig von ihren Ableitungsbäumen dieselben Zeichenfolgen.

Answer

Semantisch äquivalente formale Sprachen haben dieselbe Grammatik.

Answer

Semantisch äquivalente formale Sprachen haben dieselbe Anzahl von Terminal- und Nicht-Terminal-Symbolen.

Question 3

Wie tragen Petri-Netze zur Modellierung und Analyse von Systemen mit parallelen Abläufen bei?

Accepted Answer

Sie ermöglichen die Darstellung von Kommunikation und Synchronisation zwischen parallelen Prozessen.

Answer

Sie sind nur für die Modellierung sequenzieller Systeme geeignet.

Answer

Sie können nur zur Analyse statischer Systeme verwendet werden.

Question 4

Wie trägt die Theoretische Informatik zu unserem Verständnis von künstlicher Intelligenz (KI) und maschinellem Lernen (ML) bei?

Accepted Answer

Sie liefert die mathematische Grundlage für die Modellierung von KI-Problemen und die Analyse ihrer Komplexität.

Answer

Sie spielt keine Rolle für das Verständnis von KI, da KI auf empirischen Methoden basiert.

Answer

Sie befasst sich nur mit der Entwicklung von Algorithmen und hat keinen Einfluss auf das Verständnis von KI.

Answer

Sie ist für maschinelles Lernen irrelevant, da maschinelles Lernen auf statistischen Modellen basiert.

Question 5

Was versteht man unter semantischer Äquivalenz formaler Sprachen? Beschreibe außerdem Methoden, um die semantische Äquivalenz zweier formaler Sprachen zu ermitteln.

Accepted Answer

Semantische Äquivalenz bedeutet, dass zwei formale Sprachen unabhängig von ihren Grammatiken dieselben Zeichenfolgen akzeptieren.

Answer

Semantische Äquivalenz bedeutet, dass zwei formale Sprachen dieselbe Grammatik haben, auch wenn sie unterschiedliche Zeichenfolgen akzeptieren.

Answer

Semantische Äquivalenz gilt nur für reguläre Sprachen.

Question 6

Wie trägt die Theoretische Informatik zur Entwicklung und Analyse von Verschlüsselungsverfahren bei?

Accepted Answer

Sie liefert die mathematische Grundlage zur Modellierung und Analyse von Verschlüsselungsprozessen.

Answer

Sie dient nur der theoretischen Betrachtung von Verschlüsselungsalgorithmen.

Answer

Sie ist nicht auf moderne Verschlüsselungsalgorithmen anwendbar.

Answer

Sie konzentriert sich ausschließlich auf die Entwicklung neuer Verschlüsselungsalgorithmen.

Question 7

Wie trägt die Typentheorie zur Verbesserung der Sicherheit, Zuverlässigkeit und Wartbarkeit von Software bei?

Accepted Answer

Sie stellt sicher, dass Variablen gültige Werte haben, wodurch Laufzeitfehler vermieden werden.

Answer

Sie ermöglicht die Unterteilung von Programmen in kleinere, leichter zu wartende Module.

Answer

Sie reduziert die Komplexität von Programmen, indem redundanter Code eliminiert wird.

Answer

Sie findet ausschließlich in funktionalen Programmiersprachen Anwendung.

Question 8

Welche Eigenschaft trifft auf Turingmaschinen zu?

Accepted Answer

Sie können alle berechenbaren Funktionen berechnen.

Answer

Sie sind nichtdeterministisch.

Answer

Sie haben eine begrenzte Speicherkapazität.

Answer

Sie verarbeiten nur endliche Eingaben.

Question 9

Welche Eigenschaft ist für einen endlichen Automaten charakteristisch?

Accepted Answer

Er besitzt genau einen Anfangszustand.

Answer

Er erkennt jede Sprache.

Answer

Er kann keine Zeichen unterscheiden.

Answer

Er kann keine Schleifen enthalten.

Question 10

Welche Aussage trifft auf die Church-Turing-These zu?

Accepted Answer

Turingmaschinen sind ein Modell für universelle Berechenbarkeit.

Answer

Turingmaschinen können nur Probleme lösen, die einen Algorithmus mit endlich vielen Schritten haben.

Answer

Turingmaschinen können jedes Problem lösen, das von einem endlichen Automaten gelöst werden kann.

Question 11

Wie beeinflussen Quantencomputer die Theoretische Informatik? Erläutere, wie Quantenalgorithmen die Grenzen der lösbaren Probleme erweitern und neue Möglichkeiten für die Problemanalyse eröffnen.

Accepted Answer

Quantencomputer können Probleme lösen, die für klassische Computer effizient nicht lösbar sind.

Answer

Quantenalgorithmen lösen nur Probleme, die auch klassische Computer lösen können, aber schneller.

Answer

Quantencomputer haben keinen Einfluss auf die Theoretische Informatik, da sie nur schnellere klassische Computer sind.

Answer

Die Auswirkungen von Quantencomputern auf die Theoretische Informatik sind noch unbekannt, da sie sich in der Entwicklung befinden.

Question 12

Welche Aussage beschreibt die Hauptfunktion regulärer Ausdrücke am besten?

Accepted Answer

Reguläre Ausdrücke sind eine formale Sprache zur Beschreibung und Bearbeitung von Mustern in Text.

Answer

Reguläre Ausdrücke dienen hauptsächlich der Textsuche.

Answer

Reguläre Ausdrücke werden hauptsächlich zur Überprüfung der Gültigkeit von E-Mail-Adressen verwendet.

Answer

Reguläre Ausdrücke sind ausschließlich für die Programmierung in Java vorgesehen.

Question 13

Welche Eigenschaft ist typisch für Turingmaschinen?

Accepted Answer

Unbegrenzter Speicher

Answer

Nicht-deterministisches Verhalten

Answer

Nur reguläre Spracherkennung

Answer

Keine praktische Bedeutung

Question 14

Welches Merkmal ist charakteristisch für einen nicht-deterministischen endlichen Automaten (NFA)?

Accepted Answer

Ein NFA kann für eine Eingabe mehrere Akzeptanzpfade haben.

Answer

Ein NFA ist immer effizienter als ein deterministischer endlicher Automat (DFA) bei der Verarbeitung einer Eingabe.

Answer

Ein NFA kann unendliche Eingaben verarbeiten.

Question 15

Welche Aussage über die Turingmaschine ist falsch?

Accepted Answer

Eine Turingmaschine ist ein nichtdeterministischer Automat.

Answer

Eine Turingmaschine ist ein mathematisches Modell eines Rechners.

Answer

Eine Turingmaschine kann jede berechenbare Funktion berechnen.

Answer

Eine Turingmaschine hat ein unendliches Band.

Question 16

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 17

Welcher Beweis wird in der Theoretischen Informatik verwendet, um die Nicht-Berechenbarkeit einer Funktion zu beweisen?

Accepted Answer

Diagonalisierungsbeweis

Answer

Induktionsbeweis

Answer

Widerspruchsbeweis

Answer

Existenzbeweis

Question 18

Welche Aussage über die Chomsky-Hierarchie ist korrekt?

Accepted Answer

Die Klasse der rekursiv aufzählbaren Sprachen ist eine Teilmenge der kontextsensitiven Sprachen.

Answer

Die Klasse der kontextsensitiven Sprachen ist eine Teilmenge der regulären Sprachen.

Answer

Die Klasse der unentscheidbaren Sprachen ist eine Teilmenge der nichtkontextsensitiven Sprachen.

Answer

Die Klasse der kontextfreien Sprachen ist eine Teilmenge der regulären Sprachen.

Question 19

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

Accepted Answer

Wenn ein NP-vollständiges Problem effizient gelöst werden kann, dann können alle NP-Probleme effizient gelöst werden.

Answer

Jedes NP-vollständige Problem kann effizient gelöst werden.

Answer

Es gibt keine bekannten NP-vollständigen Probleme.

Answer

Die Anzahl der NP-vollständigen Probleme ist unendlich.

Question 20

Welche Eigenschaft trifft auf endliche Automaten zu?

Accepted Answer

Sie haben eine begrenzte Anzahl von Zuständen.

Answer

Sie können jede Sprache erkennen.

Answer

Sie können keine Berechnungen ausführen.

Answer

Sie können mehrere Eingaben gleichzeitig verarbeiten.

Question 21

Welche Eigenschaft trifft auf Turingmaschinen zu?

Accepted Answer

Sie können alle berechenbaren Funktionen berechnen.

Answer

Sie arbeiten nur deterministisch.

Answer

Sie benötigen immer unendlich viel Zeit für Berechnungen.

Answer

Sie können keine rekursiven Funktionen berechnen.

Question 22

Welche Eigenschaft trifft auf Turingmaschinen zu?

Accepted Answer

Sie können alle Probleme lösen, für die es einen Algorithmus gibt.

Answer

Sie sind deterministische Automaten.

Answer

Das Halteproblem für sie ist lösbar.

Answer

Sie sind endliche Automaten.

Question 23

Welche Eigenschaft ist für Turingmaschinen charakteristisch?

Accepted Answer

Sie können jede berechenbare Funktion berechnen.

Answer

Sie können alle Probleme lösen.

Answer

Sie haben einen begrenzten Speicher.

Question 24

Welche Aussage über deterministische endliche Automaten (DFA) trifft **nicht** zu?

Accepted Answer

DFAs sind nichtdeterministisch.

Answer

DFAs erkennen reguläre Sprachen.

Answer

DFAs haben eine begrenzte Anzahl von Zuständen.

Answer

DFAs können unendliche Eingaben verarbeiten.

Question 25

Welche Aussage über endliche Automaten ist nicht korrekt?

Accepted Answer

Endliche Automaten können Eingaben beliebiger Länge verarbeiten.

Answer

Endliche Automaten können nur eine begrenzte Anzahl von Zuständen haben.

Answer

Endliche Automaten können nur reguläre Sprachen erkennen.

Question 26

Welche der folgenden Eigenschaften trifft auf endliche Automaten zu?

Accepted Answer

Sie können nur eine begrenzte Anzahl von Zuständen annehmen.

Answer

Sie können unendlich viele Zustände annehmen.

Answer

Ihre Zustände können Bezeichnungen mit beliebiger Länge haben.

Question 27

Welche Sprache wird durch den regulären Ausdruck (a|b)*abb definiert?

Accepted Answer

Alle Zeichenketten, die mit "abb" enden

Answer

Alle Zeichenketten, die nur "a" und "b" enthalten

Answer

Alle Zeichenketten, die genau ein "b" enthalten

Answer

Alle Zeichenketten, die mindestens ein "a" enthalten

Question 28

Was besagt das Halteproblem?

Accepted Answer

Es ist unentscheidbar, ob ein gegebenes Programm für jede Eingabe terminiert.

Answer

Es ist entscheidbar, ob ein gegebenes Programm für eine bestimmte Eingabe terminiert.

Answer

Es ist entscheidbar, ob ein gegebenes Programm fehlerfrei ist.

Question 29

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

Accepted Answer

P

Answer

NP-vollständig

Answer

NP-schwer

Answer

NP

Question 30

Was ist eine Turingmaschine?

Accepted Answer

Ein theoretisches Modell eines Computers, das alle berechenbaren Funktionen berechnen kann.

Answer

Ein Computer, der menschliche Sprache verstehen kann.

Answer

Eine Maschine, die nur eine begrenzte Anzahl von Berechnungen ausführen kann.

Question 31

Welche Komplexitätsklasse beschreibt Probleme, die in polynomieller Speicherplatzkomplexität gelöst werden können?

Accepted Answer

PSPACE

Answer

P

Question 32

Was ist die Chomsky-Hierarchie?

Accepted Answer

Eine Klassifizierung formaler Sprachen nach ihren Grammatiktypen.

Answer

Eine Klassifizierung von Turingmaschinentypen.

Answer

Eine Klassifizierung von Automatentypen.

Question 33

Welche der folgenden Aussagen beschreibt eine formale Sprache korrekt?

Accepted Answer

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

Answer

Eine formale Sprache ist eine Menge von Wörtern in natürlicher Sprache.

Answer

Eine formale Sprache ist eine Menge von Befehlen in einer Programmiersprache.

Question 34

Welche der folgenden Aussagen zum Halting-Problem ist korrekt?

Accepted Answer

Es existiert kein Algorithmus, der für ein beliebiges Programm bestimmen kann, ob es terminiert.

Answer

Das Halting-Problem kann für Programme mit nichtdeterministischem Verhalten gelöst werden.

Answer

Das Halting-Problem kann für Programme mit deterministischem Verhalten gelöst werden.

Question 35

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

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

EXP

Question 36

Welche Methode wird zur Analyse der Laufzeit eines Algorithmus verwendet?

Accepted Answer

Asymptotische Analyse

Answer

Experimentelle Analyse

Answer

Qualitative Analyse

Answer

Statistische Analyse

Question 37

Welche der folgenden Aussagen über reguläre Ausdrücke ist falsch?

Accepted Answer

Sie können unendlich viele Zeichen darstellen.

Answer

Sie können verwendet werden, um die Sprache aller durch einen endlichen Automaten akzeptierten Zeichenfolgen zu beschreiben.

Answer

Sie sind eine prägnante Möglichkeit, Suchmuster darzustellen.

Question 38

Welche der folgenden Aussagen über das Halteproblem ist richtig?

Accepted Answer

Es gibt für Turingmaschinen keinen Algorithmus, der für alle Eingaben korrekt entscheidet, ob die Turingmaschine anhält oder nicht.

Answer

Es kann in polynomialer Zeit gelöst werden.

Answer

Es kann für alle Arten von Computern gelöst werden.

Question 39

Welche der folgenden Techniken kann verwendet werden, um die Komplexität eines Algorithmus zu reduzieren?

Accepted Answer

Teilen und Herrschen

Answer

Künstliche Intelligenz

Answer

Auswendiglernen

Answer

Zufällige Suche

Question 40

Welche der folgenden Aussagen über Turingmaschinen ist falsch?

Accepted Answer

Sie sind eine physische Art von Computer.

Answer

Sie können jedes Problem lösen, das mit einem Algorithmus lösbar ist.

Answer

Sie haben ein unendliches Band.

Answer

Sie haben einen endlichen Satz von Zuständen.

Question 41

Welches der folgenden Alphabete ist ein reguläres Alphabet?

Accepted Answer

Menge aller Zeichenfolgen über {a, b}

Answer

Menge aller Zeichenfolgen mit einer Länge von genau 3

Answer

Menge aller Palindrome

Answer

Menge aller Primzahlen

Question 42

Welche Aussage über endliche Automaten ist korrekt?

Accepted Answer

Ein endlicher Automat kann jede reguläre Sprache erkennen.

Answer

Ein endlicher Automat kann jede kontextfreie Sprache erkennen.

Answer

Ein endlicher Automat hat immer eine deterministische Akzeptanzbedingung.

Question 43

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

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

EXP

Question 44

Welche Aussage über das Halteproblem ist korrekt?

Accepted Answer

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

Answer

Das Halteproblem ist lösbar für Programme in einer deterministischen Programmiersprache.

Answer

Das Halteproblem ist lösbar, wenn das Programm eine begrenzte Anzahl von Zuständen hat.

Question 45

Welche Technik kann zur Überprüfung der Gültigkeit einer booleschen Formel verwendet werden?

Accepted Answer

Wahrheitstabelle

Answer

Schnelle Fourier-Transformation

Answer

Algorithmus von Ford-Fulkerson

Answer

Induktionsbeweis

Question 46

Welche der folgenden Aussagen über formale Sprachen ist **falsch**?

Accepted Answer

Formale Sprachen sind endliche Mengen von Wörtern.

Answer

Formale Sprachen werden durch eine Grammatik definiert.

Answer

Ein Wort ist eine Folge von Symbolen.

Question 47

Welche Komplexitätsklasse enthält alle Probleme, die durch eine deterministische Turingmaschine in **polynomialer** Zeit gelöst werden können?

Accepted Answer

P

Answer

EXPTIME

Answer

RE

Answer

NP

Question 48

Welches der folgenden Konzepte ist eine **abzählbar unendliche** Menge von Symbolen?

Accepted Answer

Alphabet

Answer

Sprache

Answer

Grammatik

Question 49

Welche der folgenden Aussagen über Turingmaschinen ist **richtig**?

Accepted Answer

Turingmaschinen können jedes berechenbare Problem lösen.

Answer

Turingmaschinen sind immer deterministisch.

Answer

Turingmaschinen verwenden nur einen endlichen Speicher.

Answer

Turingmaschinen halten immer an.

Question 50

Welcher Satz besagt, dass es unmöglich ist, zu entscheiden, ob ein gegebenes Programm **anhält**?

Accepted Answer

Halteproblem

Answer

P=NP-Problem

Answer

Pumping-Lemma

Answer

Kirchen-Turing-These

Question 51

Welche der folgenden Grammatiken erzeugt die Sprache {**(ab)^n | n ≥ 0**}?

Accepted Answer

S → SS | ab

Answer

S → a | b

Answer

S → abS | ε

Answer

S → aS | b

Question 52

Welche der folgenden Aussagen über reguläre Sprachen ist **falsch**?

Accepted Answer

Reguläre Sprachen können durch kontextfreie Grammatiken beschrieben werden.

Answer

Die Vereinigung zweier regulärer Sprachen ist eine reguläre Sprache.

Answer

Reguläre Sprachen können durch endliche Automaten erkannt werden.

Question 53

Welche der folgenden Funktionen ist **nicht** berechenbar?

Accepted Answer

Die Funktion, die das Halteproblem für alle Turingmaschinen löst.

Answer

Die Funktion, die den größten gemeinsamen Teiler zweier natürlicher Zahlen bestimmt.

Answer

Die Funktion, die die Summe zweier natürlicher Zahlen berechnet.

Question 54

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

Accepted Answer

Das Traveling Salesperson Problem (TSP)

Answer

Das Finden des kürzesten Pfades in einem gerichteten Graphen.

Answer

Das Sortieren eines Arrays von Zahlen.

Question 55

Was ist das **Pumping-Lemma** für reguläre Sprachen?

Accepted Answer

Ein Satz, der besagt, dass jede reguläre Sprache eine Eigenschaft hat, die es ermöglicht, bestimmte Teilstrings innerhalb von Wörtern beliebig oft zu wiederholen, ohne die Zugehörigkeit des Wortes zur Sprache zu ändern.

Answer

Ein Algorithmus, der die Regularität einer Sprache überprüft.

Question 56

Welche der folgenden Aussagen über Turingmaschinen ist **richtig**?

Accepted Answer

Turingmaschinen können alle berechenbaren Funktionen berechnen.

Answer

Turingmaschinen sind begrenzt in ihrer Rechenleistung.

Answer

Turingmaschinen können in der Praxis effizient implementiert werden.

Question 57

Welche der folgenden Klassen von Problemen ist in P enthalten?

Accepted Answer

Die Klasse von Problemen, die in polynomieller Zeit lösbar sind.

Answer

Die Klasse von Problemen, die in exponentieller Zeit lösbar sind.

Answer

Die Klasse von Problemen, die NP-vollständig sind.

Question 58

Was ist die Chomsky-Hierarchie?

Accepted Answer

Eine Hierarchie von formalen Grammatiken, die die Komplexität von Sprachen einteilt.

Answer

Eine Methode zur Konstruktion von Algorithmen.

Answer

Eine Sammlung von Programmiersprachen.

Question 59

Welche der folgenden Aussagen über die Klasse NP ist **falsch**?

Accepted Answer

Alle Probleme in NP sind in P.

Answer

Die Frage, ob P gleich NP ist, ist eines der wichtigsten ungelösten Probleme der Informatik.

Answer

Die Klasse NP enthält Probleme, die in polynomieller Zeit verifizierbar sind.

Answer

Die Klasse NP enthält viele wichtige praktische Probleme.

Question 60

Welcher Typ von Automaten ist am besten geeignet, um reguläre Sprachen zu erkennen?

Accepted Answer

Endlicher Automat.

Answer

Turingmaschine.

Answer

Kellerautomat.

Answer

Linear beschränkter Automat.

Question 61

Welche der folgenden Aussagen über kontextfreie Grammatiken ist **richtig**?

Accepted Answer

Kontextfreie Grammatiken können Sprachen beschreiben, die nicht durch endliche Automaten erkannt werden können.

Answer

Kontextfreie Grammatiken können alle Sprachen beschreiben.

Question 62

Was ist die Entscheidungsaufgabe, die durch die Turing-Maschine gelöst wird?

Accepted Answer

Halteproblem

Answer

Zählproblem

Answer

Erreichbarkeitsproblem

Answer

Existenzproblem

Question 63

Welche Komplexitätsklasse umfasst alle Probleme, die in polynomialer Zeit durch eine deterministische Turing-Maschine gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

EXPTIME

Question 64

Was ist das Ziel der Kontextfreien Grammatik?

Accepted Answer

Beschreiben von Sprachen, die von Pushdown-Automaten erkannt werden können

Answer

Beschreiben von Sprachen, die von Turing-Maschinen erkannt werden können

Answer

Beschreiben von Sprachen, die von Zustandsmaschinen erkannt werden können