Theoretische Grundlagen der Informatik 2 (Automaten und Komplexität)Module description #40745 / Version 1
- 6 CP
- Portfolio examination
- Graded
- Summer semester
- German
This module description is not valid in the current semester (Winter semester 2026/27).
| Module / Version | #40745 / #1 |
|---|---|
| Validity | SS 2014 – Summer semester 2020 |
| Available language(s) | German |
| Credit points | 6 |
| Person responsible for the module | Niedermeier, Rolf |
| Grading | Graded |
| Exam format | Portfolio examination |
| Language(s) of instruction | German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34351100 FG Algorithmik und Komplexitätstheorie (AKT) |
Contact
| Office | TEL 5-1 |
|---|---|
| Contact person | Not specified |
| E-mail address | lehre@akt.tu-berlin.de |
| Website | http://www.akt.tu-berlin.de/menue/teaching |
Learning outcomes
Die Studierenden beherrschen den Umgang mit formalen Sprachen, Grammatiken, endlichen Automaten, Kellerautomaten und Turingmaschinen. Sie besitzen ein Verständnis der grundlegenden Komplexitätsklassen und sind befähigt, die Komplexität ausgewählter Problembeispiele zu beurteilen. Entsprechende Aufgabenstellungen können sie sowohl selbständig als auch in Kleingruppen bearbeiten.
Das Modul vermittelt überwiegend:
Fachkompetenz 50x Methodenkompetenz 50x Systemkompetenz 0x Sozialkompetenz 0x
Das Modul vermittelt überwiegend:
Fachkompetenz 50x Methodenkompetenz 50x Systemkompetenz 0x Sozialkompetenz 0x
Content
* Chomsky-Hierarchie mit den verschiedenen Grammatiktypen
* deterministische und nichtdeterministische endliche Automaten
* Äquivalenz von endlichen Automaten und regulären Grammatiken
* deterministische und nichtdeterministische Kellerautomaten
* Äquivalenz von Kellerautomaten und kontextfreien Grammatiken
* deterministische und nichtdeterministische Turingmaschinen
* Äquivalenz von Turingmaschinen und Chomsky-Grammatiken
* Aufwand von Algorithmen und Komplexität von Problemen
* Komplexität von Wortproblemen der Chomsky-Hierarchie Rechenaufwand
* P, NP und NP-Vollständigkeit
* Satz von Cook
* deterministische und nichtdeterministische endliche Automaten
* Äquivalenz von endlichen Automaten und regulären Grammatiken
* deterministische und nichtdeterministische Kellerautomaten
* Äquivalenz von Kellerautomaten und kontextfreien Grammatiken
* deterministische und nichtdeterministische Turingmaschinen
* Äquivalenz von Turingmaschinen und Chomsky-Grammatiken
* Aufwand von Algorithmen und Komplexität von Problemen
* Komplexität von Wortproblemen der Chomsky-Hierarchie Rechenaufwand
* P, NP und NP-Vollständigkeit
* Satz von Cook
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Automaten und Komplexität (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 6 h | 90 h |
| 120 h | |||
Automaten und Komplexität (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 2 h | 30 h |
| 60 h | |||
The workload of the module adds up to 180 hours. The module therefore comprises 6 credit points.
Description of teaching and learning methods
Die fachlichen Inhalte des Moduls werden in der Vorlesung vermittelt. Zudem wird eine Großübung angeboten, in der nochmals auf besondere Themen der Vorlesung eingegangen wird sowie Problemlösungen erläutert werden. Es wird jedoch kein zusätzlicher
Lehrstoff vermittelt, daher ist die Teilnahme fakultativ.
Die Anwendung und Festigung des Stoffs geschieht durch das regelmäßige Bearbeiten von Aufgabenblättern und die Besprechung des Stoffs und der Aufgaben in Tutorien im interaktiven Stil. Die Aufgaben werden von den Studierenden in Kleingruppen
bearbeitet. Die Unterrichtssprache im Modul ist deutsch.
Lehrstoff vermittelt, daher ist die Teilnahme fakultativ.
Die Anwendung und Festigung des Stoffs geschieht durch das regelmäßige Bearbeiten von Aufgabenblättern und die Besprechung des Stoffs und der Aufgaben in Tutorien im interaktiven Stil. Die Aufgaben werden von den Studierenden in Kleingruppen
bearbeitet. Die Unterrichtssprache im Modul ist deutsch.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Es wird die Kenntnis des Moduls „Grundlagen und algebraische Strukturen” vorausgesetzt
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Portfolio examination |
| Language | German |
Test elements
| Name | Points/Weight | Category | Duration/Extent |
|---|---|---|---|
| Endklausur | 80 | ||
| Multiple-Choice-Test | 20 |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Bachelor-Informatik-Studenten mit QISPOS-Kennung melden sich in QISPOS an. Darin sind die Anmeldungen zum Multiple-Choice-Test und EK enthalten.
Bachelor-Teilnehmer ohne QISPOS-Kennung, Diplom-Studenten sowie andere Studiengänge melden sich direkt im Prüfungsamt an.
Die Anmeldung zu den Tutorien erfolgt über MOSES.
Bachelor-Teilnehmer ohne QISPOS-Kennung, Diplom-Studenten sowie andere Studiengänge melden sich direkt im Prüfungsamt an.
Die Anmeldung zu den Tutorien erfolgt über MOSES.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
available
Recommended literature
- Uwe Schöning: Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008
Assigned programs
This module is not used in any program.
Miscellaneous
Not specified