1. Modulverzeichnis (MTS)
  2. Module
  3. Modulbeschreibung anzeigen

Theoretische Informatik

Zur Modulseite PDF generieren

#41282 / #1

Seit SoSe 2026

Deutsch, Englisch

Theoretische Informatik

6

Nichterlein, André

Benotet

Schriftliche Prüfung

Deutsch

Zugehörigkeit


Fakultät IV

Institut für Softwaretechnik und Theoretische Informatik

34351100 FG Algorithmik und Komplexitätstheorie

Keine Angabe

Kontakt


EN 23

Thielcke, Christlinde

lehre@akt.tu-berlin.de

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.

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:

LehrveranstaltungenArtNummerTurnusSpracheSWS ISIS VVZ
Theoretische InformatikTUTWiSede2
Theoretische InformatikVLWiSede2

Fakultativer Bereich

LehrveranstaltungenArtNummerTurnusSpracheSWS ISIS VVZ
Theoretische InformatikGroßübungWiSede2
ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

Theoretische Informatik (TUT):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.02.0h30.0h
Vor-/Nachbereitung15.01.0h15.0h
45.0h(~2 LP)

Theoretische Informatik (VL):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.02.0h30.0h
Vor-/Nachbereitung (inkl. optionaler Besuch der Großübung)15.03.0h45.0h
75.0h(~3 LP)

Theoretische Informatik (Großübung):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.02.0h30.0h
30.0h(~1 LP)

Lehrveranstaltungsunabhängiger Aufwand:

AufwandbeschreibungMultiplikatorStundenGesamt
Bearbeitung der Hausaufgaben für den Übungsschein1.030.0h30.0h
Klausurvorbereitung1.030.0h30.0h
60.0h(~2 LP)
Der Aufwand des Moduls summiert sich zu 180.0 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:

Voraussetzung
Leistungsnachweis »Unbenoteter Übungsschein«

Abschluss des Moduls

Benotung

Benotet

Prüfungsform

Schriftliche Prüfung

Sprache(n)

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

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

Verfügbarkeit:  nicht verfügbar

 

Skript in elektronischer Form

Verfügbarkeit:  nicht verfügbar

 

Literatur

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 / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
Dieses Modul findet in keinem Studiengang Verwendung.

Studierende anderer Studiengänge können dieses Modul ohne Kapazitätsprüfung belegen.

Sonstiges

Keine Angabe