Theoretische Informatik lernen: Quizze und Übungen für die Qualifikationsphase 2

Question 1

Erläutere die Bedeutung der Theoretischen Informatik für moderne Bereiche wie maschinelles Lernen, künstliche Intelligenz und Kryptographie.

Accepted Answer

Sie liefert grundlegende Konzepte und Werkzeuge zur Modellierung, Analyse und Lösung komplexer Probleme in diesen Bereichen.

Answer

Sie hat keinen direkten Einfluss auf diese Bereiche, da sie sich nur mit abstrakten Konzepten beschäftigt.

Answer

Sie wird nur in der Forschung eingesetzt und hat keine Bedeutung für die Entwicklung praktischer Anwendungen.

Question 2

Was versteht man in der Theorie formaler Sprachen unter einem **Alphabet** und einer **Zeichenkette**? Erläutere ihre Bedeutung für die Beschreibung formaler Sprachen.

Accepted Answer

Ein **Alphabet** ist eine **endliche Menge** von Symbolen. Eine **Zeichenkette** ist eine **Folge** von Symbolen aus dem Alphabet.

Answer

Ein Alphabet ist eine unendliche Menge von Symbolen. Eine Zeichenkette ist eine Teilmenge des Alphabets.

Answer

Ein Alphabet ist eine Folge von Zeichen. Eine Zeichenkette ist ein Symbol aus dem Alphabet.

Question 3

Was ist die Funktion des Epsilon-Übergangs in endlichen Automaten? Erläutere seine praktische Anwendung anhand eines konkreten Beispiels.

Accepted Answer

Der Epsilon-Übergang ermöglicht einen Zustandswechsel ohne Eingabezeichen und modelliert optionale oder wiederholbare Eingabesymbole.

Answer

Der Epsilon-Übergang definiert nur Start- und Endzustände.

Answer

Der Epsilon-Übergang hat keine besondere Bedeutung in endlichen Automaten.

Question 4

Was bedeutet **NP-Vollständigkeit**? Erkläre ihre Bedeutung für die praktische Lösbarkeit von Problemen und nenne ein Beispiel für ein NP-vollständiges Problem.

Accepted Answer

Ein NP-vollständiges Problem ist ein Problem, das genauso schwer zu lösen ist wie jedes andere NP-Problem.

Answer

Ein NP-vollständiges Problem ist ein Problem, das in polynomieller Zeit gelöst werden kann.

Answer

Ein NP-vollständiges Problem ist ein Problem, das nur mit einem Quantencomputer gelöst werden kann.

Answer

Ein NP-vollständiges Problem ist ein Problem, für das es keinen Algorithmus gibt, der es in polynomialer Zeit löst.

Question 5

Wie trägt die Theoretische Informatik zur Entwicklung und Optimierung von Datenbankabfragesprachen bei?

Accepted Answer

Sie ermöglicht die Entwicklung effizienter und benutzerfreundlicher Abfragesprachen.

Answer

Sie ist irrelevant für die Entwicklung von Abfragesprachen.

Answer

Sie liefert nur abstrakte Grundlagen ohne praktische Bedeutung.

Question 6

Was sind μ-rekursive Funktionen? Nennen Sie Beispiele und erläutern Sie ihre Eigenschaften und Anwendungen.

Accepted Answer

Funktionen, die durch Grundoperationen und begrenzte Rekursionen definiert werden.

Answer

Funktionen mit unendlich vielen Rekursionen, die nicht berechenbar sind.

Answer

Funktionen, die nur durch Grundoperationen definiert werden, ohne Rekursion.

Answer

Funktionen, die durch beliebige mathematische Operationen definiert werden können.

Question 7

Welche drei gängigen Methoden werden zur Implementierung endlicher Automaten verwendet? Erläutern Sie kurz deren Vor- und Nachteile.

Accepted Answer

Zustandsübergangstabelle:
Vorteile: Einfach zu erstellen und zu analysieren
Nachteile: Schwer zu visualisieren

Accepted Answer

Zustandsdiagramm:
Vorteile: Einfach zu visualisieren und zu analysieren
Nachteile: Komplexer zu erstellen

Accepted Answer

Regulärer Ausdruck:
Vorteile: Einfach zu erstellen und zu analysieren
Nachteile: Begrenzt in der Ausdrucksfähigkeit

Question 8

Welche Aussage über reguläre Sprachen ist korrekt?

Accepted Answer

Endliche Automaten können reguläre Sprachen erkennen.

Answer

Reguläre Sprachen sind unter Vereinigung nicht abgeschlossen.

Answer

