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

Verteilte Algorithmen (HK)

Ein Algorithmus heißt verteilt, wenn er auf einer physikalisch oder logisch verteilten Architektur arbeitet. Solche Algorithmen werden praktisch zunehmend wichtiger. In der Vorlesung wird eine Reihe solcher Algorithmen vorgestellt und ihre Korrektheit bewiesen. Mit Vorlesungen zu Methoden und Modellen des Systementwurfes oder zur Computergestützten Verifikation ergänzt sich dieser Halbkurs zu einem Ganzkurs.

Computergestützte Verifikation (HK -– auch Praktische Informatik)

Wir studieren computergestützte Verfahren, mit denen überprüft werden kann, ob ein gegebenes Modell eines Systems eine gegebene Spezifikation erfüllt. Der erste Teil betrifft finite state systems, z.B. Schaltkreise und Protokolle, wo leistungsstarke Methoden es bereits bis zur Praxisreife bringen. Der zweite Teil handelt von infinite state systems, unter anderem Echtzeitsystemen, hybriden Systemen und Software, die gerade im Mittelpunkt gegenwärtiger Forschung stehen.

Logik in der Informatik (HK)

Logik spielt ein grundlegende Rolle in vielen verschiedenen Bereichen der Informatik, etwa dem Schaltkreisentwurf, dem Software-Engineering, der künstlichen Intelligenz, der Datenbanken, und natürlich auch der theoretischen Informatik. Die Logik in der Informatik baut auf der mathematischen Logik auf, die sich etwa seit Ende des 19. Jahrhunderts herausgebildet hat. In den letzten 30 Jahren hat sich die Logik in der Informatik aber in eine eigenständige, von den Anwendungen bestimmte Richtung entwickelt.
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.

SAT-Solving und Constraint Satisfaction Probleme (HK)

Im Zentrum der Vorlesung steht das Erfüllbarkeitsproblem der Aussagenlogik (kurz SAT-Problem), d.h. das Problem, zu einer gegebenen Formel der Aussagenlogik zu entscheiden, ob sie eine erfüllende Belegung besitzt. Wegen seiner Allgemeinheit lassen sich viele praktische Probleme auf das SAT-Problem reduzieren. So findet das Problem Anwendungen im Bereich der Planungsprobleme in der künstlichen Intelligenz, im Bereich des Model-Checkings und verschiedenen anderen Gebieten. Obschon das Problem 1971 von Cook als NP-vollständig nachgewiesen wurde, sind in den letzten Jahren SAT-Solver entwickelt worden, die Formeln mit vielen tausend Variablen routinemäßig auf Erfüllbarkeit hin überprüfen können. Erst diese Algorithmen erlauben die Anwendung des SAT-Problems im industriellen Maßstab. Im Verlauf des Vorlesung werden wir verschiedene sehr unterschiedliche Verfahren und Methoden rund um das SAT-Problem kennen lernen. Zunächst werden die verschiedenen Ansätze zur Entwicklung von Algorithmen zur Lösung des Problems vorgestellt, insbesondere die auf dem DLL-Algorithmus aufbauenden Suchverfahren sowie randomisierte Algorithmen. Daneben werden wir auf die verschiedenen praktischen Anwendungen des Problems eingehen, z.B. im Bereich des Bounded-Model-Checking. Einen wichtigen Teil der Vorlesung werden aber auch Methoden einnehmen, mit denen untere Schranken für die Laufzeit von SAT-Algorithmen nachgewiesen werden können. Wir werden im Verlauf der Vorlesung sehr nah an die aktuelle Forschung in diesem Gebiet herankommen. Daher kann die Vorlesung interessierten Studierenden als Basis für darauf aufbauende Studien- und Diplomarbeiten dienen.

Graphen und Algorithmen (HK oder K - 1. Teil)

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.
http://www.informatik.hu-berlin.de/Forschung_Lehre/algorithmen/lehre/ lvws0405/VL_ga1.html

Stochastische Prozesse (HK, auch math. Ergänzungsfach)

Stochastische Prozesse sind Prozesse, die von zufaelligen Ereignissen beeinflusst werden. Beispiele in der Informatik sind etwa randomisierte Algorithmen, die zur Loesung eines Problems den Zufall als Hilfsmittel benutzen. Auch viele Prozesse in Anwendungsgebieten koennen als stochastische Prozesse modelliert werden. Gegenstand der Vorlesung sind Methoden zur Untersuchung stochastischer Prozesse sowie einige fuer die Informatik relevante Beispielklassen.

Randomisierte Algorithmen und Probabilistische Analyse (HK)

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.

Kryptologie 1 (HK)

Kryptografische Verfahren dienen u.a. der sicheren Speicherung und Übertragung von Daten oder Nachrichten. In der Vorlesung werden sowohl symmetrische Verschlüsselungsverfahren (wie DES und IDEA) als auch Public-Key Systeme (wie RSA und ElGamal) behandelt.