Theoretische Informatik II: Fortgeschrittene Konzepte für Informatik-Studenten

Question 1

Welche grundlegende Einschränkung gilt für Turing-Maschinen?

Accepted Answer

Sie können nur eine begrenzte Anzahl verschiedener Symbole auf ihrem Band speichern.

Answer

Sie können auf jedem Eingabeband in endlicher Zeit anhalten.

Answer

Sie können keine Funktionen berechnen, die in modernen Programmiersprachen implementiert werden können.

Answer

Sie führen ausschließlich deterministische Berechnungen durch.

Question 2

Welche Aussage beschreibt eine Turing-Maschine zutreffend?

Accepted Answer

Ein theoretisches Modell für eine Rechenmaschine mit unbegrenztem Speicher

Answer

Ein praktisches Werkzeug zur Lösung realer Probleme

Answer

Eine Maschine, die nur polynomial zeitlösbare Probleme lösen kann

Answer

Eine spezialisierte Maschine zur Berechnung von Zahlenfolgen

Question 3

Welche Eigenschaft ist charakteristisch für deterministische endliche Automaten?

Accepted Answer

Sie erlauben keine Eingabefolgen, die zu mehreren Endzuständen führen.

Answer

Sie erkennen alle Sprachen, die durch reguläre Ausdrücke beschrieben werden können.

Answer

Sie besitzen einen Startzustand, aber keine Endzustände.

Answer

Ihre Anzahl an Zuständen hängt von der Länge der akzeptierten Eingabefolgen ab.

Question 4

Welche Eigenschaft von Pushdown-Automaten ist zutreffend?

Accepted Answer

Sie können verschachtelte Strukturen verarbeiten.

Answer

Sie sind immer deterministisch.

Answer

Sie erkennen nur reguläre Sprachen.

Answer

Sie können keine leeren Stapel verarbeiten.

Question 5

Welches der folgenden Probleme ist ein klassisches NP-vollständiges Problem, das sich auf die Suche nach kürzesten Pfaden in Graphen bezieht?

Accepted Answer

Das Hamiltonzyklusproblem

Answer

Das Sortierproblem

Answer

Das Primzahltestproblem

Answer

Das Schachproblem

Question 6

Welche Aussage über Kontextfreie Grammatiken (CFGs) ist definitiv falsch?

Accepted Answer

CFGs können alle in der realen Welt vorkommenden Sprachen generieren.

Answer

CFGs sind leistungsfähiger als reguläre Ausdrücke.

Answer

Die linke Seite einer CFG-Regel kann mehrere Symbole enthalten.

Question 7

Welche der folgenden Optionen ist eine formale Sprache, die **nicht** kontextfrei ist?

Accepted Answer

Unendliche kontextfreie Grammatik

Answer

Reguläre Ausdrücke

Answer

Endliche Automaten

Answer

Pushdown-Automaten

Question 8

Welcher Softwareentwicklungsansatz zeichnet sich durch einen schrittweisen Prozess aus, der Flexibilität und Anpassungsfähigkeit priorisiert?

Accepted Answer

Agiler Ansatz

Answer

Wasserfallmodell

Answer

Spiralmodell

Question 9

Welche Komponente eines Betriebssystems ist für die Verwaltung des Zugriffs auf die Hardware verantwortlich?

Accepted Answer

Kernel

Answer

Shell

Answer

Dateisystem

Answer

Speicherverwaltung

Question 10

Welche Datenstruktur ermöglicht in allen Fällen einen konstanten, positionsunabhängigen Zugriff auf ihre Elemente?

Accepted Answer

Hashtabelle

Answer

Verkettete Liste

Answer

Binärbaum

Answer

Heap

Question 11

Welche Eigenschaft trifft auf Pushdown-Automaten zu?

Accepted Answer

Ihre Eingabe wird auf einem Stapel gespeichert.

Answer

Sie können jede Sprache erkennen.

Answer

Sie erkennen nur reguläre Ausdrücke.

Question 12

Welche Komponente in einem Computersystem ist für die Verwaltung des Arbeitsspeichers und dessen Zuweisung an Prozesse verantwortlich?

