А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 1 / 42 План лекции Введение 1 А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 2 / 42 План лекции Введение 1 Задача кэширования 2 А. Куликов (CS клуб при ПОМИ) 21.

Главная >> Программы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

с/к “Эффективные алгоритмы”

Лекция 21: Алгоритмы, обрабатывающие вход по

мере поступления

А. Куликов

Computer Science клуб при ПОМИ

http://logic.pdmi.ras.ru/infclub/

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 1 / 42

План лекции

Введение

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 2 / 42 План лекции Введение 1 Задача кэширования 2 А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 2 / 42 План лекции Введение 1 Задача кэширования 2 Задача о покрытии множествами 3 А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 2 / План лекции Введение Задача кэширования Задача о покрытии множествами А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 3 / Введение Введение А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 4 / Введение Введение Все рассмотренные нами до сегодняшнего дня алгоритмы получали свои входные данные сразу.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 4 / Введение Введение Все рассмотренные нами до сегодняшнего дня алгоритмы получали свои входные данные сразу.

На практике же сущесвуют задачи, которые нужно решать, не зная заранее все входные данные.

Например, системная программа, контролирующая работу операционной системы, должна производить некоторые действия (принимать решения, записывать что-то на выход) до того, как поступят все данные.

На практике же сущесвуют задачи, которые нужно решать, не зная заранее все входные данные.

Такие алгоритмы называются алгоритмами, работающими в реальном времени, или online-алгоритмами.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 4 / Оценка эффективности Оценка эффективности А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 5 / Оценка эффективности Оценка эффективности Как правило, online-алгоритм получает последовательность А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 5 / Оценка эффективности Оценка эффективности Как правило, online-алгоритм получает последовательность По каждому из запросов он должен предоставить некоторый сервис до того, как получит следующий запрос.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 5 / Оценка эффективности Оценка эффективности Как правило, online-алгоритм получает последовательность По каждому из запросов он должен предоставить некоторый сервис до того, как получит следующий запрос.

Обычно есть несколько возможностей предоставить сервис, каждой из которых сопоставлена некоторая стоимость.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 5 / Оценка эффективности Определение А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 6 / Оценка эффективности Определение Online алгоритм A называется c-оптимальным (c-competitive), если для любой последовательности запросов r и любого алгоритма B, которому вся последовательност запросов дается Оценка эффективности Определение Online алгоритм A называется c-оптимальным (c-competitive), если для любой последовательности запросов r и любого алгоритма B, которому вся последовательност запросов дается Коэффициентом оптимальности (competitiveness coefficient) cA алгоритма A называется инфимум таких c, что A c-оптимален.

Аренда лыж Аренда лыж А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Аренда лыж Аренда лыж Представьте себя на горнолыжном курорте.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Аренда лыж Аренда лыж Представьте себя на горнолыжном курорте.

Вы решили кататься, пока позволяет погода, поэтому заранее не знаете, сколько именно (вы не верите прогнозам погоды).

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Аренда лыж Аренда лыж Представьте себя на горнолыжном курорте.

У вас нет лыж, но есть две возможности: арендовать лыжи за руб. в сутки или купить лыжи за 150 руб.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Аренда лыж Аренда лыж Представьте себя на горнолыжном курорте.

У вас нет лыж, но есть две возможности: арендовать лыжи за руб. в сутки или купить лыжи за 150 руб.

Если вы купите лыжи в первый же день, а на следующий день все расстает, вы потратите много денег.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Аренда лыж Аренда лыж Представьте себя на горнолыжном курорте.

У вас нет лыж, но есть две возможности: арендовать лыжи за руб. в сутки или купить лыжи за 150 руб.

Если вы купите лыжи в первый же день, а на следующий день все расстает, вы потратите много денег.

С другой стороны, если вы решите каждый день брать лыжи на прокат, то за два месяца вы потратите стоимость четырех пар А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Аренда лыж Аренда лыж Представьте себя на горнолыжном курорте.

У вас нет лыж, но есть две возможности: арендовать лыжи за руб. в сутки или купить лыжи за 150 руб.

Если вы купите лыжи в первый же день, а на следующий день все расстает, вы потратите много денег.

