Задача 22

Оценить, какую долю общего числа возможных последовательностей следует учитывать в практических расчетах, если эргодический источник характеризуется параметрами , бит, а . Здесь число элементов алфавита; длина последовательности из элементов алфавита; энтропия источника.

Задача 23

Определить возможный эффект от устранения избыточности при передаче текста на русском языке.

Задача 24

Провести эффективное кодирование ансамбля из восьми знаков, характеристики которого представлены в таблице З.4.

Таблица З.4. – Исходный алфавит

Знаки	Вероятность	Кодовые комбинации	Ступень разбиения
		1	I
		01
		001	II
		0001	III
		00001	IV
			Окончание таблицы З.4
		000001	V
		0000001	VI
		0000000	VII

Задача 25

Определить среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля, приведенного в таблице З.5.

Таблица З.5. – Исходный алфавит

Знаки	Вероятность	Кодовые комбинации	Ступень разбиения
	0,22	11
	0,2	101	II
	0,16	100	III
	0,16	01	I
	0,10	001	IV
	0,10	0001	V
	0,04	00001	VI
	0,02	0000	VII

Задача 26

На шахматной доске в одной из клеток поставлена фигура, причём все положения фигуры одинаково вероятны. Какое минимальное количество вопросов, на которые можно ответить «да» или «нет», нужно поставить, чтобы определить положение фигуры. Как нужно задавать вопросы, чтобы минимизировать их количество?

Задача 27

Статистика говорит, что 70% мужчин имеют тёмные волосы, 25% женщин – блондинки, а 80% блондинок выходят замуж за темноволосых мужчин. Сколько информации о цвете волос мужа несёт цвет волос его жены?

Задача 28

Пусть множества и состоят из двух элементов, именно из 0 и 1. Предположим, что распределение вероятностей на множестве задано следующим образом: , , , . Являются ли ансамбли и статистически независимыми?

Задача 29

Пусть дискретный источник без памяти имеет энтропию =2,5 бит. Пусть 100 сообщений такого источника кодируются десятичным равномерным кодом. Оцените наименьшее количество кодовых символов, которое может появиться на выходе кодера. Как зависит это количество от допустимой вероятности ошибки?

Задача 30

Построить групповой код объёмом 15 слов, способный исправлять единичные и обнаруживать двойные ошибки.

Задача 31

Доказать, что мощность множества всех подмножеств множества из элементов равна .

Задача 32

Доказать тождество

Задача 33

Сколько различных последовательностей длиной можно составить из элементов дискретного множества

Задача 34

Для дискретного постоянного источника с распределением вероятностей

1)

2)

определить собственную информацию каждой из букв, энтропию. Сколько информации содержится в последовательности

Задача 35

Доказать, что линейная комбинация выпуклых функций с положительными коэффициентами – выпуклая функция.

Задача 36

Доказать, что

.

Как запишется это свойство энтропии для дискретного множества, состоящего из элементов?

Задача 37

Алфавит источника . Задана вероятность Построить зависимость энтропии от величины

Задача 38

При каком соотношении между параметрами и простая марковская цепь с матрицей переходных вероятностей

порождает последовательность независимых сообщений?

Задача 39

Укажите стационарное распределение вероятностей для цепи Маркова с матрицей переходных вероятностей

.

Задача 40

Найти стационарное распределение для неэргодической цепи Маркова с матрицей переходных вероятностей

.

Задача 41

Двоичный источник задается простой цепью Маркова с матрицей переходных вероятностей

.

Найти собственную информацию последовательности 0110, энтропию .

Задача 42

Имеется постоянный источник троичных сообщений. Алфавит источника имеет вид . Для распределений вероятностей

1)

2)

построить зависимости скорости равномерного кода от длины кодируемых блоков: 1) при нулевой вероятности ошибки, 2) при допустимой вероятности ошибки, равной 0,1. Сопоставить скорость кодов с энтропией источника.

Задача 43

Построить код Хаффмена для источника с вероятностями букв, равными: 0,3; 0,25; 0,15; 0,1; 0,1; 0,05; 0,05. Сравнить среднюю длину кодовых слов с энтропией источника.

Задача 44

Рассматривается троичный постоянный источник с вероятностями букв

1)

2) .

Построить коды Хаффмена для отдельных букв алфавита , для , для . Сопоставить скорости кодов с энтропией источника.

Задача 45

Для двоичного постоянного источника с вероятностью единицы, равной 0,1; исследовать зависимости скорости кода Хаффмена от длины кодируемых блоков.

Задача 46

Троичный источник задан цепью Маркова с матрицей переходных вероятностей

.

Вычислить энтропию , считая начальное распределение на буквах совпадающим со стационарным распределением. Определить скорость кодирования при кодировании кодом Хаффмена ансамблей , .

Задача 47

Построить код Шеннона постоянного источника из задачи 45. Сопоставить среднюю длину со средней длиной кодовых слов кода Хаффмена и с энтропией источника.

Задача 48

Построить код Гилберта–Мура постоянного источника из задачи 45. Сопоставить среднюю длину со средней длиной кодовых слов кода Хаффмена и с энтропией источника.

Задача 49

Закодировать арифметическим кодом последовательность 01001 на выходе двоичного источника с вероятностью единицы, равной 0,4. Сравнить длину кодовой последовательности с собственной информацией последовательности и с суммарной длиной кодовой последовательности при независимом кодировании символов кодом Шеннона.

Задача 50

Объяснить, почему завершение кодирования в программе (Приложение 5) эквивалентно преобразованию кодового слова кода Шеннона в кодовое слово кода Гилберта–Мура.

Задача 51

Какие конкретно изменения нужно внести в алгоритмы арифметического кодирования и декодирования (Приложение 4), чтобы применить их к источнику, описываемому моделью простой цепи Маркова?

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Шеннон, К. Математическая теория связи. Работы по теории информации и кибернетике/ К. Шеннон. – М.: Изд-во иностр. лит-ры, 1963. – 830 с.

2. Дмитриев, В.И. Прикладная теория информации/ В.И. Дмитриев. – М.: Высшая школа, 1989. – 320 с.

3. Кудряшов, Б.Д. Теория информации/ Б.Д. Кудряшов. – СПб.: Питер, 2009. – 320 с.

4. Колесник, В.Д. Курс теории информации/ В.Д. Колесник, Г.Ш. Полтырев. – М.: Наука, 1982. – 416 с.

5. Феллер, В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т.1:пер. с англ./ В. Феллер. – М.: Мир, 1984. – 528 с.

6. Белов, А.А. Теория вероятностей и математическая статистика: учебник/ А.А. Белов, Б.А. Баллод, Н.Н. Елизарова. – Ростов н/ Д.: Феникс, 2008. – 318 с.

7. Свирид, Ю.В. Основы теории информации: курс лекций/ Ю.В. Свирид. – Минск: БГУ, 2003. – 139 с.

8. Яглом, А.М. Вероятность и информация/ А.М. Яглом, И.М. Яглом. – 3.е, перераб. и доп. изд. – М.: Наука, 1973. – 512 с.

9. Вентцель, Е.С. Теория вероятностей/ Е.С. Вентцель. – М.: Высшая школа, 2000. – 576 с.

10. Орлов, В.А. Теория информации в упражнениях и задачах/ В.А. Орлов, Л.И. Филлипов. – М.: Высшая школа, 1976. – 136 с.