Accepted Answer

MMU

Answer

CPU

Answer

SSD

Answer

RAM

Question 13

Welche Eigenschaft ist für Turing-Maschinen charakteristisch?

Accepted Answer

Berechnung aller berechenbaren Funktionen

Answer

Begrenzte Anzahl von Zuständen und Symbolen

Answer

Sowohl deterministische als auch nicht-deterministische Ausführung

Question 14

Welche Hauptaufgabe übernimmt ein Betriebssystem?

Accepted Answer

Verwaltung von Prozessen und Speicher

Answer

Ausführung von Anwendungssoftware

Answer

Speicherung von Nutzerdaten

Answer

Bereitstellung einer grafischen Oberfläche

Question 15

Welche der folgenden Aussagen über Turing-Maschinen, die die Sprache L = {w | w ist ein Palindrom} erkennen, ist richtig?

Accepted Answer

Eine nichtdeterministische Turing-Maschine kann L in linearer Zeit erkennen.

Answer

Eine deterministische Turing-Maschine kann L in linearer Zeit erkennen.

Answer

Es gibt keine Turing-Maschine, die L erkennt.

Question 16

Was ist die zutreffendste Beschreibung des Konzepts der Vererbung in der objektorientierten Programmierung?

Accepted Answer

Unterklassen können Eigenschaften und Methoden von Oberklassen übernehmen und erweitern.

Accepted Answer

Vererbung ermöglicht es, Code wiederzuverwenden, indem er von anderen Klassen geerbt wird.

Answer

Vererbung dient dazu, mehrere Objekte eines Typs in einer Datenstruktur zu gruppieren.

Question 17

Welche Aussage über die Komplexitätsklasse NP-vollständig ist zutreffend?

Accepted Answer

Wenn ein Problem auf ein NP-vollständiges Problem reduziert werden kann, ist es ebenfalls NP-vollständig.

Answer

NP-vollständige Probleme können in polynomialer Zeit gelöst werden.

Answer

NP-vollständige Probleme können nur durch Brute-Force-Suche gelöst werden.

Question 18

Welche Eigenschaft ist charakteristisch für eine reguläre Sprache?

Accepted Answer

Erkennbar durch einen endlichen Automaten

Answer

Erzeugbar durch eine kontextfreie Grammatik

Answer

Nicht erkennbar durch eine Turing-Maschine

Question 19

Welche Eigenschaft trifft auf **deterministische** endliche Automaten zu?

Accepted Answer

Sie können nur reguläre Sprachen erkennen.

Answer

Sie können nicht-deterministisch sein.

Answer

Sie können unendlich viele Zustände haben.

Answer

Sie können unendlich viele Eingabezeichen verarbeiten.

Question 20

Welche der folgenden Aussagen beschreibt die Komplexitätsklasse NP korrekt?

Accepted Answer

NP umfasst Probleme, für die Lösungen in polynomieller Zeit nichtdeterministisch überprüft werden können.

Answer

NP umfasst Probleme, für die eine Lösung in exponentieller Zeit deterministisch gefunden werden kann.

Answer

NP umfasst Optimierungsprobleme, für die in polynomieller Zeit nichtdeterministisch optimale Lösungen gefunden werden können.

Answer

NP umfasst alle Probleme, für die eine Lösung in polynomieller Zeit deterministisch gefunden werden kann.

Question 21

Welche der folgenden Aussagen über endliche Automaten ist NICHT korrekt?

Accepted Answer

Endliche Automaten können alle Sprachen erkennen.

Answer

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

Question 22

Unterscheiden Sie zwischen deterministischen und nicht-deterministischen Turing-Maschinen. Nennen Sie für jeden Typ ein Beispiel.

Accepted Answer

Deterministisch: Für jeden Zustand und jedes Bandsymbol gibt es nur eine mögliche Aktion. Beispiel: Zählen von Nullen.

Accepted Answer

Nicht-deterministisch: Für jeden Zustand und jedes Bandsymbol gibt es möglicherweise mehrere mögliche Aktionen. Beispiel: Finden eines Weges in einem Labyrinth.