Kontextfreie Sprachen sind immer auch reguläre Sprachen.

Answer

Reguläre Grammatiken haben immer eine eindeutige Ableitung für jedes Wort.

Question 9

Wie trägt die Theoretische Informatik zur Kryptographie bei, insbesondere bei der Entwicklung von Verschlüsselungsalgorithmen und digitalen Signaturen?

Accepted Answer

Die Theoretische Informatik hilft bei der Entwicklung von Verschlüsselungsalgorithmen, die Brute-Force-Angriffen widerstehen können.

Accepted Answer

Die Theoretische Informatik unterstützt die Entwicklung digitaler Signaturen, die Fälschungen verhindern können.

Answer

Die Theoretische Informatik ist für die Kryptographie nicht relevant.

Answer

Die Theoretische Informatik liefert nur abstrakte Konzepte, die sich nicht auf die Kryptographie anwenden lassen.

Question 10

Welche Eigenschaften treffen auf endliche Automaten zu?

Accepted Answer

Sie können alle regulären Sprachen erkennen.

Accepted Answer

Ihr Zustand ist immer eindeutig bestimmt.

Answer

Sie benötigen unendlich viel Speicher.

Answer

Sie können nur deterministisch sein.

Question 11

Welche Aussage über reguläre Sprachen trifft **zu**?

Accepted Answer

Reguläre Ausdrücke können reguläre Sprachen **beschreiben**.

Answer

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

Answer

Kontextfreie Sprachen sind eine **Teilmenge** von regulären Sprachen.

Question 12

Welche ethischen Auswirkungen können theoretische Konzepte und Algorithmen auf unsere Gesellschaft haben?

Accepted Answer

Theoretische Konzepte und Algorithmen können erhebliche Auswirkungen auf die Gesellschaft haben.

Answer

Theoretische Konzepte haben keine gesellschaftlichen Auswirkungen.

Answer

Informatiker tragen keine Verantwortung für die ethischen Folgen ihrer Arbeit.

Question 13

Welches der folgenden Modelle ist ein deterministischer endlicher Automat?

Accepted Answer

DFA

Answer

Nichtdeterministischer endlicher Automat (NFA)

Answer

Turingmaschine

Answer

Pushdown-Automat (PDA)

Question 14

Welche Aussage über formale Sprachen trifft zu?

Accepted Answer

Eine formale Sprache ist eine Menge wohlgeformter Zeichenketten über einem Alphabet.

Answer

Eine formale Sprache kann nur endlich viele Zeichenketten enthalten.

Answer

Eine formale Sprache ist immer eine Teilmenge der natürlichen Zahlen.

Answer

Eine formale Sprache darf keine leeren Zeichenketten enthalten.

Question 15

Welches Problem gehört zur Klasse der NP-vollständigen Probleme?

Accepted Answer

SAT-Problem

Answer

Lineare Programmierung

Answer

Sortierproblem

Answer

Primzahltest

Question 16

Was ist das Ziel der Theoretischen Informatik?

Accepted Answer

Die grundlegenden Konzepte der Informatik verstehen und ihre Anwendung in der Praxis erkennen.

Answer

Praktische Anwendungen für Computer entwickeln.

Answer

Die Geschichte der Informatik studieren.

Answer

Algorithmen für komplexe Probleme entwerfen.

Question 17

Welches der folgenden Modelle ist ein nichtdeterministischer endlicher Automat?

Accepted Answer

NFA

Answer

Determinierter endlicher Automat (DFA)

Answer

Turingmaschine

Answer

Pushdown-Automat (PDA)

Question 18

Welches Problem ist NP-schwer?

Accepted Answer

Hamiltonkreisproblem

Answer

Lineare Programmierung

Answer

Primzahltest

Answer

Sortierproblem

Question 19

Welche der folgenden Aussagen über formale Sprachen trifft zu?

Accepted Answer

Eine formale Sprache ist eine Menge von Zeichenketten, die den Regeln einer formalen Grammatik entsprechen.

Answer

Eine formale Sprache ist eine Menge von Wörtern mit einer vorgegebenen Länge.

Answer

Eine formale Sprache ist eine Menge von Sätzen, die einer bestimmten Syntax folgen.

Question 20

Welcher Automatentyp akzeptiert genau die Menge aller Zeichenketten, die mit dem Buchstaben 'a' beginnen und mit dem Buchstaben 'b' enden?

Accepted Answer

Deterministischer endlicher Automat

Answer

Nichtdeterministischer endlicher Automat

Answer

Pushdown-Automat

Question 21

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

Accepted Answer

