Theoretische Informatik | Vordiplom | Informatik | Universität Trier

Theoretische Informatik | Informatik

04.04.2003

Art der Hochschule:

Universität

Prüfungsort:

Trier

Studienfach:

Informatik

Art der Prüfung:

Vordiplom

Prüfungsfach:

Theoretische Informatik

Dauer:

30-40 Minuten

Note:

Konntest du mit einem selbst gewählten Thema beginnen?

keine Angabe

Versucht der Prüfer bei Schwierigkeiten zu helfen?

keine Angabe

Prüfungsablauf / Tipps

Themen:
- reguläre Sprachen, endl. Automaten
- Berechenbarkeit
- Komplexität
- Äquivalenzrelationen
.. also überwiegend Grundlagen

Quellen:
- Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik
- Uwe Schöning: Theoretische Informatik - kurz gefasst
- Renate Winter: Theoretische Informatik

Prüfungsfragen

- Reguläre Sprachen
Definition: Grammatik, Chomsky-Hierarchie, reguläre Grammatik
reguläre Ausdrücke mit zugehörigen Sprachen induktiv definieren
endliche Automaten: DFA, NFA definieren, mit Überführungsfunktion für Wörter (diese aber nur für DFA induktiv definieren) und akzeptierten Sprachen L(M)
Beweis NFA => DFA, nur Konstruktion des DFA M':=(Q', Sigma, delta', Q0, F'), kein Beweis
Frage nach nicht regulären Sprachen, mein angebotenes Bsp. {anbm|n != m} hätte zu weit geführt
Pumping Lemma aufschreiben; Zusatzfrage, warum man es bei endlichen Sprachen nicht anwenden könne (habe ich nicht verstanden)

- Berechenbarkeit
Def. intuitive Berechenbarkeit, Turing-Berechenbarkeit mit Def. von DTM/NTM
Idee, warum k-Band-TM 1-Band-TM, an Skizze erklären
Primitiv-rekursive Funktionen (nur Definition)
erklären, daß Ackermann-Funktion nicht primitiv-rekursiv. Anfang nur mündlich (Eigenschaften der A.-Fkt.), schriftlich den Schluß (Widerspruchsbeweis a(c,c) =: g(c) < a(c,c))

- Komplexität
Def. NP-vollständig (A in NP und A NP-hart), Klasse NP nur mündlich definieren
NP-hart aber ausführlich: (polynomielle) Reduzierbarkeit
Wie zeigt man, daß ein Problem NP-vollst. ist (Guess&Check; => A in NP, NP-hart nach Definition, oder bekanntes NP-hartes Problem B polynomiell reduzieren auf A)

- Logik
Standardfrage: Def. Äquivalenzrelation mit Beispiel, habe Myhill-Nerode-Relation RL angegeben (ohne Beweis)

Studienfächer