Answer

Falsch: Deterministische Turing-Maschinen können sich in beide Richtungen bewegen.

Answer

Falsch: Nicht-deterministische Turing-Maschinen haben immer nur ein Band.

Question 23

Was sind die grundlegenden Prinzipien der Kryptographie und warum ist sie für die Sicherheit moderner Computersysteme von entscheidender Bedeutung?

Accepted Answer

Kryptographie schützt Privatsphäre und Vertraulichkeit durch Verschlüsselung und Entschlüsselung von Nachrichten.

Accepted Answer

Kryptographie umfasst mathematische Algorithmen und Protokolle für kryptographische Vorgänge.

Answer

Kryptographie ist nur für militärische Zwecke relevant und hat keine Auswirkungen auf alltägliche Computersysteme.

Question 24

Welche ethischen Bedenken bestehen bei der Entwicklung und dem Einsatz von KI? Nennen Sie Maßnahmen zur Minimierung potenzieller Risiken.

Accepted Answer

KI kann Arbeitsplätze vernichten und soziale Probleme verursachen.

Accepted Answer

KI kann für gefährliche Technologien wie Waffen missbraucht werden.

Accepted Answer

KI kann zur Überwachung und Kontrolle von Menschen eingesetzt werden und die Privatsphäre verletzen.

Answer

KI hat keine ethischen Auswirkungen, da sie nur ein Werkzeug ist.

Question 25

Welche Aussage beschreibt die Church-Turing-These korrekt?

Accepted Answer

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

Answer

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

Answer

Jede Turing-Maschine kann jede beliebige Funktion berechnen.

Question 26

Welche Aussage beschreibt die Komplexitätsklasse P korrekt?

Accepted Answer

P enthält Probleme, die auf einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden können.

Answer

P ist identisch mit NP.

Answer

P umfasst Probleme, die auf einer probabilistischen Turingmaschine in exponentieller Zeit gelöst werden können.

Answer

P ist eine überabzählbare Menge.

Question 27

Nenne die wichtigsten Eigenschaften einer Turing-Maschine.

Accepted Answer

Ein unendliches Band zur Datenspeicherung und ein Lese-/Schreibkopf zur Datenverarbeitung.

Answer

Ein physisches Gerät zur Lösung aller Probleme.

Answer

Ein Algorithmus mit einer begrenzten Anzahl von Schritten zur Lösung aller endlichen Probleme.

Question 28

Erläutern Sie die Bedeutung ethischer Überlegungen bei der Entwicklung und dem Einsatz von KI. Begründen Sie Ihre Antwort.

Accepted Answer

Ethik ist entscheidend für die Entwicklung von KI-Systemen, die mit menschlichen Werten übereinstimmen und verantwortungsvoll eingesetzt werden können.

Answer

Ethik ist irrelevant für die KI-Entwicklung, da es sich um technische Probleme handelt.

Answer

Ethik dient lediglich dazu, Fehlerfreiheit und Unvoreingenommenheit von KI-Systemen sicherzustellen.

Answer

Ethik betrifft nur KI-Forscher und hat keine Auswirkungen auf den praktischen Einsatz von KI.

Question 29

Heuristiken sind ein wichtiger Bestandteil der Problemlösung. Erläutern Sie ihre Rolle bei der Bewältigung komplexer Probleme und nennen Sie Beispiele für ihre praktische Anwendung.

Accepted Answer

Heuristiken sind grobe Richtlinien, die auf Erfahrungswerten basieren und oft zu guten, aber nicht unbedingt optimalen Lösungen führen.

Answer

Heuristiken sind exakte Algorithmen, die immer die optimale Lösung für ein Problem liefern.

Answer

Heuristiken sind Algorithmen, die garantiert eine Lösung für jedes Problem finden.

Question 30

Welche der folgenden Verschlüsselungsmethoden ist eine symmetrische Verschlüsselungsanwendung?

Accepted Answer

AES

Answer

RSA

Answer

Diffie-Hellman

Answer

ElGamal

Question 31

