Theoretische Informatik I: Grundlagen für Informatiker

Question 1

Welcher Automatentyp kann die größte Menge an Sprachen erkennen?

Accepted Answer

Turingmaschine

Answer

Deterministischer endlicher Automat (DFA)

Answer

Nicht-deterministischer endlicher Automat (NFA)

Answer

Pushdown-Automat (PDA)

Question 2

Welche Eigenschaft ist für endliche Automaten unerlässlich?

Accepted Answer

Sie erkennen nur reguläre Sprachen.

Answer

Sie sind immer nicht-deterministisch.

Answer

Sie haben unendlich viele Zustände.

Answer

Sie erkennen alle von Turingmaschinen erkennbaren Sprachen.

Question 3

Welche der folgenden Aussagen beschreibt eine grundlegende Eigenschaft endlicher Automaten?

Accepted Answer

Zustandsänderungen erfolgen nur durch Übergänge.

Answer

Sie können jede beliebige Sprache erkennen.

Answer

Sie verfügen über eine Ausgabefunktion.

Answer

Sie existieren ausschließlich in nichtdeterministischer Form.

Question 4

Welche Aussage über endliche Automaten ist richtig?

Accepted Answer

Endliche Automaten können nur eine begrenzte Anzahl von Symbolen verarbeiten.

Answer

Endliche Automaten können auch unendliche Sprachen erkennen.

Answer

Endliche Automaten sind immer deterministisch.

Answer

Endliche Automaten können keine leeren Zeichen verarbeiten.

Question 5

Welche Aussage über Turingmaschinen ist zutreffend?

Accepted Answer

Turingmaschinen können alle berechenbaren Funktionen berechnen.

Answer

Turingmaschinen sind nichtdeterministische Automaten.

Answer

Das Halteproblem für Turingmaschinen kann gelöst werden.

Answer

Turingmaschinen benötigen unendlich viel Speicher.

Question 6

Was ist die Eigenschaft, die Turingmaschinen von endlichen Automaten unterscheidet?

Accepted Answer

Turingmaschinen können unendlich viele Symbole auf ihrem Band speichern.

Answer

Turingmaschinen sind deterministisch.

Answer

Turingmaschinen können nur endliche Zustände annehmen.

Answer

Turingmaschinen können Lambda-Übergänge ausführen.

Question 7

Welche Eigenschaft ist charakteristisch für einen deterministischen endlichen Automaten (DFA)?

Accepted Answer

Er folgt für jede Eingabe immer demselben Pfad.

Answer

Er besitzt nur einen Startzustand.

Answer

Er kann alle Sprachen erkennen.

Answer

Er hat möglicherweise keine Endzustände.

Question 8

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

Accepted Answer

a^n b^n c^m

Answer

a*b

Answer

a^2b^3

Answer

(ab)*

Question 9

Welche Eigenschaft ist typisch für endliche Automaten?

Accepted Answer

Sie haben eine begrenzte Anzahl von Zuständen.

Answer

Sie können alle Sprachen erkennen.

Answer

Sie können keine leeren Zeichenketten verarbeiten.

Answer

Sie können alle rekursiven Sprachen erkennen.

Question 10

Welche Eigenschaft trifft auf endliche Automaten zu?

Accepted Answer

Sie können deterministisch oder nicht-deterministisch sein.

Answer

Sie können eine beliebige Anzahl von Zuständen haben.

Answer

Sie können unendlich lange Eingaben verarbeiten.

Answer

Sie sind äquivalent zu Grammatiken.

Question 11

Was ist die herausragende Eigenschaft von **Turingmaschinen**?

Accepted Answer

Sie können jede berechenbare Funktion ausführen, da sie universell berechenbar sind.

Answer

Sie treffen keine zufälligen Entscheidungen, da sie deterministisch sind.

Answer

Sie sind auf endliche Eingaben beschränkt, was ihre Verwendung einschränkt.

Answer

Sie benötigen immer eine begrenzte Anzahl von Schritten, um eine Berechnung abzuschließen.

Question 12

Welche Methoden eignen sich besonders für die Optimierung von Problemen mit mehreren Zielsetzungen?

Accepted Answer

Gewichtete Summenmethode

Accepted Answer

