The traditional theory on algorithms and their complexity generally gives runtime bounds in terms of the size of an instance; with the need to process ever larger data sets, these analyses have lost a lot of their predictive power since even many polynomial time algorithms can not be used to process huge amounts of data. Consequently, frameworks have been developed to more closely model the data encountered in practical settings. This allows us to design algorithms with much better runtime guarantees for some practical data, as well as develop a much more detailed complexity theory of such algorithms.
This seminar will give an overview of some of the modern algorithmic approaches that allow us to more accurately analyse real-world problems, such as parameterized and fine-grained analysis, randomization, and streaming and online algorithms.
Studiendekanat Elektrotechnik, Informatik und Mathematik
Weitere Informationen aus Stud.IP zu dieser Veranstaltung