Team

Abteilungsleiter

Default Avatar

Prof. Dr. Carsten Lutz

Universitätsprofessor

Paulinum
Augustusplatz 10, Raum P 810
04109 Leipzig

Telefon: +49 341 97-32343
Telefax: +49 341 97-32299

Sekretariat

Default Avatar

Petra Gamrath

Sekretärin

Paulinum
Augustusplatz 10, Raum  P 825
04109 Leipzig

Telefon: +49 341 97-32230
Telefax: +49 341 97-32299

Wissenschaftliche Mitarbeiter:Innen

Default Avatar

Maurice Funk

Wiss. Mitarbeiter

Paulinum
Augustusplatz 10, Raum P 812
04109 Leipzig

Telefon: +49 341 97-32236
Telefax: +49 341 97-32299

Default Avatar

Gustav Leopold Grabolle

Wiss. Mitarbeiter

Paulinum
Augustusplatz 10, Raum P 821
04109 Leipzig

Telefon: +49 341 97-32234
Telefax: +49 341 97-32299

Default Avatar

Simon Hosemann

Wiss. Mitarbeiter

Paulinum
Augustusplatz 10, Raum P 823
04109 Leipzig

Default Avatar

Quentin Maniere

Wiss. Mitarbeiter

Löhrs Carré
Humboldtstraße 25, Raum D03.27
04105 Leipzig

Default Avatar

Dr. Marcin Przybylko

Wiss. Mitarbeiter

Paulinum
Augustusplatz 10, Raum P 812
04109 Leipzig

Telefon: +49 341 97-32286
Telefax: +49 341 97-32299

Default Avatar

Lukas Schulze

Wiss. Mitarbeiter

Paulinum
Augustusplatz 10, Raum P 812
04109 Leipzig

Telefon: +49 341 97-32365
Telefax: +49 341 97-32299

Lehre

Sommersemester 2024

MOODLE-KURSSEITE

Beschreibungslogiken sind eine Familie von Wissensrepräsentationsformalismen, die es erlauben, die wichtigen Begriffe eines Anwendungsbereiches (seine Terminologie) in einer formalen, logik-basierten Sprache zu beschreiben. Derartige Logiken werden in verschiedenen Anwendungen eingesetzt, insbesondere aber zur semantischen Annotation von Daten in der Datenintegration und im World Wide Web. So basiert etwa die bekannte Web Ontology Language OWL im wesentlichen auf einer Beschreibungslogik. Die Vorlesung beginnt mit einer Einführung in das Gebiet der Beschreibungslogik und der Ontologien. In diesem Teil werden die Syntax und Semantik verschiedener Beschreibungslogiken sowie grundlegende Schlussfolgerungsprobleme diskutiert. Darauf aufbauend werden wir die Ausdrucksstärke verschiedener Logiken untersuchen, die Komplexität der wichtigsten Schlussfolgerungsprobleme analysieren, sowie die Grundlagen für in der Praxis effiziente Algorithmen entwickeln.

Moodle-Kursseite​​​​​​​

Logik gehört zu den zentralen theoretischen Grundlagen der Informatik und hat einen wesentlichen Einfluss auf die Entwicklung verschiedener Teilgebiete wie beispielsweise Datenbanken, Verifikation, Komplexitätstheorie und formale Sprachen. Diese Vorlesung bietet eine Einführung in die grundlegenden Themen der Logik, mit einem Schwerpunkt auf der Aussagenlogik und der Prädikatenlogik erster Stufe sowie einem kurzen Blick in die Prädikatenlogik zweiter Stufe.

Moodle-Kursseite

