Vorlesung und Übung (6 SWS/9 ECTS)
In dieser Vorlesung wird in die Grundlagen der theoretischen Informatik eingeführt. Im Mittelpunkt stehen mathematische Modelle für Algorithmen, Automaten und formale Sprachen. Ebenso werden Fragestellungen behandelt, welche Berechnungsprobleme überhaupt algorithmisch lösbar sind und wie wie die Klasse der effizient lösbaren Berechnungsprobleme aussieht.
Termine
| Vorlesung: | Mittwoch, 08:15-09:45 Uhr, R 513 (S. Kosub) |
| Donnerstag, 08:15-09:45 Uhr, A 703 (S. Kosub) | |
| Übung: | Montag, 10:00-11:30 Uhr, D 247 (A: Dr. Maciej Gratkowski) |
| Montag, 13:30-15:00 Uhr, D 247 (B: Dr. Maciej Gratkowski) | |
| Montag, 15:15-16:45 Uhr, D 247 (C: Dr. Maciej Gratkowski | |
| Klausur: | Dienstag, 23.07.2013, 10:00-12:00 Uhr, R 513 (Ersttermin) |
| Dienstag, 15.10.2013, 10:00-12:00 Uhr, C 336 (Zweittermin) |
Übungsblätter
Übungsblätter werden immer am Donnerstag (ausschließlich elektronisch) auf der Vorlesungswebseite als PDF-Datei zur Verfügung gestellt.
Die Aufgaben sind innerhalb einer Woche zu bearbeiten. Die Abgabe der Lösung als aus LaTeX erzeugte PDF-Datei ist bis Freitag, 08:00 Uhr per Email an den jeweiligen Tutor möglich. Die Besprechung der Aufgaben und die Rückgabe der korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung. Das Erlangen von mindestens der Hälfte der möglichen Punkte und die regelmäßige, aktive Teilnahme an den Übungen ist Voraussetzung für die Zulassung zur Klausur.
Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.
- 1. Übungsblatt - Ausgabe: 18:04.13 - Abgabe: 26.04.13 (PDF, 155 KB)
- 2. Übungsblatt - Ausgabe: 25.04.13 - Abgabe: 03.05.13 (PDF, 155 KB)
- 3. Übungsblatt - Ausgabe: 02.05.13 - Abgabe: 10.05.13 (PDF, 178 KB)
- 4. Übungsblatt - Ausgabe: 09.05.13 - Abgabe: 17.05.13 (PDF, 149 KB)
- 5. Übungsblatt - Ausgabe: 16.05.13 - Abgabe: 24.05.13 (PDF, 137 KB)
- 6. Übungsblatt - Ausgabe: 23.05.13 - Abgabe: 31.05.13 (PDF, 179 KB)
- 7. Übungsblatt - Ausgabe: 30.05.13 - Abgabe: 07.06.13 (PDF, 144 KB)
- 8. Übungsblatt - Ausgabe: 06.05.13 - Abgabe: 14.06.13 (PDF, 143 KB)
- 9. Übungsblatt - Ausgabe: 13.06.13 - Abgabe: 21.06.13 (PDF, 130 KB)
- 10. Übungsblatt - Ausgabe: 20.06.13 - Abgabe: 28.06.13 (PDF, 152 KB)
- 11. Übungsblatt - Ausgabe: 27.06.13 - Abgabe: 05.07.13 (PDF, 142 KB)
- 12. Übungsblatt - Ausgabe: 04.07.13 - Abgabe: 12.07.13 (PDF, 168 KB)
Inhalt
Inhalte der Vorlesung:
- Algorithmentheorie
- Berechenbarkeitstheorie
- Komplexitätstheorie
- Automatentheorie
- Theorie der Formalen Sprachen
Skriptum
Im Laufe der Vorlesung wird ein Skript zur Vorlesung zur Verfügung gestellt werden. Die jeweils aktuelle Version finden Sie hier. Sollten Sie Anregungen zum Skript haben oder Fehler jeglicher Art finden, schreiben Sie bitte eine kurze Email.
Literatur
Ergänzendes und vertiefendes Material zu Vorlesung und Skriptum findet sich in folgenden Lehrbüchern:
- Klaus W. Wagner. Theoretische Informatik. Eine kompakte Einführung. 2. Auflage, Springer-Verlag, Berlin, 2003.
- Uwe Schöning. Theoretische Informatik - kurz gefasst. 5. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2008.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3. Auflage, Prentice Hall, Upper Saddle River, NJ, 2006.