Grundlagen der Theoretischen Informatik I
Wintersemester 2009/2010
| Lehrbeauftragter: |
Prof. Dr. Jürgen Dassow
|
| Wochenstunden: |
3+2+0 |
| Zuhörerkreis: |
Bachelor CV, Inf, IngIF, WIF, 3. Semester |
| Voraussetzungen: |
keine
|
| Prüfung: |
Klausur, 120 Minuten
|
Inhalt:
Intuitiver Algorithmenbegriff und seine Formalisierung durch LOOP/WHILE-Programme und Turing-Maschinen, Gleichwertigkeit der beiden
Formalisierungen, Existenz nichtberechenbarer Funktionen und unentscheidbarer Probleme;
Regelgrammatiken und die von ihnen erzeugten Sprachen, Chomsky-Hierarchie,
Sprachen als Mengen von Wörtern, die von Automaten akzeptierter werden,
algebraische Charakterisierung von regulären Sprachen;
Zeit- und Raumkomplexität auf der Basis von Turing-Maschinen, Definition und Existenz NP-vollständiger Probleme.
Prüfung:
Die Wiederholungsklausur findet am Dienstag,
dem 20. Juli 2010, im Raum G16-H5 von 08:00 bis 10:00 Uhr statt.
Die Plätze sind spätestens 07:45 Uhr einzunehmen.
Literatur: Siehe erste Folie.
Skript:
Teil 1,
Teil 2,
Teil 3,
Teil 4,
Teil 5.
Folien:
Teil 1,
Teil 2,
Teil 3,
Teil 4,
Teil 5,
Teil 6.
Übungsaufgaben:
-
Übungsblatt 1 (43. KW),
Übungsblatt 2 (44. KW),
Übungsblatt 3 (45. KW),
Übungsblatt 4 (46. KW),
Übungsblatt 5 (47. KW),
-
Übungsblatt 6 (48. KW),
Übungsblatt 7 (49. KW),
Übungsblatt 8 (50. KW),
Übungsblatt 9 (51. KW),
-
Übungsblatt 10 (52./1. KW),
Übungsblatt 11 (2. KW),
Übungsblatt 12 (3. KW),
Übungsblatt 13 (4. KW).
Zur Lehreseite der Forschungsgruppe Theoretische Informatik
Webmaster