Подготовка к ЕГЭ 2020

букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды

двух букв: 10, 111.
Коды остальных пяти букв имеют одинаковую длину.
Какова минимальная суммарная длина всех семи кодовых слов?

A – 10
Б – 111
В – ?
Г – ?
Д – ?
Е – ?
Ж – ?

Длина = 2 + 3 + 5*3 = 5 + 15 = 20

из букв А, Б, В, Г, Д, Е, решили использовать

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

Решение:
Для нахождения кодовых слов будем использовать двоичное дерево.
Буквы будем размещать на конечных узлах дерева — листьях.
Условие Фано выполняется, поскольку при проходе от корня дерева к букве в середине пути не встречается других букв.
Суммарная длина кодовых слов для букв В, Г, Д, Е = 4 + 4 + 4 + 4 = 16.
Ответ:  16

из букв К, Л, М, Н, П, Р, ре­ши­ли ис­поль­зо­вать

не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв К, Л, М, Н ис­поль­зо­ва­ли со­от­вет­ствен­но ко­до­вые слова 000, 001, 010, 11. Для двух остав­ших­ся букв — П и Р — длины ко­до­вых слов не­из­вест­ны. Ука­жи­те крат­чай­шее воз­мож­ное ко­до­вое слово для буквы П, при ко­то­ром код будет удо­вле­тво­рять усло­вию Фано. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

виде файла без использования сжатия данных. Получившийся файл был передан

в город А по каналу связи за 75 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 3 раза выше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б за 90 секунд. Во сколько раз скорость пропускная способность канала в город Б больше пропускной способности канала в город А?

Б  А: 75 сек
Б  А: 90 сек
I1=v1*t1 = v1*75
I2= v2*t2 = v2*90
I2=I1*2*3 – после оцифровки
v2=I2/t2 = I1*2*3/90 = I1*6/90 = I1/15 =
=v1*75/15 = v1*5
v2=5*v1

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

пикселей записываются в файл один за другим без промежутков. Объём файла с изображением не может превышать 260 Кбайт без учёта размера заголовка файла. Какое максимальное количество цветов можно использовать в палитре?

Объём растрового графического файла
I = K· i
N = 2i
К – разрешение монитора (количество графических точек)
i – глубина цвета (бит)
N – количество цветов в палитре
I – объём изображения (бит, байт, Кбайт, Мбайт, Гбайт)

РЕШЕНИЕ:
Глубина цвета:



i  4 бит
Количество цветов в палитре:
N= 2i = 24 = 16

Ответ: 16

пикселей отведено 40 Кбайт памяти без учёта размера заголовка файла.

Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?

А, Р, Т, записаны в алфавитном порядке. Вот начало списка:

АААА
АААМ
АААР
АААТ
...
Какое количество слов находятся между словами МАРТ и РАМТ (включая эти слова)?

0
1
2
3

МАРТ  10234 = 1*43 + 2*41 +3*40 = 64 + 8 + 3 = 75 + 1 = 76
(+1 так как нумерация начинается с 0)

РАМТ  20134 = 2*43 + 1*41 +3*40 = 128 + 4 + 3 = 135 + 1 = 136

Количество слов = 136 – 76 = 60 + 1 = 61

4-я система счисления

только буквы З, И, М, А, причём в каждом слове

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

Решение:
Буква И может стоять на одном из пяти мест:
И****, *И***, **И**, ***И* и ****И, где * обозначает любой из оставшихся двух символов (З, М)
В каждом случае в остальных четырёх позициях может быть любая из двух букв З, М, поэтому при заданном расположении буквы И имеем 24 = 16 вариантов.
Всего вариантов с буквой И: 5 · 16 = 80
Аналогично с буквой А: 5 · 16 = 80
Всего: 80 + 80 = 160
Ответ: 160

быть буквы Н, О, Т, К, И, за­пи­са­ны в ал­фа­вит­ном

по­ряд­ке и про­ну­ме­ро­ва­ны, на­чи­ная с 1.
Ниже при­ве­де­но на­ча­ло спис­ка.
1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ
…
Под каким но­ме­ром в спис­ке идёт пер­вое слово, ко­то­рое на­чи­на­ет­ся с буквы О?

пользователю выдаётся пароль, состоящий из 10 символов и содержащий только

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

k бит поз­во­ля­ют ко­ди­ро­вать 2k зна­че­ний, по­это­му для ко­ди­ро­ва­ния 26-сим­воль­но­го ал­фа­ви­та тре­бу­ет­ся 5 бит, по­сколь­ку 25 = 32 ≥ 26.
Для хра­не­ния 10 сим­во­лов тре­бу­ет­ся 5 · 10 = 50 бит.
Ми­ни­маль­ное ко­ли­че­ство байт, вме­ща­ю­щее в себя 50 битов со­став­ля­ет 7 байт (берём бли­жай­шее к 50 не мень­шее зна­че­ние, крат­ное вось­ми: это число 56 – 7 байт).
Для хра­не­ния све­де­ний об одном поль­зо­ва­те­ле тре­бу­ет­ся 7 + 6 = 13 байт.
Объём памяти, необходимый для хранения сведений о 30 пользователях составляет: 30 * 13 = 390 байт.

пользователю выдаётся пароль, состоящий из 7 символов и содержащий только

символы из 26-символьного набора прописных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 30 пользователях потребовалось 600 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

k бит поз­во­ля­ют ко­ди­ро­вать 2k зна­че­ний, по­это­му для ко­ди­ро­ва­ния 26-сим­воль­но­го ал­фа­ви­та тре­бу­ет­ся 5 бит, по­сколь­ку 25 = 32 ≥ 26.
Для хра­не­ния 7 сим­во­лов тре­бу­ет­ся 5 · 7 = 35 бит.
Ми­ни­маль­ное ко­ли­че­ство байт, вме­ща­ю­щее в себя 35 битов со­став­ля­ет 5 байт (берём бли­жай­шее к 35 не мень­шее зна­че­ние, крат­ное вось­ми: это число 40 – 5 байт).
Для хра­не­ния све­де­ний об одном поль­зо­ва­те­ле тре­бу­ет­ся 600/30 = 20 байт.
Для хра­не­ния до­пол­ни­тель­ной ин­фор­ма­ции от­во­дит­ся 20 − 5 = 15 байт.

РЕШЕНИЕ:

ОТВЕТ: 15

поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 15 сим­во­лов и со­дер­жа­щий толь­ко

сим­во­лы из 8-сим­воль­но­го на­бо­ра: А, В, C, D, Е, F, G, H. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля, для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего от­ве­де­но 24 байт на од­но­го поль­зо­ва­те­ля. Опре­де­ли­те объём па­мя­ти (в бай­тах), не­об­хо­ди­мый для хра­не­ния све­де­ний о 20 поль­зо­ва­те­лях. В от­ве­те за­пи­ши­те толь­ко целое число — ко­ли­че­ство байт.