Online Algorithms with Advice

the supervisor, Adi Rosén, is not fluent enough in French. Le contexte général In online computation, the data is revealed one element at a time. Algorithms dealing with online problems must make decisions upon receipt of each element without knowing the entire sequences of elements. Online algorithms have many real world applications such as paging, task scheduling, routing and investing algorithms. One classical abstract online problem is termed the k-server problem. This problem is defined by a metric space, M, k mobile servers and a request sequence σ. Each request is to a node of M and a server must be moved to the requested node before the next request is revealed to the algorithm. The goal is to minimize the distance traveled by the k servers over σ. Competitive analysis is used to gauge the effectiveness of an algorithm against the optimal manner in solving the problem. Although competitive analysis is a meaningful method for performing a worst-case analysis, it has been criticized as being too pessimistic and that it does not convey enough information about the performance of the algorithm analyzed. For example, paging algorithms such as LRU (Least Recently Used), FIFO (First In First Our)