Информация и её кодирование: алгоритмы и способы решения

1.

Информация и ее
кодирование: алгоритмы и
способы решения
Лавинова Татьяна Валерьевна,
учитель информатики и ИКТ МАОУ «ЛИТ»

2.

Задание 4
Тема: Кодирование и декодирование информации

3.

Что проверяется:
Умение кодировать и декодировать информацию.
1.1.2. Процесс передачи информации, источник и приёмник
информации. Сигнал, кодирование и декодирование.
Искажение информации.
1.2.2. Умение интерпретировать результаты, получаемые
в ходе моделирования реальных процессов (?)

4.

Что нужно знать:
• кодирование – это перевод информации с одного языка на
другой (запись в другой системе символов, в другом алфавите)
• обычно кодированием называют перевод информации с
«человеческого» языка на формальный, например, в двоичный
код, а декодированием – обратный переход
• один символ исходного сообщения может заменяться одним
символом нового кода или несколькими символами, а может
быть и наоборот – несколько символов исходного сообщения
заменяются одним символом в новом коде (китайские иероглифы
обозначают целые слова и понятия)

5.

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

6.

Что нужно знать:
• выполнение одного из условий Фано достаточно, но не
необходимо для однозначного декодирования;
• если в условии задачи утверждается, что код удовлетворяет
условию Фано, имеется в виду прямое условие Фано: ни одно
кодовое слово не совпадает с началом другого кодового слова;
если утверждается, что код допускает однозначное
декодирование, то нужно проверять как прямое, так и обратное
условия Фано.

7.

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

8.

0
0
1
1
0
1
А
0
Е
1
0
1
0
1
И
У
0
Б
Л
0
1
0
1
С
К
Р
Т
Ответ: 1100

9.

Задача № 134 (Поляков К.Ю.)
• Для кодирования некоторой последовательности, состоящей из
букв А, Б, В, Г, Д, Е, Ж, З, решили использовать неравномерный
двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В,
Г, Д, Е использовали соответственно кодовые слова 10, 110, 010,
0110, 111, 0111. Укажите кратчайшее возможное кодовое слово
для буквы Ж, при котором код будет допускать однозначное
декодирование. Если таких кодов несколько, укажите код с
наименьшим числовым значением.

10.

А - 10
Б – 110
В – 010
Г – 0110
Д – 111
Е - 0111
0
0
1
0
1
1
А
0
1
0
1
В
0
1
Г
Е
0
1
Б
Д
Ответ: 000

11.

Статград-203 (2019-2020)
По каналу связи передаются сообщения, содержащие только
заглавные русские буквы. Для передачи используется двоичный код,
удовлетворяющий условию Фано. Кодовые слова для некоторых
букв известны: А – 000, Б – 01, В – 1101, Г – 111, Д – 0010, Е – 100.
Какое наименьшее количество двоичных знаков потребуется для
кодирования слова КОКОС?

12.

1
0
1
0
1
0
Б
0
1
А
0
Д
0
1
Е
К
1
1
0
Г
0
1
О
В
0
1
С
…
К – 3х2=6
О – 4х2=8
С – 5х1=5
Всего: 19

13.

Задача № 166 (Е. Джобс)
По каналу связи передаются сообщения, содержащие только семь
букв: О, К, Т, Я, Б, Р, Ь. Для передачи используется двоичный код,
допускающий однозначное декодирование. Кодовые слова для
некоторых букв известны: К – 1010, Т – 100, Б – 0101, Р – 110, Ь –
001. Укажите минимальную возможную сумму длин кодов всех
букв.

14.

Прямое условие Фано
К – 1010
Т – 100
Б – 0101
Р – 110
Ь – 001
0
0
1
0
1
1
0
1
1
0
Т
Ь
1
Б
Всего 23 символа
0
1
0
Р
0
К

15.

Обратное условие Фано
К – 1010
Т – 100
Б – 0101
Р – 110
Ь – 001
1
0
0
0
1
1
0
0
Т
Всего 22 символа
0
1
Р
1
Ь
1
0
К
Б
1

