Готовимся к ЕГЭ

Официальные документы по ЕГЭ (посмотреть)
Демоверсии и КИМы прошлых лет (посмотреть)
Областной Центр мониторинга качества образования (посмотреть)

Распоряжение об установлении минимального количества баллов (посмотреть)
Справка о планируемых изменениях КИМ (посмотреть)


_________________________________________________________________________________
Задание 1

_________________________________________________________________________________
Задание 5

Пример 1 (№ 13535)
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Решение:  Будем строить граф, причем слева будут нули, а справа единицы


Ответ : 1000



Пример 2 (№ 1102)

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

Решение: 
Сначала следует представить данные в условии числа в двоичном коде для этого воспользуемся таблицей триад и тетрад:

№п/п





0
0
0
0
0
0
1
1
0
0
0
1
2
2
0
0
1
0
3
3
0
0
1
1
4
4
0
1
0
0
5
5
0
1
0
1
6
6
0
1
1
0
7
7
0
1
1
1
8
8
1
0
0
0
9
9
1
0
0
1
10
A
1
0
1
0
11
B
1
0
1
1
12
C
1
1
0
0
13
D
1
1
0
1
14
E
1
1
1
0
15
F
1
1
1
1
Красным цветом на соответствие букв и цифр
Д
Х
Р
О
В
0
1
2
3
4
00
01
10
11
100
ХОРОВОД — 011110111001100. Теперь разобьём это представление по три цифры справа налево и переведём полученный набор чисел в десятичный код, затем в восьмеричный (восьмеричное предствление совпадает с десятичным при разбиении тройками) 011 110 111 001 100 — 3 6 7 1 4
Ответ: 36714

Пример 3 (№ 7441)
Для кодирования некоторой последовательности, состоящей из букв А, Б, В,Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:
А — 0; Б — 100; В — 1010; Г — 111; Д — 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В — 101
2) это невозможно
3) для буквы В — 010
4) для буквы Б — 10

Решение:
Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Первый вариант ответа подходит. Третий вариант не подходит, поскольку код буквы А является началом кода буквы В. Четвёртый вариант ответа не подходит, т. к. в таком случае код буквы Б является началом кода буквы В.
Ответ: Правильный ответ указан под номером: 1.

Пример 4 (№ 15100)

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

Буква
Кодовое слово
А
11
Б
0010
Г
100
Е
0011

Буква
Кодовое слово
И
М
01
Р
000
Т

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

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение: Ветки будет две одну начнем с нуля другую с единицы

Ответ: 1010


Пример 5 (№ 3682)
Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Закодируйте таким образом изображение и запишите результат в восьмеричной системе счисления.


Решение: 
Код первой строки: 10101.
Код второй строки: 11000.
Код третьей строки: 01010.
Запишем коды по порядку в одну строку: 101011100001010. Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел в десятичный код (восьмеричное предствление совпадает с десятичным при разбиении тройками).
101 011 100 001 010 — 5 3 4 1 2

Ответ: 53412