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 |