Для кодирования сообщений решено использовать последовательности

• отношение количества вариантов (или чисел) N к количеству информации которую несет в себе один из вариантов I: N=2 I
• полный информационный объем сообщения V равен количество символов в сообщении K умноженное на количество информации на каждый символ I: V=K*I
• Формула Шеннона для равновероятных событий: I=log₂N
• если алфавит имеет мощность ( количество символов в этом алфавите) М, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно K=M N ; для двоичного кодирования (мощность алфавита M –2 символа) получаем известную формулу:K=2 N

N бит	1	2	3	4	5	6	7	8	9	10
K вариантов	2	4	8	16	32	64	128	256	512	1024

Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло,чтобы с его помощью можно было передать 18 различных сигналов?

Решение задачи №1.

В данной задаче мощность алфавита равна трем («включено», «выключено» или «мигает»). Количество необходимых сигналов 18, следовательно 18=3 N , N=3.

Ответ: Количество лампочек равно 3.

Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

1) 80 бит 2) 70 байт 3) 80 байт 4) 560 байт

Решение задачи №2.

Определим информационный объем одного измерения: количество возможных вариантов равно 100 (т.к. результатом одного измерения является целое число от 0 до100 процентов), следовательно, информационный объем одного варианта измерения находится по формуле: 100=2 I , I = 7 бит.

Так как станция сделала 80 измерений, следовательно, информационный объем результатов наблюдений равен 7*80=560 бит, но такого ответа нет, значит переведем биты в байты: 560/8=70 байт.

Ответ: Информационный объем результатов наблюдений равен 70 байтам.

Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?

1) 64 2) 50 3) 32 4)20

Решение задачи №3.

Мощность алфавита равна 2. Длина слова равна 5. Количество различных последовательностей К=2 5 =32.

Ответ: Количество различных последовательностей 32.

В корзине лежат 8 черных шаров и 24 белых.Сколько бит информации несет сообщение о том, что достали черный шар?

1) 2 бита 2) 4 бита 3) 8 бит 4) 24бита

Решение задачи №4.

В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?

1) 4 2) 8 3) 16 4)32

Решение задачи №5.

Данная задача похожа на задачу №4, только нам надо определить количество карандашей по известному количеству информации который несет один карандаш.
Определим количество возможных событий (вариантов получения белого карандаша) по формуле Шеннона: log 2 N=4, следовательно, N=16.
Количество возможных событий получения белого карандаша равно 16, следовательно, количество белых карандашей составляет 1/16 всех карандашей. Всего карандашей 64, следовательно белых карандашей 64/16=4.
Ответ: 4 белых карандаша.

В корзине лежат черные и белые шары. Среди них18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?

1) 18 2) 24 3) 36 4)48

Решение задачи №6

Найдем по формуле Шеннона вероятность получения белого шара: log₂N=2, N=4, следовательно, вероятность получения белого шара равна 1/4 (25%), а вероятность получения черного шара соответственно 3/4(75%). Если 75% всех шариков черные, их количество 18, тогда 25% всех шариков белые, их количество (18*25)/75=6.

Осталось найти количество всех шариков в корзине 18+6=24.

Ответ: 24 шарика.

В некоторой стране автомобильный номер длиной 5 символов составляется из заглавных букв (всего используется 30 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 50 автомобильных номеров.

1) 100 байт 2) 150 байт 3) 200 байт 4)250 байт

Решение задачи №7.

Количество символов используемых для кодирования номера составляет: 30 букв + 10 цифр = 40 символов. Количество информации несущий один символ равен 6 бит (2 I =40, но количество информации не может быть дробным числом, поэтому берем ближайшую степень двойки большую количества символов 2 6 =64).

Мы нашли количество информации заложенное в каждом символе, количество символов в номере равно 5, следовательно 5*6=30 бит. Каждый номер равен 30 битам информации, но по условию задачи каждый номер кодируется одинаковым и минимально возможным количеством байт, следовательно нам необходимо узнать сколько байт в 30 битах. Если разделить 30 на 8 получится дробное число, а нам необходимо найти целое количество байт на каждый номер, поэтому находим ближайший множитель 8-ки который превысит количество бит, это 4 (8*4=32). Каждый номер кодируется 4 байтами.

Для хранения 50 автомобильных номеров потребуется: 4*50=200 байт.

Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 11 символов. В пароле можно использовать десятичные цифры и 12 различных символов местного алфавита,причем все буквы используются в двух начертаниях – строчные и прописные. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый пароль – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 60 паролей.

1) 720 байт 2) 660 байт 3) 540 байт 4)600 байт

Решение задачи №9.

Количество символов используемых для кодирования пароля составляет: 10 цифр + 12 строчных букв + 12 прописных букв = 34 символа. Количество информации несущий один символ равен 6 бит (2 I =34, но количество информации не может быть дробным числом, поэтому берем ближайшую степень двойки большую количества символов 2 6 =64).

