Жадные алгоритмы (17 марта 2018)

  1. [5 минут] Введение и рюкзак: непрерывный рюкзак, равносильность сортировки выбору первого элемента

  2. [10 минут] Гамильтонов путь
    1. Конь и правило Варнсдорфа
    2. Вариации: рандом или прижиматься к границе; начинать с рандома или с угла/стороны/центра.
    3. Применение к произвольному графу. Вероятностный алгоритм, поэтому запустить нужно несколько раз. Можно не 1 ребро брать, а k минимальных.
    4. Отсечение перебора для произвольного графа: остаток связен

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

  4. [20 минут] Хаффман (повторение с дискретки)
    1. Принцип сжатия: символам сопоставляем разные коды. Минимизируем Σ counti leni
    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, и leni↑ counti↓
      2. Заменим пару с минимальными count1 и count2 на новую вершину count1 + count2
      3. Реализация кучей за O(ΣlogΣ). Получение собственно кодов.
      4. [skipped] (ушла на практику) Реализация очередью за O(sort + Σ)
    5. Хранение дерева: можно хранить собственно, можно массив count, можно сжать хаффманом
− Перерыв −
  1. [30 минут] Задачи, решаемые сортировкой. Выбор компаратора.
    1. Примеры задач
      1. Сортировка по ti (успеть сделать побольше заданий!)
      2. Сортировка по di (успеть все! дедлайн на время концов) док-во выбором минимума
      3. Спортсмены si, mi выстраиваются в башню
      4. Сортировка по feei/ti (штраф = Ti*feei)
    2. Обобщение
      1. Если решение сортировка, то существует компаратор, его не обязательно описывать формулой
      2. Применяем к feei/ti
      3. Применяем к ti+di
      4. Применяем к задаче о двух станках без доказательства