|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[112] сливаемых узлов. В упражнении 17.3-3 мы предложим вам доказать, что стоимость дерева равна сумме стоимостей всех слияний, необходимых для его построения. Стало быть, алгоритм Huffman на каждом шаге выбирает слияние, наименее увеличивающее стоимость. Теперь установим свойство оптимальности для подзадач. Пусть фиксирован алфавит С и два символа ж, у этого алфавита, а С - алфавит, который получится из С, если выкинуть ж и у и добавить новый символ z. Рассмотрим кодовые деревья для С, в которых ж и у (точнее, соответствующие им листья) являются братьями. Каждому такому дереву соответствует кодовое дерево для С, которое получится, если выбросить вершины ж и у, а их общего родителя считать кодом символа z. При этом соответствии каждому кодовому дереву для С соответствует ровно два кодовых дерева для С (в одном из них ж будет левым ребёнком, в другом - правым). Пусть для каждого символа с из С фиксирована его частота /[с]. Определим частоты для символов из С, считая частотой символа z сумму /[ж] + f[y]; для остальных символов частоты остаются теми же, что и в С Тогда для кодовых деревьев (для обоих алфавитов) определены стоимости. Лемма 17.3. Стоимости соответствующих друг другу деревьев Т и Т (при описанном соответствии) отличаются на величину Доказательство. Легко видеть, что dj(c) = djt(c) для всех с £ С \{х,у}, а также что dj(x) = dj(y) = dx(z) + 1. Следовательно, Эта лемма показывает, что выполнено свойство оптимальности для подзадач (оптимальное дерево Г соответствует оптимальному дереву Т для меньшей задачи). Из двух доказанных лемм легко следует Теорема 17.4. Алгоритм Huffman строит оптимальный префиксный код. Доказательство. Лемма 17.2 показывает, что оптимальные кодовые деревья можно искать среди таких, у которых два наиболее редких символа (назовём из ж и у) являются братьями. Им соответствуют деревья для алфавита С, в котором символы ж и у слиты в один символ z. Считая частоту символа z равной сумме частот ж и /И + /Ы- f[x]dT(x) + f[y]dT(y) f[z]dT,(z) + (f[x] + f[y]) □ у, можно применить лемму 17.3 и увидеть, что нам остаётся найти оптимальное кодовое дерево для алфавита С и затем добавить к вершине z двух детей, помеченных символами хну. Это и делает алгоритм Huffman.□ Упражнения 17.3-1 Докажите, что в бинарном дереве, соответствующем оптимальному префиксному коду, всякая вершина либо является листом, либо имеет двух детей. 17.3-2 Найдите код Хаффмена для алфавита, в котором частоты символов совпадают с первыми восемью числами Фибоначчи: а : 1 Ъ : 1 с:2 d:3 е:5 f : 8 g : 13 h : 21. Что будет, если в алфавите га символов, частоты которых совпадают с первыми га числами Фибоначчи? 17.3-3 Докажите, что стоимость двоичного дерева, соответствующего префиксному коду, можно вычислить следующим образом: для каждой вершины, не являющейся листом, найти сумму частот ее детей, и сложить все полученные числа. 17.3-4 Расположим символы алфавита в порядке убывания (невозрастания) частот. Докажите, что в оптимальном префиксном коде длины кодирующих эти символы последовательностей битов будут идти в неубывающем порядке. 17.3-5 Докажите, что оптимальный префиксный код для алфавита из га символов может быть представлен последовательностью из 2га - 1 + ra[log2 га] битов. (Указание: для задания структуры дерева достаточно 2га - 1 битов.) 17.3-6 Обобщите алгоритм Хаффмена на тернарные коды (каждый символ кодируется последовательностью из цифр 0, 1 и 2). Коды, порождаемые вашим алгоритмом, должны быть оптимальны. 17.3-7 Пусть алфавит содержит 28 = 256 символов, причём максимальная частота превосходит минимальную не более чем вдвое. Покажите, что для алфавита с такими частотами код Хаффмена не более эффективен, чем равномерный восьмибитовый код. 17.3-8 Профессор утверждает, что написанная им программа сжатия информации позволяет сжать любой файл длины 1000 (последовательность из тысячи 8-битовых байтов) хотя бы на один бит, после чего написанная им программа восстановления сможет восстановить исходный файл. Почему он неправ? (Указание: сравните количество возможных файлов с количеством сжатых файлов). ★ 17.4 Теоретические основы жадных алгоритмов В этом разделе мы вкратце расскажем о красивом разделе комбинаторики, связанном с жадными алгоритмами, - теории матро-идов. С помощью этой теории часто (хотя и не всегда: задачи из разделов 17.1 и 17.3 теорией матроидов не покрываются) удаётся установить, что данный жадный алгоритм даёт оптимум. Теория матроидов быстро развивается (см. ссылки в конце главы). 17.4.1. Матроиды Матроидом (matroid) называется пара М = (S,X), удовлетворяющая следующим условиям. 1.S - конечное непустое множество. 2.X - непустое семейство подмножеств S; входящие в X подмножества называют независимыми (independent). При этом должно выполняться такое свойство: изВе!иАСВ следует А £ X (в частности, всегда 0 £ X). Семейство X, удовлетворяющее этому условию, называется наследственным (hereditary). 3.Если А £ X, В £ X и А < \В\, то существует такой элемент х £ В\А, что A U {ж} £ X. Это свойство семейства X называют свойством замены (exchange property). Термин «матроид» принадлежит Хасслеру Уитни (Hassler Whitney). Он занимался матричными матроидами (matric matroids), у которых S - множество всех строк некоторой матрицы, и множество строк считается независимым, если эти строки линейно независимы в обычном смысле. (Легко показать, что действительно получается матроид, см. упр. 17.4-2.) Другим примером является графовый матроид (graphic matroid) (Sg,Xg), строящийся по неориентированному графу G следующим образом: Sq совпадает со множеством рёбер графа, a Xq состоит из всех ацикличных (т.е. являющихся лесами) множеств рёбер. Графовые матроиды тесно связаны с задачей о минимальном покрывающем дереве, которую мы рассмотрим в главе 24. Теорема 17.5. Если G = (V, Е) - неориентированный граф, то Mq = (Sg,Xg) является матроидом. Доказательство. Так как подграф ацикличного графа ацикличен, множество Xq наследственно, и остаётся проверить свойство заме- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||