С.В. Яблонский - Введение в дискретную математику (1060464), страница 37
Текст из файла (страница 37)
П р и м е р 9. Сеть Г (а, Ь), изображенная иа рис. Зт, будет я-сетью. е Ркс. 32 Рвс. 31 Каждой и-сети можко поставить в соответствие миожество укладок дерева, яекоицевым вершинам которых сопоставлены символы р и е. Воэможиы два случая: 1) Г(а, Ь) — Гь(а, Ь), где о=р или о г. Сети Гье(а, Ь) ставим в соответствие пучок из Ь (Ь ~ 2) ребер «), корень которого помечен символом о (рис. 32). 2) Г(а, Ь) расщепляется иа сеть Гье(а, Ь) и сети Г,(а'", Ь'"), ..., Г«(а<лл, Ьи') (о р или о е).
Выпускаем иэ корня, помечепиого символом о, Ь (Ь > 2) ребер «), «) Порядок ребер з пучке ври о р прояззолев, прв с = « соответствует порядку ребер з свтв Гь«(е, Ь). ч, па сглазы н свтп которые соответствуют внутренним сетям (рнс. 32). Далее, концам ребер, которым соответствуют нетривиальные сети, приписываем символ, отличный от о (его обозначим через о з)). После этого для каждой нетривиальной сети Рвс.
ЗЗ Рзс. 34 Г,(а'о, Ь'о) применяют либо и. 1, либо и. 2 н строят пучки в вершинах о и т. д. (рис. 33). В построенной укладке дерева каждый пучок ребер содержит не менее двух ребер. Таким образом, каждой н-сети соответствует множество укладок дерева. Неизоморфныьг п-сетям соответствуют непересекающиеся множества укладок. Значит число я-сетей не превосходит числа укладок деревьев.
Рассмотрим укладку дерева для л-сети из примера 9 (рис. 34). Легко видеть, что укладка дерева, соответствующая я-сети с Ь ребрами, имеет Ь концевых вершин. Итак,' изучение я-сетей может быть сведено к изучению укладок деревьев специального вида. Покажем, что эта связь позволяет переносить некоторые факты, известные для деревьев, на я-сети. Т во р е м а 5.
Пусть я(Ь) — максимальное число коварно неизоморфньгх и-сетей с Ь ребринн. Тогда я(Ь)< ч 4м Доказательство. Очевидно, что искомое число не превосходит числа укладок выше указанного типа деревьев с Ь концевыми вершинами, у которых каждый пучок исходящих ребер содержит не менее.
двух ребер. Обозначим через ( число ребер в дереве из этого класса. По инд ции докажем, что ((2Ь вЂ” 2 при Ь>2. Г азис индукции. Еслнп-сетьсодержитдзаребра: Ь 2, то очевидно, что соответствующее дерево содержит ') Где о=несла о=рв о=р,есле о=в гл. 2. свти 255 две концевые вершины, т. е. с =2 и неравенство выполнено.
Индуктивный переход. Пусть неравенство верно для деревьев, соответствующих я-сетязс с менее, чем Ь ребрами. Рассмотрим я-сеть Г(а, Ь) с й ребрами н соответствующее ей дерево (рис. 35). Если Г(а, Ь) Гь~(а, Ь),то с Ь)2 н неравенство, очевидно, выполнено. Если Г(а, Ь) допускает расщепление, то в дереве число т исходящих нз корня ребер равно числу ребер внешней сети расщепления сети Г(а, Ь) и по условию т > 2. Деревья 0„ ..., ссс соответствуют нетривиальным внутренним сетям этого расщепления, с < и, Обозначим через сс и йс (с = 1, ..., с) число ребер и число концевых вершин в Рыс. 35 дереве Рс. По предположеншо индукции сс<2йс — 2 (с= с, ..., г), кроме того, очевидно, с ~~1с+т 1с Х йс+(т — г) Ь. Мы ивсеем с-с с-1 с с ~~", сс+ т(2~ Ьс — 2с + т с-1 с-1 у с 2 ~ ~ йс + (т — г)1 — т = 2Ь вЂ” т(2Ь вЂ” 2, с-1 Ф так как т > 2.
Для оценки величины п(й), заметим, что в каждой укладке дерева из данного класса символы р и з можно расставить двумя способами. В силу этого, ислольэуя оценку для числа укладок деревьев с заданным числом ребер, имеем я (й) ( 2 . 4'" ' < 4'" ЧАСТЬ 1Ч ТЕОРИЯ КОДИРОВАНИЯ Вопросы кодирования играют существенную роль в математике. Кодирование позволяет изучение одних объектов сводить к изучению других.
Хорошо известно, какую роль сыграло изображение чисел в десятичной системе счисления. Весьма важным в развитии математики было появление метода координат, который позволил кодировать геометрическяе объекты при помощи аналитических выражевий. Однако, здесь средства кодирования являлись вспомогательным аппаратом и не были предметом изучения. Совсем другое значение почучили коды в связи с изучением управляющих систем.
Появилась необходимость систематического исследования в области теории кодирования. Основной круг задач может быть прослежен ка примере из области связи, который характеризуется схемой, представленной ка рис. 1. Пусть задан алфавит 6 =1ае ..., а,), состоящий из конечного числа букв. Конечпую последовательность символов из 6 А = ача;,... а;„ будем называть словом в алфавите 6, а число и — длиной слова А.
Длину слова А будем обозпачать через 1(А). ч. 1Р. теоРпя кодпговлння гзт Пусть Я=о'(6) — множество всех непустых слов в алфавите 6, и о' — некоторое подмножество множества Ю. Обьект, порождающий слова из д', называется источником сообщениК а слова из д' — сообщениями. Источником сообщений может быть автомат, человек и т. п. Обычно при рассмотрении задач теории кодирования используется дополнительная информация об источнике сообщений в виде некоторого его описания. Существует ряд способов описаний источников сообщений: а) теоретико-множественное описание осуществляется путем фиксации мощностных характеристик о',например, 8 — множество всех слов заданной длины т; б) статистическое окиеание осуществляется заданием вероятностных характеристик д', например, Я' 8, и заданы вероятности р„..., р, появления букв а„...
..., ., Ы „ 1); в) логическое описание — зто описание множества 8 как некоторого «языка». Оно характеризует способы построения множества Л', например, В' может быть порождено некоторым автоматом. Пусть задан алфавит 6, где 6 (Ь„..., Ь,). Через В обозначим слово в алфавите 6 и через 8(6)— множество всех непустых слов в алфавите 6. Пусть задано отображение Р, которое каждому слову А, А вг 8'(Ф), ставит в соответствие слово В Р(А), В «и В(6). Слово В будем называть кодом сообщения А, а переход от слова А к его коду — кодированием.
В теории кодирования отображения Г задается векоторым алгоритмом. Пример 1. а) Алфавитное кодирование. Рассмотрим соответствие между буквами алфавита И и некоторыми словами в алфавите 6: а,— В„ а,— В„ а,— В,. у Ввевенне в ниекуетную натенатику ч. 1у. теог»»я код»»говання Это соответствие называют схемой и обозначают через Е. Оно определяет алфавитное кодирование следующим образом: каждому слову А = а»,...
а;„из 8'(6) = Я(5) ставится в соответствие слово В=В»»... В»„, называемое кодом слова А. Слова В„..., В, называются элементарными кодами. б) Равнол»ернов кодирование. Пусть (А„..., А,) — некоторое подмножество попарно различных слов в алфавите»й, имеющих одинаковую длину и. Очевидно, что каждое слово А, которое допускает разложение вида А А»,...А»„„ имеет единственное разложение. Пусть, далее, Я'(6)— подмножество всех слов в алфавите И, допускающих разложение вышеуказанного вида. Рассмотрим схему А,— В„ где элементарные коды В, имеют одинаковую длину. Схема Х определяет равномерное кодирование следующим образом: каждому слову А = А»,... А»„из Б'(6) ставится в соответствие слово В В» ...
В»„, называемое кодом слова А. Выбор кодов связан с различными обстоятельствами, а именно: с удобством передачи кодов (например, двоичный код ,технически легче использовать); с обеспечением удобства восприятия (например, машинные коды удобны для работы процессора); с обеспечением максимальной пропускной способности капала; с обеспечением помехоустойчивости; с достижением определенных свойств алгоритма кодирования (например, простота кодирования, возможность однозначного декодирования) и т. п. Канал связи можно рассматривать как устройство с одним входом и одним выходом (см. рис.
2). На вход этого устройства поступает код сообщения В. На выходе получают В' — код сообщения на выходе, где В' — слово в некотором алфавите 6' и В' = ЯВ). ч. и'. ТеоРня кодпРОВАния 259 В простейшем случае (тождественный канал без помех), т. е. в случае идеальной линии связи, В' В (или ((В) ° = В) и значит 6' = 6. В общем случае канал связи может включать в себя преобразование кодов и 6'т= 6 (как, например, в ЭВМ).
Источник потаех вноси~ ошибки в канал связи, вызывая искажения кодов на выходе. Для описания источника помех используют д' ~ ~ д' два способа: а) логика-комбинаторное описание Рве. 2 обычно связано с указанием ограничений на число единичных ошибок; б) статистическое описание осуществляется заданием вероятностных характеристик источника. Код сообщении на выходе в случае тождественного канала представляет собой некоторое слово в алфавите 6' 6. Однако источник помех может приводить к тому, что В' чь В. Сообщение на выходе представляет собой слово в некотором алфавпте 6. В случае тождественного канала, т. е.
при передаче сообщений, 6 т(. Переход от кодов сообщений па выходе к сообщениям на выходе предполагает дза преобразования. Коррекция кода сообщения на выходе. Это преобразование вовможно только для специальных кодов сообщений. В том случае, если мы имеем дело с передачей сообщений, происходит переход от В' к В. Декодирование. Оно представляет собой переход от кода, полученного из кода сообщения на выходе после коррекции, к сообщению на выходе.
Декодирование возможно также не для всяких кодов, а только для специальных кодов сообщений. В случае передачи сообщений декодирование возможно, если существует обратное отображенив Г-'. В данной главе мы познакомимся с элементами теории кодирования. При отборе материала мы стремились дать представление: а) о главных классах кодов; б) о теоретико-вероятностных и комбинаторно-логических подходах к описанию задач; в) о характере математических задач в этой области; г) о методах решения задач теории кодирования. ч. гу.
твогня гюдпРОВАш!я 2СО В $1 — 4 научается алфавитное кодирование. Изложение концентрируется вокруг двух аадач: выяснения возможности одноаначного декодирования и построения кодов с наименьшей иабыточкостью. В т 5 изучается один класс кодов иа семейства так называемых равномерных кодов. Здесь рассматривается эадача о построении помехоустойчивых кодов. $ $. Критерий одновначности декодяровапия Здесь мы рассматриваем алфавитное кодирование для алфавитов И и 6, задаваемое схемой Х: а,-Вь (Е)' а,— В„ и полагаем Я'(И) = Ю(И), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
