Информационные технологии

Дисциплина  «Теоретические основы информационных технологий и систем»

 

Задания для выполнения практических занятий

Упражнение 1 Каков код букв W и w в ASCII?

Ответ: Десятичный - W- 87, w- 119.

Упражнение 2 В цифровых магнитофонах DAT частота дискретизации - 48КГц. Какова максимальная частота звуковых волн, которые можно точно воспроизводить на таких магнитофонах?

Ответ:   24 КГц , так как в промышленности принимают частоту (согласно теории о выборках) не менее чем в два раза выше наибольшей частоты гармоники, входящей в дискретизируемую величину.

Упражнение 3 Сколько бит в одном килобайте?

1КВ = 8192 bit

Упражнение 4 Какое из соотношений несет в себе больше информации или ?

Ответ:   x=5 несет в себе больше информации чем х > 3.

Упражнение 5 Найти энтропию дискретной случайной величины , заданной распределением

 

Ответ: H(X) = HX = I(X;X):   HX = - log

Упражнение 6 Значения дискретной случайной величины и определяются подбрасыванием двух идеальных монет, а дискретная случайная величина равна сумме количества "гербов", выпавших при подбрасывании этих монет. Сколько информации об содержится в ?

Ответ: Так как монеты идеальные и Y=X +X то можно предположить что X =X , следовательно X содержит в себе  информации о Y.

 

Упражнение 7 Сколько информации об содержится в дискретной случайной величине , где независимые дискретные случайные величины и могут с равной вероятностью принимать значение либо 0, либо 1? Найти и . Каков характер зависимости между и ?

 

X1	0	1
p	0,5	0,5

X2	0	1
p	0,5	0,5

 

 

Z=(x1+1)^2-x2

X1/x2	0	1
0	1	3
1	0	4

Z	0	1	3	4
p	0,25	0,25	0,25	0,25

 

 

 бит/сим

 бит/сим

Упражнение 8 Дискретные случайные величины , - зависимы и распределены также как и соответствующие дискретные случайные величины из предыдущей задачи. Найти , если совместное распределение вероятностей и описывается законом

 

X1	0	1
p	0,5	0,5

X2	0	1
p	0,5	0,5

 

 

I(X1,X2)=2* 1/3 * log₂((1/3)/0,25)+2*1/6 log₂((1/6)/0,25)=1/3(2* log₂(2/3)+ log₂(4/3))=1,04 бит/ сим

Упражнение 9 Дискретные случайные величины и определяются подбрасыванием двух идеальных тетраэдров, грани которых помечены числами от 1 до 4. дискретная случайная величина равна сумме чисел, выпавших при подбрасывании этих тетраэдров, т.е. . Вычислить , и .

Решение:

X1	1	2	3	4
p	0.25	0.25	0.25	0.25

X2	1	2	3	4
p	0.25	0.25	0.25	0.25

 

 

 

Y= X1+ X2

Таблица, определяющая У:

Х1/х2	1	2	3	4
1	2	3	4	5
2	3	4	5	6
3	4	5	6	7
4	5	6	7	8

у	2	3	4	5	6	7	8
р	1/16	2/16	3/16	4/16	3/16	2/16	1/16

 

I(X1;У)=НХ1+НУ-Н(X1;У)= НУ- НХ1

НХ1=log₂4=2 бит/символ

НУ=2*(1/16 log₂16)+2*(2/16 log₂8)+ 2*(3/16 log₂₍16/3))+4/16 log₂4=3.75 бит/символ

I(X1;У)=3,75-2=1,75 бит/символ

 

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

Решение:

X1	1	2	3	4
p	0.25	0.25	0.25	0.25

X2	1	2	3	4
p	0.25	0.25	0.25	0.25

 

 

 

Z= X1*X2

Таблица, определяющая У:

Х1/х2		1		2		3		4
1		1		2		3		4
2		2		4		6		8
3		3		6		9		12
4		4		8		12		16
Z	1		2		3		4		6		8	9	12	16
P	1/16		2/16		2/16		3/16		2/16		2/16	1/16	2/16	1/16

I(X1;Z)=НХ1+НZ-Н(X1;Z)= НZ- НХ1

НХ1=log₂4=2 бит/символ

НZ=3*(1/16 log₂16)+5*(2/16 log₂8)+ 3/16 log₂₍16/3)=2.69 бит/символ

I(X1;У)=2.69-2=0.69 бит/символ

Упражнение 11 Дискретная случайная величина может принимать три значения , 0 и 1 с равными вероятностями. Дискретная случайная величина с равными вероятностями может принимать значения 0, 1 и 2. и - независимы. . Найти , , , , .

Решение:

X1	-1	0	1
p	1/3	1/3	1/3

X2	0	1	2
p	1/3	1/3	1/3

 

 

 

Y= X1^2+X2

Таблица, определяющая Y:

Х1/х2		-1		0		1
0		1		0		1
1		2		1		2
2		3		2		3
Y	1		2		3		0
P	3/9		3/9		2/9		1/9