16.

Задача № 189 (Поляков К.Ю.)
Все заглавные буквы русского алфавита закодированы
неравномерным двоичным кодом, для которого выполняется
условие Фано: никакое кодовое слово не совпадает с началом
другого кодового слова. Известно, что слову СКОЛОК соответствует
код 11101001000001. Какой код соответствует слову ЛОСК?
11101001000001
С
К
О
Л
О
ЛОСК -1000011101
К

17.

Задание 193 (Поляков К.Ю.)
Для кодирования некоторой последовательности, состоящей из
букв Е, Л, П, К, Р, C, решили использовать неравномерный
двоичный код, для которого выполняется условие Фано. Для букв К
и Р использовали соответственно кодовые слова 011, 11. Найдите
кодовую последовательность наименьшей длины для кодирования
слова ПЕРЕПЕЛ и запишите полученный результат в восьмеричном
коде. Если таких кодов несколько, укажите код с наименьшим
числовым значением.

18.

К – 011
Р - 11
1
0
0
0
1
П
1
Е
0
Р
1
К
0
1
Л
С
П Е Р Е П Е Л
00 10 11 10 00 10 0100
Ответ: 27044

19.

Задание 8
Тема: Кодирование данных, комбинаторика, системы счисления

20.

Что проверяется:
• Знание основных понятий и методов, используемых при
измерении количества информации
• 1.6.1. Формализация понятия алгоритма
• 1.1.4. Читать и отлаживать программы на языке
программирования (?)

21.

Что нужно знать:
• в русском языке 33 буквы: 10 гласных букв (а, у, о, ы, и, э, я, ю, ё, е), 21
согласная буква (б, в, г, д, ж, з, й, к, л, м, н, п, р, с, т, ф, х, ц, ч, ш, щ) и два
знака (ь, ъ);
• алфавит английского языка по написанию совпадает с латинским
алфавитом и состоит из 26 букв;
• принципы работы с числами, записанными в позиционных системах
счисления;
• если слово состоит из L букв, причем есть n1 вариантов выбора первой
буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов
вычисляется как произведение;
• N = n1 · n2 · … · nL;
• если слово состоит из L букв, причем каждая буква может быть выбрана n
способами, то число возможных слов вычисляется как N = nL .

22.

Открытый вариант ЕГЭ-2023
Все четырёхбуквенные слова, составленные из букв А, Б, З, И,
записаны в алфавитном порядке и пронумерованы начиная с 1.
Ниже приведено начало списка.
1. АААА
2. АААБ
3. АААЗ
4. АААИ
5. ААБА
…
Под каким номером стоит слово ИЗБА?

23.

• А-0, Б-1, З-2, И-3 – четверичная система счисления
• ИЗБА – 32104 = 3*43 + 2*42 + 4 = 228
• Расположение элементов:
№1- 0
№2–1
№3–2
…
Число 228 стоит на 229м месте
Ответ: 229

24.

Задача 127 (А.Н. Носкин)
Петя составляет список из 4-буквенных слов, в состав которых входят
только буквы О, С, Е, Н, Ь. Петя расположил слова в обратном
алфавитном порядке. Вот начало списка:
1. ЬЬЬЬ
2. ЬЬЬС
3. ЬЬЬО
4. ЬЬЬН
5. ЬЬЬЕ
6. ЬЬСЬ
……
Запишите слово, которое стоит в этом списке под номером 100.

25.

• Ь – 0, С – 1, 0 – 2, Н- 3, Е – 4 – пятеричная система счисления
• Под № 100 находится число 99
• 99 = 3445 = ЬНЕЕ
• Ответ: ЬНЕЕ

26.