С другой стороны, если вы решите каждый день брать лыжи на прокат, то за два месяца вы потратите стоимость четырех пар А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 7 / Поиск припаркованной машины Поиск припаркованной машины А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 8 / Поиск припаркованной машины Поиск припаркованной машины Рассеянный профессор, выйдя из института, осознал, что не помнит, где припарковал свою машину.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 8 / Поиск припаркованной машины Поиск припаркованной машины Рассеянный профессор, выйдя из института, осознал, что не помнит, где припарковал свою машину.

Будем считать, что здание института круглое и машина припаркована рядом с ним.

Что же делать профессору?

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 8 / Online-алгоритм Online-алгоритм А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 9 / Online-алгоритм Online-алгоритм Заметим, что online-алгоритм для задачи аренды лыж полностью задается днем N, в который нужно купить лыжи (после этого платить не нужно).

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 9 / Online-алгоритм Online-алгоритм Заметим, что online-алгоритм для задачи аренды лыж полностью задается днем N, в который нужно купить лыжи (после этого платить не нужно).

Итак, какое же N оптимально?

Если N мало, мы рискуем купить лыжи и уехать с ними на следующий день домой.

Итак, какое же N оптимально?

Если N мало, мы рискуем купить лыжи и уехать с ними на следующий день домой.

Если же N велико, мы рискуем прокатать до покупки несколько стоимостей лыж.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 9 / 2-оптимальный online-алгоритм 2-оптимальный online-алгоритм А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 10 / 2-оптимальный online-алгоритм 2-оптимальный online-алгоритм 2-оптимальный алгоритм: брать лыжи в прокат первые 14 дней, а на 15-й день купить их.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 10 / 2-оптимальный online-алгоритм 2-оптимальный online-алгоритм 2-оптимальный алгоритм: брать лыжи в прокат первые 14 дней, а на 15-й день купить их.

Легко видеть, что данный алгоритм 2-оптимален.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 10 / Online-алгоритм для поиска припаркованной машины Online-алгоритм для поиска припаркованной машины А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 11 / Online-алгоритм для поиска припаркованной машины Online-алгоритм для поиска припаркованной машины Рассмотрим такой алгоритм: профессор сходит направо на расстояние 1, потом вернется и сходит налево на расстояние 2, потом опять вернется и сходит направо на расстояние 4, и так далее до тех пор, пока не найдется машина.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 11 / Online-алгоритм для поиска припаркованной машины Online-алгоритм для поиска припаркованной машины Рассмотрим такой алгоритм: профессор сходит направо на расстояние 1, потом вернется и сходит налево на расстояние 2, потом опять вернется и сходит направо на расстояние 4, и так далее до тех пор, пока не найдется машина.

Покажем, что данный алгоритм 9-оптимален.

Неприятнее всего профессору тогда, когда он не дошел маленького до своей машины на одной из итераций.

Покажем, что данный алгоритм 9-оптимален.

Неприятнее всего профессору тогда, когда он не дошел маленького до своей машины на одной из итераций.

В такой ситуации ему придется вернуться назад, сходить в противоположную сторону и только потом найти машину.

Покажем, что данный алгоритм 9-оптимален.

Неприятнее всего профессору тогда, когда он не дошел маленького до своей машины на одной из итераций.

Пусть расстояние до машины равно 2i+1 +. Тогда ему придется 2·(1+2+· · ·+2i+2 )+2i+1 + = 2·(2i+3 1)+2i+1 + = 9·2i+1 +2.

План лекции Введение Задача кэширования Задача о покрытии множествами А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 12 / Задача кэширования (paging problem) Задача кэширования (paging problem) А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 13 / Задача кэширования (paging problem) Задача кэширования (paging problem) У компьютера есть два вида памяти: дисковая, большая по объему, но медленная, и оперативная, быстрая, но меньше по Задача кэширования (paging problem) Задача кэширования (paging problem) У компьютера есть два вида памяти: дисковая, большая по объему, но медленная, и оперативная, быстрая, но меньше по Все операции над данными (в частности, запуск программ) производятся в оперативной памяти; дисковая память используется лишь для их хранения.

Задача кэширования (paging problem) Задача кэширования (paging problem) У компьютера есть два вида памяти: дисковая, большая по объему, но медленная, и оперативная, быстрая, но меньше по Все операции над данными (в частности, запуск программ) производятся в оперативной памяти; дисковая память используется лишь для их хранения.

Если обращения к одному и тому же месту дисковой памяти повторяются, можно сэкономить время на том, что выделить в оперативной памяти определенное место (кэш), в которой сохранять считанные данные.

