Veranstaltungsart und -inhalt
|
Titel |
Theoretische Informatik |
Dozent |
Prof. Reischuk |
Einordnung |
Bachelor-Studiengang Informatik (Pflicht) 3. Semester |
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
- (Un-)Entscheidbarkeit und Aufzählbarkeit
- Halteproblem und Church-Turing These
|
Qualifikationsziele: |
- theoretische Grundlagen der Syntax und der operationalen Semantik von Programmiersprachen kennen
- Möglichkeiten und Grenzen der Informatik verstehen
- algorithmische Probleme modellieren und mit geeigneten Werkzeugen lösen können
- algorithmische Probleme nach ihrer Komplexität klassifizieren können
|
Leistungsnachweise erfolgen durch: |
- Übungsaufgaben (wöchentlich)
- Projektaufgaben
- aktive Teilnahme in Übungsgruppen
- Klausuren, 90 Min. (voraus. 26.2.2008)
|
|
Diese Veranstaltung baut direkt auf folgenden Lehrmodulen auf, die erfolgreich abgeschlossen sein sollten:
- Logik für Informatiker
- Algorithmen und Datenstrukturen
|
Buchempfehlungen: |
- J. Hopcroft, J. Ullman, R. Motwani: Introduction to Automata Theory, Languages and Computation, Addison Wesley 2001
- R. Reischuk, Komplexitätstheorie, Band I, Teubner 1998
- Savage: Models of Computation, Addison Wesley 1998
- Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit, Teubner 1992
- C. Papadimitriou: Computational Complexity, Addison Wesley 1994
- E. Rich, Automata, Computability, and Complexity, Pearson 2008
|
Wiki |
Wiki zur Veranstaltung »Theoretische Informatik«
|
Vorlesung |
Dozent |
Prof. Reischuk |
Umfang |
4 SWS, ECTS-Credits: 8 |
Termine |
Di 10:45 – 12:15, H1; Do 10:00 – 12:00 V2
|
Übung |
Assistent |
Elberfeld |
Umfang |
2 SWS |
Termine |
Mo 12:00 – 18:00, Seminarraum Informatik 2 + 3; Gruppe 1: 12:00-14:00, Gruppe 2: 14:00-16:00, Gruppe 3: 16:00-18:00
|