Informatik-Kolloquien
323. Informatik-Kolloquium
Hochschulöffentliche Vorträge im Rahmen des Berufungsverfahrens
Vorträge, Montag, 20. Juni 2022 und Dienstag 21. Juni 2022
Die Übertragung erfolgt per Videokonferenzsystem BigBlueButton.
Die Zugangsdaten können vorher im Dekanat ( dekanat@…) erfragt werden.
20. Juni 2022, 09:15 Uhr - Frau Prof. Dorothea Baumeister
NP-Vollständigkeit und das P/NP-Problem
In diesem Lehrvortrag wird zunächst die Klasse NP und das Konzept der NP-Vollständigkeit kurz eingeführt. Danach wird der Satz von Cook angegeben. Darauf aufbauend wird dann am Beispiel des Problems der unabhängigen Menge in Graphen ein NP-Vollständigkeitsbeweis erarbeitet und an einem konkreten Beispiel erläutert. Zum Abschluss erfolgt eine Diskussion über die Hintergründe der NP-Vollständigkeit, sowie das damit zusammenhängende P/NP-Problem.
Collective Decisions Through Scoring Systems
This talk will give a brief overview of the field computational social choice, an interdisciplinary research area at the interface between computer science and social choice theory. The use of mechanisms originating from social choice theory in computer science applications, especially in artificial intelligence (e.g., recommender systems and multi-agent systems), emerges diverse research questions. A formal mathematical specification and analysis of these mechanisms is required and different forms of influence arise new importance since the outcome may have major consequences. A central topic in computational social choice is the study of elections, where votes are given as ordered lists over candidates. A common way of determining winners is then to apply some scoring system, where each position is associated with a specific score. This setting is transferable to other situations such as sports tournaments. The design of such systems, i.e., the choice of score values, may have a crucial influence. This talk will summarize some theoretical results for this problem, as well as a case study of data from Formula 1.
20. Juni 2022, 10:45 Uhr - Herr Dr. Pascal Lenzner
NP-Vollständigkeit und das P/NP-Problem
Zusammenfassung: Ist das Verifizieren einer gegebenen Lösung einfacher als die Berechnung einer Lösung? Diese fundamentale Frage steckt hinter dem größten offenen Problem der theoretischen Informatik: Dem P/NP Problem. In dieser Lehreinheit wird dieses Problem formal definiert und anhand von Beispielen aus der Routenplanung illustriert. Wir werden die Komplexitätsklasse NP kennenlernen und mittels des Begriffs der NP-Vollständigkeit die interessante Beobachtung, dass ein einziger effizienter Algorithmus für eines von tausenden praktisch relevanten Problemen genügen würde, um die große Frage der Informatik zu lösen. Auf dem Weg zu dieser Einsicht werden wir ein wichtiges und überaus nützliches Konzept der Informatik antreffen: Die Polynomialzeit-Reduktion von Entscheidungsproblemen.
An Algorithmic Game Theory View on Network Creation and Location Choice
Many phenomena like the structure of the Internet, the emergence of homogeneous communities in cities, and the location choices of competing firms in a spatial market are the outcome of the complex interaction of selfish agents. These settings can be modeled as strategic games and methods from the thriving research area Algorithmic Game Theory can be employed to rigorously analyze them. In this talk I will highlight some of the key research questions in Algorithmic Game Theory with case studies in selfish network creation and strategic location choice. In particular, I will focus on measuring the quality of equilibrium outcomes via the Price of Anarchy, the study of game dynamics via potential function analysis, and on efficient algorithms for deciding equilibrium existence. With the use of these concepts I will present insights on when a central authority is needed for creating networks, why residential patterns in cities stabilize over time, and how competing firms can find a suitable location for their facilities.
20. Juni 2022, 13:00 Uhr- Herr Dr. Dominik Scheder
NP-Vollständigkeit und das P/NP-Problem
In diesem 20-minütigen Vortrag werde ich die Komplexitätsklassen P und NP so wie die Konzepte der Reduktion und der NP-Vollständigkeit anhand einschlägiger Beispiele einführen:
- Erreichbarkeit in Graphen als Beispiel eines Problems, für das wir einen effizienten und einfachen Algorithmus kennen (zum Beispiel Tiefensuche)
- Perfekte Matchings in bipartite Graphen als Beispiel eines Problems, für das wir einen effizienten aber nicht einfachen Algorithmus kennen.
- Hamiltonscher Kreis als Beispiel eines NP-vollständigen Problems.
Anhand der obigen Beispiele werde ich nun eine informelle Definition der Klassen P und NP geben. Als nächstes werde ich den Begriff der Reduktion mit zwei Beispielen erklären:
- Reduktion eines einfachen Domino-Überdeckungsproblems auf Perfekte Matchings. Dies tue ich, um die wohl intuitivere Richtung von Reduktionen zu verdeutlichen: von einem neuen Problem A auf ein bereits gelöstes, bekannt einfaches Problem B.
- Reduktion von Hamiltonschem Kreis auf das Traveling-Salesman-Problem. Zweck ist, die in Komplexitätstheorie übliche aber a priori weniger intuitive Richtung zu illustrieren: die Reduktion eines bekannt schwierigen Problems A auf ein neues Problem B.
Jetzt können wir das Phänomen der NP-Vollständigkeit einführen. Für eine vollständige Definition hätten wir natürlich auch den Begriff "effizienter Algorithmus" präzise definieren müssen. In einer "richtigen" Lehrvorlesung wäre das wohl bereits in einer früheren Sitzung geschehen.
Past and future research on Boolean Satisfiability
The Boolean Satisfiability Problem, short SAT, is perhaps the most central NP-complete problem. Although this dashes any hope for an efficient algorithm, tremendous amounts of research is done in designing heuristics that work well on real-world instances (SAT solvers); identifying easy subclasses; finding moderately exponential algorithms (improing over brute force search); and understanding its general role in complexity theory. In this talk, I will tell the story of the quest for moderately exponential algorithms, its successes and failures, and how it has lead to a sequence of fruitful conjectures. Also, I will explain why understanding SAT is important not only from an algorithmic point of view but also for making progress towards another holy grail of theoretical computer science, which is circuit lower bounds.
20. Juni 2022, 14:30 Uhr- Herr Dr. Kevin Schewior
NP-Vollständigkeit und das P/NP-Problem
In dieser Lehrprobe werden wir kurz die Definitionen von P und NP aus der vergangenen Vorlesung wiederholen. Wir werden anschließend natürliche Beispielprobleme aus NP kennenlernen, deren Zugehörigkeit zu P nicht eindeutig ist. Es wird sich herausstellen, dass es sich bei diesen Problemen um sogenannte NP-vollständige Probleme handelt, d.h. Probleme, deren Zugehörigkeit zu P die Zugehörigkeit zu P *aller* Probleme in NP bedeuten würde. Ob Ersteres der Fall ist, ist jedoch eine der großen ungelösten Fragen der Mathematik: Das P/NP-Problem, für dessen Lösung Sie eine Million Dollar (und jede Menge Ruhm) erhalten.
Algorithms under Low Information Cost: Theory and Applications
Traditionally, one assumes that the entire input data to algorithmic problems is known and that the bottleneck to achieving optimal solutions is computational power. In practice, however, this view is often oversimplified since, for instance, the solution quality may depend on events that happen in the future. In some applications, it may be possible to eradicate some of the uncertainty at some information cost. In this presentation, I introduce theoretical models for such settings as well as my results and visions for this field. Finally, I present cooperations with practical parters, in which we also face uncertainty.
21. Juni 2022, 09:15 Uhr - Frau Dr. Karin Quaas
NP-Vollständigkeit und das P/NP-Problem
In der letzten Vorlesung haben wir gezeigt, dass 2-SAT in P liegt.
Für die Probleme SAT, 3-SAT und CNFSAT hingegen haben wir keinen Polynomialzeitalgorithmus kennengelernt. Diese Probleme scheinen erheblich schwerer zu sein als 2-SAT.
Eine der größten offenen Fragen der Informatik ist die Frage, ob alle Probleme, die in der Komplexitätsklasse NP liegen, in polynomieller Zeit gelöst werden können; mit anderen Worten, gilt P=NP? Für einige der in NP liegenden Probleme wurden im Laufe der Zeit Polynomialzeitalgorithmen vorgestellt (z.B. Primzahltest). Für die schwersten der in NP liegenden Probleme ist dies bisher nicht gelungen. Aber was sind die schwersten Probleme? In dieser Vorlesung lernen wir den Begriff der NP-vollständigen Probleme kennen. Wir werden formal beweisen, dass es sich bei SAT, 3-SAT und CNFSAT um NP-vollständige, also um Beispiele der schwersten in NP liegenden Probleme handelt.
Emptiness Problem for Constraint Büchi Automata
We study the emptiness problem for constraint Büchi automata. A constraint automaton is a Büchi automaton equipped with a finite set of variables ranging over some infinite data domain. The transitions of the automaton are labelled with constraints that put restrictions on the values of the variables. A typical constraint for variables ranging over the integers is that the current value of a variable should be strictly smaller than the value of another variable at the next position of the input word. Solving the emptiness problem for such automata, that is, determining whether the language accepted by a given constraint B\"uchi automaton is empty or not, amounts up to solving a constraint satisfaction problem on infinitely many variables. This can be challenging, depending on the data domain and the relations that are used to define the constraints. We give an overview over recent results concerning the emptiness problem.
(This is a talk about joint work with Stephane Demri and Dominik Peteler.)
21. Juni 2022, 10:45 Uhr - Herr Dr. Joachim Spoerhase
NP-Vollständigkeit und das P/NP-Problem
In dieser Lehrprobe lernen wir das Konzept der Polynomialzeitreduktion kennen, mit dem wir Entscheidungsprobleme hinsichtlich ihrer Schwierigkeit miteinander vergleichen können. Wir zeigen, dass das Erfüllbarkeitsproblem (SAT) aus der Aussagenlogik auf das Cliquenproblem aus der Graphentheorie reduzierbar ist. Wir diskutieren auch den Satz von Cook-Levin, der besagt, dass SAT NP-vollständig, und somit jedes Problem in NP auf SAT reduzierbar ist. Wir beobachten, dass NP-Vollständigkeit ein universelles Phänomen ist, das auf zahlreiche Entscheidungsprobleme aus verschiedensten Anwendungsbereichen zutrifft. Schließlich lernen wir das eng damit verknüpfte P-NP-Problem kennen, welches eine der wichtigsten offenen Fragen der theoretischen Informatik darstellt.
Towards Understanding the Role of Structure in Combinatorial Optimization
The task of determining an optimal solution to a given problem (combinatorial optimization problem) is ubiquitous in computer science, mathematics, and many related areas of application. A prominent example is the very active research area of clustering problems, which aim at categorizing a set of objects into groups (clusters) of similar objects. Clustering problems arise, for example, in data analysis, machine learning, social choice, and operations research. From an algorithms and complexity point of view, the ultimate goal in combinatorial optimization is to design algorithms that achieve a provably best-possible trade-off between the quality of the solution computed by the algorithm and the required computational resources such as running time. For various basic (nearly unstructured) types of problems such provably best-possible algorithms are known from the literature. On the other hand, existing results for more structured problems (arising in the various domains of application) are much more scattered and ad-hoc. In this talk, I give an overview over my research plans. My first goal is to build a unified theory of optimization algorithms for structured problems arising, for example, in clustering, packing, network design, and geometry. My second goal is to leverage the structural properties of more realistic problem instances in order to obtain stronger provable bounds on quality and computational resources. I discuss some of my previous results for clustering, packing, network design, and geometric optimization problems, which can be seen as first steps towards these goals.
21. Juni 2022, 13:00 Uhr - Herr Dr. Armin Weiß
NP-Vollständigkeit und das P/NP-Problem
Nach einer kurzen informellen Definition der Klassen P und NP, werde ich einige typische Probleme für beide Klassen beschreiben. Auf zwei NP-vollständige Probleme möchte ich hierbei genauer eingehen: Erfüllbarkeit Boolscher Formeln (SAT) und das 3-Färbbarkeitsproblem für Graphen. Hier werde ich zeigen, dass beide Probleme in Polynomialzeit aufeinander reduziert werden können. Diese Beispiele illustrieren auf einfache Weisen den Nutzen und die Bedeutung von Reduktionen sowie den Begriff der NP-Vollständigkeit. Mit dem (Vor-)Wissen, dass SAT NP-vollständig ist, folgt nun, dass auch 3-Färbbarkeit NP-vollständig ist. Zum Abschluss möchte ich mögliche Konsequenzen von P gleich NP bzw. P ungleich NP skizzieren.
Sorting: Practice, Theory, and Beyond
Sorting is among the most fundamental tasks performed by computers. Therefore, efficient sorting algorithms are of general interest. In this talk I will present some of my recent results concerning both practical and theoretical aspects of sorting. First, we will consider Blockquicksort, an approach to avoid conditional branches in Quicksort yielding up to a 2x speed-up compared to classical Quicksort implementations. The key idea is to separate the control flow (comparisons) from the data flow. After that we will turn to QuickXsort. This is a general scheme which can be used to combine Quicksort with some other sorting algorithm X. The advantage is that, even if X requires additional space for data elements, QuickXsort often can be implemented in-place. A natural candidate for X is Mergesort allowing for an efficient in-place Mergesort variant. In the last part of the talk, I will give a short overview of computational problems in group theory, which are a main focus of my research. Here, I study the complexity of the word, conjugacy, isomorphism, equation satisfiability, and other problems also using methods from the neighboring fields of circuit complexity and algebraic complexity.
Alle interessierten Personen sind herzlich eingeladen!
