English
I310 – Grundlagen der Informatik II
Foundations of Computer Science II
Version: 2
PD Prof. Dr.-Ing. habil. Hans-Joachim Böhme
hans-joachim.boehme(at)htw-dresden.de
PD Prof. Dr.-Ing. habil. Hans-Joachim Böhme
hans-joachim.boehme(at)htw-dresden.de
Deutsch
4.00 Credits
120 Stunden
3.00 SWS (2.00 SWS Vorlesung | 1.00 SWS Übung)
75.00 Stunden
Schriftliche Prüfungsleistung
Prüfungsdauer: 90 min | Wichtung: 100 %
2/1/0 V/Ü/P
Skripte, Folien, Arbeitsblätter, Aufgabensammlung
1. Einführung in die Theoretische Informatik
- Historische Entwicklung
- Teilgebiete
2. Mathematische Grundlagen
- Mengenbegriff, Mengenoperationen, Potenzmenge
- Relationen und Funktionen
- Zahlen: natürliche, rationale und reelle Zahlen
- Rekursion und induktive Beweise
3. Formale Sprachen und endliche Automaten
- Sprache und Grammatik, Chomsky-Hierarchie
- Reguläre, kontextfreie und kontextsensitive Sprachen
- Deterministische und nichtdeterministische endliche Automaten
- Kellerautomaten
- Turing-Maschine
4. Berechenbarkeit und Entscheidbarkeit
- Berechnungsmodelle: Loop-, While-, Goto-Programme, primitiv-rekursive Funktionen, Turing-Maschinen
- Definition von Entscheidbarkeit
- Konzept der charakteristischen Funktion
- Unentscheidbare Probleme
5. Komplexitätstheorie
- Algorithmische Komplexität, O-Kalkül, Rechnen im O-Kalkül
- Komplexitätsklassen
- NP-Vollständigkeit
6. Zusammenfassung
- Wechselbeziehungen zwischen den einzelnen behandelten Konzepten
Die Studierenden sollen nach dem Absolvieren der Lehrveranstaltung
- die Grundkonzepte der Theoretischen Informatik kennen und verstehen,
- algorithmische und strukturelle Problemstellungen analysieren und einordnen sowie
- die vermittelten Konzepte sicher auf diese Problemstellungen anwenden können.
Aufbauend auf Grundlagen der Informatik I (I-110)
- Skripte zur Lehrveranstaltung
- Dirk W. Hoffmann: Theoretische Informatik, Hanser
- Skripte zur Lehrveranstaltung
- Tutorials der Webseite NLogSpace: https://www.youtube.com/c/NLogSpace
- Aufgabensammlung