Parametrisierte Komplexitätsbetrachtungen sind ein aktuelles und wichtiges Thema in der Algorithmen- und Komplexitätstheorie. Man betrachtet schwere (meist NP-vollständige) Probleme sowie interessante Parametrisierungen dieser Probleme. Eine Parametrisierung ist insbesondere dann interessant, wenn sich ein Algorithmus findet, der nur im Parameter exponentielle Laufzeit hat, nicht aber in der Eingabegröße. Dies nennt man "Fixed-Parameter Tractable (FPT)". Beispielsweise ist das Erfüllbarkeitsproblem der Aussagenlogik FPT, wenn man als Parameter die Anzahl der Variablen wählt. Im Gegensatz dazu ist das Cliquenproblem (wahrscheinlich) nicht FPT, wenn man als Parameter die Cliquengröße wählt. Da es oft viele natürliche Parametrisierungen gibt, entsteht ein großer Raum von Komplexitätsfragen. In den letzten Jahren hat sich im Gebiet der parametrisierten Komplexität ein reichhaltiger Schatz von algorithmischen Techniken entwickelt, mit denen die parametrisierte Komplexität analysiert und Probleme in FPT platziert werden können. Diese Techniken stehen im Mittelpunkt des angebotenen Seminars.

Wintersemester 2023/24

Moodle-Kursseite

Wörter und formale Sprachen sind ein grundlegendes Abstraktionsmittel der Informatik, mit denen z.B. Programme und verschiedene Arten von Datenstrukturen beschrieben werden können. In dieser Vorlesung werden zwei wichtige Klassen von formalen Sprachen vorgestellt, die regulären Sprachen und die kontextfreien Sprachen. Eng verknüpft mit formalen Sprachen sind Automaten und Grammatiken, die endliche Beschreibungen von unendlichen Sprachen zur Verfügung stellen. Wir stellen Automaten und Grammatiken für reguläre und kontextfreie Sprachen vor und studieren zentrale algorithmische Probleme, die im Zusammenhang damit stehen.

Moodle-Kursseite

Die Vorlesung beschäftigt sich mit fortgeschrittenen Themen der Prädikatenlogik erster und höherer Stufe. Präsentiert werden unter anderem bekannte Techniken und Resultate aus den Bereichen endliche Modelltheorie und deskriptive Komplexitätstheorie, wie etwa Ehrenfeucht-Fraisse Spiele in verschiedenen Varianten, Lokalität, der Satz von Fagin und verwandte Resultate auf geordneten Strukturen, der Satz von Büchi, 0/1-Gesetze und der Satz von Courcelle.

Moodle-Kursseite

In diesem Seminar werden ausgesuchte Themen der theoretischen Informatik behandelt, unter anderem aus den Bereichen Automatentheorie, Komplexitätstheorie, Berechenbarkeit und Logik. Voraussetzung ist das Grundwissen aus den Veranstaltungen "Logik", "Automaten und Sprachen", sowie "Berechenbarkeit". Die Teilnehmer wählen eines der angebotenen Themen, bearbeiten dieses selbstständig und stellen es in einem Vortrag vor.

In diesem Seminar werden aktuelle Forschungsthemen aus den Bereichen Wissensrepräsentation, Datenbanktheorie, Logik in der Informatik und theoretische Informatik diskutiert. Es dient zudem dem Halten von Abschlussvorträgen für Masterarbeiten. Studierende sind herzlich willkommen, das Seminar kann jedoch nicht wie ein übliches MSc-Seminar belegt werden.

Das Seminar findet unregelmäßig Mittwochs 15-17 Uhr im Raum P701 statt. Der erste Termin ist am 18.10.

Sommersemester 2023

Moodle-Kursseite

Beschreibungslogiken sind eine Familie von Wissensrepräsentationsformalismen, die es erlauben, die wichtigen Begriffe eines Anwendungsbereiches (seine Terminologie) in einer formalen, logik-basierten Sprache zu beschreiben. Derartige Logiken werden in verschiedenen Anwendungen eingesetzt, insbesondere aber zur semantischen Annotation von Daten in der Datenintegration und im World Wide Web. So basiert etwa die bekannte Web Ontology Language OWL im wesentlichen auf einer Beschreibungslogik. Die Vorlesung beginnt mit einer Einführung in das Gebiet der Beschreibungslogik und der Ontologien. In diesem Teil werden die Syntax und Semantik verschiedener Beschreibungslogiken sowie grundlegende Schlussfolgerungsprobleme diskutiert. Darauf aufbauend werden wir die Ausdrucksstärke verschiedener Logiken untersuchen, die Komplexität der wichtigsten Schlussfolgerungsprobleme analysieren, sowie die Grundlagen für in der Praxis effiziente Algorithmen entwickeln.

