Lehrveranstaltungen
Bachelor Basismodule
-
Diskrete Modellierung
Inhalt
In der Informatik wird die Modellierung mit Hilfe diskreter Strukturen als typische Arbeitsmethode in vielen Bereichen angewandt. Spezielle Modelle werden eingesetzt, um Probleme präzise zu beschreiben und sind damit Voraussetzung für ihre Lösung.
Zuerst werden grundlegende Begriffe und Methoden, wie Mengenlehre, Funktionen und Aussagenlogik, geklärt. Anschließend werden die verschiedenen grundlegenden Kalküle Graphen, Markov-Ketten, endliche Automaten, kontextfreie Grammatiken und Prädikatenlogik untersucht. Diese Kalküle haben sich in vielen Fragestellungen der diskreten Modellierung als fundamental herausgestellt.
Lernziele: Kenntnis der grundlegenden Modellierungsmethoden und Beherrschen der entsprechenden Techniken. Fähigkeit zur präzisen und formalen Ausdrucksweise sowie der sicheren Argumentation.
Materialen
Ws 17/18 – zur Veranstaltungsseite -
Datenstrukturen
Inhalt
Die Vorlesung behandelt die Laufzeitanalyse, fundamentale Datenstrukturen und allgemeine Methoden für den Entwurf und die Analyse von Datenstrukturen. Die Analyse von Datenstrukturen im Hinblick auf Laufzeit und Speicherplatzbedarf wird motiviert. Die asymptotische Notation wird eingeführt, und Methoden zur Lösung von Rekursionsgleichungen werden besprochen.
Elementare Datenstrukturen wie Listen, Keller und Warteschlangen werden beschrieben und analysiert. Weiter werden die Darstellung von Bäumen und allgemeinen Graphen im Rechner und Algorithmen zur systematischen Durchmusterung von Graphen diskutiert.
Der Begriff des abstrakten Datentyps wird eingeführt und motiviert, und effiziente Realisierungen der Datentypen des Wörterbuchs und der Prioritätswarteschlange unter Benutzung von Bäumen (beispielsweise AVL-, Splay-Bäume und B-Bäume) und Hashing (auch verteiltes Hashing und Bloom-Filter) werden besprochen. Außerdem werden effiziente Datenstrukturen für das Union-Find-Problem behandelt.
Materialen
SoSe 15 – zur Veranstaltungsseite -
Theoretische Informatik I / Algorithmentheorie
Inhalt
Die Vorlesung behandelt fundamentale Algorithmen, und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen, sowie die NP-Vollständigkeit und die Grenzen der Berechenbarkeit. Algorithmen für Ordnungsprobleme wie Sortieren und Mischen wie auch Algorithmen für Graphprobleme wie die Berechnung kürzester Wege und minimaler Spannbäume werden beschrieben und analysiert.
Algorithmentypen bzw. Entwurfsmethoden wie Greedy-Algorithmen, Teile-und-Beherrsche und dynamisches Programmieren werden eingeführt und angewandt. Das Konzept der NP-Vollständigkeit erlaubt die Untersuchung der algorithmischen Komplexität von Problemen. Die NP-Vollständigkeit des Erfüllbarkeitsproblems und weiterer Berechnungsprobleme wird gezeigt.
Abschließend wird ein Ausblick auf die Behandlung komplexer algorithmischer Probleme unter Betonung der Approximationsalgorithmen gegeben. Der Begriff der Berechenbarkeit wird eingeführt und ausführlich diskutiert. Es werden Beispiele für nicht entscheidbare Sprachen angeführt, und mit dem Satz von Rice wird nachgewiesen, dass fast alle interessanten Fragen über das Verhalten eines Programms unentscheidbar sind.
Materialen
WiSe 12/13 – [Skript] [Videos] [Slides] [Zusammenfassung] – [Blätter] [Alte Klausuren][Slides]
The following documents are available:
[Zusammenfassung]
The following documents are available:
[Blätter]
The following documents are available:
[Alte Klausuren]
The following documents are available:
Vertiefungsmodule und Master
-
Theoretische Informatik 2
Inhalt
Die Vorlesung „Theoretische Informatik 2“ beschließt den Zyklus der Grundlagenvorlesungen zur theoretischen Informatik. Dabei greifen wir Konzepte aus den vorangegangenen Modulen auf und vertiefen sie. Beispielsweise gehen wir der fundamentalen Frage nach, ob ein in einer höheren Programmiersprache geschriebenes Programm syntaktisch korrekt ist. Dies führt uns auf das Wortproblem für kontextfreie Sprachen; diese Sprachenklasse ist bereits aus der Vorlesung „Diskrete Modellierung“ bekannt. Der CYK-Algorithmus löst das Wortproblem mithilfe der dynamischen Programmierung, eine Technik, die in der Vorlesung „Theoretische Informatik 1“ vorgestellt wurde. Von besonderer Bedeutung sind deterministisch kontextfreie Sprachen, deren Wortproblem sogar in Linearzeit gelöst werden kann.
Die Klassen P und NP haben wir in der Vorlesung „Theoretische Informatik 1“ kennengelernt. Sie erfassen Probleme, die von deterministischen bzw. nichtdeterministischen Turingmaschinen in polynomieller Zeit gelöst werden können. Anstelle der Laufzeit von Algorithmen betrachten wir ihren Speicherbedarf und erhalten die vielleicht überraschende Erkenntnis, dass Nichtdeterminismus nur zu einer quadratischen Speicherplatzersparnis führt. Darüber hinaus spannen wir den Bogen zu randomisierten Algorithmen sowie Quantenberechnungen und untersuchen die Komplexität von Spielen.
Parallelisierung von Berechnungen hat im Zeitalter der Mehrkernprozessoren immens an Bedeutung gewonnen und verspricht die schnelle Verarbeitung riesiger Datenmengen sowie die Lösung größerer Probleminstanzen. Daher widmen wir uns im letzen Teil der Vorlesung der Frage, inwieweit Berechnungen durch Parallelisierung beschleunigt werden können. Neben einer Charakterisierung von Problemen, für die es vermutlich keine schnellen parallelen Algorithmen gibt, entdecken wir einen engen Zusammenhang zwischen der Speicherplatz-Komplexität eines Problems und der Laufzeit paralleler Berechnungen.
Materialen
SoSe 17 – zur Veranstaltungsseite -
Approximationsalgorithmen
Inhalt
Der erste Teil der Veranstaltung behandelt effiziente Optimierungsalgorithmen. Insbesondere werden Greedy-Algorithmen und Matroide, dynamische Programmierung und die lineare Programmierung (Simplex und Interior Point Verfahren) beschrieben und im Detail analysiert.
Der zweite Teil ist der Approximation von NP-harten Optimierungsproblemen gewidmet, wobei auf der linearen Programmierung aufbauende Heuristiken eine wichtige Rolle spielen. Desweiteren werden neben maßgeschneiderten Heuristiken für fundamentale Optimierungsprobleme (wie etwa das Travelling Salesman Problem, Bin Packing Scheduling und Clustering Probleme) auch allgemeine Entwurfsprinzipien (lokale Suchverfahren, Branch & Bound, genetische Algorithmen, Lin-Kernighan und Kernighan-Lin) vorgestellt.
Der dritte Teil der Vorlesung befasst sich mit der Frage, welche Approximationsgüte mit effizienten Algorithmen überhaupt erreicht werden kann. Dazu wird das Konzept der PCP Komplexitätsklassen (Probabilistically Checkable Proofs), das PCP Theorem und lückenbewahrende Reduktionen zwischen Optimierungsproblemen eingeführt.
Lernziele: Die Vermittlung wichtiger Entwurfsprinzipien für Heuristiken soll den eigenständigen Entwurf von Optimierungs- oder Approximationsalgorithmen ermöglichen. Desweiteren werden Analysemethoden bereitgestellt, um die Approximationsgüte vorgeschlagener Algorithmen beurteilen zu können. Lückenbewahrende Reduktionen im Zusammenspiel mit dem PCP Theorem zeigen die Grenzen effizienter Approximierbarkeit auf und vervollständigen somit den Entwurfsprozess.
Materialen
WiSe 13/14 – [Skript] [Videos] [Slides] – [Blätter][Slides]
The following documents are available:
-
Computational Learning Theory
Inhalt
Probleme des überwachten Lernens (supervised learning) werden untersucht.
Im ersten Teil der Veranstaltung wird das Modell des "wahrscheinlich approximativ korrekten" Lernens vorgestellt: aus klassifizierten Beispielen ist eine Hypothese abzuleiten, die einem Zielkonzept mit hoher Wahrscheinlichkeit nahe kommt. Die Beispielkomplexität ("Wie viele Beispiele werden für ein erfolgreiches Lernen benötigt?") und die algorithmische Komplexität ("Wie bestimmt man eine Hypothese, die die Trainingsmenge möglichst gut erklärt?") werden untersucht. Beziehungen zum Online-Lernen ("Lerne mit möglichst wenigen Gegenbeispielen, wenn in jedem Schritt eine Hypothese offenzulegen ist.") werden hergestellt.
Im zweiten Teil der Veranstaltung werden grundlegende Methoden (Validierung, stochastischer Gradientenabstieg) erörtert. Fundamentale Lernmethoden wie Support-Vektor Maschinen und neuronale Netzwerke, statistische Lernmethoden und Entscheidungsbaum-Methoden werden mit Hilfe der Ergebnisse des ersten Teils der Veranstaltung betrachtet und analysiert.
Lernziele: Die mathematische Behandlung der Lernmodelle ermöglicht eine Einordnung der algorithmischen Komplexität wie auch eine Bestimmung der Beispiel-Komplexität für die jeweiligen Lernprobleme. Ein Verständnis der Stärken und Schwächen der einzelnen Lernverfahren erlaubt eine gezielte Anwendung und Modifikation der Lernverfahren.
Materialen
SoSe 17 – zur Veranstaltungsseite -
Effiziente Algorithmen
Inhalt
Ein zentrales Problem der Informatik ist der Entwurf von ressourcenschonenden Algorithmen. In der Veranstaltung werden deshalb fundamentale Fragestellungen im Entwurf und in der Analyse effizienter sequentieller Algorithmen und Datenstrukturen besprochen. Es werden die folgenden Themengebiete behandelt:
- Entwurfsmethoden für randomisierte Algorithmen.
- Der Entwurf und die Analyse von Online-Algorithmen mit kleinem Wettbewerbsfaktor.
Lernziele: Die Vermittlung wichtiger Entwurfs- und Analyseprinzipien, bzw. die Beschreibung und Analyse fundamentaler Algorithmen für deterministische, randomisierte oder Online-Berechnungen soll den eigenständigen Entwurf von effizienten Algorithmen ermöglichen. Ein weiteres Ziel ist die Fähigkeit, eine algorithmische Lösung im Himblick auf ihre Effizienz fundiert beurteilen zu können.
Materialen
SoSe 12 – [Skript] [Slides] – [Blätter (EN)][Slides]
The following documents are available:
[Blätter (EN)]
The following documents are available:
-
Internet Algorithmen
Inhalt
Das Internet erfordert neue Modellbildungen, wie etwa das Streaming Data Modell in der Behandlung großer Datenmengen oder die Spieltheorie in der Modellierung egoistischer Benutzer. Desweiteren muss der Tatsache Rechnung getragen werden, dass komplexe Probleme wie das Routing von Paketen durch verteiltes, unkoordiniertes Rechnen bewältigt werden müssen. Die Veranstaltung führt in diese Modellbildungen ein und beschreibt algorithmische Lösungen wichtiger algorithmischer Probleme des Internets.
Der erste Teil ist Algorithmen zur Behandlung großer Datenmengen gewidmet. Hierzu gehören algorithmische Aspekte im Entwurf von Suchmaschinen wie auch die Lösung von Problemen im Streaming Data Modell. Desweiteren werden Hashing-Verfahren (verteiltes Hashing, Bloom-Filter) für Web-Anwendungen vorgestellt.
Im zweiten Teil werden algorithmische Fragestellungen behandelt, die sich vorwiegend im Internet Routing ergeben. Hierzu gehören etwa der Entwurf von Erasure Correcting Codes, die Untersuchung von Queueing-Strategien im Hinblick auf universelle Stabilität, die Analyse von Mechanismen zur End-to-End Congestion Control sowie die Begegnung von Denial-of-Service Attacken.
Der letzte Teil der Veranstaltung behandelt die algorithmische Spieltheorie, um das Verhalten egoistischer Benutzer des Internet im Kontext knapper Ressourcen, wie etwa Rechenzeit und Routing Kapazität, zu modellieren. Dazu werden fundamentale algorithmische Probleme der Spieltheorie, wie etwa die Bestimmung von Nash- Gleichgewichten oder der Entwurf von Auktionen, untersucht.
Materialen
SoSe 14 – [Skript] [Videos] [Slides] – [Blätter][Slides]
The following documents are available:
-
Komplexitätstheorie
Inhalt
In der Komplexitätstheorie versuchen wir zu verstehen, welche Eigenschaften ein algorithmisches Problem schwierig machen.
Beispielsweise haben wir bereits in der Theoretischen Informatik 1 die Klasse der NP-harten Probleme kennengelernt, zu deren deterministischer Lösung ein polynomieller Aufwand der Ressource "Laufzeit" vermutlich nicht ausreichend ist. Wir betrachten Probleme, wie etwa die Berechnung von Gewinnstrategien für Zwei-Personen-Spiele oder die Frage, ob zwei NFAs äquivalent sind: Diese Probleme werden wahrscheinlich noch nicht einmal in der Klasse NP liegen, wir führen deshalb eine neue Klasse ein, um die Schwierigkeit dieser Probleme zu charakterisieren. Desweiteren untersuchen wir, welche Probleme in P parallelisierbar sind. Die Frage nach der Approximationskomplexität erfordert eine gänzlich neue Sichtweise auf die Klasse NP.
Warum kann man bisher nicht zeigen, dass P eine echte Teilklasse von NP ist? Wir diskutieren Indizien dafür, dass radikal neue Beweismethoden notwendig sind und beschreiben für einige konkrete Probleme Fortschritte in unteren Schranken für die jeweils benötigten Ressourcen.
Materialen
SoSe 13 – [Skript] [Videos] [Slides] – [Blätter][Slides]
The following documents are available:
-
Parallel and Distributed Algorithms
Inhalt
Im ersten Teil der Veranstaltung werden Algorithmen für Multicomputer (Cluster aus Workstations) entworfen und Modelle zur Evaluierung der Algorithmen vorgeschlagen. Insbesondere werden Algorithmen der parallelen linearen Algebra beschrieben und analysiert; zu diesen Algorithmen gehören die Berechnung von Matrix- und Matrix-Vektor Produkten, die Gaußsche Eliminierung, iterative Methoden zur Lösung von linearen Gleichungssystemen wie auch die diskrete Fourier-Transformation. Desweiteren werden Monte Carlo Methoden und Markoff-Ketten exemplarisch vorgestellt wie auch parallele Varianten von Approximations- und Optimierungsverfahren (Backtraining, Branch & Bound und Alpha-Beta Pruning). Der erste Teil endet mit einer Diskussion von Methoden zur Lastverteilung.
Im zweiten Teil der Veranstaltung werden Algorithmen für Multiprocessor-Architekturen behandelt, wobei das formale Modell der PRAMs benutzt wird. Schwerpunkte bilden hier Algorithmen für verkettete Listen und Bäume, Such-, Misch- und Sortierprobleme sowie graphtheoretische Fragestellungen. Die Vorlesung schließt mit der Einführung der P-Vollständigkeit, um Einsicht in die Parallelisierbarkeit von Problemen zu erhalten.
Materialen
WiSe 09/10 – [Skript] [Slides] – [Blätter][Slides]
The following documents are available: