Archive: Spring Semester 2013
CS206 Theorie der Informatik
| Dozenten | Christian Tschudin, Malte Helmert |
| Assistenten | Martin Wehrle |
| Tutoren | Florian Pommerening, Jendrik Seipp, Silvan Sievers |
| Vorlesung | Mo 13-15 Uhr, Mi 15-17 Uhr; Bernoullistrasse SR 205 |
| Startveranstaltung | Mi, 27.2.2013 |
| 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-17 Uhr (Bernoullistrasse SR 205), Mi 17-19 Uhr (Bernoullistrasse SR 205), Mi 17-19 Uhr (Schanzenstrasse) |
| 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. Auflage, Spektrum Verlag, 2008 U. Schöning: "Logik für Informatiker", 5. Auflage,Spektrum Verlag, 2000 |
| Anmeldung |
Belegen
-
Gruppeneinteilung
Die Einteilung der Übungsgruppen kann jetzt in Courses eingesehen werden. |
| Kreditpunkte | 6 ECTS-Punkte |
| Vorlesungsverzeichnis Nr. | 10948-01 |
| Nr. | Thema | Datum | Folien |
| 0. | Organisatorisches | 27.02.2013 |
(Slides)
|
| 1. | Aussagenlogik (I) | 04.03.2013 |
(Slides)
|
| 2. | Aussagenlogik (II), Prädikatenlogik | 06.03.2013 |
(Slides)
|
| 3. | Prädikatenlogik (II), Grammatik | 11.03.2013 |
(Slides)
|
| 4. | Sprache, Grammatik, endliche Automaten | 13.03.2013 |
(Slides)
|
| 5. | Nicht-determ. endl. Automaten, RegEx, Pumping Lemma | 18.03.2013 |
(Slides)
|
| 6. | Predictive Parser, Chomsky Normalform, Kellerautomat, TM | 20.3.2013 |
(Slides),
(Busy Beaver) |
| 7. | TM, WHILE-Prog, LOOP-Prog, primitiv-rekursive Funktionen | 25.3.2013 |
(Slides)
|
| 8. | Ackermann, GOTO-Prog, mu-Rekursion | 27.3.2013 |
(Slides)
|
| 9. | rekursiv aufzählbar, (semi-)entscheidbar | 3.4.2013 |
(Slides)
|
| 10. | Wiederholung: Automatentheorie und formale Sprachen | 10.4.2013 |
(Bildschirm)
(Drucker) |
| 11. | Wiederholung: Berechenbarkeitstheorie | 15.4.2013 |
(Bildschirm)
(Drucker) |
| 12. | III.4 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit | 17.4.2013 |
(Bildschirm)
(Drucker) |
| 13. | III.5 Postsches Korrespondenzproblem | 24.4.2013 |
(Bildschirm)
(Drucker) |
| 14. | IV.1 Komplexitätstheorie: Motivation und Einführung | 29.4.2013 |
(Bildschirm)
(Drucker) |
| 15. | IV.2 Nichtdeterminismus | 6.5.2013 |
(Bildschirm)
(Drucker) |
| 16. | IV.3 P, NP und polynomielle Reduktionen | 8.5.2013 |
(Bildschirm)
(Drucker) |
| 17. | IV.4 Satz von Cook und Levin | 13.5.2013 |
(Bildschirm)
(Drucker) |
| 18. | IV.5 Einige NP-vollständige Probleme | 15.5.2013 |
(Bildschirm)
(Drucker) |