Приближения, модели вычислений (19 марта 2021)

  1. Алгоритм Кармаркар-Карпа (1982)
    1. Что уже умеем для partition? Как оно себя ведёт на случайных R 0-1 весах?
    2. 0-1 → 0-1/n → 0-1/n2 → ...
    3. Алгоритм. Интуиция того, что это n-logn
    4. [хешей мы ещё не знаем, только упоминаем] Применение для поиска теста к полиномиальным хешами.

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

  3. Задача о надстроке
    1. Пример задачи: есть много кусочков генома, нужно собрать из них геном.
    2. Сведение к TSP. Решение динамикой за O(2nn2).
    3. Простое жадное решение. Гипотеза: это 2-приближение.

  4. Задачи
    1. Центроид: запрос = сумма по всем вершина на расстояние ровно d от данной
    2. Жадность: разбить число в виде суммы 5 квадратов
− Перерыв −
  1. Модели вычислений
    1. RAM
      1. Какие операции разрешены? add/sub/mul/div/jz/jump/halt/in/out
      2. Память. Специальный регистр "результат вычислений". Программа не может менять саму себя.
      3. Выводим: (div → a>b; jump, jz → for, while; if; function)
    2. RAM-w
      1. Какой размер регистров? RAM − неограниченные целые числа, RAM-w, до 2w.
      2. Читы из неограниченности : операции с массивами, как с целыми числами за O(1)
      3. Читы из неограниченности : bitset, bfs за O(V), Флойд за O(V2).
      4. Читы из неограниченности : сумма w-битных чисел в массиве за O(logn) (первую половину складываем со второй)
    3. Машина Тьюринга
      1. Определение: лента, ...
      2. Запрограммировать что-нибудь на Тьюринге : даны i, a, вернуть a[i]
    4. Классы: Тьюринг в полином раз отличается от RAM-w, в RAM все NP решаются за полином (распараллелим за счёт длины числа)