Epsilon-Constraint-Methode

Answer

Lineare Programmierung

Answer

Dynamische Programmierung

Question 13

Welche Optimierungsmethode ist für Probleme mit mehreren gleichwertigen Zielsetzungen geeignet?

Accepted Answer

Multi-Ziel-Optimierung

Answer

Greedy-Algorithmus

Answer

Dynamische Programmierung

Question 14

Wie funktioniert eine Universelle Turingmaschine (UTM)?

Accepted Answer

Sie arbeitet mit einem begrenzten Satz von Anweisungen und kann jede berechenbare Funktion simulieren.

Answer

Sie benötigt immer endlich viele Schritte, um eine Eingabe zu verarbeiten und gibt immer ein Ergebnis aus.

Answer

Sie ist ein nichtdeterministischer Automat, der sich in jedem Schritt nicht eindeutig verhält.

Answer

Sie kann alle Probleme lösen, die von einem endlichen Automaten gelöst werden können.

Question 15

Welche Aussage beschreibt die Komplexitätstheorie am besten?

Accepted Answer

Sie untersucht die Ressourcen, die Algorithmen zur Problemlösung benötigen.

Answer

Sie konzentriert sich nur auf die Entwicklung effizienter Algorithmen für alle Eingaben.

Answer

Sie analysiert mathematische Strukturen zur Untersuchung von Programmeigenschaften.

Answer

Sie ist ein rein theoretisches Konzept ohne praktische Bedeutung.

Question 16

Welche Hauptaufgabe erfüllt der Stapelspeicher in einem Pushdown-Automaten (PDA)?

Accepted Answer

Zwischenspeicherung von Symbolen für die Verarbeitung beliebig langer Eingabewörter

Answer

Speicherung des aktuellen Automatenzustands

Answer

Ablage der Übergangsregeln des Automaten

Answer

Speicherung der vom PDA erkannten Sprache

Question 17

Was ist die beste Beschreibung einer Turingmaschine?

Accepted Answer

Ein theoretisches Modell für einen Computer mit unendlichem Speicher.

Answer

Ein reales Gerät, das alle Probleme lösen kann.

Answer

Ein endlicher Automat mit begrenztem Speicher.

Answer

Eine Computersimulation, die nur grundlegende Operationen ausführt.

Question 18

Welcher wesentliche Unterschied in den Verarbeitungsfähigkeiten ergibt sich aus dem Stapelspeicher eines Pushdown-Automaten (PDA) im Vergleich zu einem endlichen Automaten (FA)?

Accepted Answer

PDAs können verschachtelte Strukturen wie Klammerpaare erkennen, FAs hingegen nicht.

Answer

FAs können nicht-deterministische Übergänge ausführen, PDAs hingegen nicht.

Answer

PDAs können keine Zeichenfolgen über einem endlichen Alphabet verarbeiten, FAs hingegen schon.

Answer

FAs können kontextfreie Sprachen erkennen, PDAs hingegen nicht.

Question 19

Welche Aussage über Turingmaschinen trifft zu?

Accepted Answer

Sie können alle berechenbaren Funktionen berechnen.

Answer

Sie sind ausschließlich deterministisch.

Answer

Das Halteproblem für sie ist lösbar.

Answer

Sie sind auf eine endliche Anzahl von Zuständen beschränkt.

Question 20

Was ist die beste Beschreibung der Komplexitätstheorie?

Accepted Answer

Die Lehre von der Berechenbarkeit und den Grenzen von Berechnungen.

Answer

Die Untersuchung der Eigenschaften formaler Sprachen und Automaten.

Answer

Die Entwicklung neuer Algorithmen für die Lösung komplexer Probleme.

Answer

Die Untersuchung der sozialen Auswirkungen der Technologie.

Question 21

Was ist der Hauptunterschied zwischen deterministischen und nicht-deterministischen endlichen Automaten?

Accepted Answer

Deterministische Automaten folgen einer eindeutigen Eingabekette, während nicht-deterministische Automaten mehrere mögliche Ketten zulassen.

Answer

Deterministische Automaten erkennen nur reguläre Sprachen, nicht-deterministische Automaten auch nicht-reguläre Sprachen.

Answer

