Онлайн-алгоритмы для управления буфером: конкурентный анализ

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