Moodle-Kursseite​​​​​​​

Logik gehört zu den zentralen theoretischen Grundlagen der Informatik und hat einen wesentlichen Einfluss auf die Entwicklung verschiedener Teilgebiete wie beispielsweise Datenbanken, Verifikation, Komplexitätstheorie und formale Sprachen. Diese Vorlesung bietet eine Einführung in die grundlegenden Themen der Logik, mit einem Schwerpunkt auf der Aussagenlogik und der Prädikatenlogik erster Stufe sowie einem kurzen Blick in die Prädikatenlogik zweiter Stufe.

Moodle-Kursseite

Parametrisierte Komplexitätsbetrachtungen sind ein aktuelles und wichtiges Thema in der Algorithmen- und Komplexitätstheorie. Man betrachtet schwere (meist NP-vollständige) Probleme sowie interessante Parametrisierungen dieser Probleme. Eine Parametrisierung ist insbesondere dann interessant, wenn sich ein Algorithmus findet, der nur im Parameter exponentielle Laufzeit hat, nicht aber in der Eingabegröße. Dies  nennt man  "Fixed-Parameter Tractable (FPT)". Beispielsweise ist das Erfüllbarkeitsproblem der Aussagenlogik FPT, wenn man als Parameter die Anzahl der Variablen wählt. Im Gegensatz dazu ist das Cliquenproblem (wahrscheinlich) nicht FPT, wenn man als Parameter die Cliquengröße wählt. Da es oft viele natürliche Parametrisierungen gibt, entsteht ein großer Raum von Komplexitätsfragen. In den letzten Jahren hat sich im Gebiet der parametrisierten Komplexität  ein reichhaltiger Schatz von algorithmischen Techniken entwickelt, mit denen die parametrisierte Komplexität analysiert und Probleme in FPT platziert werden können. Diese Techniken stehen im Mittelpunkt des angebotenen Seminars

Wintersemester 2022/23

Moodle-Kursseite

Wörter und formale Sprachen sind ein grundlegendes Abstraktionsmittel der Informatik, mit denen z.B. Programme und verschiedene Arten von Datenstrukturen beschrieben werden können. In dieser Vorlesung werden zwei wichtige Klassen von formalen Sprachen vorgestellt, die regulären Sprachen und die kontextfreien Sprachen. Eng verknüpft mit formalen Sprachen sind Automaten und Grammatiken, die endliche Beschreibungen von unendlichen Sprachen zur Verfügung stellen. Wir stellen Automaten und Grammatiken für reguläre und kontextfreie Sprachen vor und studieren zentrale algorithmische Probleme, die im Zusammenhang damit stehen.

Moodle-Kursseite

Die Vorlesung beschäftigt sich mit fortgeschrittenen Themen der Prädikatenlogik erster und höherer Stufe. Präsentiert werden unter anderem bekannte Techniken und Resultate aus den Bereichen endliche Modelltheorie und deskriptive Komplexitätstheorie, wie etwa Ehrenfeucht-Fraisse Spiele in verschiedenen Varianten, Lokalität, der Satz von Fagin und verwandte Resultate auf geordneten Strukturen, der Satz von Büchi, 0/1-Gesetze und der Satz von Courcelle.

Moodle-Kursseite

