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) | ps (zip) | |
| b | Konstruktion einer Grammatik für die Sprache aller Wörter die, mit "ab" beginnen/ die "ab" enthalten |
ps (zip) | |
| 1 | Grammatiken (ps, pdf | Lokale Kopien: pdf) | ps | |
| t | Tipps | html | |
| i | Infos zu den Chomsky-Typen | ps (zip) | |
| i | Hinweise zur Notation {a,b}*; (ab)* etc. | html | |
| 2 | Grammatiken 2 (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| t | Lösung zu Blatt 1 Aufgabe 5 | ps (zip) | |
| 3 | Reguläre Sprachen (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| b | DEA der Wörter mit Vielfachen von fünf a's erkennt und Beweis seiner Korrektheit durch Wortinduktion | ps (zip) | |
| 4 | Reguläre Sprachen/ Ausdrücke (ps, pdf | Lokale Kopien: 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 |
ps (zip) | |
| 5 | Reguläre Sprachen (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| i | Myhill/ Nerode [neu 26.3.2002] | html | |
| 6 | Reguläre Sprachen und kontextfreie Sprachen (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| 7 | Kontextfreie Sprachen (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| i | Wie komme ich zur Greibach-Normal-Form? | ps (zip) | |
| 8 | Kellerautomaten (ps, pdf | Lokale Kopien: 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) |
ps (zip) | |
| i | Kurzüberblick: Wo sind wir? | ps (zip) | |
| 9 | Turingmaschinen (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| Die 5a) wurde am 13.1.2002 (nach der Übungsgruppe) nochmal korrigiert [ist bei der Lösung zur 9 dabei] | ps (zip) | ||
| 10 | Turing- und Loop-Berechenbarkeit (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| 11 | While- und Goto-Programme, primitive Rekursion (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| 12 | Rekursive Funktionen (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| 13 | Entscheidbarkeit, Reduzierbarkeit (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| 14 | PCP (ps, pdf | Lokale Kopien: pdf) | ps (zip) | |
| i | Stichpunkte: Kapitel 2 | ps (zip) | |
| 15 | Komplexität (ps, pdf | Lokale Kopien: 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...