27.10.2015 Немного об онлайн алгоритмах (Павел Чуприков)

Мы определим понятие онлайн задачи и онлайн алгоритма. Рассмотрим методы оценки эффективности таких алгоритмов, и связанные с ними виды научных результатов (на примере задачи "О выделении страниц памяти"). Затем перейдем к задаче управления буфером и докажем некоторые нижние оценки для онлайн алгоритмов решения данной задачи.