Задача № 258 (Р. Тукеев)
Марат составляет шестибуквенные слова из букв слова А, И, К, Л, М, Ь и записывает
их в алфавитном порядке в список. Вот начало списка:
1. АААААА
2. АААААИ
3. АААААК
4. АААААЛ
5. АААААМ
6. АААААЬ
7. ААААИА
...
Найдите номер первого слова в списке, начинающегося на К и заканчивающегося на
Ь, в котором каждая буква встречается всего лишь раз, а разница между номерами
этого слова и его перевёртыша составляет 26655. В ответе укажите сумму цифр этого
номера. (Пример перевёртыша: питон – нотип).

27.

Примечание: Программа выводит сами числа!!! Нужно найти сумму цифр меньшего

28.

Статград (апрель 2023 г.)
Виктор составляет коды из букв, входящих в слово ВИКТОР. Каждая
буква должна входить в код ровно один раз. Все возможные коды
Виктор записывает в алфавитном порядке и нумерует. Начало
списка выглядит так:
1. ВИКОРТ
2. ВИКОТР
3. ВИКРОТ
Какой код будет записан под номером 266?

29.

30.

permutations – перестановки, например:
Результат: [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'),
('C', 'B', 'A')]

31.

product – декартово произведение (все возможные слова заданной
длины, составленные из данного алфавита), например:
Результат: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'),
('C', 'B'), ('C', 'C')]

32.

Задача № 232 (Поляков)
Определите количество семизначных чисел, записанных в
девятеричной системе счисления, учитывая, что числа не могут
начинаться с цифр 2 и 6 и не должны заканчиваться на пару
одинаковых цифр (например, на 00).
• Алфавит девятеричной системы счисления: 0, 1, 2, 3, 4, 5, 6, 7, 8;
• из цифр составляем 7-значные числа – используем product

33.

34.

Задача № 234 (Поляков)
Вася составляет слова из букв слова АКАДЕМИК. Код должен
состоять из 8 букв, и каждая буква в нём должна встречаться
столько же раз, сколько в заданном слове. Кроме того, в коде не
должны стоять рядом две гласные и две согласные буквы. Сколько
различных слов может составить Вася?
• Слова составляются перестановкой букв – используем
permutation;
• в слове «Академик» есть повторяющиеся буквы;
• слова должны быть разные.

35.

Если не использовать множество, то общее количество слов необходимо
разделить на 2! (перестановки с повторениями)

36.

Задача № 267 (А. Богданов)
Оля составляет слова перестановкой букв слова СПОРТЛОТО, избегая
слов с гласной в конце слова. Все полученные различные слова Оля
отсортировала по алфавиту и пронумеровала, начиная с 1. Какой
номер у последнего слова?

37.

Если не использовать множество, то общее количество слов необходимо
разделить на 2!*3! (перестановки с повторениями)

38.

Задание 11
Тема: Вычисление информационного объема сообщения

39.

Что проверяется:
• Умение подсчитывать информационный объём сообщения.
• 1.1.3. Дискретное (цифровое) представление текстовой,
графической, звуковой информации и видеоинформации.
Единицы измерения количества информации.
• 1.3.1. Умение оценивать объём памяти, необходимый для
хранения информации.

40.

Что нужно знать:
• с помощью K бит можно закодировать Q 2 K различных вариантов
(чисел);
• степени двойки;
• при измерении количества информации принимается, что в одном
байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте
(1 Мбайт) – 1024 Кбайта;
• чтобы найти информационный объем сообщения (текста) I, нужно
умножить количество символов (отсчетов) N на число бит на символ
(отсчет) K: I N K

41.

Что нужно знать:
• мощность алфавита M – это количество символов в этом
алфавите
• если алфавит имеет мощность M, то количество всех возможных
«слов» (символьных цепочек) длиной N (без учета смысла) равно
Q=M N для двоичного кодирования (мощность алфавита M – 2
символа) получаем известную формулу: Q=2N

42.

