← Все тренажёры Теория информации, энтропия Шеннона и алгоритмы сжатия

Теория информации, энтропия Шеннона и алгоритмы сжатия

Энтропия, префиксные коды и алгоритм Хаффмана.

27 заданий · Теория информации и кодирование

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Как определяется энтропия Шеннона дискретного источника с распределением вероятностей P=(p1,…,pn)P = (p_1, \dots, p_n)?

2

При каком распределении вероятностей nn символов энтропия дискретного источника достигает своего абсолютного максимума?

3

В чем заключается условие Фано для схемы алфавитного кодирования?

4

Какое неравенство связывает длины кодовых слов ℓi\ell_i в dd-ичном алфавите для существования префиксного (и однозначно декодируемого) кода?

5

Как устроен алгоритм построения дерева Хаффмана?

6

Чему равна собственная информация I(a)I(a) события, вероятность которого равна p=18p = \frac{1}{8}?

7

В чем главное преимущество арифметического кодирования перед кодированием Хаффмана?

8

Дан двоичный код: c(a)=0c(a) = 0, c(b)=01c(b) = 01, c(c)=11c(c) = 11. Является ли он префиксным?

9

Чему равна энтропия честной монеты с двумя равновероятными исходами (p1=p2=0.5p_1 = p_2 = 0.5)?

Блок 2. Краткий ответ

10

Источник порождает 4 равновероятных символа (p1=p2=p3=p4=0.25p_1 = p_2 = p_3 = p_4 = 0.25). Вычислите энтропию источника H(X)H(X) в битах.

целое число

11

Проверьте неравенство Крафта для длин двоичных кодовых слов: ℓ=(1,2,3,3)\ell = (1, 2, 3, 3). Вычислите сумму ∑2−ℓi\sum 2^{-\ell_i}. Если сумма равна 1, запишите в ответе 1.

целое число

12

В алфавите из 3 символов заданы вероятности p1=0.5,p2=0.25,p3=0.25p_1 = 0.5, p_2 = 0.25, p_3 = 0.25 и длины кодовых слов Хаффмана: ℓ1=1,ℓ2=2,ℓ3=2\ell_1 = 1, \ell_2 = 2, \ell_3 = 2. Найдите точное значение средней длины кодового слова LL. Введите десятичную дробь без округления.

число

13

Какова глубина листа с наименьшей вероятностью в дереве Хаффмана для источника с вероятностями 0.7,0.15,0.150.7, 0.15, 0.15?

целое число

14

Сколько бит необходимо для равномерного кодирования каждого из 32 различных символов алфавита?

целое число

15

Чему равна энтропия детерминированного источника, в котором вероятность одного события равна 1, а всех остальных — 0?

целое число

Блок 3. Несколько верных вариантов

16

Какие из следующих наборов двоичных кодовых слов удовлетворяют условию Фано (являются префиксными кодами)?

Отметьте все верные варианты

17

Какие свойства справедливы для информационной энтропии Шеннона H(X)H(X)?

Отметьте все верные варианты

18

Какие утверждения об алгоритме Хаффмана верны?

Отметьте все верные варианты

19

Для каких из перечисленных наборов длин двоичных кодовых слов выполнено неравенство Крафта ∑2−ℓi≤1\sum 2^{-\ell_i} \le 1?

Отметьте все верные варианты

20

Какие утверждения об арифметическом кодировании верны?

Отметьте все верные варианты

21

Какие параметры влияют на избыточность R=L−H(X)R = L - H(X) кода?

Отметьте все верные варианты

Блок 4. Дополнение по презентациям

22

RLE записывает максимальные серии в формате «символ затем число повторений». Как закодируется строка AAAABBA?

23

LZW использует начальный словарь A↦1A\mapsto1, B↦2B\mapsto2; новые коды выдаются с 3. Запишите последовательность кодов для ABAABABA.

коды по порядку через запятую или пробел

24

Коэффициент сжатия определён как отношение исходного размера к сжатому. Файл уменьшился со 120 до 40 байт. Чему равен коэффициент?

целое число

25

При арифметическом кодировании AA занимает [0,0.5)[0,0.5), BB — [0.5,1)[0.5,1). Кодируется слово BA. Чему равна нижняя граница итогового полуинтервала?

десятичная дробь

26

Какие утверждения о RLE и LZW верны?

Отметьте все верные варианты

27

Что верно о классических шифрах замены и перестановки из лекции?

Отметьте все верные варианты

Завершение теста

Все ответы сохраняются автоматически. Нажмите для отправки на проверку.

Карта заданий (27)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.