Сборы к РОИ, группа A1 (23 марта 2016)

1. Анекдот: частичные суммы, sparse, а как произведение по модулю за O(1)?
1. Учимся делать Disjoint Sparse Table
2. Учимся пользоваться им за O(1)
2. Отжиг
1. Локальные оптимизации
2. Локальные оптимизации + рандом + несколько раз
3. Отжиг для непрерывной функции (R=радиус, T=время)
4. Отжиг для дискретной функции (что такое R?)
3. Перебор
1. Задача о рюкзаке: сумма не более W, максимизировать стоимость
1. Жадность (сортировка)
2. Отсечение по ответу
3. Запоминание
4. 4-русских
2. Алгоритм A^*, применение к перебору на примере задачи о рюкзаке
3. Задача о максимальной клике
4. Задача о мультирюкзаке: разбить предметы на минимальное число рюкзаков
4. Расщепление
1. По максимальной степени на примере вершинного покрытия
2. По минимальной степени на примере независимого множества