Algorithmen & Komplexität

Arbeitsgruppe

Forschung

Lehre

Abschlussarbeiten

Vorlesungsangebot

Diskrete Modellierung

• Thematik:
  In der Informatik wird das Modellieren mittels diskreter Strukturen als typische Arbeitsmethode invielen Bereichen angewandt. Es dient der präzisen Beschreibung von Problemen durch spezielle Modelle undist damit Voraussetzung für die Lösung eines Problems bzw. ermöglicht oft einen systematischen Entwurf. In den verschiedenen Gebieten der Informatik werden unterschiedliche, jeweils an die Art der Probleme und Aufgaben angepasste, Modellierungsmethoden verwendet.
  Innerhalb der Veranstaltung sollen zunächst die grundlegenden Begriffe wie z.B. Modell und Modellierung, geklärt werden. Anschließend werden verschiedene Ausdrucksmittel der Modellierung untersucht: Grundlegende Kalküle wie der Kalkül der Mengen, die Aussagen- und Prädikatenlogik, Graphen, endliche Automaten, Markov-Ketten, kontextfreie Grammatiken.
• Umfang: 3V, 2Ü, 1EÜ
• Alle Dozenten in den Grundlagen der Informatik
• Turnus: Jedes Wintersemester

Algorithmen und Datenstrukturen 1

• Thematik:
  Die Vorlesung behandelt die Laufzeitanalyse, fundamentale Datenstrukturen und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die Analyse 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. 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.
  Die Darstellung von Bäumen und allgemeinen Graphen im Rechner und Algorithmen zur systematischen Durchmusterung von Graphen wird diskutiert. Weiterführende Algorithmen für Graphenprobleme wie minimale Spannbaüme und kürzeste Wege und werden besprochen, und der Einsatz von Datenstrukturen in diesen Verfahren exemplarisch vorgestellt. Algorithmentypen bzw. Entwurfsmethoden wie Greedy-Algorithmen, Teile-und-Beherrsche und dynamisches Programmieren werden eingeführt und angewandt.
• Umfang: 3V, 2Ü
• Alle Dozenten in den Grundlagen der Informatik
• Turnus: Jedes Sommersemester

Algorithmen und Datenstrukturen 2

• Thematik:
  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 werden beschrieben und analysiert.
  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. Ab­schließend wird ein Ausblick auf die effiziente Approximation komplexer algorithmischer Probleme und die exakte Lösung in Spezialfällen gegeben. Hierbei werden Konzepte wie Approximations- oder exakte Algorithmen behandelt.
  Der Begriff der Berechenbarkeit wird eingeführt und ausführlich diskutiert. Es werden Beispiele für nicht ent­scheidbare Sprachen angeführt, und mit dem Satz von Rice wird nachgewiesen, dass fast alle interessanten Fragen über das Verhalten eines Programms unentscheidbar sind.
• Umfang: 3V, 2Ü
• Alle Dozenten in den Grundlagen der Informatik
• Turnus: Jedes Wintersemester

---

Algorithmische Spieltheorie

• Thematik:
  Die Vorlesung behandelt die Analyse von Algorithmen und Rechnersystemen mittles spieltheoretischer Konzepte und Techniken, mit Bezug zu Anwendungen z.B. in verteilten Systemen, Auktionen, Online-Märkten, bei der Ressourcenaufteilung etc. Konkrete Themen im Inhalt der Vorlesung sind z.B. Spiele in Normalform, Qualität von Gleichgewichten und der Preis der Anarchie, Auktionen, Anreizkompatibilität und VCG-Mechanismen, Sponsored Search, Social Choice und Unmöglichkeitsresultate, Komplexität von Gleichgewichten und Mechanismen, Matching- und Flussprobleme in Märkten, Cake-Cutting, etc.
