Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMontag, 11. November 2019 

Theoretische Informatik


Informatik | Theoretische Informatik | Druckansicht04.04.2003
Art der Hochschule: Universität
Prüfungsort: Trier
Studienfach: Informatik
Art der Prüfung: Vordiplom
Prüfer: Prof. Dr. Stefan Näher
Prüfungsfach: Theoretische Informatik
Dauer der Prüfung: 30-40 Minuten
Note: 1;
Konntest du mit einem selbst gewählten Thema beginnen? Nein.
Versucht der Prüfer bei Schwierigkeiten zu helfen? Ja.

  • Prüfungsablauf
  • Tipps
Prüfungsfragen
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
- 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)
ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/protokoll/352">Theoretische Informatik </a>