Deterministische Automaten sind immer effizienter als nicht-deterministische Automaten.

Question 22

Welche praktischen Anwendungen hat die Theoretische Informatik in anderen Fachbereichen wie Linguistik, Biologie oder Kognitionswissenschaft?

Accepted Answer

Textanalyse und Spracherkennung in der Linguistik

Accepted Answer

Modellierung biologischer Systeme in der Bioinformatik

Accepted Answer

Entwicklung von KI-Algorithmen in der Kognitionswissenschaft

Answer

Optimierung von Verkehrssystemen in der Verkehrsforschung

Question 23

Welche Bedeutung haben aktuelle Forschungsthemen in der Theoretischen Informatik für das Fachgebiet?

Accepted Answer

Sie erweitern die theoretischen Grundlagen und treiben technologischen Fortschritt voran.

Answer

Sie konzentrieren sich nur auf theoretische Probleme ohne praktische Relevanz.

Answer

Sie sind nur für Informatikexperten interessant und haben keine Auswirkungen auf andere Bereiche.

Answer

Sie sind bereits vollständig gelöst und haben keine offenen Fragen mehr.

Question 24

Wie lässt sich entscheiden, ob ein Wort zur formalen Sprache L = {w : w enthält eine gerade Anzahl an 'a's} gehört?

Accepted Answer

Überprüfen, ob die Anzahl der 'a's im Wort gerade ist.

Answer

Überprüfen, ob das Wort mit 'a' beginnt oder endet.

Answer

Überprüfen, ob das Wort eine ungerade Anzahl an 'a's enthält.

Question 25

Wie hilft die Komplexitätstheorie bei der Untersuchung von Algorithmen?

Accepted Answer

Sie ordnet Probleme nach Schwierigkeit und findet effiziente Algorithmen für bestimmte Probleme.

Answer

Sie beweist die Richtigkeit von Algorithmen.

Answer

Sie verkürzt die Laufzeit von Algorithmen.

Answer

Sie hat nur theoretische Bedeutung und keine praktische Anwendung.

Question 26

Beweisen Sie, dass die Sprache L = {w : w enthält eine ungerade Anzahl an 'a's} nicht regulär ist. Verwenden Sie dazu das Pumping-Lemma für reguläre Sprachen.

Accepted Answer

Verwenden Sie das Pumping-Lemma für reguläre Sprachen.

Answer

Konstruieren Sie einen minimalen DFA für L.

Answer

Überprüfen Sie, ob L von einem NFA aktzeptiert wird.

Question 27

Das Halteproblem fragt, ob man für eine Turingmaschine und eine Eingabe entscheiden kann, ob die Turingmaschine bei dieser Eingabe:

Accepted Answer

anhält

Answer

eine gerade Anzahl von Zuständen hat

Answer

eine unendliche Schleife durchläuft

Question 28

Welche Aussage beschreibt die Rolle der universellen Turingmaschine im Vergleich zu anderen Turingmaschinen am zutreffendsten?

Accepted Answer

Eine universelle Turingmaschine kann jede berechenbare Funktion ausführen.

Answer

Eine universelle Turingmaschine ist eine spezielle Art einer regulären Turingmaschine.

Answer

Eine reguläre Turingmaschine kann eine universelle Turingmaschine simulieren.

Answer

Eine universelle Turingmaschine hat begrenzte Fähigkeiten.

Question 29

Welche ethische Verantwortung tragen Informatiker*innen im Umgang mit theoretischen Konzepten? Erläutern Sie, wie diese Konzepte die Gesellschaft beeinflussen können.

Accepted Answer

Theoretische Konzepte können für gesellschaftlichen Fortschritt genutzt werden, erfordern aber eine Abwägung von Chancen und Risiken.

Answer

Theoretische Konzepte sind ethisch neutral und ihre Auswirkungen hängen von ihrer Anwendung ab.

Answer

Informatiker*innen sollten sich nur auf die Entwicklung neutraler Technologien konzentrieren.

Question 30

Wie beeinflusst die hierarchische Struktur der Chomsky-Hierarchie die Berechnungskomplexität formaler Sprachen?

Accepted Answer

Die Chomsky-Hierarchie ordnet Sprachen nach ihrer Komplexität, wobei einfachere Sprachen unten und komplexere Sprachen oben stehen.