Поскольку объем кэша ограничен, периодически придется стирать из него данные (записывать на их место другие); качество алгоритма определяется тем, насколько он сможет предугадать, какие данные еще понадобятся (и их не следует стирать), а Формальная постановка задачи Формальная постановка задачи А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 14 / Формальная постановка задачи Формальная постановка задачи Вся память (и дисковая, и оперативная) разбита на блоки равной А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 14 / Формальная постановка задачи Формальная постановка задачи Вся память (и дисковая, и оперативная) разбита на блоки равной Блоки пронумерованы, причем кэш состоит из k блоков, а диск — А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 14 / Формальная постановка задачи Формальная постановка задачи Вся память (и дисковая, и оперативная) разбита на блоки равной Блоки пронумерованы, причем кэш состоит из k блоков, а диск — На очередном шаге к нам поступает запрос на какой-то блок с диска; если этот блок в кэше уже имеется, нам достаточно сообщить его номер в кэше; если нет, нам надо предварительно решить, в какое место кэша записать этот блок и сделать это, считав блок с диска.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 14 / Формальная постановка задачи Формальная постановка задачи Вся память (и дисковая, и оперативная) разбита на блоки равной Блоки пронумерованы, причем кэш состоит из k блоков, а диск — На очередном шаге к нам поступает запрос на какой-то блок с диска; если этот блок в кэше уже имеется, нам достаточно сообщить его номер в кэше; если нет, нам надо предварительно решить, в какое место кэша записать этот блок и сделать это, считав блок с диска.

Время работы алгоритма измеряется количеством считываний с А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 14 / Формальная постановка задачи Формальная постановка задачи Вся память (и дисковая, и оперативная) разбита на блоки равной Блоки пронумерованы, причем кэш состоит из k блоков, а диск — На очередном шаге к нам поступает запрос на какой-то блок с диска; если этот блок в кэше уже имеется, нам достаточно сообщить его номер в кэше; если нет, нам надо предварительно решить, в какое место кэша записать этот блок и сделать это, считав блок с диска.

Время работы алгоритма измеряется количеством считываний с Будем считать, что в начальный момент времени кэш пуст.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 14 / Известные эвристики Известные эвристики А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 15 / Известные эвристики Известные эвристики Когда приходит запрос на блок, которого нет в кэше, online-алгоритму приходится стереть какой-нибудь блок из кэша и на его место записать запрошенный блок.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 15 / Известные эвристики Известные эвристики Когда приходит запрос на блок, которого нет в кэше, online-алгоритму приходится стереть какой-нибудь блок из кэша и на его место записать запрошенный блок.

Стандартные эвристики выбора такого блока:

Least Recently Used, LRU: стереть блок, последний запрос на Известные эвристики Известные эвристики Когда приходит запрос на блок, которого нет в кэше, online-алгоритму приходится стереть какой-нибудь блок из кэша и на его место записать запрошенный блок.

Стандартные эвристики выбора такого блока:

Least Recently Used, LRU: стереть блок, последний запрос на First-in, First-out, FIFO: стереть блок, находящийся в кэше Известные эвристики Известные эвристики Когда приходит запрос на блок, которого нет в кэше, online-алгоритму приходится стереть какой-нибудь блок из кэша и на его место записать запрошенный блок.

Стандартные эвристики выбора такого блока:

Least Recently Used, LRU: стереть блок, последний запрос на First-in, First-out, FIFO: стереть блок, находящийся в кэше Least Frequently Used, LFU: стереть блок, который запрашивался А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 15 / Оптимальный offline-алгоритм Алгоритм MIN При запросе блока, которого нет в кэше, стереть из кэша тот блок, запрос на который будет в будущем позже всего.

Оптимальный offline-алгоритм Алгоритм MIN При запросе блока, которого нет в кэше, стереть из кэша тот блок, запрос на который будет в будущем позже всего.

Упражнения Пусть диск состоит из t = k + 1 блока.

Показать, что для любого детерминированного offline-алгоритма A для задачи кэширования существует последовательность из N запросов r, такая что costA (r ) = N.

Упражнения Пусть диск состоит из t = k + 1 блока.

Показать, что для любой последовательности из N запросов r Нижняя оценка для детерминированных алгоритмов Лемма Для любого детерминированного алгоритма A для задачи кэширования cA k.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 17 / Нижняя оценка для детерминированных алгоритмов Лемма Для любого детерминированного алгоритма A для задачи кэширования cA k.

