Конспект: расписания, Хаффман, покрытие множеств

Понятия

Префиксный код - ни одно слово не является началом другого; равносилен двоичному дереву с символами в листьях.

Цена кода - Σ f_i·d_i, она же сумма всех слияний Хаффмана.

c-приближённый алгоритм - для любого входа ответ не хуже оптимума в c раз.

Что унести

Расписания на одном процессоре: критерий задаётся ЦЕЛЬЮ.

почему SPT: задача на k-м месте входит в Σ C ровно (n − k + 1) раз
            Σ C = n·t_(1) + (n−1)·t_(2) + ... + 1·t_(n)

на задачах 8, 1, 3, 2:  по возрастанию 24   по убыванию 46   как дано 43
                        последнее завершение 14 во всех случаях

Доказательство всех трёх - обмен СОСЕДНИХ: такая перестановка не затрагивает остальные задачи, в выкладке остаются два слагаемых. Для SPT разница равна t_i − t_j, для EDF используется только сравнение сроков - поэтому длительности и не входят в критерий.

ХАФФМАН
пока узлов больше одного:
    взять ДВА САМЫХ РЕДКИХ узла среди ВСЕХ (включая созданные ранее)
    заменить одним с суммарной частотой
цена = сумма всех слияний = Σ f·d
очередь с приоритетом → Θ(n·log n)

доказательство: обмен ЛИСТЬЕВ. Перестановка самого редкого символа с листом
максимальной глубины меняет цену на (f_a − f_x)·(d_x − d_a) <= 0.
подзадача: цена(T) = цена(T') + f_x + f_y - прибавка не зависит от формы дерева

На частотах 45, 16, 13, 12, 9, 5: слияния 14, 25, 30, 55, 100, цена 224 бита против 300 у трёхбитного кода; энтропия 2.22 бита на символ, Хаффман 2.24. Код не единственный, цена единственна. Хаффман не хуже энтропии плюс один бит на символ; при сильном перекосе частот берут арифметическое кодирование.

Покрытие множеств - NP-трудно, точной жадности нет.

Контрпример к оптимальности: A={1,2,3,4}, B={1,2,5}, C={3,4,6} - жадность берёт 3, оптимум 2 (B ∪ C).

Гарантия не равна качеству. Замер на звезде с отростками (рёбра 0-1, 0-2, 0-3, 1-4, 2-5, 3-6): «оба конца» дал 6 (ровно вдвое, его граница), жадность по степени с ХУДШЕЙ гарантией - 4, оптимум - 3. Выбирать между ними надо замером на своих данных; гарантия нужна, когда вход может быть любым.

Тихие ошибки: выбрать критерий, не назвав цель; применить SPT там, где важны сроки; не возвращать созданный узел в очередь Хаффмана; читать «гарантия 2» как «ошибается вдвое»; переносить жадность расписаний на две машины (NP-трудно); применять «оба конца» к взвешенному вершинному покрытию.

Куда это ведёт

Следующая глава - матроиды: общий ответ на вопрос «почему в одних задачах жадность всегда права». Там же выяснится, что Крускал из раздела 11 - это жадность на матроиде, а значит его корректность следует из общей теоремы, а не из отдельного доказательства.