Answer

Die Chomsky-Hierarchie hat keinen Einfluss auf die Berechnungskomplexität.

Answer

Nur kontextfreie Sprachen sind berechenbar.

Answer

Die Berechnungskomplexität hängt nur von der Länge der Sprache ab.

Question 31

Erstellen Sie eine formale Grammatik für eine Sprache, die alle Zeichenketten über dem Alphabet {a, b} enthält, die eine gerade Anzahl von 'a's und eine ungerade Anzahl von 'b's aufweisen.

Accepted Answer

S -> aTb | bSa

Answer

S -> aS | bS

Answer

S -> aT | bT

Answer

S -> T | B

Question 32

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

Accepted Answer

Die Menge aller Turingmaschinen, die anhalten

Answer

Die Menge aller Palindrome

Answer

Die Menge aller Primzahlen

Answer

Die Menge aller Programme in einer bestimmten Programmiersprache

Question 33

Welches Konzept ist eine Verallgemeinerung von regulären Ausdrücken?

Accepted Answer

Kontextfreie Grammatiken

Answer

Kellerautomaten

Answer

Turingmaschinen

Answer

Logische Formeln

Question 34

Nennen Sie die verschiedenen Ansätze zur Klassifizierung formaler Sprachen und erläutern Sie deren Vor- und Nachteile.

Accepted Answer

Chomsky-Hierarchie

Accepted Answer

Akzeptanzkriterien

Accepted Answer

Grammatiktyp

Question 35

Nennen Sie praktische Anwendungen der Theoretischen Informatik in den Bereichen Künstliche Intelligenz, maschinelles Lernen und Kryptographie.

Accepted Answer

Modellierung und Analyse von Algorithmen in KI und maschinellem Lernen.

Answer

Keine praktischen Anwendungen in diesen Bereichen.

Answer

Ausschließlich relevant für Kryptographie.

Answer

Keine Rolle bei der Entwicklung von KI-Systemen.

Question 36

Welche der folgenden Rechenmodelle hat **nicht** die gleiche Berechnungskompetenz wie eine Turingmaschine?

Accepted Answer

Nichtdeterministischer endlicher Automat

Answer

Registermaschine

Answer

Lambda-Kalkül

Answer

Post-Maschine

Question 37

Welche der folgenden Aussagen über formale Sprachen trifft zu?

Accepted Answer

Sie können sowohl endlich als auch unendlich sein.

Answer

Sie sind immer kontextfrei.

Answer

Sie werden nicht in der Informatik verwendet.

Answer

Sie sind alle endlich.

Question 38

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

Accepted Answer

Es ist ein Satz, der die Eigenschaften aller regulären Sprachen beschreibt.

Answer

Es ist eine Methode, einen regulären Ausdruck für eine Sprache zu konstruieren.

Answer

Es ist ein Algorithmus, der einen endlichen Automaten in einen regulären Ausdruck umwandelt.

Answer

Es ist ein Verfahren zum Testen der Gültigkeit eines regulären Ausdrucks.

Question 39

Was ist das Beweisverfahren der Widerspruchsannahme?

Accepted Answer

Es ist ein Beweisverfahren, das eine Annahme als wahr annimmt und versucht, daraus einen Widerspruch abzuleiten.

Answer

Es ist ein Beweisverfahren, das eine Aussage für alle natürlichen Zahlen beweist.

Answer

Es ist ein heuristisches Verfahren, das zur Lösung von Problemen verwendet wird.

Answer

Es ist ein axiomatisches Beweisverfahren, das auf einer Menge von Axiomen basiert.

Question 40

Welche Aussage über Turingmaschinen ist falsch?

Accepted Answer

Sie haben einen begrenzten Zustandsraum.

Answer

Sie stellen ein universelles Berechnungsmodell dar.

Answer

Sie können Probleme lösen, die nicht durch endliche Automaten lösbar sind.

Answer

Sie können beliebige Algorithmen simulieren.

Question 41

Was ist das Halteproblem?

Accepted Answer

Das Problem festzustellen, ob eine Turingmaschine auf einer gegebenen Eingabe anhält oder nicht anhält.

Answer