Открытый вариант ЕГЭ-2023
При регистрации в компьютерной системе каждому пользователю выдаётся
пароль, состоящий из 23 символов. В качестве символов используются буквы
из 12-символьного алфавита. В базе данных для хранения сведений о
каждом пользователе отведено одинаковое и минимально возможное
целое число байт. При этом используется посимвольное кодирование
паролей, все символы кодируются одинаковым и минимально возможным
количеством бит. Кроме собственно пароля в системе хранятся
дополнительные сведения о каждом пользователе, для чего выделено целое
число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 297 пользователях потребовалось 13 068 байт.
Сколько байт выделено для хранения дополнительных сведений об одном
пользователе?
В ответе запишите только целое число – количество байт.

43.

К = 23
М = 12 -> i = 4
На 1 пароль: I1 = 23*4 = 92 бита -> 12 байт
На 297 пользователей 13068 байт -> на одного 44 байта
44 – 12 = 32 байт на доп. информацию
Ответ: 32 байт

44.

Статград, апрель 2023 г.
В информационной системе хранится информация об объектах определённой
структуры. Описание каждого объекта включает в себя код объекта, описание
структуры объекта и дополнительную информацию.
Код объекта состоит из 13 символов, каждый из которых может быть либо одной
из 10 десятичных цифр, либо одной из 26 заглавных латинских букв. Каждый
символ кодируется минимально возможным числом бит, а для хранения всего
кода отводится минимально возможное целое число байт.
Структура объекта описывается как последовательность простых элементов.
Всего существует 500 различных простых элементов. Каждый простой элемент
кодируется одинаковым для всех элементов минимально возможным
количеством бит. Для описания структуры объекта выделяется одинаковое для
всех объектов минимальное количество байт, достаточное для записи 60 простых
элементов.
Для хранения дополнительной информации выделяется одинаковое для всех
объектов целое число байт.
Известно, что для хранения данных о 16384 объектах потребовалось 2 Мбайт.
Сколько байт выделено для хранения дополнительной информации об одном
объекте?

45.

Код + структура + доп.информация
1. Код
К = 13
М = 10 + 26 = 36 -> i = 6
Iк = 13 * 6 =78 бит -> 10 байт
2. Структура
М = 500 -> i = 9
60 * 9 = 540 бит -> 68 байт
На 16384 элемента 2 Мб -> 128 байт на 1 объект.
3. Доп.информация: 128 – 68 – 10 = 50 байт
Ответ: 50 байт

46.

Задача № 36 (Поляков К.Ю.)
При регистрации в компьютерной системе каждому пользователю
выдаётся идентификатор, состоящий из 10 символов, первый и
последний из которых – одна из 18 букв, а остальные – цифры
(допускается использование 10 десятичных цифр). Каждый такой
идентификатор в компьютерной программе записывается
минимально возможным и одинаковым целым количеством байт
(при этом используют посимвольное кодирование; все цифры
кодируются одинаковым и минимально возможным количеством
бит, все буквы также кодируются одинаковым и минимально
возможным количеством бит). Определите объём памяти в байтах,
отводимый этой программой для записи 25 паролей.

47.

К = 10 = 2 буквы + 8 цифр
Мб = 18 -> i б = 5
Iб = 2 * 5 = 10 бит на буквы
Мц = 10 -> i ц = 4
Iц = 8 * 4 = 32 бита
I = 10 + 32 = 42 бита -> 6 байт на 1 идентификатор
25 * 6 = 150 байт
Ответ: 150 байт

48.

Задача № 60 (Д.В. Богданов)
В некоторой стране используют автомобильные номера, состоящие
из двух частей: ровно двух букв из 10-буквенного алфавита и далее
ровно трёх десятичных цифр. Каждая часть кодируется отдельно
помощью минимально возможного количества битов, одинакового
для всех номеров. Какое минимальное количество байт
необходимо зарезервировать для хранения информации о 24
таких номерах?

49.

