Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 75
Текст из файла (страница 75)
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). 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).
72" ' з — 1т 3.8. ! „1 !. Указание. См. гл., задачу 1.11. 3.10. 1) Рассмотреть В„" (Н). 2) Например, А = !Н; Н Е В", ОНО четное). 3.11. Инду кция по п. При п = 1 последовательность (0), (1) образует требуемый цикл в В . Пусть Нв, Ны ..., Нз 1 является циклом в В". Если а "- набор в В", то обозначим через ои набор из В"г', полученный приписыванием символа и Е 10, 1) справа к набору а.
Тогда последовательность авО, НгО, ..., Н зО., Н з1, ..., Нз1, ае1 является циклом в В" +1. 3.12. 1), а), в), д), ж), з) Векторы а являются п-универсальными, в остальных случаях нет. 3.13. 1) Ц2) = 4, ЦЗ) = 6, 1(4) = 8. 3.14. 1) Нижняя оценка. Пусть а = (101.. 0), Д = (О!... Ц, М = = (7 Е В„": Осг Ю 70 = 1), Аз = (Н) О М, Аз = (7)) 1З М. Ясно, что р(п) > > )А~ (и)( = (Аз(и)! = и. 2) Нижняя оценка. Пусть А = 1(ом ..., оы) Е В": сзз = 1). Ясно, что р''1и) > ~А~ = 2" Верхняя оценка. Если ОВГЗ Я ) 1 для любых Н, ~9 Е А С В", то А не содержит противоположных наборов. Положив А = 16: Н Е А), имеем А О А С В', А О А = О.
Отсюда ~А~ (2" 3.16. !П.Л. К!ейшап.) Пусть 1(п, гп, й) чисао троек Я, 71, у) таких, что НЕВв",ОА, ДЕВ~', 7ЕВ,'„'+я и НО!7=7, НГ1)з=О. Тогда "-("."") ='<™') - '(© -"И"-') '((. "") — -") ('"'.") Отсюда вытекает требуемое неравенство. 3.17. 1) Шары радиуса ! с центрами в кодовых словах не пересекаются тогда и только тогда, когда расстояние между двумя кодовыми словами не меньше 21-Е 1.
3.18. Ц 3. 2) 4. 3) 3. 4) 4. 5) 4. 3.19. Указание. Использовать задачу 3.17. 3.20. 1) Обнаруживает одну ошибку и исправляет ноль ошибок. 2)п — 1и [ ~. 3) — — 1 и 4) Обнаруживает одну ошибку при четных п и ноль ошибок при нечетных и,. исправляет ноль ошибок. 3.21. 1) 100110. 2) 110011. 3) 0011001. 4) 1010101. 5) 111001011011. б) 0010110001111. 7) 1110000110011. 8) 000011110111011. зоо Гл. 711. Элементы теории кодирования 3.22.
1) 1. 2) 110. 3) 110. 4) 0011. 5) 0101. 6) 1101. 7) 0011. 8) 0111110. 9) 110110100. 10) П110111101. 3.24. 1) д(х ) = хг(хзхзхех - Ч хзхзхлхз). 2) д(х ) = хз(хлхо(хьх3з о хзхз) о х1хзхлхз). 3.25. 1) Вообще говоря, нет. 2) Ла. 3) Вообгце говоря, нет. 3.26.
Пусть С = ((оз...о„) Е С: о1 ОЗ...о„= о). Тогда Со и Се являются кодами, обнаруживающими одну ошибку, и шах(~Со~, ~С1() > ~С~/2. 3.34. Пусть С С В" — - код с расстоянием д+ 1 и о Е В". Положим Сн = (7 Е В": 7 = В Ю В, В Е С). Тогда, если С является (и, д)-кодом и р(Й, В) ~ (д, то С- П Сд = О.
Отсюда вытекает требуемое неравенство. 3.35. Утверждение вытехает из задачи 3.34 и из того, что р(В, )7) < д для любых вершин В, В из (д — Ц-мерной грани куба В". 3.36. Неравенство следует из задачи 3.35 при С = В". 3.38. 2" 3.39. Не существует. Имеем (Я(л~(Й)! = 148 при всех Й Е Выз. Но 148 не является степенью двойки, что противоречит задаче 3.27. 3.41.
Пусть в некотором зквидистантном (и, 24 -Е 1)-коде С содержатся три вершины Н, Д, 7. Без ограничения общности можно считать, что В = О. Тогда (Щ = )Я = 24-~-1, а значит, р(В, 7) четное число, что противоречит условию. 3.42. Разобьем ц координат на блоки величины ф2. Каждому блоку сопоставим набор, в котором единицы стоят в координатах, содержащихся в данном блоке.
Полученное множество наборов образует зквидистантный (и, д)-код мощности (2нЯ. 3.44. Указание. Использовать задачу 3.33, 5). 3.45. 1) Пусть С --. максимальный (и, й, 24)-код. 'Гогда подмножество С10 = СПВ,"л является (н — 1, й — 1, 24)-кодом. Число пар (з, В), где 1 < 1 < ц, )1 Е Сбц не превосходит н. т(и — 1, й — 1, 24). С другой стороны, для каждого набора В Е С существует ровно й таких пар. Отсюда й т(п, й, 24) < н т(п — 1, й — 1, 24). С учетом того, что т(н, й, 24)— целое число, получаем требуемое неравенство.
2) Вытекает (применить индукцию) из задачи 1) с учетом того., что т(п. — й 1- д — 1, д — 1, 24) = 1. 4.2. 1) а), в), г) Нет. 6), д), е) Лз.. 2) а) (000, 111) О А. 6) Вз*'. в), г) Вз. д) А О (0000, 0010, 1101, 1111), е) А О (0000, 0001, 1010, 1110). 3) а) (10Ц. 6) (100). в), г) О. д) (1001). е) (1010). 4.7. 1) а) в) 2. г) 1, д) ж) 4. (ооп) . (10100) „(10001) 2) а) Н=(11). 6) Н" (ШО1' в) Н* ~01000]' г) Н* (ШОО~' 0101010 1001100 шоооо~ 0001111 4.11. 4(С(М)) = 7. 24 Г.
П. Гаврилов, А. А. Сапоженко 370 Ответы, указания, решеннв Глава У111 1.1. Ц (20)з. Билеты неравноценны. Первый билет можно распределить 20-ю способами, второй 19-ю, третий — 18-ю. 2) 20'. 3) С(20,. 3). 1.2. Ц 9!. 2) С(9, 3) С(6, 3). Первую шеренгу можно выбрать С(9, 3) способами, после чего вторую С(6, 3) способами. Пользуясь правилом произведения, получаем результат. 1.3. Ц Каждый из членов перестановки с повторениями можно выбрать независимо от других и способами. С использованием правила произведения получаем, что Р(и, т) = и".
2) Из каждого (и, т)-сочетания без повторений путем перестановок можно получить т) различных (и, т)-перестановок, причем каждая (и, т)- перестановка может быть получена таким способом. Отсюда т! С(и, т) = = Р(и, т). Поскольку (см. пример 3) Р(и, т) = (п)„то С(и, т) = (и),)т! = = (".) 3) Каждому (из т)-сочетанию А с повторениями, составленному из элементов множества С = (ам..., а„), поставим в соотвотствие вектор а(А) длины и + т — 1 из т единиц и и — 1 нулей такой, что число нулей, находюцихся между (1 — Ц-й и 1-й единицами, равно числу элементов а„входяздих в сочетание А (1 = 2, ..., и), а число нулей, стоящих перед первой единицей (после (и — Ц-й единицы), равно числу элементов ае (соответственно элементов а„),входяппзх в сочетание А.
Это соответствие между сочетаниями и векторами взаимно однозначно. С другой стороны, число векторов с и — 1 единицами и т нулями равно С(и + т — 1,и. — Ц, поскольку каждому такому вектору можно взаимно однозначно сопоставить сочетание из и+ т — 1 элементов по и — 1. Отсюда с учетом результата предыдущей задачи получаем, что С(и, т) = ) витт — 11 и — 1 14 Цй" 2)йл.йз... й» 3) ( ). 1.6. Ц 2 ".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
