Жадные алгоритмы (29 марта 2017)

1. [5 минут] Введение и рюкзак: непрерывный рюкзак, равносильность сортировки выбору первого элемента
2. [10 минут] Гамильтонов путь
1. Конь и правило Варнсдорфа
2. Вариации: рандом или прижиматься к границе; начинать с рандома или с угла/стороны/центра.
3. Применение к произвольному графу. Вероятностный алгоритм, поэтому запустить нужно несколько раз. Можно не 1 ребро брать, а k минимальных.
4. Отсечение для произвольного графа: остаток связен
3. [15 минут] Коммивояжёр
1. Формулировка: есть неравенство треугольника, граф полный
2. 2 приближение через MST
3. 1.5 приближение через MST (дополняем до эйлерова, добавляя)
4. Локальные оптимизации: перестановка, reverse для пересекающегося

1. [20 минут] Хаффман (повторение с дискретки)
1. Принцип сжатия: символам сопоставляем разные коды. Минимизируем Σ count_i len_i
2. Чтобы можно было однозначно декодировать сделаем коды беспрефиксными (пример с a=0, b=0; a=0, b=00; a=0, b=1, c=01)
3. Кодирование (encode) за O(length). Раскодирование (decode) за O(length) построением дерева кодов (бора строк).
4. Доказательство корректности + алгоритм
1. Рассмотрим дерево, в нём нет deg = 1, и len_i↑ count_i↓
2. Заменим пару с минимальными count₁ и count₂ на новую вершину count₁ + count₂
3. [skipped] Реализация кучей за O(ΣlogΣ). Получение собственно кодов.
4. [skipped] Реализация очередью за O(sort + Σ)
5. Хранение дерева: можно хранить собственно, можно массив count, можно сжать хаффманом
2. [30 минут] Компаратор
1. Примеры задач
1. Сортировка по t_i (успеть сделать побольше заданий!)
2. Сортировка по d_i (успеть все! дедлайн на время концов) док-во выбором минимума
3. Спортсмены s_i, m_i выстраиваются в башню
4. Сортировка по fee_i/t_i (штраф = T_i*fee_i)
2. Обобщение
1. Если решение сортировка, то существует компаратор, его не обязательно описывать формулой
2. Применяем к fee_i/t_i
3. Применяем к t_i+d_i
4. Применяем к задаче о двух станках без доказательства