Номер: 2 буквы + 3 цифры
Буквы: на каждую из двух позиций – любая из 10 букв
10 * 10 = 100 вариантов (т.е. Мб = 100, iб = 7 бит)
Цифры: на каждую из трех позиций – любая из 10 цифр
10 * 10 * 10 = 1000 (т.е Мц = 1000, iц = 10 бит)
На 1 номер: 7 + 10 = 17 бит
Всего: 14*24/8 = 51 байт
Ответ: 51 байт.

50.

Задача № 108 (Информатик-БУ)
При регистрации в компьютерной системе каждому пользователю
присваивается уникальный идентификатор, состоящий из 10-ти
символов. Каждый символ идентификатора может быть одной из 26ти строчных латинских букв, либо десятичной цифрой. Помимо
идентификатора, в базе данных для каждого пользователя хранятся
дополнительные сведения. Для хранения идентификатора выделено
минимально возможное целое число битов. Идентификатор и
дополнительные сведения хранятся отдельно. Для хранения
информации о каждом пользователе в базе отведено одинаковое
минимальное возможное целое число байт. Сколько битов выделено
для хранения дополнительных сведений, если известно, что на 100
пользователей отведено 1000 байт?

51.

Идентификатор + доп.сведения
И – 10 символов
М = 26 + 10 = 36
Имеем 10 символов, каждый из которых может быть любым из 36 ->
3610 вариантов
I1 = log2 (3610) = 52 бита на 1 вариант
На 100 пользователей 1000 байт -> на одного – 10 байт = 80 бит
80 – 52 = 28 бит на доп.сведения
Ответ: 28 бит.

52.

Задание 7
Тема: Кодирование растровых изображений. Кодирование звука. Скорость
передачи звука

53.

Что проверяется:
• Умение определять объём памяти, необходимый для хранения
графической и звуковой информации.
• 3.3.1. Форматы графических и звуковых объектов.
• 1.3.2. Оценивать скорость передачи и обработки информации.

54.

Что нужно знать:
• для хранения растрового изображения нужно выделить в памяти I = N · i
битов, где N – количество пикселей и i – глубина цвета (разрядность
кодирования);
• количество пикселей изображения N вычисляется как произведение ширины
рисунка на высоту (в пикселях);
• глубина кодирования – это количество бит, которые выделяются на хранение
цвета одного пикселя;
• при глубине кодирования i битов на пиксель код каждого пикселя
выбирается из 2i возможных вариантов, поэтому можно использовать не
более 2i различных цветов;
• нужно помнить, что
1 Мбайт = 220 байт = 223 бит,
1 Кбайт = 210 байт = 213 бит.

55.

Что нужно знать:
• при оцифровке звука в памяти запоминаются только отдельные
значения сигнала, который нужно выдать на динамик или наушники;
• частота дискретизации определяет количество отсчетов,
запоминаемых за 1 секунду; 1 Гц (один герц) – это один отсчет в
секунду, а 8 кГц – это 8000 отсчетов в секунду;
• глубина кодирования – это количество бит, которые выделяются на
один отсчет;
• для хранения информации о звуке длительностью t секунд,
закодированном с частотой дискретизации f Гц и глубиной
кодирования B бит требуется B*f*t бит памяти;
• при двухканальной записи (стерео) объем памяти, необходимый для
хранения данных одного канала, умножается на 2.

56.

Что нужно знать:
• «физический» аналог задачи:
• объем переданной информации Q вычисляется по формуле Q = q*t

57.

Задача № 111 (ЕГЭ-2022)
Для хранения сжатого произвольного растрового изображения
размером 640 на 256 пикселей отведено 170 Кбайт памяти без
учёта размера заголовка файла. Исходный файл изображения
больше, чем сжатый, на 35% (считая размер сжатого файла за
100%). Для кодирования цвета каждого пикселя используется
одинаковое количество бит, коды пикселей записываются в файл
один за другим без промежутков. Какое максимальное количество
цветов можно использовать в изображении?

58.

К=640 * 256
Iисх = Iсж + 0,35 * Iсж = 1,35* Iсж
170∗1024∗8∗1,35
i=
= 11, 475 -> i = 11
640∗256
N = 211 = 2048
Ответ: 2048