I(X1;Y)=НХ1+НY-Н(X1;Y)= НY- НХ1=1.95-1.73=0.22

I(X2;Y)=НХ2+НY-Н(X2;Y)= НY- НХ2=0.22

НХ1=log₂3=HX2=1.73 бит/символ

НY=1/9 log₂9+2/9 log₂4.5+ 6/9 log₂3=1.95 бит/символ

I(X1;У)=2.69-2=0.69 бит/символ= I(X2;У)

Упражнение 12 Найти энтропии дискретных случайных величин , , и количество информации, содержащейся в относительно . и - независимы и задаются распределениями

 

Решение:

X	0	1	3	4
p	1/8	1/8	1/4	1/2

Y	-2	2
p	3/8	5/8

 

 

 

Z= X+Y

Таблица, определяющая Z:

Х/Y		0		1		3		4
-2		-2		-1		1		2
2		2		3		5		6
Z	-2		-1		1		2		3		5	6
P	1/8		1/8		1/8		2/8		1/8		1/8	1/8

НХ=1/4*log₂8+1/4* log₂4+1/2* log₂2=1.75 бит/символ

HY=3/8* log₂8/3+5/8* log₂8/5=1.4

НZ=6*(1/8 log₂8)+1/4log₂4=2.75 бит/символ

I(Z;У)=2.75-1.4=1.35 бит/символ

 

Упражнение 13 Найти энтропию д.с.в. и среднюю длину каждого из приведенных кодов для этой д.с.в.

1) Находим энтропию д.с.в.  , как в предыдущем задании:

  ;

.

2) Вычисляем среднее значение длины кода для источника: или .

1. ; ;   бит/символ;

2. ; ;   бит/символ;

3. ; ;   бит/символ;

4. ; ;   бит/символ

Упражнение 14 д.с.в. равна количеству "гербов", выпавших на двух идеальных монетках. Найти энтропию . Придумать минимальный код для , вычислить его среднюю длину и обосновать его минимальность.

X=X1+X2

X1=X2	0		1
p	1/2		1/2
X1/x2		0		1
0		0		1
1		1		0

X	0	1
P	1/2	1/2

 

 

 

HX= log₂2=1 бит/символ

Р(х1)=Р(х2)=0.5

Х	0	1
Р	1/2	1/2
code	0	01

Упражнение 16 Про д.с.в. известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений , результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для .

Решение:

Составим таблицу распределений  для Х

Буква	Появлений	Вероятность	Код	Длина кода
И	4	0,125	0	1
О	2	0,0625	110	3
Р	2	0,0625	111	3
А	1	0,03125	101000	6
E	1	0,03125	101001	6
М	1	0,03125	101011	6
Н	1	0,03125	100110	6
Т	1	0,03125	101111	6
Ф	1	0,03125	101101	6
Ц	1	0,03125	100001	6
Я	1	0,03125	100011	6

 

	P(L(X))	Итого:
L(X)=1	1 / 8	0,125
L(X)=3	1 / 16	0,188
L(X)=6	1 / 32	0,188
		0,5

 

Упражнение 17 Вычислить и предложения , про которое известно, что оно достоверно на 50%, и предложения , достоверность которого 25%.

Ответ:  inf(s) = -log p(s),      

               inf(s ) = -log =1, 

              inf(s ) = -log =2, 

 

Упражнение 18 Вычислить среднее количество бит, приходящихся на одно кодируемое значение д.с.в. для блочного кода Хаффмена. Длина блока - 2 бита. д.с.в. берется из таблицы

 

Решение

X	P	Code(x)
A	0.4	0
B	0.2	11
C	0.4	10

ML(X)=1.6 бит/символ

HX= log₂5-0.8=1.52 бит/символ

 

Упражнение 19 Вычислить энтропию д.с.в. и среднее количество бит, приходящихся на одно кодируемое значение для кодов Хаффмена и Шеннона-Фэно для . д.с.в. задается следующим распределением вероятностей:

Ответ: бит/сим

              /2=1,29  бит/сим

           

X    01              10               11                100              101 p

1

 

Упражнение 20 Закодировать сообщения "AABCDAACCCCDBB", "КИБЕРНЕТИКИ" и "СИНЯЯ СИНЕВА СИНИ", вычислить длины в битах полученных кодов, используя алгоритмы LZW.

Ответ:

 
"AABCDAACCCCDBB" - "D 111 A 10 B 110 C 0 " - "1010110011110100000111110110" - "28"  
"КИБЕРНЕТИКИ" - "И 00 К 011 Н 101 Т 111 Б 100 Р 110 Е 010 " - "011001000101101010101110001100" - "30"  
"СИНЯЯ СИНЕВА СИНИ" - "И 00 111 Н 10 Я 110 А 0110 В 01111 С 010 Е 01110 " - "0100010110110111010001001110011110110111010001000" - "49"