Zum Inhalt springen
Technische Universität Berlin English
Vorlesungsverzeichnis und Modultransfersystem

Theoretische InformatikModulbeschreibung #41282 / Version 1

← Zur Modulseite English version
Modul / Version#41282 / #1
GültigkeitSeit SoSe 2026
Verfügbare Sprache(n)Englisch, Deutsch
Leistungspunkte6
Modulverantwortliche*rNichterlein, André
BenotungBenotet
PrüfungsformSchriftliche Prüfung
Lehrsprache(n)Deutsch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34351100 FG Algorithmik und Komplexitätstheorie (AKT)

Kontakt

SekretariatEN 23
Ansprechpartner*inThielcke, Christlinde
E-Mail-Adresselehre@akt.tu-berlin.de
Webseitehttps://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.

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

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Theoretische InformatikTutorium Wintersemester[de]2 ISIS
Theoretische InformatikVorlesung Wintersemester[de]2 ISIS

Fakultativer Bereich

Aus den folgenden Veranstaltungen muss eine Auswahl abgeschlossen werden:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Theoretische InformatikGroßübung Wintersemester[de]2 ISIS

Veranstaltungen im Vorlesungsverzeichnis

Veranstaltungen, die aus den Lehrveranstaltungen dieses Moduls angelegt wurden.

WiSe 2026/27 (17)

Theoretische Informatik (Tutorium) 15

Alle Gruppen dieser Lehrveranstaltung im Verzeichnis

Theoretische Informatik (Vorlesung) 1

Alle Gruppen dieser Lehrveranstaltung im Verzeichnis

Theoretische Informatik (Großübung) 1

Alle Gruppen dieser Lehrveranstaltung im Verzeichnis

Arbeitsaufwand und Leistungspunkte

Theoretische Informatik (Tutorium)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
Vor-/Nachbereitung151 h15 h
45 h

Theoretische Informatik (Vorlesung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
Vor-/Nachbereitung (inkl. optionaler Besuch der Großübung)153 h45 h
75 h

Theoretische Informatik (Großübung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
30 h

Lehrveranstaltungsunabhängiger Aufwand

AufwandbeschreibungMultiplikatorStundenGesamt
Bearbeitung der Hausaufgaben für den Übungsschein130 h30 h
Klausurvorbereitung130 h30 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.

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

BenotungBenotet
PrüfungsformSchriftliche Prüfung
SpracheDeutsch
Dauer/Umfang2 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

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.

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 / StuPOSemesterStudiengangsbereich
Informatik
StuPO 2015
SoSe 2026Pflichtbereich
WiSe 2026/27Pflichtbereich › Theoretische Grundlagen der Informatik
Informatik
StuPO 2025
WiSe 2026/27Pflichtbereich › Mathematisch-algorithmisch-konzeptionelle Kompetenzen

Sonstiges

Keine Angabe