Расчетно-графическая работа по дисциплине «Теоретические основы информационных процессов»

Федеральное агентство по образованию РФ

Государственное образовательное учреждение высшего  профессионального образования

 

 

 

 

 

 

 

 

 

 

 

 

 

Расчетно-графическая  работа

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

Вариант 17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

УФА 2009

Задание 1:

Перевести число из 10-ичной системы  счисления в 2-ичную и обратно.

Исходное число: 117₁₀

 

Решение:

117/2 = 58, остаток 1

58/2 = 29, остаток 0

29/2 = 14, остаток 1

14/2 = 7, остаток 0

7/2 = 3, остаток 1

3/2 = 1, остаток 1

1/2 = 0, остаток 1

 

117₁₀ = 1110101₂

1110101₂ = 1*2⁶ + 1*2⁵ + 1*2⁴ + 0*2³ + 1*2² + 0*2¹ + 1*2⁰ = 64 + 32 + 16 + 4 + 1 = 117₁₀

 

Задание 2:

На вход устройства поступают сообщения  S1..S8 с вероятностями P_i.

Закодировать данные сообщения, используя  процедуры:

1. Шеннона-Фано
2. Хаффмана

и определить среднюю длину кодового слова

 

Исходные данные:

Сообщения	Pi
S1	0.03
S2	0.11
S3	0.02
S4	0.2
S5	0.19
S6	0.02
S7	0.13
S8	0.3

 

1. Кодирование процедурой Шеннона-Фано:

 

Сообщения	Pi	1	2	3	4	5	6
S8	0.3	0	0
S4	0.2	0	1
S5	0.19	1	0
S7	0.13	1	1	0
S2	0.11	1	1	1	0
S1	0.03	1	1	1	1	0
S3	0.02	1	1	1	1	1	0
S6	0.02	1	1	1	1	1	1

 

0.3
0.2
0.19
0.13
0.11
0.03
0.02
0.02

 

 

Сообщения	Коды	Pi	Длина
S1	11110	0.03	5
S2	1110	0.11	4
S3	111110	0.02	6
S4	01	0.2	2
S5	10	0.19	2
S6	111111	0.02	6
S7	110	0.13	3
S8	00	0.3	2

Определим эффективность построенного кода по формуле

= 0.3*2+0.2*2+0.19*2+0.13*3+0.11*4+0.03*5+0.02*6+0.02*6 = 2.6 (бит/сообщение)

 

 

2. Кодирование процедурой Хаффмана:

 

Шаги:

1. S8_0.3 S4_0.2 S5_0.19 S7_0.13 S2_0.11 (S3_0.02 + S6_0.02)_0.04 S1_0.03
2. S8_0.3 S4_0.2 S5_0.19 S7_0.13 S2_0.11 ((S3_0.02 + S6_0.02)_0.04 + S1_0.03) _0.07
3. S8_0.3 S4_0.2 S5_0.19 (S2_0.11 + ((S3_0.02 + S6_0.02)_0.04 + S1_0.03) _0.07) _0.18 S7_0.13
4. (S2_0.11 + ((S3_0.02 + S6_0.02)_0.04 + S1_0.03) _0.07) _0.18 + S7_0.13) _0.31 S8_0.3 S4_0.2 S5_0.19
5. (S4_0.2 + S5_0.19) _0.39
6. ((S2_0.11 + ((S3_0.02 + S6_0.02)_0.04 + S1_0.03) _0.07) _0.18 + S7_0.13) _0.31 S8_0.3) _0.61 (S4_0.2 + S5_0.19) _0.39
7. (((S2_0.11 + ((S3_0.02 + S6_0.02)_0.04 + S1_0.03) _0.07) _0.18 + S7_0.13) _0.31 S8_0.3) _0.61 + (S4_0.2 + S5_0.19) _0.39)₁

 

Сообщения	Коды	Pi	Длина
S1	00011	0.03	5
S2	0000	0.11	4
S3	000101	0.02	6
S4	10	0.2	2
S5	11	0.19	2
S6	000100	0.02	6
S7	001	0.13	3
S8	01	0.3	2

Определим эффективность построенного кода по формуле

= 0,03*5+0,11*4+0,02*6+0,2*2+0,19*2+0,02*6+0,13*3+0,3*2= 2.6 (бит/сообщение)

 

 

Задание 3:

Построить B-дерево пошагово, добавляя следующие ключи (k..k).

Затем удалить 3, 5, 7 ключ пошагово из приведенного списка.

 

Пошаговое добавление ключей:

Шаг 1 – 18

Шаг 2 – 1

Шаг 3 – 5

Шаг 4 – 16

Шаг 5 – 55

Шаг 6 – 27

Шаг 7 – 19

Шаг 8 – 20

Шаг 9 – 26

Шаг 10 – 8

Шаг 11 – 6

 

 

 

Пошаговое удаление ключей 3, 5, 7

Ключ 3 – 5

Ключ 5 – 55

Ключ 7 – 19