Жадность (5 марта 2021)

1. [5 минут] Введение
   1. MST Краскал − мы знаем, какое ребро взять первым! это жадность
   2. НОП − мы её решаем динамикой, можно решать перебором, жадное решение могло бы выглядеть так : из match(a[0]) и match(b[0]) взять ближайшее
   3. То, с чем вы сталкиваетесь каждый день: какую задачу делать первой, чтобы успеть ко всем дедлайнам? Ту, у которой дедлайн раньше!
   
   
2. [5 минут] Непрерывный рюкзак
   1. Решение 1 = мы знаем, какой элемент взять точно выгодно (элемент с максимальным частным)
   2. Решение 2 = сортировка по частному (по индукции каждый раз берём макс частное ⇒ берём в порядке сортировки)
   
   
3. Задачи, решаемые сортировкой
   1. Выполнить побольше заданий (сортировка по t_i) к моменту T.
   2. Выполнить задания максимальной суммарной стоимости к моменту T − это уже рюкзак, не решается.
   3. Успеть все задания с дедлайнами (сортируем по дедлайну d_i). Док-во выбором первого (остальных всё ещё можно выполнить) или последнего (задача стала проще).
   4. [skipped] Ушло в практику: Сортировка по t_i+d_i (успеть все! дедлайн на время начала).
   5. [skipped] Ушло в практику: спортсмены s_i, m_i выстраиваются в башню
   6. Сортировка по fee_i/t_i (штраф = T_i*fee_i, T_i − время окончания)
   7. Задача про ленту и файлы, сортировка по size_i/count_i (время обращения к файлу − его позиция) (переформулировка предыдущей задачи)
   
   
4. Компаратор
   1. Максимизация скалярного произведения. Транснеравенство.
   2. Идея компаратора: solve(n=2) ⇒ sort-order (если решение − сортировка, то &exists; компаратор, его не обязательно описывать формулой)
   3. Применяем к fee_i/t_i
   
   
5. 2 станка
   1. Применяем тему компаратору к задаче о двух станках. Получаем не верный компаратор. min(a_i, b_j) < min(a_j, b_i).
   2. Почему не работает? Практика: пострессим. Теория он не транзитивный для случая, когда бывают a_i=b_i.
   3. Кстати, что будет с sort, если ему передать не антирефлексивный или нетранзитивный компаратор? (не отсортирует)
   4. Верный компаратор. min(2a_i, 2b_j+1) < min(2a_j, 2b_i+1) cf
   5. Верное решение с составным компаратором.

1. Общие слова про архиваторы
   1. Не существует идеального архиватора (что-то обязательно не сожмётся).
   2. Как можно сжимать данные? Представьте себе bmp-файл, внутри красный квадратик. LRE-сжатие рулит.
   3. Как можно сжимать данные? Представьте себе литературный текст. Слов мало, можно каждому сопоставить его номер в словаре.
   4. Как можно сжимать данные? У разных символов разные частоты. Можно разным символам давать разные коды. Можно даже вещественных длин (арифметическое кодирование).
   
   
2. Хаффман (повторение с дискретки?)
   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 мета символ, сведёмся к такой же задаче
   5. Реализация кучей за O(ΣlogΣ).
   6. [skipped] Ушла на практику: реализация очередью за O(sort + Σ)
   7. На выходе получили дерево кодов, обошли его, получили сами коды.
   8. Что хранить в файле? Логичнее всего массив частот, по которому мы при декодировании тем же самым алгоритмам построим те же самые коды.
   9. Корректность хаффмана: рассмотрим дерево, в нём нет deg=1, и len_i↑ count_i↓, минимальные count₁ и count₂ − обязательно братья.
   10. Хранение дерева: можно хранить собственно, можно массив count, можно сжать хаффманом
   
   
3. [10 минут] Гамильтонов путь
   1. Конь и правило Варнсдорфа. Вариации: рандом или прижиматься к границе; начинать с рандома или с угла/стороны/центра.
   2. Применение к произвольному графу. Вероятностный алгоритм (среди минимальных случайную), поэтому запустить нужно несколько раз. Можно не 1 ребро брать, а k минимальных.
   
   
4. [15 минут] Коммивояжёр. Приближённые алгоритмы.
   1. Общие слова, что такое приближённые алгоритмы.
   2. Формулировка: есть неравенство треугольника, граф полный
   3. Жадное 2-приближение через MST
   4. Жадное 1.5-приближение через MST (Кристофидес: дополняем до эйлерова, добавляя рёбра)
   5. Локальные оптимизации: перестановка, reverse для пересекающегося
   6. (bonus) Как быстро искать MST? (а) Вороной. (б) Искать k ближайших точек (или сеточкой, или проекцией на случайную прямую).