Das Problem festzustellen, ob ein gegebenes Problem berechenbar ist.

Answer

Das Problem festzustellen, ob ein gegebener Graph einen Hamiltonkreis enthält.

Answer

Das Problem festzustellen, ob ein gegebenes Programm semantisch korrekt ist.

Question 42

Welche Aussage beschreibt die grundlegenden Eigenschaften einer Turingmaschine am besten?

Accepted Answer

Eine Turingmaschine ist ein theoretisches Modell eines Computers, der Berechnungen auf einem unendlich langen Band ausführen kann.

Answer

Eine Turingmaschine kann nur reguläre Sprachen erkennen.

Answer

Eine Turingmaschine ist auf die Verarbeitung endlich langer Eingaben beschränkt.

Answer

Eine Turingmaschine ist ein nichtdeterministischer Automat.

Question 43

Wie verknüpft der Satz von Chomsky-Schützenberger formale Sprachen, Automatentheorie und Komplexitätstheorie?

Accepted Answer

Er ordnet jeder Sprachklasse eine Automatenklasse zu.

Answer

Er besagt, dass kontextfreie Sprachen regulär sind.

Answer

Er definiert Entscheidbarkeit und Nicht-Entscheidbarkeit.

Answer

Er ist die Grundlage für Turing-Maschinen.

Question 44

Wie trägt die Theoretische Informatik zur Entwicklung sicherer Verschlüsselungsprotokolle bei?

Accepted Answer

Sie bietet mathematische Werkzeuge zur Analyse der Sicherheit von Verschlüsselungsprotokollen.

Answer

Sie entwickelt die Algorithmen für Verschlüsselungsprotokolle.

Answer

Sie ist für die Entwicklung von Verschlüsselungsprotokollen irrelevant.

Answer

Sie entwirft die Hardware für die Implementierung von Verschlüsselungsprotokollen.

Question 45

Was besagt die Halteproblematik und welche Folgen hat sie für die Informatik, insbesondere für KI und Softwareentwicklung?

Accepted Answer

Es gibt keinen Algorithmus, der für jedes Programm und jede Eingabe entscheiden kann, ob das Programm anhält.

Answer

Die Halteproblematik gilt nur für Programme in bestimmten Programmiersprachen.

Answer

Die Halteproblematik hat keine Auswirkungen auf die praktische Informatik.

Answer

Paralleles Rechnen kann die Halteproblematik lösen.

Question 46

Was ist die definierende Eigenschaft eines deterministischen endlichen Automaten (DFA)?

Accepted Answer

Für jede Eingabe und jeden Zustand existiert genau eine Transition.

Answer

Für jede Eingabe und jeden Zustand existiert mindestens eine Transition.

Answer

Der Automat akzeptiert nur leere Zeichenfolgen

Question 47

Welche Zeichenfolgenmenge wird durch den regulären Ausdruck (a|b)* beschrieben?

Accepted Answer

Alle Zeichenfolgen, die nur aus 'a' und 'b' bestehen

Answer

Alle Zeichenfolgen, die mit 'a' oder 'b' beginnen

Answer

Alle Zeichenfolgen, die 'a' nicht enthalten

Question 48

Welcher Automatentyp kann genau die kontextfreien Sprachen erkennen?

Accepted Answer

Pushdown-Automat

Answer

Deterministischer endlicher Automat

Answer

Nichtdeterministischer endlicher Automat

Answer

Turingmaschine

Question 49

Welche Aussage zur Church-Turing-These ist korrekt?

Accepted Answer

Jede berechenbare Funktion kann von einer Turingmaschine berechnet werden.

Answer

Jede intuitiv berechenbare Funktion kann durch einen Computer berechnet werden.

Question 50

Welche Eigenschaft trifft auf Turingmaschinen zu?

Accepted Answer

Turingmaschinen können jeden Algorithmus ausführen.

Answer

Turingmaschinen haben immer eine eindeutige Akzeptanz-Entscheidung.

Question 51

Was ist der Hauptunterschied zwischen deterministischen und nichtdeterministischen Turingmaschinen?

Accepted Answer

Nichtdeterministische Turingmaschinen können Sackgassen betreten.

Answer

Nichtdeterministische Turingmaschinen haben immer eine eindeutige Akzeptanz-Entscheidung.

