Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 74
Текст из файла (страница 74)
364 Ответы, указания, решения Глава УП 1.1. Ц, 3), 4), 6) Код С не обладает свойстном префикса. 2), 5) Код обладает свойством префикса. 1.2. Ц Код не является однозначно декодируемым. Неоднозначно декодируемое слово: 01122 01. 2)., 4), 5), 8) Кол однозначно декодируемый. 3 0010001001. 6) 01101100112100. 7) 010210112 ) 1.3. Ц, 2), 4) Р является кодом одного сообщения. 3), 8) Р не является кодом сообшения. 5) — 7) Р является кодом более чем одного сообшения. 1.4. Ц Р е ш е н и е. Пусть С(А) множество двоичных разложений чисел из А; С(А) = (1, 101, 110, 111, 1100, 1101, 1000Ц. Вычеркнув из С(А) слова 1 и 110, получим префиксный код. Вычеркиванием меньшего числа слов обойтись нельзя.
Таким образом, для задачи а) В = А)(1, 6). 2) а) В = А)(1, 3, 6, 8); б) В = А)(Ц. 3) а) В = А1(2, 6, 7, 8, 9); б) В = А)(2, 7). 4) а) В = А)(1, 2, 5); б) В = А)(1, 2). 1.5. Ц 1201012. 2) 0101010101010101010101010 3) (ОЦН 400. 4) Если Ь = 4, то 01010101, если Ь > 4,то 01010101010. 5) 0(10)~1 *"1, где Н(тв Ь) наименьшее общее кратное чисел т и Ь.
6) (1100)", если й = Зв, в = 1, 2...; в противном случае решений нет. 7) (10Ц~О для всех Ь = 1, 2,... 8) (110)Я (Ь = 2в). 1.6. Ц с = (а, Ьа, ЬЬа, ЬЬЬ). 2) с = (а, Ьа, ЬЬЬа, ЬЬаЬ, ЬЬЬЬ, ЬЬаа). 3) с = (аЬ, Ьа, ЬЬа, ЬЬЬ, аааа, аааЬ, ааЬл, ааЬЬ). 4) с = (аа, аЬ, Ьа, ЬЬаа, ЬЬаЬ, ЬЬЬа). 1 1 1 1 9 1.7.
Ц Нет, гак как — -~- — 4- — -~- — = — > 1. 2 4 4 8 8 1 1 1 1 2) Па, так как — 4- — 4- — 4- — ( 1. 3) Па. 4) Па. 8 9 9 27 1.8. Ц Воспользуемся неравенством Макмиллана. Пусть 1, — длины ~сз ~с~ ч 1 х 1 (С( кодовых слов кода С. Тогда яз — > кз — = — > 1. Код но может быть 26 2 2" ,=з однозначно декодируемым.
2) Нет, так как если бы код С был префиксным, то он был бы однозначно декодируемым. 1.9. Пусть код С(В) с набором длин кодовых слов 1ы 19, ..., 1„нс является деходируемым. Тогда в графе Сп существует контур или петля, проходящие через вершину Л. Число вершин (и дуг) в контуре не больше, чем в графе Св, н, следовательно, не больше 14- ~ (1, — Ц = 1з' — т+ 1. =-1 Збб Гл. (т11, Элементы теории кодирования Идя вдоль контура от вершины Л, рассмотрим слова, приписанные паре (дуга вершина, являющаяся концом дуги). Ясно, что суммарное количество букв для каждой такой пары не превосходит ! и может быть равно 1 только для первой пары. Отсюда и вытекает утверждение.
1.10. Пусть С вЂ” алфавитный код с набором длин кодовых слов !т, !з... пцп 1, = Ь, шах !, = 1, ~ !, = Лт. Из предыдущей задачи вытекает, =т,. т=т, что если код С не является однозначно декодируемым, то существует сло- во в кодирующем алфавите длины не больше 1+ (Лà — г+ Ц(! — Ц < Лт!. Тогда в алфавите сообщений длина соответствующих слов будет не боль- ше Лт!/Гй. 1.11. Ц Пусть ! максимальная из длин слов в М.
Тогда для числа г 4+ 4 слов в М имеем т < ~ ~т/' = . Отсюда 1 > ! он (9 + г(д — Ц ) — 1. 4 †=. т 2) Доля Ь, слон длины, не превосходятцей ! = (1 — е) (обо(1 + г(д — Ц), не больше Ч Ч Если г=2, 9=2,то О,« — <( — ) 2 2 2 тз/ Если г>2, тГ)2и г ° д>4,то г(д — Ц)3 и (4) 1.15. Ц Утверждение вытекает из результата задачи 1.9. 2) Указание. Рассмотреть код С(Е) = (а, (аЬ)ьт', (Ьа)~тз) (Ь ) Ц.
Убедиться,что единственный контур в Сш проходящий через Л,проходит последовательно через вершины (Ьа) тЬ, а(Ьа)' (т = 1, ..., Ь + Ц, а ГР соответствующее этому контуру слово имеет вид (аЬ) ~ ~ а. Зтптп 2.1. Ц, 2) Например, С = (О, 10, ПО, 111). 3) Например, С = (ООт 01, 10, 110, 11Ц, 2.2. Ц Например, С = (а, Ь, са, сЬ, сс). 2) Например, С = (а, Ь, са, сЬ, тта, ссЬ, ссс).
Г1 1 1 1 1 14 2.3. Ц Например, Р = ( —; —; —; —; —; — т; оптимальным является ! 2' 4' 8' 16' 32' 32 код С = (О, 10, 110, 1110, 11110, 11111). Р е пт е н и е. Проведем редукцию длин (1, 2, 3, 4, 5. 5) — т (1, 2т 3, 4, 4) 4 — т (1, 2т 3, 3) — т (1, 2, 2) 4 (1, Ц. Двоичный код с набором длин (1, Ц, очевидно, существует и является единственным и оптимальным при лю- /1 1т бом распределении вероятностей, например, при Г = (-; -/!, С = (От 1). 2 2 Проводя с набором Р преобразования, соответствующие переходу от набора длин (1, Ц к исходному, и деля всякий раз соответствующую вероятГ1 1 1 1 1 1 ность появления слова пополам, приходим к Р = ( †; †; †; †: †; — т 2 4 8 16' 32 32 и С = (О, 10, 110, 1110, 11110, 11111).
366 Ответы, указания, решения 2) Например, Р = (0,2; 0,2: 0,2; 0,2; 0,2); оптимальным является код С = (00, 01, 10, 110, 111). Г1 1 1 1 1 1 1л 3) Например, Р = ( —: —; —; —; —; —; — 1, С = (00, 01, 100, 101, 4 ' 4 8 16 16 16 16 1100, 1101, 1110, 111Ц. Г1 1 1 11 5) Например, Р = ( —; —; —; — 1., С = (а, Ь, са, сЬ). 3 3 6 6 Г1 1 1 1 1 1 1 11 10) Например, Р = ( — —; —. — —; — —; — ~, С = (а Ь, са, сЬ, сс, сГГ 8 8 8 8 8 8 8 8 4а, ГГЬ, ГГс, ГЫ). 2.4. Ц, 3), 4), 8) Код оптимален. 2)., 9), 10) Код не оптимален.
2.5. а) Леревья 2), 4), 8), 10) являются насыщенными, остальные не являются насытденными. б) Леревья 1), 2), 4), 8), 10) могут являться остовами оптимальных деревьев, остальные не могут. 2.6. 1) Утверждение верно. Всякий двоичный оптимальный код является полным. 2) Вообще говоря, утверждение неверно (см.
задачу 2.5, б), 1)). 3), 5) Утверждение верно. 4) Вообгце говоря, неверно (см. задачу 2.5, б), 1)). б) Утверждение верно. Показать можно индукцией по числу концевых вершин. 2.7. 1*) Пусть С полный д-значнгяй код с длинами кодовых слов Л.
(1 = 1, ..., т). Пусть Л = ГпахЛ,. Из полноты кода С следует, что каждое слово длины Л в алфавите В имеет префиксом (не обязательно собственным) некоторое кодовое слово. Число слов длины Л, имеющих префиксом слово ш, длины Л„равно 9~ л*. Если ш, и ш -- два кодовых слова, то множества Вл(ш,) и В (ш ) слов длины Л в алфавите В, имеющих префиксом л — л, л кодовые слова ш, и иГм не пеРесекаютсЯ. Отсюда ял д ' = д, что и 1< <ы требовалось доказать. 2) База индукции - - двоичный оптимальный код с двумя сообщениями. Индуктивный переход осуществляется с помощью теоремы редукции. 3) Лля 6 ) 2 утверждение, вообще говоря, неверно.
Пример: д = 3, Г1 1 1 11 Р = [ —; —; —; — 1, С = (а, Ь, са, сЬ). Код С оптимальный, но не полный, 3 3 6 6 тах как 3 ' -~- 3 ' + 3 + 3 = 8/9 < 1. 2.8. Если для некоторого кодового слова ш максимальной длины 1 не найдется слова, отличающегося от ш последней буквой, то, нс нарушая прсфиксности кода, можно заменить слово его префиксом длины 1 — 1, что противоречит оптимальности кода. 2.9. Указание. См. задачу 2.8. 2.10.
1), 4), 6) Нет, см. задачу 2.9. 2), 7), 8) Нет. Нарушено неравенство Макмиллана. 3), 5) Оптимальный ход сугцествует. 2.11. 1), 3), 5), 7), 9) Не существует. 2), 4), б), 8), 10) Существует. 2.13. 1) Указание. Лостаточно убедиться, что почти равномерный код можно построить в результате алгоритма Хаффмена. 367 Гл. 171. Элементы теории кодирования /1 1 1 2) Указание. Рассмотреть распределение Р = ( — +е, —, ..., —, 1 1 т ш ш — — е), где е < —. тз 2тн 2.14.
1) Указание. Провести доказательство индукцией по т с при- менением теоремы редухции. /1 1 1 1 1 2.16. Например, Р = ( —, —, ..., 2 4 2 з 2™ О 2 з) 2.16. Базис индукции: ш = 2. Утверждение очевидно. На шаге индук- ции использовать задачу 2.14. 2.17. В процоссе преобразования набора вероятностей неоднозначность может возникнуть при упорядочении вероятностей по невозрастанию. Если набор содержит т вероятностей, то разместить сумму наименьших двух вероятностей среди оставшихся т — 2 можно не более чем т — 1 способами. В процессе сопоставления вероятностям кодовых слов на каждом шаге имеется две возможности.
Отсюда вытекает опенка. 2.18. 1) Число непустых слов длины не больше тп — 1 равно Ь а' < . Число однозначных отображений букв алфавита А в е е д — 1' ш« тз слова в алфавите В, ~В~ = д, плины меньше т не превосходят д 2) а) Верно. б) Число тупиковых кодов мощности т не превосходят числа помеченных корневых деревьев с т висячими вершинами. Число непомеченных деревьев с т висячими вершинами не превосходит 4з" (см. гл.
У1, задачи 3.6 и 3.10). Пометить ребра можно не более чем дм способами. 3.1. 2) Вытекает из того, что )и — у! < )и — Д+ )УУ вЂ” у! для всех о, уу, у из (О, 1). б) Вытекает из того, что (и — 11) = л +  — 2о)1 для всех о, )1 из (О, 1). 3.2.1) и 2" '. 2) ( ).2' 3.3.
Ц (,). 2) ~ (,.). о«<г пз -~- й — т 3) ( ) (й ), если з = - — делое неотрицательное число. з,) (,й — о )' 2 3.4. Ц 2 2) О, если т < ш; 2 , если т = та ( „ ) 2 , еслн т = ш -~ 2й ( тц О, если т = 2й + т — 1, й = О, 1,... или если т > и. 3) О, осли й -Е т < ш нли если т -Е й = т -~- 24 — 1, д = О, 1, ..., или если т -т й > и; ( ), если й з-т = тд ( ) ( ), если й -'т т = = ш -е 24, И = О, 1, ... З.б. 1) Пусть существуют наборы а,,З, у, удовлетворяющие условиям. Положим оу = О, 6 = Уз ОУ Н., 6= у бзик, Ясно, что !)6!) > 2пу'3 и ОЩ > 2и(3.
Но тогда р(6, е) = р(уд, у) < 2п/3. 368 Ответы, указания, решения 3.6. 3) При 1. = О, и, а также при 1. = и/2 и четных п. 4) Пусть А . полная система. Рассмотрим систему уравнений р(Н,,В,)=г, И=1,....,к). Очевидно, что г,Е10,1,...,п) И=1,... ..., Й). Каждый набор (гы г, ..., гя), при котором система имеет решения, однозначно определяет некоторый вектор !У Е В". Отсюда (п -Н 1) ) 2". Верхняя оценка для числа векторов в базисной системе может быть получена из того, что система р(Й„В) = г„является системой линейных уравнений с п неизвестными. б) Нижняя оценка вытекает из задачи 1) и оценки числа возрастающих цепей длины п — 1, верхняя из задачи 4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