Die Komplexitätstheorie untersucht die Beziehung zwischen der Größe der Eingabe eines Algorithmus und der Anzahl der Rechenschritte, die der Algorithmus ausführt.

Answer

Die Komplexitätstheorie beschäftigt sich mit der Entwicklung effizienter Algorithmen.

Question 22

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

Accepted Answer

P

Answer

NP-vollständig

Answer

NP

Answer

EXP

Question 23

Welcher Automatentyp verfügt über eine unbegrenzte Speicherkapazität?

Accepted Answer

Turingmaschine

Answer

Deterministischer endlicher Automat

Answer

Pushdown-Automat

Answer

Nichtdeterministischer endlicher Automat

Question 24

Welche der folgenden Aussagen über NP-vollständige Probleme ist richtig?

Accepted Answer

Ein NP-vollständiges Problem kann nicht in polynomialer Zeit gelöst werden, es sei denn, P = NP.

Answer

NP-vollständige Probleme sind immer unlösbar.

Answer

Alle NP-vollständigen Probleme können in linearer Zeit gelöst werden.

Question 25

Welcher Satz besagt, dass für jedes Problem, das von einem nichtdeterministischen Turing-Automaten in polynomialer Zeit gelöst werden kann, auch ein deterministischer Turing-Automat existiert, der es in polynomialer Zeit lösen kann?

Accepted Answer

Satz von Savitch

Answer

Satz von Rice

Answer

Satz von Kleene

Answer

Satz von Church-Turing

Question 26

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

Accepted Answer

O(1)

Answer

NP-vollständig

Answer

P

Answer

NP

Question 27

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

Accepted Answer

Subgraph-Isomorphismus

Answer

Primzahlensuche

Answer

Sortierung

Answer

Dijkstra-Algorithmus

Question 28

Was ist das Ziel der Abstraktion in der Theoretischen Informatik?

Accepted Answer

Wesentliche Eigenschaften hervorzuheben und dabei unwichtige Details zu vernachlässigen.

Answer

Die Entwicklung effizienter Algorithmen.

Answer

Die Modellierung realer Systeme.

Question 29

Welcher Bereich der Theoretischen Informatik befasst sich mit der Entwicklung und Analyse von Algorithmen?

Accepted Answer

Algorithmentheorie

Answer

Automatentheorie

Answer

Komplexitätstheorie

Answer

Formale Sprachen

Question 30

Was beschreibt die Turing-Maschine am besten?

Accepted Answer

Ein theoretisches Rechenmodell, das eine endliche Menge von Zuständen und Übergangsregeln nutzt, um Eingaben zu verarbeiten.

Answer

Ein physikalisches Gerät zur Ausführung von Programmen.

Answer

Ein Algorithmus, der immer die beste Lösung findet.

Question 31

Welche Aussage beschreibt einen endlichen Automaten?

Accepted Answer

Ein mathematisches Modell mit einer begrenzten Anzahl von Zuständen und Übergangsregeln zur Verarbeitung von Eingaben.

Answer

Ein Algorithmus, der immer das gewünschte Ergebnis liefert.

Answer

Ein Programm, das beliebig viele Zustände annehmen kann.

Question 32

Was charakterisiert ein NP-vollständiges Problem?

Accepted Answer

Ein Problem in NP, auf das sich jedes andere Problem in NP in polynomialer Zeit reduzieren lässt.

Answer

Ein Problem, das mit einer Exponentialfunktion gelöst werden kann.

Answer

Ein Problem, das mit einem Zufallsalgorithmus gelöst werden kann.

Question 33

Welcher Algorithmus ist ein Beispiel für einen Greedy-Algorithmus?

Accepted Answer

Kruskals Algorithmus zur Ermittlung eines minimalen Spannbaums in einem Graphen.

Answer

Quicksort-Algorithmus zum Sortieren einer Liste.

Answer

Dynamische Programmierung zur Lösung eines Optimierungsproblems.

Question 34

Was ist der wesentliche Unterschied zwischen einem deterministischen und einem nichtdeterministischen endlichen Automaten?

Accepted Answer

Ein deterministischer endlicher Automat hat für jede Eingabe genau einen Übergang, während ein nichtdeterministischer endlicher Automat mehrere Übergänge haben kann.

Answer

Ein deterministischer endlicher Automat ist immer effizienter als ein nichtdeterministischer endlicher Automat.

Answer

Ein nichtdeterministischer endlicher Automat kann unendliche viele Zustände haben, während ein deterministischer endlicher Automat nur eine begrenzte Anzahl von Zuständen hat.

Question 35

