Theoretische Informatik Grundlagen Übungen mit Lösungen


Diese Seite beinhaltet Übungsblätter und Lösungen zur Vorlesung "Theoretische Informatik" im Wintersemester 2001/ 2002 an der Universität Tübingen. Die Vorlesung wurde von Professor Lange gehalten. Die Übungsblätter wurden von Herrn Reinhard zusammengestellt.

Die Vorlesung basiert auf dem Buch:
Uwe Schöning, Theoretische Informatik -- kurzgefaßt, dritte Auflage
Spektrum Akademie Verlag, Deutschland, 1997
ISBN-10: 3-8274-0250-6, ISBN-13: 9783827402509

Ich habe zwei Übungsgruppen betreut und ausführliche Musterlösungen verfasst, die ich hier zur Verfügung stelle.

Die Materialien eignen sich sehr gut zum Selbstlernen und zur Vorbereitung auf eine Prüfung in den behandelten Bereichen.

Viel Spaß mit den Aufgaben!

Hier finden sich Lösungen zu den Übungsblättern...
Die Lösungen sollten richtig sein, eine Garantie dafür gibt es aber nicht...

Verweise auf Seitenzahlen des Buches beziehen sich auf die DRITTE Auflage des Schöning.
In der vierten sollte das entsprechende nicht allzu weit davon weg stehen...

Nr. Titel Lösung
0 Diskrete Mathematik (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
b Konstruktion einer Grammatik für die Sprache aller Wörter die,
mit "ab" beginnen/ die "ab" enthalten
pdf ps (zip)
1 Grammatiken (ps, pdf | Lokale Kopien: pdf) pdf ps
t Tipps html
i Infos zu den Chomsky-Typen pdf ps (zip)
i Hinweise zur Notation {a,b}*; (ab)* etc. html
2 Grammatiken 2 (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
t Lösung zu Blatt 1 Aufgabe 5 pdf ps (zip)
3 Reguläre Sprachen (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
b DEA der Wörter mit Vielfachen von fünf a's erkennt und Beweis seiner Korrektheit durch Wortinduktion pdf ps (zip)
4 Reguläre Sprachen/ Ausdrücke (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
i Alles Wissenswerte zum Verfahren ?FA -> regulärer Ausdruck [neu 19.3.2002] html
b DFA -> rA am Beispiel von Blatt 4 Aufgabe 5
mit zwei unterschiedlichen Indizierungen
pdf ps (zip)
5 Reguläre Sprachen (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
i Myhill/ Nerode [neu 26.3.2002] html
6 Reguläre Sprachen und kontextfreie Sprachen (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
7 Kontextfreie Sprachen (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
i Wie komme ich zur Greibach-Normal-Form? pdf ps (zip)
8 Kellerautomaten (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
b Grammatik Typ 2 -> NPDA am Beispiel von Blatt 8 Aufgabe 1.2
NPDA -> Grammatik Typ 2 am Beispiel von Blatt 8 Aufgabe 3d)
pdf ps (zip)
i Kurzüberblick: Wo sind wir? pdf ps (zip)
 
9 Turingmaschinen (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
Die 5a) wurde am 13.1.2002 (nach der Übungsgruppe) nochmal korrigiert [ist bei der Lösung zur 9 dabei] pdf ps (zip)
10 Turing- und Loop-Berechenbarkeit (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
11 While- und Goto-Programme, primitive Rekursion (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
12 Rekursive Funktionen (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
13 Entscheidbarkeit, Reduzierbarkeit (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
14 PCP (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
i Stichpunkte: Kapitel 2 pdf ps (zip)
 
15 Komplexität (ps, pdf | Lokale Kopien: pdf) pdf ps (zip)
i Aufgabe 2 html
 
k Klausuren der letzten Jahre zum Üben findet Ihr hier html
 
i Infos zur Klausur findet Ihr hier html
 
Ich wünsche Euch allen viel Erfolg bei der Klausur!

Was mache ich mit dem "ps (zip)"?
Ich führe "unzip [name].zip" aus. Dann habe ich das ps-file und das sollte z.B. mit ghostview zu öffnen sein...
Das sieht dann auf dem Bildschirm zwar etwas seltsam aus, druckt sich aber korrekt...


© marc-oliver pahl