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

Logik und dichte GraphenModulbeschreibung #41349 / Version 1

← Zur Modulseite English version
Modul / Version#41349 / #1
GültigkeitSeit WiSe 2026/27
Verfügbare Sprache(n)Englisch, Deutsch
Leistungspunkte9
Modulverantwortliche*rKreutzer, Stephan
BenotungBenotet
PrüfungsformMündliche Prüfung
Lehrsprache(n)Englisch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34352200 FG Logik und Semantik (LaS)

Kontakt

SekretariatEN 25
Ansprechpartner*inPilz, Jana
E-Mail-Adressesekretariat@las.tu-berlin.de
Webseitehttps://www.tu.berlin/las/studium-lehre/veranstaltungsangebot

Lernergebnisse

Die Studierenden lernen eine Vielzahl von Konzepten und Methoden aus den Bereichen der Logik kennen, die als Modelltheorie und endliche Modelltheorie bekannt sind, sowie interessante neue Methoden der Kombinatorik und Graphentheorie. Insbesondere werden sie verstehen, wie diese Werkzeuge aus scheinbar sehr unterschiedlichen Fachgebieten zusammenwirken und kombiniert werden können, um wichtige Graphklassen im Rahmen der Dichteklasse zu verstehen, und wie man dies algorithmisch nutzt.

Lehrinhalte

Die Untersuchung der Komplexität der Modellprüfung von Logiken wie der Logik erster Ordnung hat eine tiefe und äußerst fruchtbare Verbindung zwischen der strukturellen und algorithmischen Graphentheorie und der rechnerischen Logik aufgezeigt. Lange Zeit konzentrierte sich die Forschung auf diesem Gebiet auf spärliche Klassen von Graphen, wobei Strukturen und Konzepte wie Graphminoren oder die Spärlichkeitstheorie eine zentrale Rolle spielten.

In den letzten Jahren hat sich die Forschung auf diesem Gebiet auf die Untersuchung dichter Klassen von Graphen verlagert. In der Graphentheorie wurden dichte Klassen von Graphen oft in Form von Zufallsgraphen untersucht, doch diese sind im Zusammenhang mit Modellprüfungs-Problemen in der rechnerischen Logik von geringerer Bedeutung.

Stattdessen sind Graphklassen, die durch Konzepte wie Stabilität oder Unabhängigkeit aus der Modelltheorie definiert sind, in den Fokus der aktuellen Forschung gerückt. Ursprünglich in logischen Begriffen definiert, hat sich in den letzten Jahren eine reichhaltige kombinatorische Theorie solcher Klassen herausgebildet.

Das Hauptziel dieses Vortrags ist es, die jüngsten Entwicklungen auf diesem Gebiet zu beleuchten. Wir werden die relevanten Werkzeuge aus der Modelltheorie vorstellen, die zur Definition von Konzepten wie stabilen und abhängigen Graphenklassen verwendet wurden. Anschließend werden wir wichtige kombinatorische Werkzeuge behandeln, die in den letzten Jahren bewiesen wurden, um diese Konzepte besser zu verstehen, und algorithmische Anwendungen der sich entwickelnden Theorie besprechen.
Abschließend werden wir auch das Konzept der Eckpunkt-Minoren und ihre Rolle in der Theorie dichter Graphen vorstellen.

Ein Großteil dieser Vorlesung befasst sich mit Forschungsergebnissen, die erst in den letzten Jahren gewonnen wurden, darunter auch einige aktuelle und laufende Forschungsprojekte.

Daher wird die Vorlesung sehr nah am aktuellen Forschungsstand sein.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Logic and Dense GraphsVorlesung Wintersemester[en]4 ISIS
Logic and Dense GraphsÜbung Wintersemester[en]2 ISIS

Veranstaltungen im Vorlesungsverzeichnis

Veranstaltungen, die aus den Lehrveranstaltungen dieses Moduls angelegt wurden.

WiSe 2026/27 (3)

Logic and Dense Graphs (Vorlesung) 2

Alle Gruppen dieser Lehrveranstaltung im Verzeichnis

Logic and Dense Graphs (Übung) 1

Alle Gruppen dieser Lehrveranstaltung im Verzeichnis

Arbeitsaufwand und Leistungspunkte

Logic and Dense Graphs (Vorlesung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit154 h60 h
Vor-/Nachbereitung158 h120 h
180 h

Logic and Dense Graphs (Übung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
Vor-/Nachbereitung154 h60 h
90 h

Der Aufwand des Moduls summiert sich zu 270 Stunden. Damit umfasst das Modul 9 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

Das Modul besteht aus einer Vorlesung, in der die relevanten Inhalte behandelt werden, sowie aus wöchentlichen Übungsstunden, die den Studierenden das Verständnis der Vorlesung erleichtern sollen.

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

Für diese Vorlesung gibt es keine festgelegten Voraussetzungen. Alle erforderlichen Werkzeuge und Methoden werden in der Vorlesung vorgestellt und erläutert.

Von den Studierenden dieser Vorlesung wird jedoch erwartet, dass sie über gewisse Grundkenntnisse in Logik verfügen, wie sie beispielsweise im Bachelor-Kurs „Logik“ des Informatikstudiengangs vermittelt werden.

Darüber hinaus sind ein ausgeprägtes Interesse an theoretischer Informatik sowie ein angemessenes Maß an sogenannter mathematischer Reife erforderlich.

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

BenotungBenotet
PrüfungsformMündliche Prüfung
SpracheEnglisch
Dauer/Umfang20-45 Minuten

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 Studierenden können sich gegen Ende des Semesters wie gewohnt für die Prüfung anmelden.

Literaturhinweise, Skripte

Skript in Papierform

nicht verfügbar

Skript in elektronischer Form

verfügbar – Wir werden eine Sammlung von Vorlesungsskripten zusammenstellen, die den Studierenden, die den Kurs belegen, zur Verfügung gestellt wird.

Empfohlene Literatur

Keine empfohlene Literatur angegeben

Zugeordnete Studiengänge

Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOSemesterStudiengangsbereich
Computer Engineering
StuPO 2015
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Computer Science (Informatik)
StuPO 2015
WiSe 2026/27Wahlpflichtbereich › Studiengebiete › Grundlagen der Informatik / Foundations of Computing
Elektrotechnik
StuPO 2015
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing

Sonstiges

Keine Angabe