Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 50
Текст из файла (страница 50)
2.19. Пусть Р = (ры рз, ..., рг) ..- набор вероятностей, а 1„(Р) = = 1п11 р(С, Р), где нижняя грань берется по всем двоичным префиксс ным кодам мощности т. Доказать, что: 1) 1.(Р) >1при т>3, 2) для всякого с > 0 и любого т > 1 существует набор вероятностей Р такой, что 1„(Р) < 1+ с. 2.20. Пусть Цт) = зцр1п11гр(С, Р), где нижняя грань берется по р с всем прсфиксным у-ичным кодам мощности т, а верхняя грань берется по всем наборам вероятностей Р = (ры рз, ..., рг) таким, что р, > О г (г = 1, ...., т), ~ ~р, = 1.
Показать, что; 1) Цт) > (1о8 т) — 1; 2) 1Я < ~1об,т) +1. 9 3. Самокорректируютциеся коды 1. Расстояние Хэммннга, шары, сферы и циклы в и-мерном кубе. Напомним, что расстоянием Хэммингп между вершинами Н и и 13 куба. В" называется число р(а, Д = ~ ~а, —,3,~, равное числу г.=1 координат, в которых векторы а и )3 различаются. Наборы а, )3 из В" называются соседними, если р(а, )3) = 1, и протпиоополоокными, осли р(а, )3) = и.
Неупорядоченная пара соседних вершин называется ребром кубо. Множество В"(а) = 113 Е В"; р(а, 13) = к) называется сферой радиуса й с центром а, а Яьв'(а) = 113 е В": р(а, )3) < й) --. Га Г. П. Гаврилов, А. А. Свпежеике 242 Гл. еВ. Элементы теории кодирования шаром радиуса к с центром а. Положим В" = В„"(О). Множест- во Вьв называется й-м слоем и-мерного куба.
11оследовательность (ао, аы ..., аь) называется цепью в В ', если руст, ы сзь) = 1. Цепь (ао, аы ..., аь) такая, что р(аь, ао) = 1, называется циклом. Цепь (ао, Йы ..., аь) такая, что а, с < а, (ю = 1, ..., Й), называется возрас- тающей цепью. Число ь' называется длиной цепи (ао, аы ..., ая). Цикл С куба Во называется 2д-циклом, если ~СГ1 Влв(а)~ = 2И+ 1 для каждого а Е С. Через В","'"," обозначим множество всех набо- ров (соы аз, ..., а„) таких, что а, = и О = 1, ..., к). Всякое такое множество называется (н — И)-мерной гранью направленно (П, ..., 1ь). 3.1. Показать, что для любых а, В, у из В" выполнены соотно- шения: 1) р(а, У3) = РАЯ, а); 2) РУа, у) < р(а, В) + РУВ, Я; 3) р(а, Й) = 0; 4) р(а.
у) = р(а е с3, у е )3), тле (сз„..., .ав) е (Вй, ..., с3ь) = = (а, В )3„..., сц. Е ~3„); 5) р(а, с3) = )(а 6)3)), где Цаы ..., а„)(! = аз -ь... + аи; 6) РСа, )3) = ОЩ 9 (٠— 20а Г1 Я, где (аы ..., а„) П фы ..., Д„) = (аз Йуу~....., а„всрв). 3.2. 1) Найти число ребер в В". 2) Найти число неупорядоченных пар наборов а, В из В" таких, что р(а, )3) = к. 3.3. Найти число вершин в подмножестве: 1) А = Вс (а), 2) А = Яьв(а); 3) А = Вь'Уа) й В" (у3), где РУо, )3) = г; 4) А = Я"Са) Г1 Я„",(Д), где РСа, )3) = г.
3.4. Пусть а, )3 . вершины куба В", а р(а, 13) = т. Найти число вершин у, удовлетворяющих условию: 1) р(а, у) + РЯ, 13) = руа, )3); 2) р(а, у) + р(В, у) = г; 3) р(а, у) = й, р()3, у) = г; 4) р(а, у) < й, РУ)3, у) > г. 3.5. Показать несовместимость следующих систем соотношений дляа,у3, уизВ" (н>2): 1) Р(а Д)> 3 Р(3 7)> 3 Р(у а)> 3 2) и(а) < иф® у), оф) < и(а Ю у), иЯ < и(а св у3); 3) 'цй~ > Р Со 30., 'цй~ > !~а ьл 5ц, И > ~!а СЭ )3~~, !а Г (дсу у)~ = О. 3.6. Множество А С В' называется полным в В", если лнзбой вектор 3 Е В" однозначно восстанавливается при условии, что для каждого Й Е А известно расстояние р(а,)3).
Полное в В" множест- 6 Х Слмокорректируюглиеся коды 243 во А называется базисным, если для любого вектора а из А множество А~(а) не является полным. 1) Показать, что любая цепь Йо, а1, ..., ао 1 в Во образует базисное множество. 2) Показать, что множества В" и В,", 1 являются полными в В" при п > 2. Указать такое п > 2, что В" не является базисным. 3) При каких и и й множество В,'" не является полным в В" 2 4) Доказатго что всякое базисное множество А С В" удовлетво- ряст уиювию п!о82'(и — Ц < ~А~ < и,. 5) Доказать, что никакая грань размерности п — 2 не является полным в В" множеством.
6) Показать, что число 2?г„базисных множеств в В" удовлетворяет неравенствам 2((п — 1)!) < г?г„< ( ). ?2" 1 3.1. Пусть 1р — взаимно однозначное отображение В" на себя. Говорят, что 1р сохраняет рлсстояние, если р(а,?2) = Р(1р(а, О2(гз)) для всех а,?д из В". Доказать, что отображение сохраняет расстояние тогда и только тогда, когда оно может быть получено: а) с помощью некоторой перестановки координат во всех наборах из В"; б) заменой 0 на 1 и 1 на 0 в некоторых координатах всех векторов. 3.8. Отображение оо множества В" в себя называется монотонным, если из и(а) < ггпу) вытекает, что о(1р(Н)) < о(1р(?1)).
Найти число монотонных отображений куба из В". 3.9*. Пусть 1(А) число ребер и-мерного куба, соединяющих пары вершин подмножества А С В", а 1о(гп) = шах ~(А)~. А С В ",. ( А ! = ю 1 1) Доказать, что 1„(т) < — т 1оя2 т. 2 2) Доказать, что оценка и. 1) достигается при т = 2". 3) Пусть А С В", ~А( > 2" '. Доказать, что 1(А) > п. 4) Доказать, что 1(А) < 11~А~ — ш1п((А!., 2' — )АД. 3.10. Пусть Р„(п) семейство подмножеств А С В" таких, что р(а, ф < 2г для любых а,?д из А.
Пусть 22„(и) = шах ~А~. АЕЕ Ггг1 1) Доказатго что максимум А по всем А Е г'„(п) не меньше ~~1 ( ). 0<г<г 2) Для нечетного и и 1 = (и — 1)/2 привести пример множества А Е Ег(п), не являющегося шаром радиуса т ни в одном из подкубов куба В" и такого, что (А! = ~ ~( ). 6<1< 3.11. Доказать по индукции, что наборы из В" можно расположить в цикл ао, а1,, аз — 1. 16* 244 Гл. 'гП. Элемвюаы творим кодирования 3.12. Лвоичный вектор (оо, оы ..., оз з) называется и-универсальным, если для всякого (Д, ..., Д,) из Во существует такой номер Й, что В,, = оьт, (1 = 1,..., и), где Й б1 = Й+1(шод2"). Например, вектор (0011) является 2-универсальным. 1) Выяснить, является ли и-универсальным вектор Н~: а) В4 = (0110); б) ггв = (0101); в) Вв = (0001 1101); г) о' = (0001 1010): д) о = (0100 0111); с) Н = (0100 1110); ж) Н'в = (0000111100101101); з) Н1в = (1100101101000011). 2) Локазать, что для всякого и существует и-универсальный вектор.
3.13. 1) Пусть 1(п) — — максимальная длина 2-цикла в В". Найти 1(2), ЦЗ), Ц4). 2) Локазатгь что для всякого 2-цикла С С В" и любой грани С размерности 4 выполнено ~С й С~ < 8. 3) Показать, что максимальная длина 2-цикла в Ва не превосходит 2" ' (и, > 3). 3.14*. Пустыр(п)~(~р'(и)) --- максимальная мощность множества А С В" такого, что уНПЯ = 1 (соответственно уайЯ = 1) для любых двух различных векторов из А.
Показать, что: 1) ~р(п) = и: 2) ьо'(п) = 2" 3.15*. Локазать, что куб В" можно представить в виде объединения попарно непересекающихся возрастающих цепей, обладающих следующими свойствами: Ц число цепей длины и, — 2Й равно ( Й) — ( Й 1), Й = 1, ..., [и/2); при этом минимальный набор каждой цепи длины и — 2Й имеет вес Й, а максимальный — вес и — Й; 2) если оо а,ты Н,тз . три последовательные вершины цепи, имеющей длину и — 2Й, то вер|пина Д такая, что Н, < В < Ввез, В ф о, ы принадлежит цепи длины п — 2Й вЂ” 2. 3.16*. Пусть А С В" такое множество наборов, что не существует наборов Л, Д, 7 из А, для которых Н П В = 0 и о 0В = у.
Пусть аь = ~А П В~",~. Показать, что а~„. ь„, аа а, + — + — ' < 2. Ь: ) (:) (.") 2. Коды, обнаруживающие и исправляющие ошибки. Подмножество С С Во называется (двоичным) кодом с расстоянием д или, короче,. (и, а)-кодом, если шш р(Н,,З) = д. Число д называа,вес ется кодовым расстоянием множества С. Максимальная мощность (и, Щ-кода будет обозначаться через т(п, д). Если мощность (и, д)- кода равна т(гц а), то он называется максимальным. Плотно упакованным кодом называется (и, 2д+ 1)-код С, удовлетворяющий сле- З 3. Самокорректируюыивсн коды 245 дующему условию: для всякого й Е В" существует )3 Е С такое, что р(а,,9) < д. Множество С С В" называется зквидистантным кодом, если величина р(Й, )3) постоянна для любой пары наборов П, )3 из С.
Множество С С В" называется равновесным кодом, если существует целое число й (О < к < п), называемое весом кода, такое, что С С В". Положим т(п, д, к) = шах ~С~, где максимум берется по всем (и., д)-кодам веса Й. Подмножества С С В" могут рассматриваться как множества двоичных слов, предназначенных для передачи по каналу связи, в котором могут происходить искажения передаваемых слов. Элементы множества С называются при этом кодовыми словами. Передача слова по каналу связи рассматривается здесь как преобразование, не меняющео длины передаваемого слова и состоящее в замене некоторых букв на противоположные, т.е. О на 1, а 1 на О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
