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, 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

Yvo Meeres

Wiss. Mitarbeiterin

Paulinum
Augustusplatz 10, Raum P 821
04109 Leipzig

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

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 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.