Динамика на подмножествах (25 ноября 2019)

  1. (только для старшей группы!) Анекдот (цель: показать, что динамика, это не только про пути)
    1. Динамика − часто это или "найти путь в графе", или "число путей в графе". Но не только.
    2. Приведите пример! Ответ: динамика по подотрезкам.

  2. Динамика по подотрезкам (цель: закрепить уже изученное на практике, порядок переходов)
    1. Пример: произведение матриц. Сводим задачу к меньшим такого же вида.
    2. Динамика тоже описывается графом, но не является напрямую задачей поиска пути на этом графе

  3. Тестирование (на примере pn+1,k ≥ pn,k ≥ pn,k-1)
    1. Стресс-тестирование (мы программисты! мы не умеем доказывать, но можем проверить)
    2. Добавить assert на ответ.
    3. Добавить assert на все промежуточные значения динамики f[n,k].
    4. Добавить assert на все неравенства c p[n,k].

  4. (только для старшей группы!) Доказательство pn+1,k ≥ pn,k ≥ pn,k-1
    1. Первое: два раза рисуем 4 картинки, в первом случае в 4-й центр − q1, во втором случае − q2
    2. Второе через первое, добавляем строгость

  5. Комбинаторика
    1. Картинка с 6 перестановками и рассказ "какие задачи мы хотим решать" (object2index, index2object, next, prev)
    2. Указание лектору: начать нужно с перестановок, там формулы. Затем обязательно скобочные последовательности, там уже динамика.
    3. Объект по номеру, номер по объекту: примеры − перестановки, скобочные последовательности
    4. Зачем это нужно? Хранение объекта минимальным числом бит (например, на диске или состояние динамики; например, разбиение на слагаемые)
    5. Следующий лексикографически: пример перестановка, скобочная последовательность
    6. Зачем это нужно? Перебор всех объектов без рекурсии

  6. Работа с множествами, как с целыми числами. Примеры на все операции.
    1. Биекция между числами 0..2n-1 и подмножествами {0,1,...,n-1}
    2. Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов.
    3. Пересечение, объединение, разность. Проверка, содержится ли.
    4. Добавить к множеству элемент: +, ^, |

  7. Динамика по подмножествам
    1. Задачи: количество единичных бит в числе и сумма на подмножестве
    2. Версия за 2nn и рекурсивная версия за 2n
    3. Динамика: количество бит в числе (bn[i] = bn[i/2] + i%2)
    4. Динамика: сумма на подмножестве (sum[i] = sum[i ^ bit] + w[bit])

  8. Гамильтонов путь и цикл
    1. Определения.
    2. Решение задачи про путь за O(2nn2) времени и O(2nn) памяти is[A, v] → is[A|2x,x].
    3. Сводим задачу про цикл к задаче про путь.
    4. Улучшаем память до 2n (битовый массив, минимальное изменение кода) end[A] |= 2v.
    5. Улучшаем время до 2nn (пересекается ли adj[x] c end[A^2x])

  9. Задача: покрасить вершины графа в минимальное число цветов
    1. Предподсчет good[A] за O(2nn2). Решение за O(4n).
    2. Перебор всех подмножеств всех множеств циклами for за O(3n), решение нашей задачи за O(3n + 2nn2).
    3. Замена O(2nn2) на O(2n) (good[] - динамика).