Лабораторные работы по теории информации для университета им. Ф. Скорины

Лабораторная работа №1

Энтропия и информация

1. Источник информации состоит из различных букв первых взятых из первых 12 букв вашего ФИО, вероятности их появления – частоты этих букв в первых 12 буквах ФИО.
a. Появление каких букв даёт самую большую информацию?
b. Посчитайте энтропию этого источника. На сколько она отличается от максимально возможной энтропии источника с таким количеством сообщений?
2. Последовательность = ‘N1990|11-N|’, где N – номер варианта (01, 02, …., 29; например, при N=02, Последовательность=02199009, при N=22 – 22199011). Случайные величины А и Б в качестве значений принимают различные цифры из последовательности и р(А=а, Б=б) есть частота встречаемости подпоследовательности аб в Последовательности.
a. Сколько всего подпоследовательностей длины 2 в Последовательности?
b. Постройте матрицу этого распределения и распределения каждой из указанных случайных величин.
c. Независимы ли случайные величины А и Б?
d. Найдите информацию события {A=1, Б=9}.
e. Найдите условную информацию события {A=1} при условии, что {Б=9}.
f. Найдите взаимную информацию между событиями {A=1} и {Б=9}.
g. Найдите энтропию совместного распределения А и Б.
h. Найдите условную энтропию А при условии Б.
i. Найдите среднюю взаимную информацию величин А и Б.

Лабораторная работа №2

Оптимальное кодирование

1. Мультимножество M строиться по следующему правилу. Берутся 8 букв из
вашего ФИО, находятся остатки их номеров при делении на 8 и к каждому из
них прибавляется 1. Полученные числа и составляют 𝑀.
Например для АААВВВББ 𝑀 = {2, 2, 2, 3, 3, 4, 4, 4}.
a. Для какого минимального D существует однозначно декодируемый код,
длины слов которого составляют 𝑀.
b. Какое наименьшее число (возможно и 0) элементов из 𝑀 нужно выкинуть,
чтобы существовал двоичный префиксный код с таким набором 𝑀’ длин
слов.
c. Для набора 𝑀′ из b постройте префиксный код с такими длинами слов и
его дерево. Является ли это дерево насыщенным?
2. Первый источник информации состоит из различных букв первых взятых из
первых 12 букв вашего ФИО, вероятности их появления – частоты этих букв в
первых 12 буквах ФИО. Второй источник информации состоит из
всевозможных подпоследовательностей длины два последовательности
П=‘N1990|11-N|’ (где N – номер варианта), вероятность появления
подпоследовательности есть частота её встречаемости в П.
a. Закодируйте первый источник информации двоичными кодами Фано и
Хаффмана.
b. Закодируйте второй источник информации троичным кодом Хаффмана.
c. Постройте деревья, соответствующие кодам из заданий a-b. Какие из
полученных деревьев являются насыщенными.
d. Найдите средние длины кодов из заданий a-b.
e. Найдите дины оптимальных кодов данных двух источников информации.

Лабораторная работа №3

Передача по каналам связи (Вариант 𝒏)

I. Задан стационарный канал связи без памяти такой, что входной алфавит
состоит из 0 и 1, символ передаётся правильно с вероятностью, и с
вероятностью переданный символ не распознаётся.
a. Постройте матрицу данного канала связи. Будет ли она стохастической?
Будет ли полученный канал симметрическим (по входу, по выходу). Оцените
его пропускную способность.
б. Пусть на вход канала связи подается случайный вектор 𝑋 принимающий
значение 0 с вероятностью 5/(𝑛 + 5) а в оставшихся случаях принимающий
значение 1. Найдите выходное распределение 𝑌 и среднюю взаимную
информацию 𝑰(𝑋; 𝑌). Достигается ли на этом распределении максимум
величины 𝑰(𝑋; 𝑌).
в. Пусть на вход канала связи подается случайный вектор 𝑋
2 принимающий
значение 00 с вероятностью 1/(𝑛 + 5), 01 – 𝑛/2(𝑛 + 5), 10 – 𝑛/2(𝑛 + 5) и 11
– 4/(𝑛 + 5). Найдите выходное распределение 𝑌
2 и среднюю взаимную
информацию.
г. Вычислите (численно или аналитически) пропускную способность вашего
канала.
II. Для канала из I и входного вектора X (из задания б) постройте декодеры по
методы максимального правдоподобия и методу апостериорной вероятности.
Являются ли они эквивалентными? Для каждого из декодеров найдите
вероятности ошибочного декодирования каждого из элементов и среднюю
вероятность ошибочного декодирования.
Основные понятия и утверждения: дискретный канал связи,
симметрический дискретный канал связи, пропускная способность канала
связи, декодеры по методы максимального правдоподобия и методу
апостериорной вероятности, средняя вероятность ошибочного
декодирования

Лабораторная работа №4

Теория чисел (Вариант 𝒏)