• Umfang: Beide Teile jeweils 2V, 1Ü
• Dozenten: Prof. Dr. Martin Hoefer, Dr. Annamaria Kovacs
• im Wintersemester 2022/23 von Prof. Hoefer

Approximationsalgorithmen

• Thematik:
  Für die meisten interessanten Optimierungsprobleme sind keine Algorithmen bekannt, die optimale Lösungen in polynomieller Zeit liefern können. Eine wichtige Alternative sind effiziente Approximationsalgorithmen, die Lösungen mit beweisbarer Gütegarantie berechnen. Die Vorlesung stellt diese Verfahren und die Analyse­techniken vor, insbesondere die Entwurfsmethoden von Greedy-Algorithmen, dynamischer Programmierung und lokaler Suche. Daneben werden Branch-and-Bound-Algorithmen und Methoden der linearen Programmierung besprochen. Eine alternative Sichtweise der Klasse NP durch Probabilistically Checkable Proofs wird angewandt, um Grenzen einer scharfen effizienten Approximation nachzuweisen.
• Umfang: Beide Teile jeweils 2V, 1Ü
• Dozenten: Prof. Dr. Martin Hoefer, Dr. Annamaria Kovacs
• im Wintersemester 2022/23 von Dr. Kovacs

Effiziente Algorithmen

• Thematik:
  Ein zentrales Problem der Informatik ist der Entwurf von ressourcenschonenden Algorithmen. In der Ver­anstaltung werden deshalb fundamentale Fragestellungen im Entwurf und in der Analyse effizienter sequentieller Algorithmen und Datenstrukturen besprochen. Eine Auswahl der folgenden Themengebiete wird behandelt:
  • Entwurfsmethoden für randomisierte Algorithmen wie etwa Stichproben, Fingerprinting und Random Walks.
  • Entwurf und Analyse von Online-Algorithmen mit kleinem Wettbewerbsfaktor
  • Algorithmische Lösung wichtiger Probleme wie etwa Matching, Flüsse in Netzwerken, lineare Programmierung, String Matching oder algorithmische Probleme der Zahlentheorie.
  • Methoden des Algorithm Engineering.
• Umfang: Beide Teile jeweils 2V, 1Ü
• Alle Dozenten in den Grundlagen der Informatik
• geplant im Sommersemester 2023 von Dr. Kovacs

Optimierung und Unsicherheit

• Thematik:
  In der Vorlesung werden Optimierungsfragen mit stochastischer oder worst-case Unsicherheit über die Eingabe untersucht. Im ersten Teil werden stochastische Online-Probleme vorgestellt, insbesondere kombinatorische Sekretärprobleme, prophetische Ungleichungen und das allgemeine Modell der Markov-Entscheidungs­prozesse. Daneben werden Probing-Probleme wie Pandora's Box diskutiert. Im zweiten Teil der Vorlesung liegt der Fokus auf spiel- und lerntheoretischen Fragen, insbesondere Empfehlungsproblemen, Varianten des Multi-Armed-Bandit Lernens sowie konvexer Online-Optimierung.
  
• Umfang: Beide Teile jeweils 2V, 1Ü
• geplant im Sommersemester 2023 von Prof. Hoefer

Theorie verteilter Systeme

• Thematik:
  In der Vorlesung werden grundlegende algorithmische Aspekte von verteilten Systemen in mathematisch rigoroser Art analysiert. Im ersten Teil geht es um Algorithmen für grundlegende Koordinationsprobleme wie Baumkonstruktion, Synchronisierung, Färbungs- oder Independent-Set-Probleme. Im zweiten Teil werden weiterführende Varianten und anspruchsvollere Aufgaben betrachtet, z.B. Routingprobleme, Algorithmen für Funknetzwerke, sowie Population Protocols oder spieltheoretische Modelle.
• Umfang: Beide Teile jeweils 2V, 1Ü
• Dozenten: Prof. Dr. Martin Hoefer
• geplant im Wintersemester 2023/24 von Prof. Hoefer