Изменения

Пусть задана последовательность из <tex>n</tex> запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера <tex>k</tex> или оставить его во внешней памяти.

'''Кэш попадание''' (англ. ''cache hit'') {{---}} результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно. Будем считать, что время обработки такого запроса равно 0.

'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое. Будем считать, что время обработки такого запроса равно 1.

== Ограничение Проблема детерминированных алгоритмов ==

<tex>k</tex> {{---}} размер кэша. Любой <tex>\alpha</tex>-оптимальный детерменированный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geq geqslant k</tex>.

Чтобы показатьОбозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \quad T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно квантор раскрыть для значения <tex>\sigma_n</tex>: <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geq geqslant k</tex>. Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, достаточно для каждого результата которого нет в данный момент в кэше детерминированного алгоритма предоставить одну такую последовательность . Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>. Посмотрим как на <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного результата вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросовна 1 больше размера кэша, при которой то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n >> k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex> 

== Алгоритм Вероятностный алгоритм ==