| Lehrbeauftragter: | Prof. Dr. Jürgen Dassow |
| Wochenstunden: | 3+2+0 |
| Zuhörerkreis: | Bachelor CV, Inf, IngIF, WIF, 3. Semester |
| Voraussetzungen: | keine |
| Prüfung: | durch Klausur, 120 Minuten, in der Prüfungszeit nach dem Semester |
| Unbenoteter Schein: | durch Klausur in der Prüfungszeit nach dem Semester |
| Klausuranmeldung: | über das Onlineportal HISQIS , vom 18. November 2011 bis 10. Januar 2012 |
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.
Zulassung zur Klausur:
Klausur: Eine Möglichkeit zur Einsicht in die Klausuren wird demnächst hier bekanntgegeben.Literatur: Siehe erste Folie.
Skript: Teil 1 Teil 2, Teil 3, Teil 4, Teil 5, Teil 6
Folien: Teil 1, Teil 2, Teil 3, Teil 4
Webmaster