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

Fine-Grained Analysis of Algorithms - Detailseite

  • Funktionen:
  • Online Belegung noch nicht möglich oder bereits abgeschlossen
Grunddaten
Veranstaltungsart Vorlesung Veranstaltungsnummer 3313047
Semester WiSe 2019/20 SWS 4
Rhythmus Moodle-Link  
Veranstaltungsstatus Freigegeben für Vorlesungsverzeichnis  Freigegeben  Sprache deutsch
Belegungsfristen - Eine Belegung ist online erforderlich Zentrale Nachfrist    14.10.2019 - 17.10.2019   
Zentrale Frist    01.07.2019 - 09.10.2019   

Termine

Gruppe 1 iCalendar Export iCalendar Export
  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer
iCalendar Export Di. 09:00 bis 11:00 wöch
Einzeltermine ausblenden
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Kratsch findet statt     40
Einzeltermine:
  • 15.10.2019
  • 22.10.2019
  • 29.10.2019
  • 05.11.2019
  • 12.11.2019
  • 19.11.2019
  • 26.11.2019
  • 03.12.2019
  • 10.12.2019
  • 17.12.2019
  • 07.01.2020
  • 14.01.2020
  • 21.01.2020
  • 28.01.2020
  • 04.02.2020
  • 11.02.2020
iCalendar Export Do. 13:00 bis 15:00 wöch
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Kratsch findet statt     40
Gruppe 1:
Zur Zeit keine Belegung möglich


Zugeordnete Person
Zugeordnete Person Zuständigkeit
Kratsch, Stefan , Prof. Dr.
Studiengänge
Abschluss Studiengang LP Semester
Master of Education (ISS)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (GYM)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (ISG)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   10  -  
Master of Education (BS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (ISS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (GYM)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (ISG)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   10  -  
Master of Science  Informatik Hauptfach ( Vertiefung: kein LA; POVersion: 2015 )   10  -  
Master of Science  Wirtschaftsinformatik Hauptfach ( Vertiefung: kein LA; POVersion: 2016 )   10  -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

For many fundamental polynomial-time solvable problems like Longest Common Subsequence or All-Pairs Shortest Paths there has been no substantial improvement in worst-case running time for decades. The area of Fine-Grained Analysis of Algorithms seeks to explain this lack of improvement. By careful reductions between problems it has been showed that progress for very different problems is often tightly related. E.g. there is a truly subcubic algorithm for All-Pairs Shortest Paths if and only if a bunch of other problems, like Minimum Weight Triangle, have truly subcubic algorithms. Similarly, many problems can only have faster algorithms if there is a breakthrough for solving the Satisfiability problem.

The lecture covers lower bounds for many fundamental problems. We will discuss the required complexity assumptions, e.g., the hypothesis that there are no truly subquadratic algorithms for the Orthogonal Vectors problem. By means of appropriate reductions we then get the lower bounds or even asymptotic equivalence for some problems. Optionally, we will discuss implications for dynamic problems, where input changes over time, and for certain NP-hard problems.

Bemerkung

Die Vorlesung findet in Englisch statt.

Strukturbaum

Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis WiSe 2019/20 gefunden:

Humboldt-Universität zu Berlin | Unter den Linden 6 | D-10099 Berlin