Идеи доказательства А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 17 / Нижняя оценка для детерминированных алгоритмов Лемма Для любого детерминированного алгоритма A для задачи кэширования cA k.

Идеи доказательства Мы покажем, что существует offline-алгоритм B и последовательность запросов r со следующими условиями.

Последовательность делится на периоды, где под периодом понимается максимальная последовательность, содержащая запросы на k различных блоков.

За каждый период A делает k считываний с диска, а B — всего А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 17 / Нижняя оценка для детерминированных алгоритмов Лемма Для любого детерминированного алгоритма A для задачи кэширования cA k.

За каждый период A делает k считываний с диска, а B — всего Последовательность строится по алгоритму A (каждый следующий запрос всегда можно сделать на блок, которого точно нет в кэше алгоритма A).

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 17 / Случайные числа Случайные числа А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 18 / Случайные числа Случайные числа Итак, детерминированные online-алгоритмы не особо хороши.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 18 / Случайные числа Случайные числа Итак, детерминированные online-алгоритмы не особо хороши.

Можем ли мы улучшить алгоритм, позволив ему пользоваться случайными числами?

Для этого сначала нужно понять, из какого класса берется противник (алгоритм, относительно которого мы оцениваем наш алгоритм).

Можем ли мы улучшить алгоритм, позволив ему пользоваться случайными числами?

Противник выдает всю последовательность сразу? Или же постепенно, смотря на наши ответы?

Можем ли мы улучшить алгоритм, позволив ему пользоваться случайными числами?

Противник выдает всю последовательность сразу? Или же постепенно, смотря на наши ответы?

Если он смотрит на наши ответы, то сразу ли он сам отвечает на свои запросы?

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 18 / Модели противников Модели противников Будем считать, что все перечисленные ниже типы противников могут знать наш алгоритм, но не знают случайных чисел, которыми мы пользуемся.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 19 / Модели противников Модели противников Будем считать, что все перечисленные ниже типы противников могут знать наш алгоритм, но не знают случайных чисел, которыми мы пользуемся.

Забывчивый противник (oblivious adversary) порождает всю последовательность заранее.

Активный offline-противник (adaptive offline adversary) порождает последовательность запросов, смотря на наши ответы.

Забывчивый противник (oblivious adversary) порождает всю последовательность заранее.

Активный offline-противник (adaptive offline adversary) порождает последовательность запросов, смотря на наши ответы.

Активный online-противник (adaptive online adversary) порождает последовательность запросов, смотря на наши ответы, но обязан сразу выдавать ответы на свои запросы.

Забывчивый противник (oblivious adversary) порождает всю последовательность заранее.

Активный offline-противник (adaptive offline adversary) порождает последовательность запросов, смотря на наши ответы.

Замечание Мы рассмотрим самую слабую из данных моделей, то есть забывчивого противника.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 19 / Забывчивый противник Забывчивый противник А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 20 / Забывчивый противник Забывчивый противник Мы будем строить вероятностный алгоритм и оценивать его относительно забывчивого противника.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 20 / Забывчивый противник Забывчивый противник Мы будем строить вероятностный алгоритм и оценивать его относительно забывчивого противника.

Поскольку наш алгоритм вероятностный, мы будем оценивать мат. ожидание количества сделанных им считываний с диска.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 20 / Алгоритм Marker Алгоритм Marker А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 21 / Алгоритм Marker Алгоритм Marker Каждый блок кэша будем помечать 0 или 1.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 21 / Алгоритм Marker Алгоритм Marker Каждый блок кэша будем помечать 0 или 1.

Все время работы разделяется на периоды.

В начале каждого периода все блоки кэша помечены 0.

Все время работы разделяется на периоды.

В начале каждого периода все блоки кэша помечены 0.

Если приходит запрос на блок, который есть в кэше, помечаем Алгоритм Marker Алгоритм Marker Каждый блок кэша будем помечать 0 или 1.

Все время работы разделяется на периоды.

В начале каждого периода все блоки кэша помечены 0.

Если приходит запрос на блок, который есть в кэше, помечаем Если же запрошенного блока нет, случайным образом выберем блок из помеченных 0, считаем туда требуемый блок и пометим Алгоритм Marker Алгоритм Marker Каждый блок кэша будем помечать 0 или 1.

Все время работы разделяется на периоды.