Welche Rolle spielen Heuristiken bei der Bewältigung von NP-schwierigen Problemen?

Accepted Answer

Heuristiken liefern oft gute Näherungslösungen für NP-schwierige Probleme und ermöglichen eine effizientere Problemlösung.

Answer

Heuristiken garantieren optimale Lösungen für NP-schwierige Probleme.

Answer

Heuristiken ermöglichen es, NP-schwierige Probleme in polynomialer Zeit zu lösen.

Question 32

Erläutere die Äquivalenz zwischen deterministischen endlichen Automaten (DFA) und regulären Ausdrücken (RE).

Accepted Answer

Zu jedem regulären Ausdruck, der eine Sprache beschreibt, existiert ein äquivalenter DFA.

Accepted Answer

Zu jedem DFA existiert ein äquivalenter regulärer Ausdruck, der dieselbe Sprache akzeptiert.

Answer

DFAs sind immer effizienter als REs bei der Spracherkennung.

Answer

REs können nur endliche Sprachen beschreiben.

Question 33

Welche Aussage beschreibt die Church-Turing-These korrekt?

Accepted Answer

Alle Funktionen, die von einem Algorithmus berechnet werden können, können auch von einer Turingmaschine berechnet werden.

Answer

Alle Funktionen, die von einer Turingmaschine berechnet werden können, können auch von einem Algorithmus berechnet werden.

Answer

Nur Turingmaschinen können berechenbare Funktionen definieren.

Answer

Nicht berechenbare Funktionen können von Turingmaschinen berechnet werden.

Question 34

Beschreibe die Bedeutung von Heuristiken bei der Bewältigung komplexer NP-vollständiger Probleme. Nenne ein konkretes Beispiel für eine Heuristik, die bei solchen Problemen eingesetzt wird.

Accepted Answer

Heuristiken sind effiziente Näherungsverfahren, die schnell Lösungen für NP-vollständige Probleme liefern, die möglicherweise nicht optimal sind.

Answer

Heuristiken sind exakte Algorithmen, die NP-vollständige Probleme in Polynomialzeit lösen.

Answer

Heuristiken sind für NP-vollständige Probleme nutzlos, da sie keine brauchbaren Lösungen liefern.

Question 35

Warum sind ethische Überlegungen bei der Entwicklung und dem Einsatz von KI wichtig?

Accepted Answer

Ethische Überlegungen gewährleisten eine verantwortungsvolle KI-Entwicklung und -Nutzung.

Answer

Ethische Überlegungen sind für die KI-Entwicklung unerheblich.

Answer

Ethische Überlegungen behindern den Fortschritt der KI-Entwicklung.

Answer

Ethische Überlegungen betreffen nur KI-Forscher.

Question 36

Welcher der folgenden Algorithmen verwendet eine symmetrische Verschlüsselung?

Accepted Answer

AES

Answer

RSA

Answer

ECC

Question 37

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

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 38

Welches kryptografische Protokoll verwendet den Diffie-Hellman-Schlüsselaustausch für eine sichere Kommunikation?

Accepted Answer

DH

Answer

RSA

Answer

AES

Answer

DES

Question 39

Welche Aussage über deterministische endliche Automaten (DFAs) ist korrekt?

Accepted Answer

DFAs können alle regulären Sprachen erkennen.

Answer

DFAs können alle kontextfreien Sprachen erkennen.

Answer

DFAs können nur endliche Sprachen erkennen.

Answer

DFAs können nur unendliche Sprachen erkennen.

Question 40

Welches kryptografische Verfahren kombiniert eine Transpositions- und eine Substitutionschiffre?

Accepted Answer

Vignère-Chiffre

Answer

Caesar-Chiffre

Answer

RSA

Answer

DES

Question 41

Welche Aussage über Hash-Funktionen ist korrekt?

Accepted Answer

Hash-Funktionen erzeugen einen eindeutigen Fingerabdruck für eine gegebene Eingabe.

Answer

Hash-Funktionen sind extrem langsam zu berechnen.

Answer

Hash-Funktionen können keine Kollisionen verursachen.

