Theoretische Informatik für Studierende der angewandten
Informatik --
Fragen
Grundvorlesung
"Theoretische Informatik für Studierende der angewandten
Informatik"
Beispiele für Prüfungsfragen
In der folgenden Liste sind einige Prüfungsfragen aufgeführt,
die hilfreich sein könnten, um den Stand der Vorbereitung auf die
Prüfung zu testen. Es ist in jedem Fall sinnvoll, zuerst zu lernen
und dann erst anhand der Fragen zu überprüfen, wie gut man
Fragen zum Stoff beantworten kann. In der Prüfung werden die
Fragen meist ein wenig variieren, so dass ein bloßes Auswendiglernen der
Lösung nicht zum Erfolg führen kann. Insbesondere ist
die Liste mit Sicherheit nicht vollständig. Die Anmerkungen in
Klammern geben jeweils Varianten der Frage an. Beim Üben der
Antworten ist zu beachten, dass man die Fragen
umfassend beantworten kann, dazu gehören insbesondere auch die
zugrundeliegenden
Definitionen sowie Begründungen/Beweise für die Antwort. Der
Schwierigkeitsgrad der Fragen ist recht verschieden. Besonders wichtig
für das Bestehen der Prüfung ist das Verständnis der
Grundlagen und das Beherrschen der einfacheren Fragen.
Weitere Beispielfragen findet man im Buch Theoretische Informatik von
Ingo Wegener, Kapitel 9.2.
Erläutere Aufbau und Arbeitsweise einer Turingmaschine.
Was besagt die (erweiterte) churchsche These?
Welche Fehlerarten gibt es bei randomisierten Algorithmen? Was
sind die zugehörigen Komplexitätsklassen?
Was ist der Unterschied zwischen Las-Vegas- und
Monte-Carlo-Algorithmen? Was sind die zugehörigen
Komplexitätsklassen?
Wie sind die Komplexitätsklassen P und NP (ZPP, RP, ...)
definiert? Welche Zusammenhänge bestehen zwischen den
Komplexitätsklassen?
Zeige, dass RP eine Teilmenge von BPP ist (analog für andere
Inklusionen).
Zeige, dass EP=ZPP.
Gib den Algorithmus für den Äquivalenztest
multilinearer Ausdrücke an und analysiere ihn.
Zeige, dass ZPP(1/3)=ZPP(1/10). Wieviele Iterationen sind
nötig?
Was versteht man unter Abschluss gegen Komplementbildung bzw.
Durchschnitt
(Vereinigung, ...)? Gib für P, NP und BPP (bzw. die Klassen
der
Chomsky-Hierarchie) an, gegen welche Operationen sie
abgeschlossen sind.
Wie arbeitet eine nichtdeterministische Turingmaschine? Was ist
der Zusammenhang zu randomisierten Turingmaschinen?
Zeige, dass HC in NP liegt. (Analog für andere
Probleme)
Definiere den Begriff NP-vollständig (NP-schwer, ...). Was
ist die Motivation für die NP-Vollständigkeitstheorie?
Definiere polynomielle Reduktionen. Welche Folgerungen kann man
daraus ziehen, dass ein Problem A auf B reduzierbar ist?
Worin bestehen die Unterschiede zwischen polynomiellen
Reduktionen und
Turing-Reduktionen?
Gib die Reduktion von 3-SAT auf Independent Set an (analog
für andere Reduktionen aus der Vorlesung).
Zeige, dass polynomielle Reduktionen reflexiv und transitiv sind.
Worin besteht der Zusammenhang zwischen den Entscheidungs- und
Optimierungsvarianten des TSP-Problems (analog für andere
Probleme)?
Wie kann man eine NTM umformen, so dass sie nach dem
Rate-Verifikationsmodus arbeitet?
Was ist eine stereotype TM und wie kann man gewöhnliche TMs
durch stereotype TMs simulieren?
Wie kann man nichtdetermistische Algorithmen in deterministische
Algorithmen umformen?
Gib die logikorientierte Charakterisierung von NP an und beweise
ihre Korrektheit.
Was besagt der Satz von Cook? Wie kann man ihn für
NP-Vollständigkeitsbeweise benutzen?
Stelle die wesentlichen Beweisideen des Satzes von Cook dar.
Definiere die Begriffe rekursiv und rekursiv aufzählbar und
erläutere den Unterschied.
Welche dieser Eigenschaften hat die Diagonalsprache (oder das
PKP)? Beweise
Deine Behauptung.
Was sind Entscheidbarkeitsreduktionen und wie kann man sie nutzen?
Erläutere und beweise den Satz von Rice.
Welche Beschreibungsformen für reguläre Sprachen gibt
es? Erkläre, wie man einen DFA in einen regulären Ausdruck
umformen kann (analog für die anderen Umformungen).
Erkläre Aufbau und Funktionsweise eines DFAs (NFAs).
Gib einen DFA für die Sprache L={w | w enthält das Teilwort
aaa} an. (Analog für andere einfache Beispielsprachen.)
Wie kann man beweisen, dass eine gegebene Sprache regulär
(bzw. nicht regulär) ist?
Gib das Pumping-Lemma für reguläre Sprachen und beweise
es.
Wende das Pumping-Lemma auf die Sprache L={w | in w kommt der
Buchstabe a mindestens sooft wie der Buchstabe b vor} an. (Analog
für andere einfache
Beispielsprachen).
Wie minimiert man DFAs? Zeige die Korrektheit des Algorithmus.
Erkläre die Potenzmengenkonstruktion. Zeige, dass DFAs
exponentiell mehr Zustände als NFAs haben können.
Wie kann man bei der Potenzmengenkonstruktion die Betrachtung
nicht erreichbarer Zustände vermeiden?
Gib einen effizienten Algorithmus für das
Endlichkeitsproblem für reguläre Sprachen an, die durch DFAs
beschrieben sind (analog für andere Probleme auf regulären
Sprachen).
Gegen welche Operationen sind die regulären Sprachen
abgeschlossen? Beweise deine Behauptung für Durchschnitt (analog
für andere Operationen).
Was sind reguläre Ausdrücke?
Gib einen regulären Ausdruck für die Sprache L={w | w
enthält Teilwort aaa} an. (Analog für andere einfache
Beispielsprachen.)
Wie sind reguläre Grammatiken definiert? Gib eine
reguläre Grammatik für L={w
| w enthält Teilwort
aaa}
an.
(Analog für andere einfache Beispielsprachen.)
Zeige, wie man aus einem DFA M eine reguläre Grammatik
für L(M) konstruieren kann.
Zeige, wie man aus einer regulären Grammatik G einen NFA
für L(G) konstruieren kann.
Aus welchen Sprachklassen besteht die Chomsky-Hierarchie? Wie
sind die Sprachklassen definiert? Welche Inklusionen gelten zwischen
den Sprachklassen? Warum sind diese Inklusionen echt?
Gib für die einzelnen Klassen der Chomsky-Hierarchie an, ob
sie die Sprache L={w | in w kommt der Buchstabe a mindestens
sooft wie
der Buchstabe b vor}
enthalten (analog für andere einfache Beispielsprachen). Beweise
deine Behauptung.
Gib an, welche Sprachklassen der Chomsky-Hierarchie gegen
Vereinigung abgeschlossen sind. Beweise deine Behauptung (analog
für andere Abschlusseigenschaften).
Gib zu den einzelnen Klassen der Chomsky-Hierarchie die
zugehörigen Maschinenmodelle an.
Zeige, dass alle Sprachen mit Chomsky-0-Grammatiken rekursiv
aufzählbar sind.
Zeige, dass alle rekursiv aufzählbaren Sprachen eine
Chomsky-0-Grammatik haben.
Wie sind kontextfreie Sprachen definiert?
Zeige, dass die Sprache L={w
| in w kommt der Buchstabe a
mindestens sooft wie der Buchstabe b vor} kontextfrei ist (analog
für andere einfache
Beispielsprachen).
Was ist die wichtigste Motivation für die Betrachtung der
kontextfreien Sprachen?
Gib das Pumping-Lemma für kontextfreie Sprachen an und
beweise es (analog für Ogdens Lemma).
Was ist die Chomsky-Normalform und wofür benötigt man
sie? Wie formt man eine kontextfreie Grammatik in Chomsky-Normalform um?
Was versteht man unter dem Wortproblem für kontextfreie
Sprachen? Gib einen Algorithmus dafür an und analysiere seine
Rechenzeit.
Wie entfernt man nutzlose Variablen?
Gegen welche Operationen sind die kontextfreien Sprachen
abgeschlossen bzw. nicht abgeschlossen? Beweise deine Behauptung
für den Durchschnitt
(analog für andere Operationen).
Wie ist die Greibach-Normalform definiert? Wie kann man
kontextfreie Grammatiken in Greibach-Normalform umformen?
Was ist ein (nicht)deterministischer Kellerautomat?
Welche Akzeptanzmodi für NPDAs kennst Du? Sind diese
äquivalent?
Was haben NPDAs mit kontextfreien Sprachen zu tun? Beweise deine
Behauptung.
Was sind LR(k)-Grammatiken?
Wie funktioniert ein LR(k)-Parser?
Was sind lineare Programme? Wie sieht ihre Standardform aus? Was
ist der Unterschied zu ganzzahligen Programmen?
Zeige, wie man MAX-k-SAT
als ganzzahliges Programm formulieren kann (analog für andere
Probleme).
Welche Eigenschaften hat die Menge der Punkte, die alle
Nebenbedingungen eines linearen Programms erfüllen?
