English
I210 – Theoretische Informatik
Theory of Computing
Version: 1
Prof. Dr. rer. nat. Boris Hollas
boris.hollas(at)htw-dresden.de
Prof. Dr. rer. nat. Boris Hollas
boris.hollas(at)htw-dresden.de
5.00 Credits
150 Stunden
4.00 SWS (2.00 SWS Vorlesung | 2.00 SWS Übung)
0.00 Stunden
Schriftliche Prüfungsleistung
Prüfungsdauer: 90 min | Wichtung: 100 %
2/2/0 V/Ü/P
- Reguläre Sprachen: DFA, NFA, reguläre Grammatiken, reguläre Ausdrücke, Pumping-Lemma.
- Kontextfreie Sprachen: PDA, kontextfreie Grammatiken, CYK-Algorithmus, Mehrdeutigkeit, einfache Top-Down und Bottom-Up-Parser.
- 0L-Systeme, Chomsky-Hierarchie.
- Entscheidbarkeit, Halteproblem, unentscheidbare Probleme.
- Komplexitätsklassen P und NP, NP-vollständige Probleme.
Die Theorie der Formalen Sprachen soll beherrscht und die Grenzen der Berechenbarkeit erkannt werden.
Grundlagen der Informatik
Boris Hollas: Grundkurs Theoretische Informatik: Mit Aufgaben und Anwendungen. Springer-Vieweg, 2. Auflage 2015
Siehe oben