Veranstaltungsart und -inhalt
|
| Titel |
Theoretische Informatik |
| Dozent |
Prof. Dr. Maciej Liskiewicz |
| Einordnung |
Bachelor-Studiengang Informatik (Pflicht) 3. Semester,
Bachelor-Studiengang Medizinische Informatik (Pflicht) 3. Semester,
Bachelor-Studiengang Medieninformatik Informatik (Pflicht) 3. Semester
Inhaltliche Voraussetzung: CS1000, CS1001
|
| Inhalte |
- Formalisierung von Problemen mittels Sprachen
- Formale Grammatiken
- reguläre Sprachen, endliche Automaten
- kontextfreie Sprachen, Kellerautomaten
- sequentielle Berechnungsmodelle: Turing-Maschinen, Registermaschinen
- sequentielle Komplexitätsklassen
- Simulation, Reduktion, Vollständigkeit
- Erfüllbarkeitsproblem, NP-Vollständigkeit
- (Un-)Entscheidbarkeit und Aufzählbarkeit
- Halteproblem und Church-Turing These
|
| Qualifikationsziele: |
- Studierenden können die theoretischen Grundlagen der Syntax und der operationalen Semantik von Programmiersprachen selbst darstellen
- Sie können Formalisierungen ineinander umwandeln, indem sie Sätze der Theoretischen Informatik anwenden
- Sie können algorithmische Probleme nach ihrer Komplexität klassifizieren
- Sie können algorithmische Probleme modellieren und mit geeigneten Werkzeugen lösen
- Sie können die Möglichkeiten und Grenzen der Informatik beurteilen
|
| Studienleistungen: |
- Übungs- bzw. Projektaufgaben
- Klausur sowie Studienleistungen
|
| Abschlussprüfung: |
|
| Buchempfehlungen: |
- J. Hopcroft, J. Ullman, R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison Wesley 2001
- Savage: Models of Computation, Addison Wesley 1998
- Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit, Teubner 1992
- C. Papadimitriou: Computational Complexity, Addison Wesley 1994
|
Creditierung |
|
Vorlesung |
| Dozent |
Prof. Dr. Maciej Liskiewicz |
| Umfang |
4 SWS |
| Termine |
Di 08:00 – 10:00, AM 1 , Do 10:00 – 12:00 Z 1/Z 2, ausser 7.2.18, dann im Z 3
|
Übung |
| Assistent |
Max Bannach M.Sc. |
| Umfang |
2 SWS |
| Termine |
6 Gruppen, Mo. 08-10h (Cook/Karp), 10-12h (Banach), 14-16h (ITCS2021, AM 4, Cook/Karp, Seminarraum Mathematik 1 (Hilbert)).
|