Answer

Hash-Funktionen können nur für Zeichenfolgen verwendet werden.

Question 42

Welche Aussage beschreibt NP-Vollständigkeit korrekt?

Accepted Answer

Wenn ein Problem NP-vollständig ist, können alle anderen NP-Probleme in polynomialer Zeit darauf reduziert werden.

Answer

NP-vollständige Probleme können immer in polynomialer Zeit gelöst werden.

Answer

NP-vollständige Probleme haben immer eine exponentielle Worst-Case-Komplexität.

Answer

NP-Vollständigkeit gilt nur für Entscheidungsprobleme.

Question 43

Inwiefern tragen Turing-Maschinen zur Entwicklung von KI-Systemen bei? Erläutern Sie ihre Rolle bei der Modellierung kognitiver Prozesse.

Accepted Answer

Turing-Maschinen ermöglichen die Simulation menschlicher Denkprozesse und unterstützen so die Entwicklung von KI-Systemen.

Answer

Turing-Maschinen sind rein theoretische Konzepte ohne praktische Bedeutung für die KI-Entwicklung.

Answer

Turing-Maschinen haben aufgrund ihrer begrenzten Rechenleistung keinen direkten Einfluss auf die KI-Entwicklung.

Question 44

Welche Technik im maschinellen Lernen zielt darauf ab, die Fähigkeit eines Modells zu verbessern, auf ungesehene Daten zu verallgemeinern?

Accepted Answer

Regularisierung

Answer

Kreuzvalidierung

Answer

Merkmalsauswahl

Question 45

Wie tragen Heuristiken zur Bewältigung NP-schwerer Probleme bei?

Accepted Answer

Heuristiken liefern in akzeptabler Zeit gute, aber nicht unbedingt optimale Lösungen für NP-schwere Probleme.

Answer

Heuristiken finden immer die exakte Lösung eines NP-schweren Problems in angemessener Zeit.

Answer

Heuristiken sind nutzlos, da sie zu ungenauen Ergebnissen führen.

Answer

Heuristiken sind nur für bestimmte Arten von NP-schweren Problemen anwendbar.

Question 46

Welche praktischen Auswirkungen hat NP-Vollständigkeit in der Informatik?

Accepted Answer

Sie beweist die Unlösbarkeit bestimmter Probleme durch effiziente Algorithmen und unterstützt so die Priorisierung von Forschung und Entwicklung.

Answer

Sie garantiert effiziente Algorithmen für zugehörige Probleme.

Answer

Sie hilft, effizient lösbare Probleme zu identifizieren.

Answer

Sie ist ein rein abstraktes Konzept ohne praktische Bedeutung.

Question 47

Die Zeitkomplexität des Bubblesort-Algorithmus zum Sortieren eines Arrays mit n Elementen beträgt:

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(n^3)

Question 48

Das primäre Ziel der Kryptographie ist es:

Accepted Answer

Informationen zu schützen

Answer

Informationen zu verbreiten

Answer

Informationen wiederherzustellen

Answer

Informationen zu zerstören

Question 49

Welche der folgenden Verschlüsselungsmethoden verwendet denselben Schlüssel zum Ver- und Entschlüsseln?

Accepted Answer

AES

Answer

RSA

Answer

ECC

Answer

Hashing

Question 50

Was ist der Zweck eines Hashwerts?

Accepted Answer

Eine eindeutige Darstellung einer Nachricht zu erstellen

Answer

Eine Nachricht zu verschlüsseln

Answer

Einen zufälligen Schlüssel zu generieren

Answer

Ein digitales Zertifikat zu erstellen

Question 51

Was ist der Hauptunterschied zwischen einem geheimen Schlüssel und einem öffentlichen Schlüssel?

Accepted Answer

Ein geheimer Schlüssel wird geheim gehalten, während ein öffentlicher Schlüssel öffentlich geteilt wird

Answer

Ein geheimer Schlüssel wird für Ver- und Entschlüsselung verwendet, während ein öffentlicher Schlüssel nur für die Verschlüsselung verwendet wird

Answer