Welche Aussage beschreibt die Church-Turing-These?

Accepted Answer

Jeder Algorithmus, der Berechnungen durchführen kann, kann auch von einer Turing-Maschine simuliert werden.

Answer

Die Church-Turing-These besagt, dass Computer alles berechnen können.

Answer

Jede Turing-Maschine kann jede andere Turing-Maschine simulieren.

Question 36

Welche der folgenden formalen Sprachen ist NICHT regulär?

Accepted Answer

aⁿbⁿcⁿ

Answer

(ab)*

Answer

10*1

Answer

anbm

Question 37

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

Accepted Answer

P

Answer

EXPTIME

Answer

NP

Answer

NP-vollständig

Question 38

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

SAT

Answer

Primzahltest

Answer

Kreisberechnung

Answer

Sortierung

Question 39

Welche Aufgabe erfüllt die formale Sprache Backus-Naur-Form (BNF) in der Informatik?

Accepted Answer

Definition der Syntax

Answer

Modellierung von Systemen

Answer

Speicherung von Daten

Answer

Übertragung von Informationen

Question 40

Worin besteht der Hauptunterschied zwischen einem DFA und einem NFA?

Accepted Answer

Ein DFA kann nur deterministische Übergänge ausführen, während ein NFA nichtdeterministische Übergänge ausführen kann.

Answer

Ein NFA kann leere Zeichenfolgen akzeptieren, während ein DFA dies nicht kann.

Answer

Ein NFA kann unendliche Akzeptanzpfade haben, während ein DFA dies nicht kann.

Answer

Ein DFA kann mehrere Startzustände haben, während ein NFA nur einen Startzustand haben kann.

Question 41

Wofür ist Alan Turing in Bezug auf die Theoretische Informatik bekannt?

Accepted Answer

Entwicklung des Turing-Modells

Answer

Erfindung des Computers

Answer

Gründung der ACM

Answer

Entwicklung des Internets

Question 42

Welche Eigenschaft kennzeichnet deterministische kontextfreie Sprachen (DCFLs)?

Accepted Answer

Sie können von deterministischen Pushdown-Automaten erkannt werden.

Answer

Sie können nicht von Turingmaschinen erkannt werden.

Answer

Sie sind immer reguläre Sprachen.

Answer

Sie können in linearer Zeit erkannt werden.

Question 43

Welche der folgenden Aussagen beschreibt den Hauptzweck formaler Sprachen in der Theoretischen Informatik am besten?

Accepted Answer

Bereitstellung eines präzisen Rahmens zur Definition der Syntax und Semantik von Programmiersprachen und Berechnungsmodellen.

Answer

Vereinfachung der Entwicklung komplexer Algorithmen.

Answer

Speicherung großer Datenmengen in effizienter Weise.

Answer

Ermöglichung der Kommunikation zwischen verschiedenen Computersystemen.

Question 44

Welches der folgenden Probleme gehört zur Klasse der NP-vollständigen Probleme?

Accepted Answer

Das Handlungsreisendenproblem

Answer

Das Sortieren einer Liste von Zahlen

Answer

Die Berechnung der Fakultät einer Zahl

Answer

Die Suche nach einem bestimmten Element in einer sortierten Liste

Question 45

Inwiefern unterscheiden sich Compiler und Interpreter?

Accepted Answer

Ein Compiler übersetzt den kompletten Quellcode auf einmal in Maschinencode, während ein Interpreter den Code zeilenweise ausführt.

Answer

Ein Compiler eignet sich für höhere Programmiersprachen, ein Interpreter für maschinennahe Sprachen.

Answer

Compiler optimieren den Code, Interpreter hingegen nicht.

Question 46

Welche Aussage über Turingmaschinen trifft **nicht** zu?

Accepted Answer

Turingmaschinen sind auf einen begrenzten Speicher beschränkt.

Answer

Turingmaschinen sind theoretische Modelle für Computer.

Answer

Turingmaschinen können jede berechenbare Funktion berechnen.

Question 47

Welche asymptotische Laufzeit hat die binäre Suche in einem sortierten Array der Länge n?

Accepted Answer

O(log n)

Answer

O(n^2)

Answer

O(n log n)

Answer

O(n)

Question 48

Welche Zeichenkette repräsentiert eine reguläre Sprache?

Accepted Answer

(a|b)*abb

Answer

{ww | w ist ein Wort über {a,b}}

Answer

a^n b^n (n >= 0)

Answer

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

Question 49

Welche Aufgabe übernimmt ein Parser in einem Compiler?

Accepted Answer

