Жадные алгоритмы

1. [10 минут] Гамильтонов путь
1. Конь и правило Варнсдорфа
2. Вариации: рандом или прижиматься к границе; начинать с рандома или с угла/стороны/центра.
3. Применение к произвольному графу. Вероятностный алгоритм, поэтому запустить нужно несколько раз. Можно не 1 ребро брать, а k минимальных.
2. [30 минут] Хаффман
1. Как обычно записывается текст в файл? Есть алфавит Σ каждому символу дают ceil(logΣ) бит.
2. Принцип сжатия: символам сопоставляем разные коды. Минимизируем Σ count_i len_i
3. Чтобы можно было однозначно декодировать сделаем коды беспрефиксными (пример с a=0, b=0; a=0, b=00; a=0, b=1, c=01)
4. Кодирование (encode) за O(length). Раскодирование (decode) за O(length) построением дерева кодов (бора строк).
5. Доказательство корректности + алгоритм
1. Рассмотрим дерево, в нём нет deg = 1, и len_i↑ count_i↓
2. Заменим пару с минимальными count_i на новую вершину
3. Реализация кучей за O(ΣlogΣ). Получение собственно кодов.
6. Хранение дерева
1. Можно записать массив частот, в decode строить дерево так же, как в encode
2. Можно писать или 0.LR или 1.символ
3. Можно перестановку символов и структуру дерева: m(logm - loge + 2).

1. [20 минут] Компаратор
1. Примеры задач
1. Сортировка по t_i (успеть побольше!)
2. Сортировка по d_i (успеть все! дедлайн на время концов) док-во выбором минимума
3. Сортировка по t_i+d_i (успеть все! дедлайн на время начала) док-во выбором максимума
4. Сортировка по fee_i/t_i (штраф = T_i*fee_i)
2. Обобщение
1. Если решение сортировка, то существует компаратор, его не обязательно описывать формулой
2. Применяем к fee_i/t_i
3. Применяем к t_i+d_i
4. Применяем к задаче о двух станках без доказательства