В начале каждого периода все блоки кэша помечены 0.

Если приходит запрос на блок, который есть в кэше, помечаем Если же запрошенного блока нет, случайным образом выберем блок из помеченных 0, считаем туда требуемый блок и пометим Если пришел запрос на блок, которого в кэше нет, и все блоки помечены 1, обнулим все пометки и начнем новый период.

Оценка оптимальности Лемма Алгоритм Marker является 2Hk -оптимальным относительно забывчивого противника.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 22 / Оценка оптимальности Лемма Алгоритм Marker является 2Hk -оптимальным относительно забывчивого противника.

Типы запросов А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 22 / Оценка оптимальности Лемма Алгоритм Marker является 2Hk -оптимальным относительно забывчивого противника.

Типы запросов Помеченный — запрос на блок, образ которого находится в кэше и А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 22 / Оценка оптимальности Лемма Алгоритм Marker является 2Hk -оптимальным относительно забывчивого противника.

Типы запросов Помеченный — запрос на блок, образ которого находится в кэше и Устаревший — запрос на блок, образ которого находится в кэше и помечен 0 (блок, оставшийся в кэше с предыдущего периода), или на блок, которого в кэше нет, но который там был на предыдущем периоде.

Чистый — запрос на блок, которого в кэше нет и не было на А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 22 / Оценка кол-ва считываний противника Оценка кол-ва считываний противника А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 23 / Оценка кол-ва считываний противника Оценка кол-ва считываний противника Обозначения:

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 23 / Оценка кол-ва считываний противника Оценка кол-ва считываний противника Обозначения:

li — кол-во чистых запросов за i-й период.

SO,i, SM,i — множества блоков в кэшах противника и нашего алгоритма, соответственно.

Оценка кол-ва считываний противника Оценка кол-ва считываний противника Обозначения:

li — кол-во чистых запросов за i-й период.

SO,i, SM,i — множества блоков в кэшах противника и нашего алгоритма, соответственно.

dI,i, dF,i — значения величины |SO,i SM,i | в начале и конце i-го периода, соответственно.

Оценка кол-ва считываний противника Оценка кол-ва считываний противника Обозначения:

li — кол-во чистых запросов за i-й период.

SO,i, SM,i — множества блоков в кэшах противника и нашего алгоритма, соответственно.

dI,i, dF,i — значения величины |SO,i SM,i | в начале и конце i-го периода, соответственно.

Наш алгоритм обязан подгрузить li блоков.

Оценка кол-ва считываний противника Оценка кол-ва считываний противника Обозначения:

li — кол-во чистых запросов за i-й период.

SO,i, SM,i — множества блоков в кэшах противника и нашего алгоритма, соответственно.

dI,i, dF,i — значения величины |SO,i SM,i | в начале и конце i-го периода, соответственно.

Наш алгоритм обязан подгрузить li блоков.

Значит, противник подгрузит хотя бы li dI,i блоков: он может выиграть у нас только за счет того, что у него в начале периода будут блоки, на которые поступят запросы.

Оценка кол-ва считываний противника Оценка кол-ва считываний противника Обозначения:

li — кол-во чистых запросов за i-й период.

SO,i, SM,i — множества блоков в кэшах противника и нашего алгоритма, соответственно.

dI,i, dF,i — значения величины |SO,i SM,i | в начале и конце i-го периода, соответственно.

Наш алгоритм обязан подгрузить li блоков.

Это кол-во также составляет не менее dF,i : все блоки, лежащие к концу периода в кэше нашего алгоритма, были запрошены;

значит, они должны были побывать и в кэше противника; если же кого-то из них там не оказалось, значит, на его место был загружен другой блок; кол-во таких загрузок не менее dF,i.

Оценка кол-ва считываний противника (продолжение) Оценка кол-ва считываний противника А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 24 / Оценка кол-ва считываний противника (продолжение) Оценка кол-ва считываний противника Итак, количества считываний противника за i-й период составляет не менее Оценка кол-ва считываний противника (продолжение) Оценка кол-ва считываний противника Итак, количества считываний противника за i-й период составляет не менее Просуммировав по всем перидоам, получим нижнюю оценку на общее число загрузок, совершенных противником:

