Wissensrepräsentation
Team
Abteilungsleiter
Sekretariat
Wissenschaftliche Mitarbeiter:Innen
Lehre
Wintersemester 2024/25
Die Komplexitätstheorie beschäftigt sich mit der inhärenten Komplexität von Berechnungsproblemen: wie viel Zeit (oder andere Ressourcen) benötigt man, um ein gegebenes Problem zu lösen—unabhängig davon, wie raffiniert der Algorithmus ist, den man verwendet? Es geht also um die Grenzen der Berechenbarkeit unter beschränkten Ressourcen. Damit stellt die Komplexitätstheorie eine wichtige Grundlage für den Entwurf und das Verständnis von effizienten Algorithmen dar. Ausserdem versucht sie, die natürliche Neugierde nach dem in der Informatik prinzipiell machbaren zu befriedigen. Diese Vorlesung bietet eine Einführung in die grundlegenden Begriffe und Resultate der Komplexitätstheorie inklusive einer Behandlung der wichtigsten Komplexitätsklassen und einiger fortgeschrittener Themen wie interaktive Beweissysteme.
Moodle-Kursseite
Die Algorithmische Lerntheorie beschäftigt sich aus der Sicht der theoretischen Informatik mit den Grundlagen des maschinellen Lernens. Mit dem zentralen Begriff des PAC Lernens wird mathematisch erfasst, was im formalen Sinne überhaupt unter Lernen (aus positiven und negativen Beispielen) zu verstehen ist. Wichtige Fragen sind dann unter anderem: für welche Konzeptklassen ist lernen möglich? Wie viele Trainingsbeispiele sind erforderlich, um mit großer Wahrscheinlichkeit und kleinem Fehler auf nicht während des Trainings betrachtete Beispiele zu generalisieren? Wann ist lernen in polynomieller Zeit möglich? Neben dem PAC Lernen wird sich diese Vorlesung auch mit anderen Lernmodellen beschäftigen, insbesondere mit Angluin's aktivem Lernen.
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.
Sommersemester 2024
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.
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
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.
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.
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
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.
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
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.
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.
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
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.
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.
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.