Das Ziel von Data Mining ist die Analyse von großen Datenmengen mittels verschiedener, oft statistisch geprägter Verfahren. Als Resultat des Data Mining entsteht ein "Modell" der Daten welches beispielsweise die Form einer Zusammenfassung oder einer Datenselektion annehmen kann. Prominente Beispiel für Data Mining Techniken sind Googles Pagerank Verfahren zur Beurteilung der Relevanz von Webseiten für ein gegebenes Suchthema und Amazons Artikelvorschlagssystem, das auf Basis von angesehenen Artikeln weitere relevante Artikel empfehlen kann. Im Kontext von großen Datenmengen, wie sie in unserer modernen Welt zunehmend verfügbar sind (Stichwort "Big Data"), spielt Data Mining heute in vielen Anwendungen der Informatik eine zentrale Rolle. Das Seminar beschäftigt sich mit dem Mining großer Datenmengen und basiert auf dem Buch Mining of Massive Datasets von Jure Leskovec, Anand Rajaraman und Jeffrey D. Ullman.

Sommersemester 2022

MOODLE-KURSSEITE 

Beschreibungslogiken sind eine Familie von Wissensrepräsentationsformalismen, die es erlauben, die wichtigen Begriffe eines Anwendungsbereiches (seine Terminologie) in einer formalen, logik-basierten Sprache zu beschreiben. Derartige Logiken werden in verschiedenen Anwendungen eingesetzt, insbesondere aber zur semantischen Annotation von Daten in der Datenintegration und im World Wide Web. So basiert etwa die bekannte Web Ontology Language OWL im wesentlichen auf einer Beschreibungslogik. Die Vorlesung beginnt mit einer Einführung in das Gebiet der Beschreibungslogik und der Ontologien. In diesem Teil werden die Syntax und Semantik verschiedener Beschreibungslogiken sowie grundlegende Schlussfolgerungsprobleme diskutiert. Darauf aufbauend werden wir die Ausdrucksstärke verschiedener Logiken untersuchen, die Komplexität der wichtigsten Schlussfolgerungsprobleme analysieren, sowie die Grundlagen für in der Praxis effiziente Algorithmen entwickeln.

Moodle-Kursseite 

Logik gehört zu den zentralen theoretischen Grundlagen der Informatik und hat einen wesentlichen Einfluß auf die Entwicklung verschiedener Teilgebiete wie beispielsweise Datenbanken, Verifikation, Komplexitätstheorie und formale Sprachen. Diese Vorlesung bietet eine Einführung in die grundlegenden Themen der Logik, mit einem Schwerpunkt auf der Aussagenlogik und der Prädikatenlogik erster Stufe sowie einem kurzen Blick in die Prädikatenlogik zweiter Stufe.

 

Moodle-Kursseite

Parametrisierte Komplexitätsbetrachtungen sind ein aktuelles und wichtiges Thema in der Algorithmen- und Komplexitätstheorie. Man betrachtet schwere (meist NP-vollständige) Probleme sowie interessante Parametrisierungen dieser Probleme. Eine Parametrisierung ist insbesondere dann interessant, wenn sich ein Algorithmus findet, der nur im Parameter exponentielle Laufzeit hat, nicht aber in der Eingabegröße. Dies  nennt man  "Fixed-Parameter Tractable (FPT)". Beispielsweise ist das Erfüllbarkeitsproblem der Aussagenlogik FPT, wenn man als Parameter die Anzahl der Variablen wählt. Im Gegensatz dazu ist das Cliquenproblem (wahrscheinlich) nicht FPT, wenn man als Parameter die Cliquengröße wählt. Da es oft viele natürliche Parametrisierungen gibt, entsteht ein großer Raum von Komplexitätsfragen. In den letzten Jahren hat sich im Gebiet der parametrisierten Komplexität  ein reichhaltiger Schatz von algorithmischen Techniken entwickelt, mit denen die parametrisierte Komplexität analysiert und Probleme in FPT platziert werden können. Diese Techniken stehen im Mittelpunkt des angebotenen Seminars.

Forschung

Auf einem Blatt Paper sind viele Formeln zu sehen

Publikationen

Hier geht es zu unseren Publikationen.

mehr erfahren