Ein geheimer Schlüssel ist kürzer als ein öffentlicher Schlüssel

Answer

Es gibt keinen Unterschied

Question 52

Welcher der folgenden Algorithmen ist ein deterministischer endlicher Automat (DFA)?

Accepted Answer

Algorithmus zur Erkennung einer Palindrom-Zeichenkette

Answer

Algorithmus zur Berechnung von Primzahlen

Answer

Dijkstra-Algorithmus

Answer

Algorithmus zum Sortieren eines Arrays

Question 53

Wie helfen Heuristiken bei der Bewältigung von NP-vollständigen Problemen?

Accepted Answer

Heuristiken liefern oft gute Näherungslösungen für NP-vollständige Probleme in praktischer Zeit.

Answer

Heuristiken garantieren die Lösung von NP-vollständigen Problemen in polynomialer Zeit.

Answer

Heuristiken sind nur für kleine Instanzen von NP-vollständigen Problemen geeignet.

Question 54

Welcher Algorithmus hat eine Laufzeitkomplexität von O(n log n)?

Accepted Answer

Quicksort

Answer

Bubblesort

Answer

Insertionsort

Answer

Selektionssort

Question 55

Welche Verschlüsselungsmethode ist eine Blockchiffre?

Accepted Answer

AES

Answer

RSA

Answer

ElGamal

Answer

Diffie-Hellman

Question 56

Welche Hash-Funktion ist kollisionsresistent?

Accepted Answer

SHA-256

Answer

MD5

Answer

CRC32

Answer

Adler-32

Question 57

Welcher Automatentyp ist am leistungsfähigsten?

Accepted Answer

Turingmaschine

Answer

Deterministischer endlicher Automat (DFA)

Answer

Nichtdeterministischer endlicher Automat (NFA)

Answer

Pushdown-Automat (PDA)

Question 58

Welche Aussage beschreibt das Halteproblem korrekt?

Accepted Answer

Es ist unentscheidbar, ob eine Turingmaschine bei einer gegebenen Eingabe anhält.

Answer

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

Answer

Es ist unentscheidbar, ob eine Turingmaschine bei allen Eingaben anhält.

Answer

Es ist entscheidbar, ob eine Turingmaschine bei allen Eingaben anhält.

Question 59

Welcher Beweis ist eine konstruktive Beweisführung?

Accepted Answer

Beweis durch Konstruktion

Answer

Beweis durch Widerspruch

Answer

Beweis durch Induktion

Answer

Beweis durch vollständige Induktion

Question 60

Welche der folgenden Aussagen über die Komplexitätsklasse NP ist wahr?

Accepted Answer

NP ist die Menge der Probleme, für die eine Lösung in polynomialer Zeit verifiziert werden kann.

Answer

NP ist die Menge der Probleme, die in polynomialer Zeit gelöst werden können.

Answer

NP ist die Menge der Probleme, für die es keine polynomielle Lösung gibt.

Question 61

Was trifft auf die P-NP-Frage zu?

Accepted Answer

Es ist nicht bekannt, ob P = NP gilt.

Answer

Es wurde bewiesen, dass P = NP gilt.

Answer

Die P-NP-Frage ist gelöst.

Answer

Es wurde bewiesen, dass P != NP gilt.

Question 62

Welche der folgenden Verschlüsselungsverfahren basiert auf dem Prinzip der öffentlichen Schlüssel?

Accepted Answer

RSA

Answer

DES

Answer

AES

Question 63

Welche der folgenden Aussagen über die Reduktion von Problemen ist korrekt?

Accepted Answer

Eine Reduktion von Problem A auf Problem B bedeutet, dass jede Instanz von Problem A in eine Instanz von Problem B transformiert werden kann.

Answer

Eine Reduktion ist eine lineare Transformation.

Question 64

Was trifft auf eine Turingmaschine zu?

Accepted Answer

Eine Turingmaschine ist ein abstraktes Modell eines Rechners.

Answer

Eine Turingmaschine kann nur eine endliche Anzahl von Zuständen haben.

Answer

Eine Turingmaschine ist ein physisches Gerät.