Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Zahlreiche wichtige algorithmische Probleme sind zwar komplexitätstheoretisch schwer, etwa NP-schwer, müssen aber in der Praxis dennoch gelöst werden. Dass dies gelingen kann, liegt daran, dass die in der Praxis vorkommenden Instanzen oft eine recht "einfache Struktur" aufweisen. Versucht man zu verstehen, was "einfache Struktur" hier bedeutet, so stößt man häufig auf Begriffe wie "baumartige" oder "hierarchisch strukturierte" Instanzen. Baumzerlegungen von Graphen geben eine natürliche Präzisierung solcher intuitiver Begriffe. Sie spielen eine wichtige Rolle sowohl in der Graphentheorie als auch in der Algorithmik. Insbesondere lassen sich sehr viele NP-schwere algorithmische Probleme effizient auf Instanzen mit guten Baumzerlegungen lösen. Diese Vorlesung ist eine Einführung in die Theorie der Baumzerlegungen und verwandter Zerlegungen und in ihre algorithmischen Anwendungen. Dabei sollen sowohl die graphentheoretischen Grundlagen als auch die algorithmischen Techniken vermittelt werden.

Automatische Theorembeweiser, also Programme, mit deren Hilfe man korrekte Folgerungen aus einer formalisierten Theorie ziehen kann, spielen eine wichtige Rolle als Werkzeuge in der Hard- und Softwareverifikation und der künstlichen Intelligenz. In der Vorlesung sollen die grundlegenden Techniken vorgestellt werden, die in modernen Theorembeweisern verwendet werden. Im Projektteil erhalten die Studierenden die Möglichkeit, diese Techniken in eigenen, prototypischen Theorembeweisern umzusetzen und zu erproben.

Die Vorlesung ist eine Einführung in die lineare Optimierung. Der Inhalt der Vorlesung sind Simplexverfahren und Dualität, sowie deren Anwendung zur Lösung von Transportproblemen und Verflechtungsaufgaben aus der Wirtschaft. Zur VL findet eine Übung statt.

Die Petrinetze haben sich als wichtiges Hilfsmittel zur Beherrschung des Entwurfs großer Systeme erwiesen. Als Hauptvorteil der Anwendung von Petrinetzen beim Systementwurf werden gewöhnlich ihre Anschaulichkeit und Analysierbarkeit genannt. Die Anschaulichkeit erleichtert den Übergang von einer verbalen Systembeschreibung zu einer formalen Systemspezifikation als Petrinetz-Modell. Die Analysierbarkeit des Petrinetz-Modells gewährleistet seine Verifizierbarkeit, nämlich die Möglichkeit, die Erfülltheit der Spezifikationen nicht durch Simulation des Modells, sondern durch Analyse zu beweisen. In den klassischen Petrinetzen ist die Zeit nur implizit als kausaler Zusammenhang zwischen Ereignissen modellierbar. In dieser Vorlesung werden wir verschiedene Erweiterungen der klassischen Petrinetzen kennen lernen, die eine explizite Modellierung der Zeit ermöglichen und Möglichkeiten der Analyse für diese zeitabhängigen Netze studieren.

Die theoretischen Grundlagen von modernen Datenbanksystemen beruhen zu einem wesentlichen Teil auf zahlreichen Verbindungen zur Logik. Eine relationale Datenbank ist aus Sicht der Logik einfach eine Grundmenge mit mathematischen Relationen; eine SQL-Anfrage ist im Kern eine Formel der Logik erster Stufe. Aufgrund dieses Zusammenhangs ermöglichen Techniken aus dem Bereich der Logik es, präzise Aussagen über die Ausdrucksstärke und die Auswertungskomplexität von Datenbankanfragesprachen zu treffen.
Die Vorlesung will den genannten Zusammenhang darstellen und die Grundzüge der Theorie relationaler Datenbanken sowie einige Erweiterungen hinsichtlich semistrukturierter Daten (XML) vorstellen. Themen sind unter anderem: Verbindungen zwischen SQL und Logik, statische Analyse und Anfrageoptimierung, Anfragesprachen mit Rekursion (Datalog), Ausdrucksstärke und Auswertungskomplexität von Anfragesprachen, semistrukturierte Daten.

Die Veranstaltung behandelt fortgeschrittene Fragestellungen aus der Kombinatorischen Optimierung, welche mit Hilfe von Graphen modelliert und gelöst werden können. Themen sind u.a.: perfekte Graphen und das Cliquenproblem, das Travelling-Salesman-Problem, Polytope und Graphen, das Regularitätsdilemma, Approximationsalgorithmen für Graphenprobleme, Grenzen der Approximierbarkeit.

Generating functions are an important tool in enumerative combinatorics. This course is a gentle introduction to generating functions, illustrated by many examples and applications. It will deal with formal power series, analytic properties of functions represented as power series and several techniques to derive asymptotics of the coefficients of generating functions. The participants will learn how to use generating functions to enumerate combinatorial objects and derive the asymtotics.
http://www.informatik.hu-berlin.de/Institut/struktur/algorithmen/lehr e/lvss06/VL_comb.html

Die moderne Kryptografie bietet neben Verfahren zur sicheren Übertragung von Nachrichten auch Lösungen für eine ganze Palette weiterer Aufgaben an. Beispielsweise können kryptografische Hashfunktionen die Integrität von Nachrichten und Daten sicherstellen, und digitale Signaturen erlauben es, die Urheberschaft eines Dokuments zu verifizieren.