Arbeitsaufwand:
270 h
|
Nummer INFM2410 |
Titel Theoretische Informatik 2: Formale Sprachen, Berechenbarkeit und Komplexitätstheorie (früher Theoretische Informatik) |
Art der Vorlesung Wahlpflicht |
|---|---|---|
| ECTS | 9 | |
|
Arbeitsaufwand - Kontaktzeit - Selbststudium |
Arbeitsaufwand:
270 h Kontaktzeit:
90 h / 6 SWS Selbststudium:
180 h |
|
| Veranstaltungsdauer | 1 Semester | |
| Häufigkeit des Angebots | Im Wintersemester | |
| Unterrichtssprache | Deutsch | |
| Prüfungsform | Klausur |
|
| Lehrform(en) | Vorlesung, Übung | |
| Inhalt | Themen sind u.a. Formale Sprachen, Automaten, Berechenbarkeit, Entscheidbarkeit und rekursive Aufzählbarkeit, Existenz unentscheidbarer Probleme, erster Satz von Rice, Komplexitätstheorie, Zeit- und Platzbedarf und NP-Vollständigkeit. |
|
| Qualifikationsziele | Die Studierenden haben die Fähigkeit, die Standardkonstruktionen aus dem Bereich endlicher Automaten und regulärer Ausdrücke auszuführen. Sie haben ein Verständnis des Phänomens der Nichtberechenbarkeit und der Häufigkeit seines Auftretens sowie ein Grundverständnis des Begriffs der NP-Vollständigkeit und seiner Motivation. |
|
| Vergabe von Leistungspunkten/Benotung |
Lehrform
Status
SWS
LP
Prüfungsform
Prüfungsdauer
Benotung
Berechnung
Modulnote (%)
Vorlesung
V
o
4
6.0
K
90
b
100
Übung
Ü
o
2
3.0
|
|
| Teilnahmevoraussetzungen | Es gibt keine besonderen Voraussetzungen. | |
| Dozent/in | Hennig, von Luxburg | |
| Literatur / Sonstiges | Kenntnisse der Vorlesungen "Mathematik für Infomatik 1: Analysis" (INFM1010) und "Theoretische Informatik 1: Algorithmen und Datenstrukturen" (INFM2420) werden empfohlen. |
|
| Zuletzt angeboten | Sommersemester 2022 | |
| Geplant für | Sommersemester 2024 | |
| Zugeordnete Studienbereiche | BIOINFM, INFM, MDZINFM2510, MEINFM | |