Question 52

Welche der folgenden Sprachen ist nicht rekursiv aufzählbar?

Accepted Answer

Die Menge aller Turingmaschinen, die auf einem leeren Band anhalten

Answer

Die Menge aller Palindrome

Answer

Die Menge aller Zeichenfolgen, die den Buchstaben 'a' enthalten

Question 53

Welche Rolle spielt die Theoretische Informatik bei der Entwicklung und dem Verständnis künstlicher neuronaler Netze?

Accepted Answer

Sie bietet Methoden zur Modellierung und Analyse neuronaler Netze.

Answer

Sie ermöglicht die Optimierung der Implementierung neuronaler Netze.

Answer

Sie hat keine direkte Bedeutung für künstliche neuronale Netze.

Question 54

Welche Aussage über formale Sprachen beschreibt korrekt ihre grundlegende Eigenschaft?

Accepted Answer

Sie definieren eine Menge von Zeichenfolgen, die bestimmten syntaktischen Regeln folgen.

Answer

Sie werden ausschließlich zur Beschreibung natürlicher Sprachen verwendet.

Answer

Sie beschreiben die Syntax sämtlicher Programmiersprachen.

Question 55

Welche Eigenschaft ist charakteristisch für eine Turingmaschine?

Accepted Answer

Sie besitzt universelle Berechnungsmöglichkeiten.

Answer

Sie arbeitet stets deterministisch.

Answer

Sie benötigt unendlich viel Speicherplatz.

Answer

Sie kann keine unendlichen Eingaben verarbeiten.

Question 56

Welches Problem gilt als nicht entscheidbar?

Accepted Answer

Halteproblem

Answer

Primzahltest

Answer

Sortierproblem

Answer

Hamiltonkreisproblem

Question 57

Welche Aussage über NP-vollständige Probleme trifft zu?

Accepted Answer

Ihre effiziente Lösbarkeit ist nicht gegeben.

Answer

Sie können ausschließlich durch Brute-Force-Suche gelöst werden.

Answer

Sie sind stets entscheidbar.

Answer

Sie weisen immer eine polynomielle Laufzeit auf.

Question 58

Welcher Beweisansatz wird herangezogen, um die Unentscheidbarkeit des Halteproblems zu belegen?

Accepted Answer

Diagonalisierungsargument

Answer

Induktionsbeweis

Answer

Kontradiktion

Question 59

Welche der folgenden Sprachen ist nicht kontextfrei?

Accepted Answer

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

Answer

{a^n | n ≥ 0}

Answer

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

Answer

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

Question 60

Was ist das Halteproblem?

Accepted Answer

Das Problem zu bestimmen, ob ein beliebiges Programm für eine beliebige Eingabe terminiert.

Answer

Das Problem, das kürzeste Programm zu finden, das ein bestimmtes Problem löst.

Answer

Das Problem, die Laufzeit eines Programms für eine bestimmte Eingabe vorherzusagen.

Question 61

Was ist eine Turing-Maschine?

Accepted Answer

Ein abstraktes Rechenmodell, das aus einem unendlich langen Band, einem Lese-/Schreibkopf und einem endlichen Satz von Anweisungen besteht.

Answer

Ein realer Computer, der alle möglichen Probleme lösen kann.

Question 62

Welche der folgenden Aussagen über Turing-Maschinen ist richtig?

Accepted Answer

Turing-Maschinen sind universell, d. h. sie können jede berechenbare Funktion berechnen.

Answer

Turing-Maschinen sind immer deterministisch.

Answer

Turing-Maschinen haben immer eine endliche Anzahl von Zuständen.

Question 63

Was besagt die Church-Turing-These?

Accepted Answer

Jede berechenbare Funktion kann von einer Turing-Maschine berechnet werden.

Answer

Turing-Maschinen sind das einfachste mögliche Rechenmodell.

Answer

Alle Probleme können in endlicher Zeit von einem Computer gelöst werden.

Question 64

Welche der folgenden Anwendungen nutzt Konzepte aus der Theoretischen Informatik?

Accepted Answer

Compilerbau

Answer

Webentwicklung

Answer

Grafikdesign

Answer

Datenbankanwendungen