Theoretische InformatikModulbeschreibung #41282 / Version 1
- 6 LP
- Schriftliche Prüfung
- Benotet
- Wintersemester
- Deutsch
| Modul / Version | #41282 / #1 |
|---|---|
| Gültigkeit | Seit SoSe 2026 |
| Verfügbare Sprache(n) | Englisch, Deutsch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Nichterlein, André |
| Benotung | Benotet |
| Prüfungsform | Schriftliche Prüfung |
| Lehrsprache(n) | Deutsch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34351100 FG Algorithmik und Komplexitätstheorie (AKT) |
Kontakt
| Sekretariat | EN 23 |
|---|---|
| Ansprechpartner*in | Thielcke, Christlinde |
| E-Mail-Adresse | lehre@akt.tu-berlin.de |
| Webseite | https://www.tu.berlin/akt/studium-lehre/lehrveranstaltungen |
Lernergebnisse
Absolventinnen und Absolventen dieses Moduls beherrschen grundlegende Konzepte der theoretischen Informatik aus den Teilgebieten Formale Sprachen und Automaten, Berechenbarkeit sowie Komplexität.
Insbesondere verstehen sie formale Sprachen und zugehörige Entscheidungsprobleme als Werkzeuge der mathematisch-exakten Formalisierung von Berechnungsproblemen.
Sie beherrschen Repräsentationen formaler Sprachen in Form von Grammatiken, endlichen Automaten, Kellerautomaten und Turingmaschinen. Sie besitzen ein Grundverständnis der Berechenbarkeit von Entscheidungsproblemen sowie grundlegender Komplexitätsklassen. Sie sind befähigt, die Berechnungskomplexität ausgewählter Problembeispiele zu beurteilen.
Entsprechende Aufgabenstellungen können sie sowohl selbständig als auch in Kleingruppen bearbeiten.
Insbesondere verstehen sie formale Sprachen und zugehörige Entscheidungsprobleme als Werkzeuge der mathematisch-exakten Formalisierung von Berechnungsproblemen.
Sie beherrschen Repräsentationen formaler Sprachen in Form von Grammatiken, endlichen Automaten, Kellerautomaten und Turingmaschinen. Sie besitzen ein Grundverständnis der Berechenbarkeit von Entscheidungsproblemen sowie grundlegender Komplexitätsklassen. Sie sind befähigt, die Berechnungskomplexität ausgewählter Problembeispiele zu beurteilen.
Entsprechende Aufgabenstellungen können sie sowohl selbständig als auch in Kleingruppen bearbeiten.
Lehrinhalte
* Wörter, Sprachen
* Chomsky-Hierarchie, Grammatiken, Nichtdeterminismus
* Endliche Automaten, reguläre Ausdrücke, Myhill-Nerode
* Kellerautomaten, CYK-Algorithmus
* Turingmaschinen, Random-Access-Maschinen, Churchsche These
* Halteproblem und Unentscheidbarkeit
* Reduzierbarkeit zwischen Problemen
* Satz von Rice
* Komplexität von Wortproblemen, Rechenaufwand, Komplexitätsklassen, Zeithierarchiesatz
* Aufwand von Algorithmen und Komplexität von Problemen wie SAT oder CLIQUE
* P, NP und NP-Vollständigkeit
* Satz von Cook und Levin
* Chomsky-Hierarchie, Grammatiken, Nichtdeterminismus
* Endliche Automaten, reguläre Ausdrücke, Myhill-Nerode
* Kellerautomaten, CYK-Algorithmus
* Turingmaschinen, Random-Access-Maschinen, Churchsche These
* Halteproblem und Unentscheidbarkeit
* Reduzierbarkeit zwischen Problemen
* Satz von Rice
* Komplexität von Wortproblemen, Rechenaufwand, Komplexitätsklassen, Zeithierarchiesatz
* Aufwand von Algorithmen und Komplexität von Problemen wie SAT oder CLIQUE
* P, NP und NP-Vollständigkeit
* Satz von Cook und Levin
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Theoretische Informatik | Tutorium | Wintersemester | [de] | 2 | WiSe 2026/27 (15) ISIS | |
| Theoretische Informatik | Vorlesung | Wintersemester | [de] | 2 | WiSe 2026/27 (1) ISIS |
Fakultativer Bereich
Aus den folgenden Veranstaltungen muss eine Auswahl abgeschlossen werden:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Theoretische Informatik | Großübung | Wintersemester | [de] | 2 | WiSe 2026/27 (1) ISIS |
Veranstaltungen im Vorlesungsverzeichnis
Veranstaltungen, die aus den Lehrveranstaltungen dieses Moduls angelegt wurden.
WiSe 2026/27 (17)
Theoretische Informatik (Tutorium) 15
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 10:00 - 12:00 MA 542
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 12:00 - 14:00 MA 648
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 12:00 - 14:00 MA 751
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 16:00 - 18:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Do. 15.10 - 17.12.26, wöchentlich, Do. 07.01 - 11.02.27, wöchentlich, 12:00 - 14:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Fr. 16.10 - 18.12.26, wöchentlich, Fr. 08.01 - 12.02.27, wöchentlich, 10:00 - 12:00 MA 142
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 10:00 - 12:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 12:00 - 14:00 EB 133C
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 12:00 - 14:00 MA 742
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 14:00 - 16:00 E-N 193
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 14:00 - 16:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 10:00 - 12:00 M 128
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 10:00 - 12:00 MA 142
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 12:00 - 14:00 MA 551
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 14:00 - 16:00 MA 143 (Tafel defekt)
Theoretische Informatik (Vorlesung) 1
- Theoretische Informatik (Vorlesung) Vorlesung
Theoretische Informatik (Großübung) 1
- Theoretische Informatik (Großübung) Großübung
Arbeitsaufwand und Leistungspunkte
Theoretische Informatik (Tutorium)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 1 h | 15 h |
| 45 h | |||
Theoretische Informatik (Vorlesung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung (inkl. optionaler Besuch der Großübung) | 15 | 3 h | 45 h |
| 75 h | |||
Theoretische Informatik (Großübung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| 30 h | |||
Lehrveranstaltungsunabhängiger Aufwand
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Bearbeitung der Hausaufgaben für den Übungsschein | 1 | 30 h | 30 h |
| Klausurvorbereitung | 1 | 30 h | 30 h |
| 60 h | |||
Der Aufwand des Moduls summiert sich zu 210 Stunden. Damit umfasst das Modul 6 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
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 Hausaufgabenblättern und die Besprechung des Stoffs und von Übungsaufgaben in Tutorien im interaktiven Stil. Die Aufgaben werden von den Studierenden in Kleingruppen bearbeitet.
Die Anwendung und Festigung des Stoffs geschieht durch das regelmäßige Bearbeiten von Hausaufgabenblättern und die Besprechung des Stoffs und von Übungsaufgaben in Tutorien im interaktiven Stil. Die Aufgaben werden von den Studierenden in Kleingruppen bearbeitet.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
Kenntnisse aus dem Modul "Formalmathematische Grundlagen".
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Die Prüfungsvoraussetzungen konnten nicht abgerufen werden.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Schriftliche Prüfung |
| Sprache | Deutsch |
| Dauer/Umfang | 2 Stunden |
Prüfungsbeschreibung (Abschluss des Moduls)
Beschreibung der Vorleistungen:
Der unbenotete Übungsschein wird mit insgesamt 50% der Punkte in den regelmäßigen zweiwöchigen Hausaufgaben erlangt.
Aufwand: ca. 30h
Der unbenotete Übungsschein wird mit insgesamt 50% der Punkte in den regelmäßigen zweiwöchigen Hausaufgaben erlangt.
Aufwand: ca. 30h
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Wintersemester.
Maximale teilnehmende Personen
Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.
Anmeldeformalitäten
Die Lehrmaterialien werden über ISIS bereitgestellt.
Die Einteilung der Tutorien erfolgt über MOSES in der ersten Vorlesungswoche.
Die Prüfungsanmeldung erfolgt in der Regel Online.
Teilnehmende mit Übungsschein (erlangt mit 50% der Gesamtpunkte der Hausaufgaben) werden zur Prüfung zugelassen.
Die An- und Abmeldefristen werden sowohl auf ISIS als auch in der Präsenzveranstaltung bekannt gegeben.
Die Einteilung der Tutorien erfolgt über MOSES in der ersten Vorlesungswoche.
Die Prüfungsanmeldung erfolgt in der Regel Online.
Teilnehmende mit Übungsschein (erlangt mit 50% der Gesamtpunkte der Hausaufgaben) werden zur Prüfung zugelassen.
Die An- und Abmeldefristen werden sowohl auf ISIS als auch in der Präsenzveranstaltung bekannt gegeben.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
- Elaine Rich: Automata, Computability, and Complexity, Pearson, 2008
- Uwe Schöning: Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008
Zugeordnete Studiengänge
Diese Modulversion wird in folgenden Studiengängen verwendet:
| Studiengang / StuPO | Semester | Studiengangsbereich |
|---|---|---|
| Informatik StuPO 2015 | SoSe 2026 | Pflichtbereich |
| WiSe 2026/27 | Pflichtbereich › Theoretische Grundlagen der Informatik | |
| Informatik StuPO 2025 | WiSe 2026/27 | Pflichtbereich › Mathematisch-algorithmisch-konzeptionelle Kompetenzen |
Sonstiges
Keine Angabe