59.

Задача № 115 (А. Кабанов)
Для хранения произвольного растрового изображения размером
640 на 480 пикселей отведено 600 Кбайт памяти без учёта размера
заголовка файла. При кодировании каждого пикселя используется
64 уровня прозрачности, а также одинаковое количество бит для
указания его цвета. Коды пикселей записываются в файл один за
другим без промежутков. Какое максимальное количество цветов
(без учета степени прозрачности) можно использовать в
изображении?

60.

К = 640 * 480
На 1 пиксель: 64 уровня прозрачности + цвет
Битовая глубина i = 6 + i ц
600*1024*8 = 640*480*(6 + i ц)
600∗1024∗8
6 + iц =
= 16 бит
640∗480
i ц = 10 бит
N = 1024
Ответ: 1024

61.

Задача № 117 (А. Кабанов)
Для хранения произвольного растрового изображения размером
480 на 768 пикселей отведено 405 Кбайт памяти без учёта размера
заголовка файла. При кодировании цвета каждого пикселя
используется одинаковое количество бит, при этом для каждых
двух бит цвета дописывается дополнительный бит контроля
чётности. Коды пикселей записываются в файл один за другим без
промежутков. Какое максимальное количество цветов можно
использовать в изображении?

62.

К=640 * 786
I= 405 Кб
405∗1024∗8
i=
= 9 бит
480∗786
_________
т.е. i = 6, N = 64
Ответ: 64

63.

Задача № 124 (Д. Статный)
На фабрике производят глобусы диаметром 40 см, на которые
требуется нанести карту. Изображение поверхности планеты,
которое нужно наносить на глобус, сохранено с линейным
разрешением 300 ppi с использованием 224 цветов. Сколько Мбайт
потребуется для хранения карты? Поверхность глобуса можно
принять за сферу, площадь поверхности сферы вычисляется по
формуле S = 4 R2, где R – радиус сферы.

64.

d = 40 см -> r = 20 см
Линейное разрешение – 300 ppi (надо перевести в пискели на см,
учесть, что карта – прямоугольник)
300∗300∗4∗3,14∗20∗20∗24
= 200,51
2,54∗2,54∗1024∗1024∗8
В ответ записываем целое число!
Ответ: 201 Мб

65.

Статград (март 2023 г)
Книгу объёмом 1 Мбайт записали как аудиокнигу. Запись велась в
формате стерео (2 канала) с частотой 32 кГц и разрешением 16 бит.
За одну минуту записывалось в среднем 1,5 Кбайт текста. Сжатие
данных позволило сократить размер полученного звукового файла
на 80 %. Для удобства использования запись разделили на
фрагменты со средним размером 20 Мбайт. Определите количество
полученных фрагментов.

66.

1. 1,5 Кб текста – 60 сек ->
60∗1024
= 40960 сек на 1 Мб текста
1,5
2∗32000∗16∗40960∗0,2
2.
= 50
20∗1024∗1024∗8
Ответ: 50

67.

Статград (февраль 2023 г)
Интернет-сервис предоставляет возможность скачать музыкальную
запись в двух вариантах: A (высокое качество) и B (среднее качество).
Оба варианта записаны в формате стерео. Вариант A оцифрован с
частотой дискретизации 88 кГц и разрешением 24 бит, вариант B – с
частотой дискретизации 44 кГц и разрешением 16 бит. В варианте A
использовано сжатие данных без потерь, при этом объём файла
уменьшился в 2 раза. В варианте B использовано сжатие с потерями,
уменьшающее размер файла в 10 раз. Известно, что размер файла
варианта B составляет 10 Мбайт. Определите размер файла для
варианта A. В ответе укажите только число – размер файла в Мбайт.

68.

88000∗24
А:
− х Мб
2
44000∗16
В:
− 10 МБ
10
88000∗24∗10∗10
= 150 Мб
2∗44000∗16
Ответ: 150