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

Logik in der Informatik (HK) (32 225)

Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen. Wichtige Themen der Logik in der Informatik sind die Ausdruckstärke formaler Sprachen und die Grenzen und Möglichkeiten des automatischen Schließens. Anwendungen der Logik finden sich in so unterschiedlichen Bereichen der Informatik wie Rechnerarchitektur, Softwaretechnik, Programmiersprachen, Datenbanken, künstliche Intelligenz, Komplexitäts- und Berechenbarkeitstheorie.
Aufbauend auf den Grundlagen der Theoretischen Informatik I werden in dieser Vorlesung auch tiefliegendere Ergebnisse und Zusammenhänge aus der Logik vorgestellt. Dabei wird es sowohl um klassische Sätze der mathematischen Logik, etwa die Gödelschen Unvollständigkeitssätze, als auch um die Anwendungen in verschiedenen Bereichen der Informatik gehen.
Die Vorlesung ist eine Kernveranstaltung im Bereich der Logik in der Informatik, auf der weitere Veranstaltungen an den Lehrstühlen Logik in der Informatik, Logik und Datenbanktheorie sowie Logik und Diskrete Systeme aufbauen.

Logik, Spiele und Automaten (HK) (32 226)

Thema der Vorlesung sind die theoretischen Grundlagen des Entwurfs und der Verifikation reaktiver Systeme, wie beispielsweise Kontrollsysteme oder Kommunikationsprotokolle. Methodisch stützt sich die Theorie auf eine Kombination von Automatentheorie, logischen Systemen zur Beschreibung von Berechnungen, und unendlichen 2-Personenspielen. Die Vorlesung gibt eine Einführung in die einzelnen Methoden und vor allem in die Zusammenhänge zwischen den Methoden. Besonderes Augenmerk wird dabei auf algorithmische Anwendungen im Bereich des Systementwurfs und der Verifikation gerichtet.

Graphen und Algorithmen 1(HK) (32 227)

Ein Graph besteht aus einer Menge von Knoten, von denen einige durch sog. Kanten verbunden sind. Mit Hilfe dieser relativ einfachen Struktur lassen sich viele wichtige Probleme modellieren und mittels geeigneter Graphenalgorithmen auch effizient loesen. Im Mittelpunkt des Halbkurses stehen Grundlagen von Graphenalgorithmen, Netzwerkfluesse, das Traveling Salesman Problem, Graphenfaerbung und planare Graphen.

Randomisierte Algorithmen und Probabilistische Analyse (HK) (32 228)

Randomized algorithms and probabilistic analysis are important tools in algorithm design and complexity theory. Randomness used in algorithms often leads to much faster algorithms that are easier to analyze than determinsitic algorithms, and the probabilistic viewpoint is essential to understand some computational models. This course covers basic probability theory, random graphs, and Markov chain Monte Carlo methods.

Komplexitätstheorie (HK) (32 229)

In dieser Vorlesung untersuchen wir eine Reihe von wichtigen algorithmischen Problemstellungen aus verschiedenen Bereichen der Informatik. Unser besonderes Interesse gilt dabei der Abschätzung der Rechenressourcen, die zu ihrer Lösung aufzubringen sind. Die Vorlesung bildet eine wichtige Grundlage für weiterführende Veranstaltungen in den Bereichen Algorithmen, Kryptologie, Algorithmisches Lernen und Algorithmisches Beweisen.