Мы нашли количество информации заложенное в каждом символе, количество символов в пароле равно 11, следовательно 11*6=66 бит. Каждый пароль равен 66 битам информации, но по условию задачи каждый пароль кодируется одинаковым и минимально возможным количеством байт, следовательно нам необходимо узнать сколько байт в 66 битах. Если разделить 66 на 8 получится дробное число, а нам необходимо найти целое количество байт на каждый пароль, поэтому находим ближайший множитель 8-ки который превысит количество бит, это 9 (8*9=72). Каждый номер кодируется 9 байтами.

Для хранения 60 паролей потребуется: 9*60=540 байт.

Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-». Сколько различных сообщений можно закодировать, используя в каждом из них не менее 2-х и не более 6 знаков?

Решение задачи №10

Мощность алфавита равна 2 (знаки «+» и «-»). Количество различных сообщений для слов из 2-ух букв равно 2 2 =4, для 3-ех букв 2 3 =8, для 4-ех 2 4 =16, для 5-и 2 5 =32, для 6-и 2 6 =64.

Нам осталось только просуммировать значения различных слов: 4+8+16+32+64=124

Ответ: можно закодировать 124 различных сообщений.

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.

Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.

Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

Код называется однозначно декодируемым, если любое сообщение, составленное из кодовых слов, можно декодировать единственным способом.

Равномерное кодирование всегда однозначно декодируемо.

Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:

Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.

Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Кодирование в различных системах счисления

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление

чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.

Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.

010 010 001 110 010 — 22162.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.

За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:

1101 0011 1010 0110₂ = D3A6₁₆

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Расшифровка сообщений

Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв – из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:

Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.

Значит, будем перебирать варианты, пока не получим подходящее слово :

1) 100 011 01 10 110

Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.

Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.

Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.

При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.

Таким об­ра­зом, ответ: АВхБ.

Однозначное кодирование

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.

Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.

1) ко­до­вое слово для буквы Е можно со­кра­тить до 01

2) ко­до­вое слово для буквы К можно со­кра­тить до 1

3) ко­до­вое слово для буквы Н можно со­кра­тить до 10

4) это не­воз­мож­но

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ты нашел то, что искал? Поделись с друзьями!

Звоните нам: 8 (800) 775-06-82 (бесплатный звонок по России) +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.

Обучающее видео
БЕСПЛАТНО

Техническая поддержка:
help@ege-study.ru (круглосуточно)

Полный онлайн-курс подготовки к ЕГЭ по математике. Структурировано. Четко. Без воды. Сдай ЕГЭ на 100 баллов!

Для нормального функционирования и Вашего удобства, сайт использует файлы cookies. Это совершенно обычная практика.Продолжая использовать портал, Вы соглашаетесь с нашей Политикой конфиденциальности.

Все поля обязательны для заполнения

Премиум

Вся часть 2 на ЕГЭ по математике, от задачи 13 до задачи 19. То, о чем не рассказывают даже ваши репетиторы. Все приемы решения задач части 2. Оформление задач на экзамене. Десятки реальных задач ЕГЭ, от простых до самых сложных.

Видеокурс «Премиум» состоит из 7 курсов для освоения части 2 ЕГЭ по математике (задачи 13-19). Длительность каждого курса – от 3,5 до 4,5 часов.

1. Уравнения (задача 13)
2. Стереометрия (задача 14)
3. Неравенства (задача 15)
4. Геометрия (задача 16)
5. Финансовая математика (задача 17)
6. Параметры (задача 18)
7. Нестандартная задача на числа и их свойства (задача 19).

Здесь то, чего нет в учебниках. Чего вам не расскажут в школе. Приемы, методы и секреты решения задач части 2.

Каждая тема разобрана с нуля. Десятки специально подобранных задач, каждая из которых помогает понять «подводные камни» и хитрости решения. Автор видеокурса Премиум – репетитор-профессионал Анна Малкова.

Получи пятерку

Видеокурс «Получи пятерку» включает все темы, необходимые для успешной сдачи ЕГЭ по математике на 60-65 баллов. Полностью все задачи 1-13 Профильного ЕГЭ по математике. Подходит также для сдачи Базового ЕГЭ по математике. Если вы хотите сдать ЕГЭ на 90-100 баллов, вам надо решать часть 1 за 30 минут и без ошибок!

Курс подготовки к ЕГЭ для 10-11 класса, а также для преподавателей. Все необходимое, чтобы решить часть 1 ЕГЭ по математике (первые 12 задач) и задачу 13 (тригонометрия). А это более 70 баллов на ЕГЭ, и без них не обойтись ни стобалльнику, ни гуманитарию.

