Для кодирования некоторой последовательности. Однозначное декодирование обеспечивается

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

Код должен удовлетворять свойству однозначного декодирования.

2 Дан фрагмент таблицы истинности выражения F.

Какое выражение соответствует F?

3 Для груп­по­вых опе­ра­ций с фай­ла­ми ис­поль­зу­ют­ся маски имен фай­лов. Маска пред­став­ля­ет собой по­сле­до­ва­тель­ность букв, цифр и про­чих до­пу­сти­мых в име­нах фай­лов сим­во­лов, в ко­то­рых также могут встре­чать­ся сле­ду­ю­щие сим­во­лы:

Сим­вол «?» (во­про­си­тель­ный знак) озна­ча­ет ровно один про­из­воль­ный сим­вол.

Сим­вол «*» (звез­доч­ка) озна­ча­ет любую по­сле­до­ва­тель­ность сим­во­лов про­из­воль­ной длины, в том числе «*» может за­да­вать и пу­стую по­сле­до­ва­тель­ность.

В ка­та­ло­ге на­хо­дит­ся 6 фай­лов:

Опре­де­ли­те, по какой из масок из них будет ото­бра­на ука­зан­ная груп­па фай­лов:

В фрагменте базы данных представлены сведения о родственных отношениях. Определите на основании приведенных данных, фамилию и инициалы внучки Симоновой Р.К.

1) Капица З.В.

2) Крюк А.М.

3) Крюк Т.Р.

4) Тирас Г.М.

Ответами к заданиям 4–23 являются число, последовательность букв или цифр, которые следует записать в бланк ответов № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

4 Сколько единиц в двоичной записи числа 127?

5 Между населенными пунктами A,B,C,D,E,F построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

6 У исполнителя Утроитель две команды, которым присвоены номера:

2. Умножь на 3

Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.

7 Дан Фрагмент электронной таблицы

Какое целое число должно быть записано в ячейке B1, чтобы построенная после выполнения вычислений диаграмма по назначениям диапазона ячеек A2:С2 соответствовала рисунку? Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.

8 Определите, что будет напечатано в результате работы следующего фрагмента программы:

9 Документ объёмом 5 Мбайт можно передать с одного компьютера на другой двумя способами:

А. Сжать архиватором, передать архив по каналу связи, распаковать.

Б. Передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если

Средняя скорость передачи данных по каналу связи составляет 2 20 бит в секунду;

Объём сжатого архиватором документа равен 50% исходного;

Время, требуемое на сжатие документа,-20 секунд, на распаковку-2 секунды?

В ответе напишите букву А если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.

10 Все 5-бук­вен­ные слова, со­став­лен­ные из букв А, К, Р, У, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке. Вот на­ча­ло спис­ка:

За­пи­ши­те слово, ко­то­рое стоит на 350-м месте от на­ча­ла спис­ка.

11. Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?

12 В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. По заданным IP-адресу узла сети и маске определите адрес сети:

IP-адрес: 217.19.128.131 Маска: 255.255.192.0

При записи ответа выберите из приведенных в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы. Точки писать не нужно.

Пример. Пусть искомый IP-адрес 192.168.128.0, и дана таблица

В этом случае правильный ответ будет записан в виде: HBAF

13 При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 11 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы И, К, Л, М, Н. Каж­дый такой па­роль в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 60 па­ро­лей.

14 Ис­пол­ни­тель Робот ходит по клет­кам бес­ко­неч­ной вер­ти­каль­ной клет­ча­той доски, пе­ре­хо­дя по одной из ко­манд вверх, вниз, впра­во, влево в со­сед­нюю клет­ку в ука­зан­ном на­прав­ле­нии. Робот вы­пол­нил сле­ду­ю­щую про­грам­му:

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

15 На рисунке- схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К

16 Ука­жи­те через за­пя­тую в по­ряд­ке воз­рас­та­ния все ос­но­ва­ния си­стем счис­ле­ния, в ко­то­рых за­пись числа 61 окан­чи­ва­ет­ся на 15.

