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

Logik und Komplexität (HK) (32227)

Thema dieser Vorlesung ist der Zusammenhang zwischen logischer Beschreibbarkeit und Komplexität. Ein Schwerpunkt ist die deskriptive Komplexitätstheorie, in der der Zusammenhang zwischen Beschreibungskomplexität und klassischer Berechnungskomplexität von Problemen untersucht wird. So können wichtige Komplexitätsklassen wie P und NP durch Erweiterungen der Logik erster Stufe beschrieben werden. Zur Bestimmung der Ausdrucksstärke der relevanten Logiken werden unter anderem Zwei-Personen Spiele behandelt. Stichworte: deskriptive Komplexität, endliche Modelltheorie, Ehrenfeucht-Fraïssé-Spiele, Fixpunktlogiken.

Anwendungen von Graphzerlegungen in Algorithmik und Logik (HK) (32228)

Viele der in der Praxis auftretenden algorithmischen Probleme auf Graphen sind NP-schwer und lassen daher keine effizienten Verfahren zu ihrer Lösung erwarten. Klassische Beispiele dafür sind Probleme aus der Routenplanung oder Färbungsprobleme. Andererseits werden viele dieser Probleme einfach, wenn man sich nur auf Bäume oder planare Graphen beschränkt. Planare Graphen sind z.B. bei der Routenplanung interessant, da die meisten Straßen- oder S-Bahn-Netze nahezu planar sind. Ausgehend von diesen Ergebnissen versucht man, möglichst große Klassen von Graphen zu identifizieren, die Polynomialzeit-Lösungsverfahren für wichtige algorithmische Probleme erlauben. Im Rahmen dieser Vorlesung werden wir uns mit effizienten Lösungsverfahren für algorithmische Probleme auf eingeschränkten Klassen von Graphen befassen. Zunächst werden dabei Methoden zum Lösen solcher Probleme auf planaren Graphen behandelt. Anschließend werden wir auf Verallgemeinerungen von Bäumen und planaren Graphen eingehen, z.B. auf "baumartige" Graphen beschränkter Baumweite oder Graphenklassen mit verbotenen Minoren. Des Weiteren werden wir Constraint-Satisfaction-Probleme auf Hypergraphen beschränkter Hyperbaumweite effizient lösen. Grundkenntnisse in Graphentheorie und Vertrautheit mit Graphzerlegungen sind hilfreich aber nicht nötig. Alle für die Vorlesung benötigten Begriffe der Graphentheorie werden neu eingeführt.

Graphen und Algorithmen 2 (HK) (32231)

Die VL setzt den im WS 2006/2007 abgehaltenen Teil 1 fort. Es werden anspruchsvollere Prinzipien der Graphenalgorithmen betrachtet, wie zum Beispiel Approximationsalgorithmen, randomisierte Verfahren und lineare Programmierung. Die VL wird durch Übungen begleitet. Kenntnis des ersten Teils der VL ist wünschenswert, aber nicht notwendig.

Analytische Kombinatorik (HK) (32232)

Erzeugende Funktionen sind ein wichtiges Werkzeug der enumerativen Kombinatorik. Dieser Kurs ist eine einfache Einleitung zu erzeugenden Funktionen, veranschaulicht durch viele Beispiele und Anwendungen. Der Kurs behandelt formale Potenzreihen, analytische Eigenschaften der Funktionen, die als Potenzreihe dargestellt werden und einige Techniken, um die Asymptotik der Koeffizienten der erzeugenden Funktionen abzuleiten.

Kryptologie – Hilfsmittel und Algorithmen (HK-1. Teil) (32233)

In dieser Vorlesung werden Grundlagen der Kryptologie zusammen mit den entsprechenden Programmen und Algorithmen behandelt. Es sind nämlich sehr oft nicht mathematische Schwächen, die Sicherheitslücken verursachen, sondern Implementierungsfehler oder Konzeptmängel. Die Vorlesung lehnt sich an das OpenSSL-Paket an. Es werden die damit umgesetzten Algorithmen, wie AES, Base64, Camellia, DES, ECDSA, Feistel-Chiffre und so weiter bis zum X.509-Standard und zu Zertifikaten behandelt.