«Теория информации»
1. Посещение: 𝟏 ⋅ 𝒏, где 𝒏 – зависит от процента посещенных пар.
2. Лабораторные работы каждая: нет в наличие −𝟏 (4-я – 0), начато выполнение 
𝟎, выполненная в тетрадке 𝟎, 𝟓, оформленная в электронном виде 1.
4. Тест: −𝟏 + (число правильных ответов)/𝟓
5. Доказательство теоремы во время практического занятия: приблизительно 1
(зависит от сложности).
Экзамен: 
1. Вы согласны с текущей оценкой по модулю 𝑵.
2. Вы почти согласны с оценкой по модулю: вы вытягиваете вопрос и (письменно) 
отвечаете на него: 𝑵 ± 𝟐.
Оценка до 8 округляется (по правилам округления), после 8 берется целая часть 
оценки. Для получения оценки выше 8 требуется доказать хотя бы одну теорему 
(можно или во время экзамена, или во время семестра).

$. 
Найти энтропию этого источника, если $$log_2(1/5) \= -2.3$$, $$log_2(2/5) \= -
1.32$$, $$log_2(3*(1/5))) \= -0.73$$.
{~1.71
~1.61
~1.81
~1.51
=1.91
}
::026:: Пусть $$P(A) \= 7/47, P(B) \= 40/47$$ при какой $$P(B|A)$$ событие B не 
зависит от события A
{=40/47.
~7/47.
~47/47.
~44/47.
~33/47.}
::033:: Дан префиксный код: $$a \= 10, b \= 11, c \= 010, d \= 000$$. Раскодируйте 
последовательность 0001101010.
{~acdb
~bcad
~cbda
~cbad
=dbca}
::039:: Даны 4 сообщения $$a, b, c, d$$ с их вероятностями $$1/8, 1/8, 1/4, 1/2$$ 
соответственно.
Выберите среднюю длину двоичного кода Хаффмана для этого источника:
{~3/2
~13/8
=7/4
~15/8
~4/2}
::045:: Даны 6 кодовых слов двоичного префиксного кода. Также указаны 
вероятности, с которыми эти слова появляются. Найти среднюю длину кода. 
Вероятности и кодовые слова:
$$0,47 - 00, 0.2 - 01, 0.14 - 100, 0.09 - 101, 0.08 - 110, 0.02 - 111$$.
{~3,42
~2,05
~1,56
~2,62
=2,33}
::051:: Дана последовательность [4 1 1 3 2 2 4 2 2 4]. Расставить символы в 
порядке убывания их частот.
{~4, 2, 3, 1
~4, 3, 2, 1
=2, 4, 1, 3
~3, 1, 4, 2
~1, 4, 2, 3}
::057:: Даны 5 последовательностей 1, 01010, 1100, 10 и 011. 
Какую из них надо удалить, чтобы оставшиеся образовывали префиксный код 
(удалять последовательность наименьшей длины)?
{=1
~01010
~10
~Все 5 последовательности образуют префиксный код.
~1100}
::063:: Даны вероятности появления пяти сообщений ['1/64', '1/16', '1/4', '21/32', 
'1/64'].
 Найдите энтропию информационного источника.
{~1.279
~1.4257
~1.4732
=1.3363
~1.2992}
::069:: Даны 4 числа: 2, 3, 4, 5. 
Найдите наименьшее число x, такое что существует двоичный префиксный код, 
длинами слов которого являются исходные числа и x. 
{=1
~2
~3
~4
~5}
::074:: Задан стационарный канал связи без памяти такой, что входной алфавит 
состоит из 0 и 1, символ передается не правильно с вероятностью - 0.15 и символ 
не распознаётся в вероятностью 0.75
С какой вероятностью надо передавать символ, чтобы матрица была 
стохастической?
{=0.1
~0.70
~0.40
~-0.30
~-0.60}
::080:: Даны длины кодов символов: 8, 7, 4, 3, 8 и их вероятности - 0.1, 0.2, 0.2, 
0.1, 0.4 соответственно. Средняя длина кода равна.
{=6.50
~6.90
~6.20
~5.70
~7.50}
::085:: Дан источник информации, состоящий из 10 букв - "LTHHRDXABK". 
Вероятности их появления – частоты этих букв слове. При кодировании 4-ичным 
кодом Хаффмана, сколько букв нужно объединять на 1-м шаге?
{=3.
~4.
~5.
~6.
~2.}
::094:: Матрица А: 
$$[[2/12\, 2/12\, 2/12]\,
[10/12\,10/12\,10/12]]$$ 
{~Матрица А является стохастической, а канал является симметрическим по 
входу
~Матрица А является стохастической, а канал является симметрическим по 
выходу
=Матрица А не является стохастической, а канал является симметрическим по 
выходу
~Матрица А является стохастической, а канал является не симметрическим
~Матрица А не является стохастической, а канал является не симметрическим}
::105:: Связь префиксного и блочного кода :
{~Префиксный это разность блочного и постфиксного
~Они не связаны
~Не всякий блочный код является префиксным
=Всякий блочный код является префиксным
~Всякий префиксный код является блочным}
::111:: Найдите значение $$\varphi(204)$$, где $$\varphi$$ - функция Эйлера.
{=64
~55
~67
~49
~48
~85}
::120:: Найдите $$\tau(n)$$ - число положительных делителей натурального 
числа. $$n = 56$$.
{=8.
~9.
~6.
~12.
~10.}
::130:: Найдите НОД трех чисел $$(72, 279, 756)$$.
{ ~6
~3
~11
=9
~8
}
::140:: На каком из шагов бинарного поиска НОД(42, 8) число а будет равняться 
нулю.
{=10
~13
~11
~8
~12}
::146:: Вычислите $$3^(3*n-1) mod (3*n+13)$$, при $$n \= 14$$
{=$$3 mod 55$$
~$$4 mod 55$$
~$$5 mod 55$$
~$$2 mod 55$$
~Нет правильного ответа}
N1 Значение функции Мёбиуса от числа 373 равно
{~0
=-1
~1
~373
~5}
N2 Задан стационарный канал без памяти, входной и выходной алфавит которого 
состоят из чисел 0,1,2. Пусть на вход этого канала подается некоторый случайный 
вектор. Этот вектор принимает значение 0 с вероятностью 0.6, значение 1 - с 
вероятностью 0.3, значение 2 - с вероятностью 0.1.
Через $$P{i,j}$$ обозначим вероятность того, что на выходе получено число i, 
если на вход подавалось число j. $$P{0,0}$$=0.9, $$P{0,1}$$=0.2, $$P{0,2}$$=0.9, 
$$P{1,0}$$=0.0, $$P{1,1}$$=0.7, $$P{1,2}$$=0.0, $$P{2,0}$$=0.1, 
$$P{2,1}$$=0.1, $$P{2,2}$$=0.1.
Пусть для этого канала и вектора построен декодер по методу апостериорной 
вероятности. Вероятность ошибочного декодирования для числа 1 равна
{~0.6
=0.3
~0.5
~-0.1
~-0.2}
N3 Случайные величины $$A$$ и $$B$$ принимают в качестве своих значений 
числа от 1 до 3. Через $$P_(i,j)$$ обозначим вероятность того, что $$A\=i,B\=j$$.
$$P_(1,1)\=0, P_(1,2)\=1/32, P_(1,3)\=1/8, P_(2,1)\=1/2, P_(2,2)\=1/8, P_(2,3)\=1/32, 
P_(3,1)\=1/16, P_(3,2)\=1/8, P_(3,3)\=0$$.
Условная энтропия $$A$$ при условии $$B$$ равна:
{~0.237
=0.787
~0.671
~1.389
~0.935}
N4 Дано множество $${4,1,3,2,4,2,1,1}$$. Какое наименьшее число элементов 
нужно выкинуть из него, чтобы существовал двоичный префиксный код, длины 
слов которого равны оставшимся числам множества?
{~5
~2
~1
=3
~4}
N5 Дано распределение,найти собственную информацию заключенную в 
событии $$A\=1 и B\=1$$.Нумерация столбцов и строк начинается с 0.A - номер 
строки. B - номер столбеца. Распределение:
$$(0.0625,0.03125,0.0625);(0.25,0.03125,0.03125);(0.25,0.03125,0.25)$$
{~7
~4
~1
~6
=5}
N6 Какое наименьшее число (возможно и 0) элементов нужно выкинуть из 
множества, длины слов которого составляют $$ 3,7,1,6,2,2,1,5 $$, чтобы 
существовал двоичный префиксный код, с такими длинами слов
{~5
~1
=2
~0
~4
}
N7 Выберите верное значение функции Эйлера от числа $$ 1963 $$
{~794
=1800
~1348
~1390
~1181
}
N8 Дано распределение,найти взаимную информацию между событиями $$A\=2 
и B\=3$$.Нумерация столбцов и строк начинается с 1.A - номер строки.B - номер 
столбеца.Распределение:$$(0.0625,0.25,0.03125);(0.03125,0.25,0.0625);(0.25,0.031
25,0.03125)$$
{=0,541
~-0,541
~0,459
~1,341
~-0,459
}
N9 Найти H(Y|X). Если дана матрица канала связи 
$$(242/245,1/245,2/245);(2/245,242/245,1/245)$$. На вход канала связи подается 
случайный вектор X принимающий значение 0 с вероятностью $$0.00390625$$,а 
значение 1 с вероятностью $$0.99609375$$
{~0,107
~0,243
~0,607
~-0,893
=0,107
}
N10 Вычислите НОД чисел $$286,397$$
{~5
=1
~2
~3
~4
}
N11 Для какого минимального D существует однозначно декодируемый код, 
длины слов которого составляют $$ 1,1,7,7,1 $$
{~3
~6
=4
~7
~8
}