17 В языке за­про­сов по­ис­ко­во­го сер­ве­ра для обо­зна­че­ния ло­ги­че­ской опе­ра­ции «ИЛИ» ис­поль­зу­ет­ся сим­вол «|», а для ло­ги­че­ской опе­ра­ции «И» – сим­вол «&».

В таб­ли­це при­ве­де­ны за­про­сы и ко­ли­че­ство най­ден­ных по ним стра­ниц не­ко­то­ро­го сег­мен­та сети Ин­тер­нет.

18 На чис­ло­вой пря­мой даны два от­рез­ка: P = и Q = . Вы­бе­ри­те такой от­ре­зок A, что фор­му­ла

((x ∈ А) → (x ∈ P)) ∨ (x ∈ Q)

тож­де­ствен­но ис­тин­на, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

19 В про­грам­ме опи­сан од­но­мер­ный це­ло­чис­лен­ный мас­сив с ин­дек­са­ми от 0 до 10 и це­ло­чис­лен­ная пе­ре­мен­ная i. В при­ве­ден­ном ниже фраг­мен­те про­грам­мы мас­сив сна­ча­ла за­пол­ня­ет­ся, а потом из­ме­ня­ет­ся:

for i:=0 to 10 do A[i]:=i;

for i:=0 to 9 do begin

Чему будут равны эле­мен­ты этого мас­си­ва?

20 Ниже на четырёх язы­ках за­пи­сан ал­го­ритм. По­лу­чив на вход число , этот ал­го­ритм пе­ча­та­ет два числа: и . Ука­жи­те наи­боль­шее из таких чисел , при вводе ко­то­рых ал­го­ритм пе­ча­та­ет сна­ча­ла 3, а потом 3. До­пус­ка­ет­ся диа­па­зон зна­че­ний для ве­ли­чин це­ло­го типа: от −2 31 до 2 31 - 1.

21 Опре­де­ли­те, какое число будет на­пе­ча­та­но в ре­зуль­та­те вы­пол­не­ния сле­ду­ю­ще­го ал­го­рит­ма (для Ва­ше­го удоб­ства ал­го­ритм пред­став­лен на четырёх язы­ках).

22 У ис­пол­ни­те­ля Удво­и­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра.

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?

Примечание.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ: 19 ___________________________.

Решение:
1) Кодируем:
А 0
Б 10
В 110
Г 1110
Д 1111
Е 10000
итого:19 Ответ: 19

1. Еще одна задача

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

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

1) 00; 2) 001; 3) 10; 4) 101

Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.

1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).

2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).

3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).

4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.

Правильный ответ : 4

Еще одна Задача 2 .

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00 2) 01 3) 11 4) 010

Решение . Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным.

1) 00 – не подходит (является началом кодового слова 000 для буквы Б);

2) 01 – не подходит (является началом кодового слова 011 для буквы Г);

3) 11– не подходит (является продолжением(!) кодового слова 1 для буквы А);

4) 010 – подходит! (не является ничьим началом и никто не является его началом).

Ответ : 4.

Замечание 1. Условие Фано является достаточным условием того, что код допускает однозначное декодирование, но не является необходимым. То есть код может допускать однозначное декодирование, но не удовлетворять условию Фано. Простейший пример таких кодов – т.н. постфиксные коды. Это такие коды, в которых никакое кодовое слово не является концом другого кодового слова. Для этих кодов расшифровка производится так же, как и для префиксных кодов, но двигаясь справа налево.

Замечание 2. В рассмотренной задаче А достаточно найти один вариант, удовлетворяющий требованиям задачи. НЕ ТРЕБУЕТСЯ доказывать, что при остальных вариантах код не будет допускать однозначного декодирования. Однако, в данном случае это сделать несложно. А именно:

1) Код Д: 00. Тогда 000000 допускает две расшифровки: ББ и ДДД.

2) Код Д: 01. Тогда 011 допускает две расшифровки: Г и ДА.

2) Код Д: 11. Тогда 11 допускает две расшифровки: АА и Д.

№	Наименование	Время	Стоимость
1	Дистанционный репетитор по информатике по Skype	1 час	от 600 руб.

Со студентами провожу занятия по высшей математике , математическому анализу , теории вероятности и математической статистике, линейной алгебре . Индивидуальные занятия в Москве в офисе на

| 21-28

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

