Theoretische Grundlagen der InformatikModule description #40743 / Version 1
- 6 CP
- Portfolio examination
- Graded
- Winter and summer semester
- German
This module description is not valid in the current semester (Winter semester 2026/27).
Current version (v8)
| Module / Version | #40743 / #1 |
|---|---|
| Validity | SS 2014 – SS 2014 |
| 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 | 34352100 FG Modellierung kognitiver Prozesse |
Contact
| Office | MAR 5-3 |
|---|---|
| Contact person | Müller-Villbrandt, Sonja |
| E-mail address | cognition@tu-berlin.de |
| Website | http://www.cognition.tu-berlin.de/menue/teaching/ |
Learning outcomes
Absolventinnen und Absolventen dieses Moduls sind in der Lage, die grundlegenden Begriffe und Formalismen der Diskreten Mathematik eigenständig anzuwenden. Sie beherrschen den Umgang mit formalen Sprachen und Grammatiken sowie mit den wichtigsten theoretischen Maschinenmodellen. Sie besitzen ein Verständnis der grundlegenden Komplexitätsklassen und sind befähigt, die Komplexität ausgewählter Beispielprobleme zu beurteilen.
Die Veranstaltung vermittelt überwiegend:
Fachkompetenz 60% Methodenkompetenz 30% Systemkompetenz 10% Sozialkompetenz 0%
Die Veranstaltung vermittelt überwiegend:
Fachkompetenz 60% Methodenkompetenz 30% Systemkompetenz 10% Sozialkompetenz 0%
Content
Mengen, Abbildungen, Relationen, Ordnungen
Grammatiken, Chomsky-Hierarchie
endliche Automaten, Kellerautomaten, Turingmaschinen
Aufwand von Algorithmen und Komplexität von Problemen
Komplexität von Wortproblemen der Chomsky-Hierarchie
P, NP und NP-Vollständigkeit
Grammatiken, Chomsky-Hierarchie
endliche Automaten, Kellerautomaten, Turingmaschinen
Aufwand von Algorithmen und Komplexität von Problemen
Komplexität von Wortproblemen der Chomsky-Hierarchie
P, NP und NP-Vollständigkeit
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Theoretische Grundlagen der Informatik | Integrated course | 0434 L 370 | Winter and summer semester | – | 4 | WS 2026/27 (3) ISIS |
Courses in the course catalog
Courses created from the teaching units of this module.
Winter semester 2026/27 (3)
Theoretische Grundlagen der Informatik (Integrated course) 3
- Theoretische Grundlagen der Informatik (Integrierte Veranstaltung) Großübung 0434 L 370
- Theoretische Grundlagen der Informatik (Integrierte Veranstaltung) Vorlesung 1 0434 L 370
- Theoretische Grundlagen der Informatik (Integrierte Veranstaltung) Vorlesung 2 0434 L 370
Workload and credit points
Theoretische Grundlagen der Informatik (Integrated course)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor- und Nachbereitung | 15 | 8 h | 120 h |
| 180 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| 0 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| 0 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 im Vorlesungsstil vermittelt. Die Anwendung und Festigung
des Stoffs geschieht durch das Besprechen von Übungsaufgaben im interaktiven Stil.
des Stoffs geschieht durch das Besprechen von Übungsaufgaben im interaktiven Stil.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
This module has no desirable prerequisites for the courses.
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 |
|---|---|---|---|
| 1. Hausaufgabe | 10 | ||
| 2. Hausaufgabe | 10 | ||
| Endklausur | 40 | ||
| Zwischenklausur | 40 |
Exam description
1. Hausaufgabe zur Semestermitte
Zwischenklausur in der Semestermitte
2. Hausaufgabe zum Semesterende
Abschlussklausur am Semesterende
Zwischenklausur in der Semestermitte
2. Hausaufgabe zum Semesterende
Abschlussklausur am Semesterende
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: Winter and summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
http://www.akt.tu-berlin.de/
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
available – Vorlesungsfolien sind unter www.isis.tu-berlin.de verfügbar.
Recommended literature
- Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson Education Deutschland / Addison Wesley
- Theoretische Informatik - kurzgefasst (Taschenbuch)Uwe Schöning Spektrum Akademischer Verlag
Assigned programs
This module is not used in any program.
Miscellaneous
Not specified