Ermitteln der syntaktischen Korrektheit eines Programms und Erstellen einer Syntaxbaumdarstellung.

Answer

Übersetzen des Quellcodes in Maschinencode.

Answer

Optimieren des Codes für schnellere Ausführung.

Question 50

Was versteht man unter dem Halteproblem in der Theoretischen Informatik?

Accepted Answer

Die Frage, ob ein gegebenes Programm für eine bestimmte Eingabe jemals anhält oder nicht.

Answer

Die Berechnung der kürzesten Ausführungszeit eines Programms.

Answer

Die Ermittlung der effizientesten Lösung für ein gegebenes Problem.

Question 51

Welcher Automatentyp kann reguläre Sprachen erkennen?

Accepted Answer

Endlicher Automat

Answer

Turingmaschine

Answer

Kellerautomat

Answer

Pushdown-Automat

Question 52

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

Accepted Answer

Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes andere NP-Problem in polynomialer Zeit darauf reduziert werden kann.

Answer

NP-vollständige Probleme sind in polynomialer Zeit lösbar.

Question 53

Welche der folgenden formalen Sprachen ist **nicht** regulär?

Accepted Answer

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

Answer

{a^n | n >= 0}

Answer

{a, b}

Question 54

Welches Problem beschreibt das Halteproblem?

Accepted Answer

Kann ein Algorithmus für jede beliebige Turingmaschine und Eingabe entscheiden, ob sie anhält?

Answer

Kann ein Algorithmus für jede beliebige Turingmaschine und Eingabe die Ausgabe berechnen?

Question 55

Welche Klasse von Problemen kann in polynomieller Zeit gelöst werden?

Accepted Answer

P

Answer

NP

Answer

EXPTIME

Question 56

Was beschreibt die Chomsky-Hierarchie?

Accepted Answer

Die Chomsky-Hierarchie ordnet formale Sprachen nach ihrer Komplexität.

Answer

Die Chomsky-Hierarchie definiert die Komplexität von Algorithmen.

Answer

Die Chomsky-Hierarchie ordnet Programmiersprachen nach ihrer Komplexität.

Question 57

Was ist das Ziel des Travelling-Salesman-Problems?

Accepted Answer

Die kürzeste Route zu finden, die alle Städte in einer Liste genau einmal besucht und zur Startstadt zurückkehrt.

Answer

Die kürzeste Route zwischen zwei gegebenen Städten zu finden.

Question 58

Was ist eine Grammatik in der formalen Sprachtheorie?

Accepted Answer

Ein Satz von Regeln, der die Syntax einer formalen Sprache definiert.

Answer

Ein Programm, das formale Sprachen generiert.

Answer

Ein Algorithmus, der die Semantik einer formalen Sprache interpretiert.

Question 59

Welche Aussage über reguläre Sprachen ist FALSCH?

Accepted Answer

Reguläre Sprachen sind unter der Operation der Komplementbildung abgeschlossen.

Answer

Reguläre Sprachen sind unter der Operation der Vereinigung abgeschlossen.

Answer

Reguläre Sprachen sind unter der Operation der Konkatenation abgeschlossen.

Question 60

Welcher Automatentyp wird zur Erkennung einer Sprache verwendet, die durch eine reguläre Grammatik definiert ist?

Accepted Answer

Endlicher Automat

Answer

Kellerautomat

Answer

Turingmaschine

Question 61

Welche Funktion ist NICHT berechenbar?

Accepted Answer

Die Funktion, die für jede natürliche Zahl n die Anzahl der Schritte bestimmt, die eine Turingmaschine benötigt, um anzuhalten, wenn sie mit n als Eingabe gestartet wird.

Answer

Die Funktion, die für jede natürliche Zahl n die Summe der ersten n natürlichen Zahlen berechnet.

Question 62

Welches Problem gehört zur Klasse der NP-vollständigen Probleme?

Accepted Answer

Das Problem, einen Hamiltonkreis in einem Graphen zu finden.

Answer

Das Problem, die kleinste natürliche Zahl zu finden, die größer als 10 ist.

Answer

Das Problem, die größte gemeinsame Teilmenge zweier Mengen zu finden.

Question 63

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

Accepted Answer

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

Answer

Ein DFA kann mehrere Startzustände haben, während ein NFA nur einen Startzustand hat.

Question 64

Welche Aussage über Turingmaschinen ist WAHR?

Accepted Answer

Turingmaschinen können jede berechenbare Funktion berechnen.

Answer

Turingmaschinen sind in der Praxis effizient implementierbar.

Answer

Turingmaschinen können nur endliche Eingaben verarbeiten.