|
|
Vorlesungsverzeichnis >> Technische Fakultät (TF) >>
|
Computational and Descriptive Complexity (CoDeCo)- Dozent/in
- Dr. Wolfgang Degen
- Angaben
- Vorlesung
4 SWS, benoteter Schein, ECTS-Studium, ECTS-Credits: 5, Sprache Deutsch oder Englisch, Zeit und Ort werden noch bekannt gegeben
Zeit und Ort: Di 16:15 - 17:45, 0.141; Bemerkung zu Zeit und Ort: Lehrstuhl Informatik 10, Cauerstraße 6
Vorbesprechung: 18.10.2011, 16:15 - 17:15 Uhr, Raum 0.141
- Studienfächer / Studienrichtungen
- WPF INF-DH-SIM ab 4 (ECTS-Credits: 5)
WPF INF-BA-V-THI ab 4 (ECTS-Credits: 5)
WPF INF-BA-W ab 5
WPF INF-BA-S ab 4
- Inhalt
- Computational Complexity Theory refers to machines (e.g. Turing machines) and to space and time used by these machines to solve problems.
The main ("classical") complexity classes arising are
L = deterministic log-space
NL = nondeterministic log-space
P = deterministic polynomial time
NP = nondeterministic polynomial time
PSPACE = deterministic polynomial space
(Note that PSPACE = NPSPACE) In contradistinction to this, Descriptive Complexity Theory specifies a problem as the set of finite models of a certain logical sentence, e.g. the set of three-colorable finite graphs arises in this manner in second-order logic.
For each of the five machine-based complexity classes listed above there is a logic whose sentences "capture" this class.
(Descriptive complexity theory is more or less co-extensive with finite model theory.)
The lecture is designed in such a way that students may also gain a seminar certificate by solving a set of exercises or giving a one-hour talk.
- Empfohlene Literatur
- (1) S. Arora, B. Barak : Computational Complexity. A modern approach. Cambridge 2009
(2) H.-D. Ebbinghaus, Joerg Flum : Finite Model Theory, Springer 1998
(3) L. Libkin : Elements of Finite Model Theory. Springer 2004
- ECTS-Informationen:
- Title:
- Computational and Descriptive Complexity
- Credits: 5
- Zusätzliche Informationen
- Erwartete Teilnehmerzahl: 10, Maximale Teilnehmerzahl: 10
Für diese Lehrveranstaltung ist eine Anmeldung erforderlich.
Die Anmeldung erfolgt über: persönlich beim Dozenten
- Institution: Lehrstuhl für Informatik 10 (Systemsimulation)
|
 |
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|