Пояснение.

Двоичные коды 00 или 01 не подходят, поскольку А и В - 000 и 011.

010 и 001 подойдут, так как не конфликтуют ни с каким другим уже имеющимся кодом, из них 001 меньше.

Ответ: 001.

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

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

Пояснение.

Код не может начинаться с 1, так как Б − 1.

0 не подойдёт, так как А и В начинаются с 0.

00 же не включает в себя никакой из кодов и также не является подстрокой какого-либо кода, поэтому подойдёт.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.

Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) это невозможно

2) для буквы В – 000

3) для буквы Б – 0

4) для буквы Г – 11

Пояснение.

Вариант 3 не подходит, потому что 0 является началом кода 0001.

Вариант 4 не подходит, потому что код 1 является началом кода 111.

Ответ: 2

Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Ва­ри­ант 1.

Екатерина Пронина (Москва) 15.12.2014 14:51

Здравствуйте! Решая задачу по вашему принципу, я столкнулась с проблемой. Приведу пример:

А - 1; Б - 000; В - 0101; Г - 001; Д - 011.

А) для буквы В - 010;

Б) это невозможно;

В) для буквы В - 101;

Г) для буквы Г - 01.

По условию Фано подходят варианты А) и Б).

Но, анализируя ответ В), получаем неоднозначность раскодирования: 1011 - (АД или ВА). По вашему условие Фано является достаточным для решения подобных задач. Как быть здесь?

Сергей Никифоров

В вашем примере верный ответ - А. Если для буквы В выбрать код 101, то 1 будет являться началом кода для буквы В, нарушится условие Фано.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–011, Б–000, В–11, Г–001, Д–10. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) это невозможно

2) для буквы А – 01

3) для буквы Б – 00

4) для буквы Г – 00

Пояснение.

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

Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

Вариант 3 не подходит, потому что 00 является началом кода 001.

Вариант 4 не подходит, потому что код 00 является началом кода 000.

Вариант 2 подходит, так как не нарушает условия Фано.

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

Ответ: 2

Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Ва­ри­ант 2.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Д – 11

2) это невозможно

3) для буквы Г – 10

4) для буквы Д – 10

Пояснение.

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

Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

Вариант 3 не подходит, потому что 10 является началом кода 100.

Вариант 4 не подходит, потому что код 10 является началом кода 100 и 101.

Вариант 1 подходит, так как не нарушает условия Фано.

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

Ответ: 1

Источник: Демонстрационная версия ЕГЭ-2013 по информатике.

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

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Пояснение.

Нельзя использовать кодовые слова, которые начинаются с 0 или с 10. 11 также не можем использовать, поскольку тогда мы больше не сможем взять никакое другое кодовое слово, а нам их нужно пять. Поэтому берём трёхзначное 110. 111 опять же не можем использовать, потому что понадобиться ещё одно кодовое слово, а вместе с этим не останется больше свободных. Теперь осталось взять всего два слова и это будут 1110 и 1111. Итого имеем 0, 10, 110, 1110 и 1111 - 14 символов.

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

декодировать полученную двоичную последовательность. Вот этот код: А – 011, Б – 000, В – 11, Г – 001, Д – 10. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Для кодирования

некоторой последовательности, состоящей
из букв А, Б, В, Г и Д, используется
неравномерный двоичный код, позволяющий
однозначно декодировать полученную
двоичную последовательность. Вот этот
код: А–11, Б–10, В–011, Г–000, Д–001. Можно
ли сократить для одной из букв длину
кодового слова так, чтобы код по-прежнему
можно было декодировать однозначно?
Коды остальных букв меняться не должны.
Выберите правильный вариант ответа. 1) для буквы Г – 00 2) это невозможно

3) для буквы В – 01 4) для буквы Б – 1

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

однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. 1) 00 2) 01 3)11 4) 010

помогите плз! 3) Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного

шахматного поля?

4) Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?

5) Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?

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

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

8) За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?

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

10) В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?

Для передачи по каналу связи сообщения, состоящего только из букв А, Б,

В, Г, решили использовать неравномерный по длине код: A – 1, Б – 01, В –

001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и

Допускалось однозначное разбиение кодированного сообщения на буквы?