AGNES -
Lehre und Prüfung online
Studierende in Vorlesung
Anmelden

Exakte Exponentialzeit-Algorithmen - Detailseite

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung Veranstaltungsnummer 3313026
Semester WiSe 2021/22 SWS 3
Rhythmus Moodle-Link  
Veranstaltungsstatus Freigegeben für Vorlesungsverzeichnis  Freigegeben  Sprache englisch
Belegungsfrist Es findet keine Online-Belegung über AGNES statt!
Veranstaltungsformat Präsenz

Termine

Gruppe 1
Tag Zeit Rhythmus Dauer Raum Gebäude Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer/-innen
Di. 11:00 bis 13:00 wöch 0313 (Hörsaal)
Stockwerk: EG


alttext alttext
RudCh26-Modul 1 Erwin-Schrödinger-Zentrum - Rudower Chaussee 26 (RUD26)

Außenbereich nutzbar Innenbereich nutzbar Parkplatz vorhanden Leitsystem im Außenbereich Barrierearmes WC vorhanden Barrierearme Anreise mit ÖPNV möglich
Kratsch findet statt   04.01.2022:  80
Mi. 11:00 bis 13:00 14tgl./1 0313 (Hörsaal)
Stockwerk: EG


alttext alttext
RudCh26-Modul 1 Erwin-Schrödinger-Zentrum - Rudower Chaussee 26 (RUD26)

Außenbereich nutzbar Innenbereich nutzbar Parkplatz vorhanden Leitsystem im Außenbereich Barrierearmes WC vorhanden Barrierearme Anreise mit ÖPNV möglich
Kratsch findet statt     80
Gruppe 1:
 


Zugeordnete Person
Zugeordnete Person Zuständigkeit
Kratsch, Stefan , Prof. Dr.
Studiengänge
Abschluss Studiengang LP Semester
Bachelor of Arts  Informatik Kernfach ( POVersion: 2010 )   -  
Bachelor of Arts  Informatik Zweitfach ( POVersion: 2010 )   -  
Bachelor of Arts  Informatik Zweitfach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Bachelor of Arts  Informatik Zweitfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Arts  Informationsman. & -tech. Monobachelor ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Arts  Informationsman. & -tech. Monobachelor ( Vertiefung: kein LA; POVersion: 2017 )   -  
Bachelor of Science  Info, Mathe und Physik Monobachelor ( Vertiefung: kein LA; POVersion: 2019 )   -  
Bachelor of Science  Informatik Kernfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Science  Informatik Kernfach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Bachelor of Science  Informatik Monobachelor ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Science  Informatik Zweitfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Science  Informatik Zweitfach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

Diese Vorlesung beschäftigt sich mit Algorithmen, die NP-schwere Probleme exakt (also optimal) lösen und dafür exponentielle Zeit aufwenden dürfen. Auch wenn es wohl keine exakten Polynomialzeitalgorithmen dafür gibt, wollen wir die Probleme trotzdem in möglichst geringer Zeit und nachweislich optimal lösen. Primär geht es in der Vorlesung um eine Vielzahl algorithmischer Techniken u.a. Branching Algorithmen, Dynamische Programmierung, Inklusion-Exklusion, Measure & Conquer, Subset Convolution und Lokale Suche.

Die Vorlesung basiert auf dem gleichnamigen Buch "Exact Exponential Algorithms" von Fedor V. Fomin und Dieter Kratsch. Das Buch kann aus dem Uninetz (oder VPN) über die Unibibliothek beim Verlag heruntergeladen werden.

Bemerkung

LV findet in Englisch statt.

Strukturbaum

Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester WiSe 2021/22. Aktuelles Semester: WiSe 2024/25.
Humboldt-Universität zu Berlin | Unter den Linden 6 | D-10099 Berlin