City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Online algorithms for buffer management: competitive analysis


Мы поговорим об онлайн-алгоритмах для решения задач управления буфером и о том, что можно сделать в таких задачах, а чего нельзя. Основным инструментом для нас станет конкурентный анализ, в котором мы сравниваем качество работы алгоритма в худшем случае с качеством работы оптимального алгоритма, который знает всю входную последовательность наперёд и обладает неограниченными ресурсами. В итоге получаются гарантии качества для любого вида трафика. Мы дадим краткое введение в тему и приведем примеры конкретных доказательств, а также сформулируем дальнейшие направления для исследований.

Course Offerings

Semester Branch
autumn 2017 Saint Petersburg