Модели памяти, приближения, надстрока, bin-packing (8 апреля 2025)

  1. Забытое: крутая жадность с заменами
    1. Задача: даны дедлайны окончания di и времена исполнения ti
    2. Выбрать макс число задач за O(n2). Сортировка по di + динамика minSumT[i,k].
    3. Выбрать макс число задач за O(nlogn). Жадность с заменами: поддерживаем minSumT только для максимально возможного maxK.
    4. Доказательство: на самом деле мы знаем весь слой динамики, ответ для каждого k ≤ maxK : minSumT[i,k] − это первые k в сортировке по ti maxK выбранных.
    5. Применяем доказательство к задаче: спортсмены с силой si, массой mi выстраиваются в башню. Выстроить всех: сортировка по si+mi.

  2. Модели вычислений
    1. Основное
      1. Интуиция RAM, RAM-w, читы с длинными числами
      2. Флойда за n3/w или n2 в ram
      3. bfs за n2/w или n в ram
      4. Основные операции в RAM (asm), пишем через них a>b (sub, jump, jz, jl, jc) и for/while/if/function; div → a>b
      5. RAM: Какие операции разрешены? add/sub/mul/div/jz/jump/halt/in/out. Специальный регистр "результат вычислений". Программа не может менять саму себя.
    2. RAM-w и RAM
      1. Какой размер регистров? RAM − неограниченные целые числа, RAM-w, до 2w.
      2. Читы из неограниченности : операции с массивами, как с целыми числами за O(1)
      3. Читы из неограниченности : bitset, bfs за O(V), Флойд за O(V2).
      4. Читы из неограниченности : сумма w-битных чисел в массиве за O(logn) (первую половину складываем со второй)
    3. Для RAM P=NP: общий алгоритм, конкретика для SAT.
    4. Строго полиномиальное время.
    5. Машина Тьюринга
      1. Определили машину Тьюринга, ленты, полнота по Тьюрингу
      2. Запрограммировать что-нибудь на Тьюринге : reverse(L,R)
      3. [skipped] Запрограммировать что-нибудь на Тьюринге : даны i, a, вернуть a[i]
      4. [skipped] Классы: Тьюринг в полином раз отличается от RAM-w. Можно RAM-w программу времени T моделировать за T2 log T.

  3. Приближения
    1. Повторили определение PTAS/FPTAS/FPRAS и алгоритмы PTAS/FPTAS для knapsack.
  4. Надстрока
    1. Пример задачи: есть много кусочков генома, нужно собрать из них геном.
    2. Сведение к TSP. Решение динамикой за O(2nn2).
    3. Простое жадное решение. Гипотеза: это 2-приближение (доказывать умеют 3.5-OPT)
    4. Сведение надстроки к weighted-set-cover (p[i,j,k] − зацепление i и j длины ровно k, покрывает какое-то множество исходных строк)
− Перерыв −
  1. Алгоритм Кармаркар-Карпа (1982)
    1. Что уже умеем для partition? Как оно себя ведёт на случайных R 0-1 весах?
    2. 0-1 → 0-1/n → 0-1/n2 → ...
    3. Алгоритм. Интуиция того, что это n-Θ(logn)
    4. [хешей мы ещё не знаем, только упоминаем] Применение для поиска теста к полиномиальным хешами.

  2. Мультирюкзак (bin packing)
    1. Повторили определение PTAS/FPTAS/FPRAS и алгоритмы.
    2. bin-packing, формулировка. Сложность 1.5-OPT приближения: определить 2 или 3 − уже NP-hard (partition)
    3. first fit: 2-OPT + доказательство.
    4. first fit decresing и best fit decresing (11/9*OPT+1 приближение)
    5. [skipped] Практически эффективное решение: локальные оптимизации (timus-1144)
    6. PTAS для bin packing: (адовая константа): (1+ε)OPT+1

  3. Задачи
    1. Центроид: запрос = сумма по всем вершинам на расстояние ровно d от данной
    2. Жадность: разбить число в виде суммы 5 квадратов