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

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

  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/ifzero/jump/halt/in/out
      2. Память. Специальный регистр "результат вычислений". Программа не может менять саму себя.
      3. Выводим из этого циклы, функции.
    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. Полнота по Тьюрингу
      3. Задача: запрограммировать что-нибудь на Тьюринге