|
Instructors: Dr. rer. nat. Frank Fischer
Event type:
Lecture/practice class
Displayed in timetable as:
08.079.23401
Hours per week:
4
Credits:
6,0
Language of instruction:
German
Min. | Max. participants:
- | -
Requirements / organisational issues:
DSeA
Contents:
Classical algorithms assume that the full information, i.e. the problem instance, is known from the beginning. Examples are the TSP, shortest path problems or sorting algorithms. In contrast, online algorithms assume that the information becomes available while the algorithm is already running. In particular, the algorithm must already make decisions while only part of the information is known. An example of this from everyday life are delivery services: customer orders have to be processed while new orders are constantly arriving. In computer science, the paging problem is a known example: while a program is running, the operating system has to decide which memory pages to remove from the main memory without knowing which of these pages will be needed again in the future.
In this lecture we deal with online algorithms and their analysis. We will learn about special analysis techniques such as competitive analysis.
|