Вся необходимая теория. Быстрые способы решения, ловушки и секреты ЕГЭ. Разобраны все актуальные задания части 1 из Банка заданий ФИПИ. Курс полностью соответствует требованиям ЕГЭ-2018.

Курс содержит 5 больших тем, по 2,5 часа каждая. Каждая тема дается с нуля, просто и понятно.

Сотни заданий ЕГЭ. Текстовые задачи и теория вероятностей. Простые и легко запоминаемые алгоритмы решения задач. Геометрия. Теория, справочный материал, разбор всех типов заданий ЕГЭ. Стереометрия. Хитрые приемы решения, полезные шпаргалки, развитие пространственного воображения. Тригонометрия с нуля – до задачи 13. Понимание вместо зубрежки. Наглядное объяснение сложных понятий. Алгебра. Корни, степени и логарифмы, функция и производная. База для решения сложных задач 2 части ЕГЭ.

Сразу после оплаты вы получите ссылки на скачивание видеокурсов и уникальные ключи к ним.

Задачи комплекта «Математические тренинги – 2019» непростые. В каждой – интересные хитрости, «подводные камни», полезные секреты.

Варианты составлены так, чтобы охватить все возможные сложные задачи, как первой, так и второй части ЕГЭ по математике.

Как пользоваться?

1. Не надо сразу просматривать задачи (и решения) всех вариантов. Такое читерство вам только помешает. Берите по одному! Задачи решайте по однойи старайтесь довести до ответа.
2. Если почти ничего не получилось – начинать надо не с решения вариантов, а с изучения математики. Вам помогут книга для подготовки к ЕГЭи Годовой Онлайн-курс.
3. Если вы правильно решили из первого варианта Маттренингов 5-7 задач – значит, знаний не хватает. Смотри пункт 1: Книгаи Годовой Онлайн-курс!
4. Обязательно разберите правильные решения. Посмотрите видеоразбор – в нем тоже много полезного.
5. Можно решать самостоятельно или вместе с друзьями. Или всем классом. А потом смотреть видеоразбор варианта.

Стоимость комплекта «Математические тренинги – 2019» – всего 1100 рублей. За 5 вариантов с решениями и видеоразбором каждого.

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Кодирование информации

• Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
• Кодирование бывает равномерным и неравномерным:
• при равномерном кодировании всем символам соответствуют коды одинаковой длины;
• при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Для решения задач с декодированием, необходимо знать условие Фано:

если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:

условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Решение 5 заданий ЕГЭ

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

• Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
• Теперь закодируем последовательность букв из слова ВОДОПАД :
• Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

Рассмотрим еще разбор 5 задания ЕГЭ:

a	b	c	d	e
000	110	01	001	10

Какой набор букв закодирован двоичной строкой 1100000100110 ?

• Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:

Результат: b a c d e.

✎ 2 вариант решения:

Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.

Сделаем дерево, согласно кодам в таблице:

Сопоставим закодированное сообщение с кодами в дереве:

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 5 задание:

Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110 .

• Рассмотрим пример из условия задачи:
• Где сами цифры исходного числа (выделим их красным цветом):

Ответ: 6 5 4 3

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Для кодирования некоторой последовательности, состоящей из букв К , Л , М , Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К — кодовое слово 10 .

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

• Найдём самые короткие возможные кодовые слова для всех букв.
• Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а — это Н).
• Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
• Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
• Суммарная длина всех четырёх кодовых слов равна:

✎ 2 вариант решения:

Будем использовать дерево. Влево откладываем , вправо — 1:

Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:

Суммарная длина всех четырёх кодовых слов равна:

Ответ: 9

По каналу связи передаются сообщения, содержащие только 4 буквы: А , Б , В , Г ; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:

Укажите кратчайшее кодовое слово для буквы Г , при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

• Наименьшие коды могли бы выглядеть, как и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
• Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00

Для кодирования некоторой последовательности, состоящей из букв А , Б , В , Г и Д , решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:

Укажите, каким кодовым словом должна быть закодирована буква Д . Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

• Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

Перепишем сверху вниз получившееся кодовое слово для Д: 101

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А , Б , Е , И , К , Л , Р , С , Т , У . Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

• Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.

При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100 :

Результат: 1100

Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А , Б , В , Г ; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

• Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
• Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).

Дерево по условию Фано (однозначно декодируется с начала):

Получившееся числовое значение кодового слова для буквы Г — 01.

Дерево по обратному условию Фано (однозначно декодируется с конца):

Получившееся числовое значение кодового слова для буквы Г — 00.

После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00 .

Результат: 00

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

• С помощью дерева отобразим известные коды для букв:

В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:

Расположим буквы в порядке их следования в слове и подставим их кодовые слова:

Посчитаем количество цифр в итоговом коде и получим 20 .

Результат: 20

Смотрите виде решения задания: