Archive: Spring Semester 2014
CS206 Theorie der Informatik
| Dozent |
Malte Helmert
Gabriele Röger |
| Tutoren |
Manuel Heusner
Florian Pommerening Jendrik Seipp Silvan Sievers |
| Vorlesung |
Montag 13:15 - 15:00; Bernoullistrasse 16, Seminarraum 205
Mittwoch 15:15 - 17:00; Bernoullistrasse 16, Seminarraum 205 |
| Startveranstaltung | 17.2.2014 |
| Prüfungszulassung | Erreichen von mindestens 50% der möglichen Punkte aus den Übungen. |
| Prüfung | Schriftlich. Die Note für die Vorlesung ergibt sich ausschliesslich aus dieser Prüfung. |
| Übungen | Mo 15:15-17:00; Seminarraum 205 |
| Kurzbeschreibung | Die Vorlesung bietet eine Einführung in die theoretische Informatik. Schwerpunktthemen sind: Logik, Automatentheorie und formale Sprachen, Berechenbarkeits- und Komplexitätstheorie. |
| Zielpublikum | Bachelor, 2. Semester |
| Literatur |
U. Schöning: "Theoretische Informatik - kurz gefasst", 5. Aufl., Spektrum Verlag, 2008
U. Schöning: "Logik für Informatiker", 5. Aufl., Spektrum Verlag, 2000 |
| Anmeldung | Belegen - Gruppenzuweisung |
| Kreditpunkte | 6 ECTS-Punkte |
| Vorlesungsverzeichnis Nr. | 10948-01 |
Vorlesungsfolien
| Nr. | Thema | Datum | Folien |
| 0. | Organisatorisches | 17.02.2014 |
(Bildschirm)
(Drucker) |
| 1. | Aussagenlogik I | 19.02.2014 |
(Bildschirm)
(Drucker) |
| 2. | Aussagenlogik II | 24.02.2014 |
(Bildschirm)
(Drucker) |
| 3. | Aussagenlogik III | 26.02.2014 03.03.2014 |
(Bildschirm)
(Drucker) |
| 4. | Prädikatenlogik I | 03.03.2014 05.03.2014 |
(Bildschirm)
(Drucker) |
| 5. | Prädikatenlogik II | 05.03.2014 17.03.2014 |
(Bildschirm)
(Drucker) |
| 6. | Formale Sprachen | 17.03.2014 |
(Bildschirm)
(Drucker) |
| 7. | Reguläre Sprachen I | 19.03.2014 24.03.2014 |
(Bildschirm)
(Drucker) |
| 8. | Reguläre Sprachen II | 26.03.2014 |
(Bildschirm)
(Drucker) |
| 9. | Kontextfreie Sprachen I | 31.03.2014 |
(Bildschirm)
(Drucker) |
| 10. | Kontextfreie Sprachen II | 02.04.2014 |
(Bildschirm)
(Drucker) |
| 11. | Typ-1 und Typ-0-Sprachen | 07.04.2014 |
(Bildschirm)
(Drucker) |
| 12. | Turing-Berechenbarkeit | 09.04.2014 |
(Bildschirm)
(Drucker) |
| 13. | LOOP-, WHILE- und GOTO-Berechenbarkeit | 09.04.2014 |
(Bildschirm)
(Drucker) |
| 14. | primitive Rekursion und µ-Rekursion | 16.04.2014 |
(Bildschirm)
(Drucker) |
| 15. | Ackermannfunktion | 28.04.2014 |
(Bildschirm)
(Drucker) |
| 16. | Entscheidbarkeit, Reduktionen, Halteproblem | 16.04.2014 |
(Bildschirm)
(Drucker) |
| 17. | Postsches Korrespondenzproblem | 07.05.2014 |
(Bildschirm)
(Drucker) |
| 18. | Komplexitätstheorie: Motivation und Einführung | 07.05.2014 |
(Bildschirm)
(Drucker) |
| 19. | P, NP und polynomielle Reduktionen | 12.05.2014 |
(Bildschirm)
(Drucker) |
| 20. | Satz von Cook und Levin | 14.05.2014 |
(Bildschirm)
(Drucker) |
| 21. | einige NP-vollständige Probleme | 19.05.2014 |
(Bildschirm)
(Drucker) |
Übungsblätter
| Nr. | Datum | Übungsblatt |
| 1. | 19.02.2014 | Blatt 1 |
| 2. | 26.02.2014 | Blatt 2 |
| 3. | 05.03.2014 | Blatt 3 |
| 4. | 19.03.2014 | Blatt 4 |
| 5. | 26.03.2014 | Blatt 5 |
| 6. | 02.04.2014 | Blatt 6 |
| 7. | 09.04.2014 | Blatt 7 |
| 8. | 16.04.2014 | Blatt 8 |
| 9. | 23.04.2014 | Blatt 9 |
| 10. | 30.04.2014 | Blatt 10 |
| 11. | 07.05.2014 | Blatt 11 |
| 12. | 14.05.2014 | Blatt 12 |