Оценка кол-ва считываний алгоритма Оценка кол-ва считываний алгоритма А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 25 / Оценка кол-ва считываний алгоритма Оценка кол-ва считываний алгоритма Алгоритм подгружает новый блок на каждый чистый запрос.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 25 / Оценка кол-ва считываний алгоритма Оценка кол-ва считываний алгоритма Алгоритм подгружает новый блок на каждый чистый запрос.

На помеченные ничего подгружать не нужно.

В i-м периоде ровно k li устаревших запросов.

На помеченные ничего подгружать не нужно.

В i-м периоде ровно k li устаревших запросов.

При устаревшем запросе мы обращаемся к блоку, который на предыдущем периоде был в кэше, но есть ли он там сейчас, мы сказать не можем (он мог быть выгружен).

На помеченные ничего подгружать не нужно.

В i-м периоде ровно k li устаревших запросов.

Посчитаем вероятность того, что j-й устаревший запрос происходит на блок, которого нет в кэше.

На помеченные ничего подгружать не нужно.

В i-м периоде ровно k li устаревших запросов.

Посчитаем вероятность того, что j-й устаревший запрос происходит на блок, которого нет в кэше.

Вспомним, что для каждого устаревшего блока в начале периода был соответствующий блок.

На помеченные ничего подгружать не нужно.

В i-м периоде ровно k li устаревших запросов.

Посчитаем вероятность того, что j-й устаревший запрос происходит на блок, которого нет в кэше.

Вспомним, что для каждого устаревшего блока в начале периода был соответствующий блок.

Пусть X — множество позиций кэша, в которых в начале периода были блоки из первых j 1 устаревших запросов.

На помеченные ничего подгружать не нужно.

В i-м периоде ровно k li устаревших запросов.

Посчитаем вероятность того, что j-й устаревший запрос происходит на блок, которого нет в кэше.

Вспомним, что для каждого устаревшего блока в начале периода был соответствующий блок.

Пусть X — множество позиций кэша, в которых в начале периода были блоки из первых j 1 устаревших запросов.

Ясно, что перед j-м устаревшим запросом все эти позиции А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 25 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 26 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Каждая позиция из X могла быть помечена 1 либо при нахождении соответствующего устаревшего блока, либо при загрузке туда чистого блока.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 26 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Каждая позиция из X могла быть помечена 1 либо при нахождении соответствующего устаревшего блока, либо при загрузке туда чистого блока.

Тогда из множества X (в котором наш блок и лежит) не более l раз производилась случайная выборка.

Посчитаем веротяность того, что наш блок при этом выживет.

Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 27 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 27 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Тогда вероятность ему выжить на первом шаге не менее K /(K 1), на втором — не менее (K 1)/(K 2) и т.д.

А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 27 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Тогда вероятность ему выжить на первом шаге не менее K /(K 1), на втором — не менее (K 1)/(K 2) и т.д.

Перемножив, получим, что вероятность выжить за все l выборок А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 27 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Тогда вероятность ему выжить на первом шаге не менее K /(K 1), на втором — не менее (K 1)/(K 2) и т.д.

Перемножив, получим, что вероятность выжить за все l выборок Значит, с вероятностью не более K = kj+1 алгоритму придется считать блок при j-м устаревшем запросе.

Тогда мат. ожидание количества считываний при устаревших запросах не превосходит Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 28 / Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Таким образом, мат. ожидание общего числа загрузок за i-й период (включая li чистых загрузок) будет не более Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Таким образом, мат. ожидание общего числа загрузок за i-й период (включая li чистых загрузок) будет не более Просуммировав по всем периодам, получим, что мат. ожидание общего числа загрузок нашего алгоритма не более L · Hk.

Оценка кол-ва считываний алгоритма (продолжение) Оценка кол-ва считываний алгоритма Таким образом, мат. ожидание общего числа загрузок за i-й период (включая li чистых загрузок) будет не более Просуммировав по всем периодам, получим, что мат. ожидание общего числа загрузок нашего алгоритма не более L · Hk.

Вспомнив, что наш противник делает хотя бы L/2 загрузок, получаем требуемую оценку на оптимальность.

План лекции Введение Задача кэширования Задача о покрытии множествами А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 29 / Online-вариант задачи о покрытии множествами Online-вариант задачи о покрытии множествами А. Куликов (CS клуб при ПОМИ) 21. Online алгоритмы 30 / Online-вариант задачи о покрытии множествами Online-вариант задачи о покрытии множествами Пусть дано множество X = {1, 2,..., n} и множество его подмножеств, || = m, каждому из которых присвоен вес 1.