Методические рекомендации для студентов по выполнению практических работ по дисциплине «Основы теории информации»

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ Государственное бюджетное образовательное учреждение среднего профессионального образования города Москвы «Московский колледж градостроительства и предпринимательства» (ГБОУ СПО МКГП)

 

 

 

 

 

 

 

 

 

 

Методические рекомендации

для студентов

по выполнению практических работ

 

по дисциплине «Основы теории информации»

 

  специальности   230701 Прикладная информатика (по отраслям)

 

курс 2

 

 

Преподаватель: Ким Игорь Васильевич

 

 

 

 

 

 

 

 

 

 

 

Москва

2013
                                                                       УТВЕРЖДАЮ

Заместитель директора по учебно-методической  работе

_____________С.В.  Насибова «___»_______________20___г.

 

Методические рекомендации 

для студентов по выполнению

практических работ

по дисциплине «  Основы теории информации » 

по специальности:   230701

Прикладная информатика (по отраслям)

рассмотрены и одобрены на заседании

ВПЦК  ВТ и КСПД

Протокол № ____от___________20___г

Председатель:_________   И.К.Воронова

                                                    подпись                                ФИО

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая работа № 1.

Представление числовой информации с помощью систем счисления.

 

Цель работы: познакомиться с алгоритмами представления десятичных целых, отрицательных и вещественных чисел в памяти ЭВМ.

 

Краткие теоретические сведения.

Все числовые данные хранятся в машине в двоичном виде, т.е. в виде последовательности нулей и единиц, однако формы хранения целых и действительных чисел различны.

Для представления чисел в памяти ПК используются два формата:

-формат с фиксированной точкой (запятой) целые числа;

-формат с плавающей точкой (запятой) вещественные числа.

Представление целых чисел

Множество целых чисел, представленных в ЭВМ, ограничено. Диапазон значений зависит от размера ячеек памяти, используемых для их хранения.

Для целых чисел существуют два представления:

-беззнаковое;

-со знаком.

В К-разрядной ячейке может храниться 2^к различных значений целых чисел.

Диапазон значений целых беззнаковых чисел (только положительные):

от 0 до 2^к - 1

для 16-разрядной ячейки от 0 до 65535

для 8-разрядной ячейки от 0 до 255

Диапазон значений целых чисел со знаком (и отрицательные, и положительные в равном количестве):

от -2^к-1 до 2^к-1-1

для 16-разрядной ячейки от -32768 до 32767

для 8-разрядной ячейки от -128 до 127

Чтобы получить внутреннее представление целого положительного числа N, хранящегося в К-разрядной ячейке, необходимо:

1. перевести число N в двоичную систему счисления;

2. полученный результат дополнить слева незначащими нулями до К разрядов.

Пример:

Получить внутреннее представление целого числа 1607 в 2-х байтовой ячейке.

Решение:

N=1607=11001000111₂.

Внутреннее представление этого числа будет: 0000 0110 0100 0111. Шестнадцатеричная форма внутреннего представления числа: 0647.

Для представления целого отрицательного числа используется дополнительный код.

Дополнительным кодом двоичного числа X в N-разрядной ячейке является число, дополняющее его до значения 2^N.

Получение дополнительного кода:

1. получить внутреннее представление положительного числа N (прямой код);

2. получить обратный код этого числа заменой 0 на 1 или 1 на 0 (обратный код);

3. к полученному числу прибавить 1.

Положительное число в прямом, обратном и дополнительном кодах не меняют свое изображение.

Использование дополнительного кода позволяет заменить операцию вычитания на операцию сложения.

A-B=A+(-B).

Процессору достаточно уметь лишь складывать числа.

Старший, К-й разряд во внутреннем представлении любого положительного числа равен 0, отрицательного числа равен 1. Поэтому этот разряд называется знаковым разрядом

Пример:

Получить внутреннее представление целого отрицательного числа - 1607.

Решение:

1. Внутреннее представление положительного числа: 000 0110 0100 0111;

2. Обратный код: 1111 1001 1011 1000;

3. Дополнительный код: 1111 1001 1011 1001 - внутреннее двоичное представление числа.

16-ричная форма: F9B9.

 Представление вещественных чисел

Вещественные числа представляются в ПК в форме с плавающей точкой.

Этот формат использует представление вещественного числа R в виде произведения мантиссы m на основание системы счисления p в некоторой целой степени n которую называют порядком:

R=m*pⁿ

Представление числа в форме с плавающей точкой неоднозначно.

Например: 25.324=25324*10¹=0.0025324*10⁴=2532.4*10^-2

В ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в нормализованном представлении должна удовлетворять условию: 0.1_p m<1_p

Иначе говоря, мантисса меньше 1 и первая значащая цифра - не 0.

В памяти компьютера мантисса представляется как целое число, содержащее только значащие цифры (0 целых и запятая не хранится). Следовательно, внутреннее представление вещественного числа сводиться к представлению пары целых чисел: мантиссы и порядка.

Например: 4-x байтовая ячейка памяти. В ячейке должна содержаться следующая информация о числе:

- знак числа;

- порядок;

- значащие цифры мантиссы.

В старшем бите 1-го байта хранятся знак числа: 0 обозначает плюс, 1 - минус.

Оставшиеся 7 бит 1-го байта содержат машинный порядок. В следующих трех байтах хранятся значащие цифры мантиссы (24 разряда).

В семи двоичных разрядах помещаются двоичные числа в диапазоне от 0000000 до 1111111. Значит, машинный порядок изменяется в диапазоне от 0 до 127 (в десятичной системе счисления). Всего 128 значений. Порядок, очевидно, может быть как положительным так и отрицательным. Разумно эти 128 значений разделить поровну между положительным и отрицательным значениями порядка: от -64 до 63.

Машинный порядок смещен относительно математического и имеет только положительные значения. Смещение выбирается так, чтобы минимальному математическому значению порядка соответствовал нуль.

Связь между машинным порядком (Мр) и математическим (р) в рассматриваемом случае выражается формулой:

Мр = р + 64

Полученная формула записана в десятичной системе. В двоичной системе формула имеет вид: Mp₂=p₂+1000000₂

Для записи внутреннего представления вещественного числа необходимо:

1) перевести модуль данного числа в двоичную систему счисления с 24 значащими цифрами;

2) нормализовать двоичное число;

3) найти машинный порядок в двоичной системе счисления;

4) учитывая знак числа, выписать его представление в 4-х байтовом машинном слове.

Пример

Записать внутреннее представление числа 250,1875 в форме с плавающей точкой.

Решение:

1) Приведем его в двоичную систему счисления с 24 значащими цифрами: 250.1875₁₀=11111010, 001100000000000000₂.

2) Запишем в форме нормализованного двоичного числа с плавающей точкой: 0,111110100011000000000000*10₂¹⁰⁰⁰. Здесь мантисса, основание системы счисления (2₁₀=10₂) и порядок (8₁₀=1000₂) записаны в двоичной системе.

3) Вычислим машинный порядок в двоичной системе счисления: Mp₂= 1000 + 100 0000 =100 1000.

4) Запишем представление числа в 4-х байтовой ячейке памяти с учетом знака числа:

Шестнадцатеричная форма: 48FA3000.

 

Пример.

По шестнадцатеричной форме внутреннего представления числа в форме с плавающей точкой C9811000 восстановить само число.

Решение: 1) Перейдем к двоичному представлению числа в 4-х байтовой ячейке, заменив каждую шестнадцатеричную цифру 4-мя двоичными цифрами:

1100 1001 1000 0001 0001 0000 0000 0000

 

2) Заметим, что получен код отрицательного числа, поскольку в старшем разряде с номером 31 записана 1. Получим порядок числа: р=1001001₂ -1000000₂=1001₂=9₁₀.

3) Запишем в форме нормализованного двоичного числа с плавающей точкой с учетом знака числа:

-0,100000010001000000000000 *2¹⁰⁰¹

4) Число в двоичной системе счисления имеет вид: -100000010.001₂.

5) Переведем число в десятичную систему счисления:

-100000010.001₂= -(1*2⁸+1*2¹+1*2^-3)= -258.125₁₀

 Задание для решений №1

1) Получить двоичную форму внутреннего представления целого числа в 2-х байтовой ячейке.

2) Получить шестнадцатеричную форму внутреннего представления целого числа 2-х байтовой ячейке.

3) По шестнадцатеричной форме внутреннего представления целого числа в 2-х байтовой ячейке восстановить само число.

 

Задание для решений №2

1) Получить шестнадцатеричную форму внутреннего представления числа в формате с плавающей точкой в 4-х байтовой ячейке.

2) По шестнадцатеричной форме внутреннего представления вещественного числа в 4-х байтовой ячейке восстановить само число.

 

Контрольные вопросы:

1.      Как представляют целые числа?

2.      Что используется для представления целого отрицательного числа?

3.      Какие числа не меняют изображения?

4.      Какой разряд называется знаковым разрядом?

5.      Что называется нормализованным представление числа в форме с плавающей точкой?

 

 

Практическая  работа № 2

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

 

 Цель работы: познакомиться с правилами недесятичной арифметики. Выработать навыки перевода чисел.

 

Краткие теоретические сведения.

Перевод чисел из одной системы счисления в другую.

Перевод чисел в десятичную систему осуществляется путем составления

степенного ряда с основанием той системы, из которой число переводится. Затем

подсчитывается значение суммы.

Двоичная арифметика.

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

Восьмеричная система счисления. Используется восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7.

Употребляется в ЭВМ как вспомогательная для записи информации в сокращенном виде. Для представления одной цифры восьмеричной системы используется три двоичных разряда (триада) (Таблица 1).

Шестнадцатеричная система счисления. Для изображения чисел употребляются 16 цифр. Первые десять цифр этой системы обозначаются цифрами от 0 до 9, а старшие шесть цифр латинскими

буквами: 10=A,

11=B,

12=C,

13=D,

14=E,

15=F.

Шестнадцатеричная система используется для записи информации в сокращенном виде. Для представления одной цифры шестнадцатеричной системы счисления используется четыре двоичных разряда (тетрада)

 

Задание №1

Переведите данное число из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную системы счисления.

772(10).

71(10).

284.375(10).

876.5(10).

281.86(10).

 

Задание № 2.

Переведите данное число в десятичную систему счисления.

1000001111(2).

1010000110(2).

101100110.011011(2).

100100110.101011(2).

1022.2.

53.9(16).

 

Задание № 3.

Сложите числа.

1100111(2)+1010111000(2).

1101111010(2)+1000111100(2).

1111101110.01(2)+1110001.011(2)

153.3(8)+1347.2(8).

e0.2(16)+1e0.4(16).

 

Задание № 4.

Выполните вычитание.

1010101110(2)-11101001(2).

1000100010(2)-110101110(2).

1010100011.011(2)-1000001010.001(2).

1517.64(8)-1500.30(8).

367.6(16)-4a.c(16).

 

Задание № 5.

Выполните умножение.

1100110(2)*101111(2).

1272.3(2)*23.14(8).

48.4(16)*5.a(16).

 

Контрольные вопросы:

1. Какая система счисления называется двоичной?

2.      Какая система счисления называется восьмеричной?

3.      Какая система счисления называется шестнадцатеричной?

4.      Как производится перевод из одной системы счисления в другой?

 

 

Практическая работа № 3.

Перевод из одной системы счисления в другую.

 

Цель: научиться переводить числа из одной системы счисления в другую.

 

Краткие теоретические сведения.

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

Все системы счисления делятся на позиционные и непозиционные.

Непозиционными системами являются такие системы счисления, в которых каждый символ сохраняет свое значение независимо от места его положения в числе. Примером непозиционной системы счисления является римская система. К недостаткам таких систем относятся наличие большого количества знаков и сложность выполнения арифметических операций.

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

Количество p различных цифр, употребляемых в позиционной системе определяет название системы счисления и называется основанием системы счисления "p".

В десятичной системе используются десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; эта система имеет основанием число десять.

Задание 1. Запишите развернутую и краткую формы записи любого числа.

В ЭВМ применяют позиционные системы счисления с недесятичным основанием: двоичную, восьмеричную, шестнадцатеричную. В аппаратной основе ЭВМ лежат двухпозиционные элементы, которые могут находиться только в двух состояниях; одно из них обозначается 0, а другое 1. Поэтому основной системой счисления применяемой в ЭВМ является двоичная система.

Двоичная система счисления.  Используется две цифры: 0 и 1.

Восьмеричная система счисления. Используется восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7.

Употребляется в ЭВМ как вспомогательная для записи информации в сокращенном виде. Для представления одной цифры восьмеричной системы используется три двоичных разряда (триада) (Таблица 1).

Шестнадцатеричная система счисления. Для изображения чисел употребляются 16 цифр. Первые десять цифр этой системы обозначаются цифрами от 0 до 9, а старшие шесть цифр латинскими

буквами: 10=A,

11=B,

12=C,

13=D,

14=E,

15=F.

Шестнадцатеричная система используется для записи информации в сокращенном виде. Для представления одной цифры шестнадцатеричной системы счисления используется четыре двоичных разряда (тетрада) (Таблица 1).

Таблица 1. Наиболее важные системы счисления.

Перевод чисел из одной системы счисления в другую.

Перевод чисел в десятичную систему осуществляется путем составления

степенного ряда с основанием той системы, из которой число переводится. Затем

подсчитывается значение суммы.

Задание 2.

Перевести 10101101.101 из «2» в «16», «8» и «10» с.с.

При одновременном использовании нескольких различных систем счисления основание системы, к которой относится число, указывается в виде нижнего индекса.

Задание 3. Переведите самостоятельно.

а) Перевести 703.048 из «10» в «2», затем в «8» и наконец, в «16»

б) Перевести B2E.416 из «16» в «10», затем в «8».

Перевод целых десятичных чисел в недесятичную систему счисления осуществляется последовательным делением десятичного числа на основание той системы, в которую оно переводится, до тех пор, пока не получится частное меньшее этого основания. Число в новой системе записывается в виде остатков деления, начиная с последнего.

Задание 4.

а) Перевести 18110 из «10» в «2».

б) Перевести 62210 из «8» в «2», затем в «10».

 

Перевод правильных дробей из десятичной системы счисления в недесятичную.

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

Задание 5. Перевести 0.312510

Замечание. Конечной десятичной дроби в другой системе счисления может  соответствовать бесконечная (иногда периодическая) дробь. В этом случае количество знаков в представлении дроби в новой системе берется в зависимости от требуемой точности.

Задание 6. Перевести 0.6510 из «10» в «2» с.с. Точность 6 знаков.

Для перевода неправильной десятичной дроби в систему счисления с недесятичным основанием необходимо отдельно перевести целую часть и отдельно дробную.

Задание 7.

Перевести 23.12510 из «10» в «2» с.с.

Необходимо отметить, что целые числа остаются целыми, а правильные дроби дробями в любой системе счисления. Для перевода восьмеричного или шестнадцатеричного числа в двоичную форму достаточно заменить каждую цифру этого числа соответствующим трехразрядным двоичным числом (триадой) (Таб. 1) или четырехразрядным двоичным числом (тетрадой) (Таб. 1), при этом отбрасывают ненужные нули в старших и младших разрядах.

Задание 8.

а)Перевести 305.47 из «8» в «10» с.с.

б)Перевести 7B2.E16 из «16» в «10».

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

Двоичная арифметика.

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

Задание 11. Выполнить сложение двоичных чисел:

а) X=1101, Y=101;

б) X=1101, Y=101, Z=111;

При вычитании двоичных чисел в данном разряде при необходимости занимается 1 из старшего разряда. Эта занимаемая 1 равна двум 1 данного разряда.

Задание 12. Заданы двоичные числа X=10010 и Y=101. Вычислить X-Y.

Умножение двоичных чисел производится по тем же правилам, что и для десятичных с помощью таблиц двоичного умножения и сложения.

Пример. 1001* 101=?

Деление двоичных чисел производится по тем же правилам, что и для десятичных. При этом используются таблицы двоичного умножения и вычитания.

Пример. 1100.011 : 10.01=

Самостоятельная работа.

Выполнить перевод числа в соответствии с вариантом.

1. Перевести десятичное число А=121 в двоичную систему счисления.

2. Перевести двоичное число А=10001010111,01 в десятичную систему

счисления.

3. Перевести десятичное число А=135,656 в двоичную систему счисления с

точностью до пяти знаков запятой.

4. Перевести двоичное число А=10111011 в десятичную систему счисления

методом деления на основание.

5. Перевести восьмеричное число А=345,766 в двоичную систему счисления.

6. Записать десятичное число А=79,346 в двоичнодесятичной

форме.

7. Перевести десятичную дробь 64

A = 63 9 в двоичную систему счисления.

8. Перевести десятичное число А=326 в троичную систему счисления.

9. Перевести десятичную дробь 40

A = 63 5 в двоичную систему счисления.

10. Перевести десятичное число А=15,647 в двоичную систему счисления.

11. 12. Перевести десятичную дробь А=0,625 в двоичную систему счисления.

13. Перевести двоичную дробь А=0,1101 в десятичную систему счисления.

14. Перевести десятичное число А=113 в двоичную систему счисления.

15. Перевести двоичное число А=11001,01 в десятичную систему счисления.

16. Перевести десятичное число А=96 в троичную систему счисления.

 

Контрольные вопросы:

1. Как переводят правильную дробь из десятичной системы счисления в недесятичную?

2.      Как осуществляется перевод из восьмеричной в двоичную?

3.      Как осуществляется перевод в 64 систему счисления?

4.      Как осуществляется перевод в 3 систему счисления?

5.      Как осуществляется перевод в 5 систему счисления?

Практическая работа № 4.

Кодирование и декодирование информации

 

Цель работы: криптоанализ и программная реализация алгоритмов перестановок для шифрования и дешифрования исходного текста.

 

Краткие теоретические сведения.

Шифры перестановки

Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки (ШП).

Пусть имеем сообщение из n символов. Его можно представить с помощью таблицы:

где i₁ - номер места зашифрованного текста, на которое попадает I-ая буква исходного сообщения при выбранном преобразовании, i₂ - номер места для II-й буквы и т.д. В верхней строке таблицы выписаны по порядку числа от 1 до n, а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени n.

Зная подстановку, задающую преобразование, можно как зашифровать, так и расшифровать текст.

Например, если для преобразования используется подстановка:

и в соответствии с ней зашифровывается слово МОСКВА, то получится слово КОСМВА.

Итак, используя метод математической индукции, определим, что существует n! вариантов заполнения нижней строки таблицы. Т.е. число различных преобразований шифра перестановки, предназначенного для зашифрования сообщения длины n, меньше либо равно n!. При больших n для вычисления n! можно пользоваться формулой Стирлинга:

.

 Примером ШП, предназначенного для зашифрования сообщения длины n, является шифр, в котором в качестве множества ключей взято множество всех подстановок степени n. Число ключей такого шифра =n!.

Для использования на практике такой шифр не удобен, т.к. при больших значениях n приходится работать с длинными таблицами.

Примеры простейших шифров перестановок

Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного «маршрута», а затем по ходу другого выписывается из нее. Такой шифр называют маршрутной перестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Используем прямоугольник размера 4×7

è

П	Р	И	М	Е	Р	М	ê
Н	Т	У	Р	Ш	Р	А	ç
О	Й	П	Е	Р	Е	С	ê
И	К	В	О	Н	А	Т	ç

Выписывать будем по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.

МАСТАЕРРЕШРНОЕРМИУПВКЙТРПНОИ

Теоретически, маршруты могут быть более изощренными.

Шифр «Сцитала» эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из m столбцов, построчно записывается сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения.

Из истории имеются еще чисто физические ограничения, накладываемые реализацией шифра Сцитала. Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 см на одном витке такого жезла уместится не более 32 букв (10π <32). Таким образом, число перестановок, реализуемых Сциталой, не больше 32.

Шифр вертикальной перестановки (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:

5	1	4	7	2	6	3
В	О	Т	П	Р	И	М
Е	Р	Ш	И	Ф	Р	А
В	Е	Р	Т	И	К	А
Л	Ь	Н	О	Й	П	Е
Р	Е	С	Т	А	Н	О
В	К	И	-	-	-	-

Выбирая столбцы в порядке, заданном ключом, выписываем последовательно буквы сверху вниз:

ОРЕЬЕКРФИЙА-МААЕО-ТШРНСИВЕВЛРВИРКПН-ПИТОТ-

Число ключей ШВП не более m!, где m - число столбцов таблицы. Пользуясь формулой Стирлинга, при больших m и n можно оценить, во сколько раз n! больше m!, если n кратно m.

В случае, когда ключ не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения.

Например, пусть ключевым словом будет ПЕРЕСТАНОВКА. Буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Таким образом, второе вхождение А получает номер 2. Поскольку Б нет, то В получает номер 3 и т.д., пока все буквы не получат номера:

ПП	ЕЕ	РР	ЕЕ	СС	ТТ	АА	НН	ОО	ВВ	КК	АА
(9	44	110	55	111	112	11	77	88	33	66	22

 

Транспозиция с фиксированным периодом d. В этом случае сообщение делится на группы символов длины d и к каждой группе применяется одна и та же перестановка. Эта перестановка является ключом; она может быть задана некоторой перестановкой первых d целых чисел. Таким образом, для d=5 в качестве перестановки можно взять: 23154. Это будет означать, что:

 

переходит в:

.

Последовательное применение двух или более транспозиций будет называться составной транспозицией. Если периоды этих транспозиций d₁,..., d_s, то, очевидно, в результате получится транспозиция периода d, где d - наименьшее общее кратное d₁,..., d_s.

 

Задание

1.      Используя один из криптографических алгоритмов перестановок, составить программу для шифрования и дешифрования текста.

2.      Подсчитать количество возможных ключей выбранного шифра, оценить стойкость шифра перестановок, сравнить с шифрами замены, сделать выводы.

 

 

 Контрольные вопросы

1.        Что называют шифрами перестановок? Дать определение и привести общий алгоритм.

2.        Какие алгоритмы шифров перестановок используются на практике?

3.        К какому классу относится древний шифр Сцитала, разновидностью какого шифра он является и как реализуется?

4.        Какой шифр называют шифром маршрутной перестановки?

5.        В чем смысл шифра вертикальной перестановки?

6.        Для чего применяется формула Стирлинга?

7.        Что такое транспозиция?

8.        Каков ключ составной транспозиции?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая работа № 5.

Алфавитное неравномерное двоичное кодирование

 

Цель работы: исследование простейших методов криптографической зашиты информации.

 

Краткие теоретические сведения.

Шифры простой замены

Система шифрования Цезаря - частный случай шифра простой замены. Метод основан на замене каждой буквы сообщения на другую букву того же алфавита, путем смещения от исходной буквы на K букв.

Известная фраза Юлия Цезаря

VENI VI D I VICI, где

A

B

C

D

E

F

G

H

I

G

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

пришел, увидел, победил, зашифрованная с помощью данного метода, преобразуется в

SBKF SFAF SFZF

при смещении на 4 символа влево.

Греческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером 5*5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в зашифрованное сообщение букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.

M	T	L	E	X
A	K	F	Q	Y
N	B	R	O	W
C	J	H	D	P
U	I	S	G	V

Схема шифрования Вижинера. Таблица Вижинера представляет собой квадратную матрицу с n² элементами, где n — число символов используемого алфавита. На рисунке показана верхняя часть таблицы Вижинера для кириллицы. Каждая строка получена циклическим сдвигом алфавита на символ. Для шифрования выбирается буквенный ключ, в соответствии с которым формируется рабочая матрица шифрования.

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

Таблица Вижинера

Осуществляется это следующим образом. Из полной таблицы выбирается первая строка и те строки, первые буквы которых соответствуют буквам ключа. Первой размещается первая строка, а под нею — строки, соответствующие буквам ключа в порядке следования этих букв в ключе шифрования.  Пример  такой  рабочей  матрицы для ключа «книга» приведен на Рис. 3.1.3.

Процесс шифрования осуществляется следующим образом:

1. под каждой буквой шифруемого текста записываются буквы ключа. Ключ при этом повторяется необходимое число раз.

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

3. полученный текст может разбиваться на группы по несколько знаков.

Пусть, например, требуется зашифровать сообщение: максимально допустимой ценой является пятьсот руб. за штуку. В соответствии с первым правилом записываем под буквами шифруемого текста буквы ключа. Получаем: 

максимально  допустимой   ценой  является пятьсот руб. за штуку

книгакнигак  нигакнигак   нигак  нигакниг акнигак ниг  ак нигак

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

ж

з

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

ж

з

и

й

к

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

 

Дальше осуществляется непосредственное шифрование в соответствии со вторым правилом, а именно: берем первую букву шифруемого текста (М) и соответствующую ей букву ключа (К); по букве шифруемого текста (М) входим в рабочую матрицу шифрования и выбираем под ней букву, расположенную в строке, соответствующей букве ключа (К),— в нашем примере такой буквой является Ч; выбранную таким образом букву помещаем в зашифрованный текст. Эта процедура циклически повторяется до зашифрования всего текста.

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

 

Расшифровка текста производится в следующей последовательности:

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

2.                  в строке подматрицы Вижинера, соответствующей букве ключа отыскивается буква, соответствующая  знаку  зашифрованного  текста.  Находящаяся   под ней буква первой строки подматрицы и будет буквой исходного  текста.

3.                  полученный текст группируется в слова по смыслу.

     Нетрудно видеть, что процедуры как прямого, так и обратного преобразования являются строго формальными, что позволяет реализовать их алгоритмически. Более того, обе процедуры легко реализуются по одному и тому же алгоритму.

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

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

С целью повышения стойкости шифрования можно использовать усовершенствованные варианты таблицы Вижинера. Приведем только некоторые из них:

·  во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке.

·  В качестве ключа используется случайность последовательных чисел. Из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10. Эти строки используются в соответствии с чередованием цифр в выбранном ключе.

   

 Известны также и многие другие модификации метода.

Алгоритм перестановки

Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Рассмотрим некоторые разновидности этого метода, которые могут быть использованы в автоматизированных системах.

Самая простая перестановка — написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы

     ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ.

получится такой шифротекст:

     ИЛЕТО ХЫМКА ККАТТ ЕДУБЪ ТСУП

В последней группе (пятерке) не хватает одной буквы. Значит, прежде чем шифровать исходное выражение, следует его дополнить незначащей буквой

(например, О) до числа, кратного пяти:

     ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительные изменения, будет выглядеть по-другому:

      ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

Кажется, ничего сложного, но при расшифровке проявляются серьезные неудобства.

Во время Гражданской войны в США в ходу был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки незначащими буквами).

     П  У  С  Т  Ь  Б  У  Д  Е  Т  Т  А  К  К  А

     К  М  Ы  Х  О  Т  Е  Л  И  К  Л  М  Н  О  П

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

    ПКУМС  ЫТХЬО  БТУЕД  ЛЕИТК  ТЛАМК  НКОАП

Если строки укоротить, а количество строк увеличить, то получится прямоугольник-решетка, в который можно записывать исходный текст. Но тут уже потребуется предварительная договоренность между адресатом и отправителем посланий, поскольку сама решетка может быть различной длины-высоты, записывать к нее можно по строкам, по столбцам, по спирали туда или по спирали обратно, можно писать и по  диагоналями, а для шифрования можно брать тоже различные направления.

Шифры сложной замены

Шифр Гронсфельда состоит в модификации шифра Цезаря числовым ключом. Для этого под буквами сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Зашифрованное сообщение получают примерно также, как в шифре Цезаря, но используют не одно жестко заданное смещение а фрагменты ключа.

Пусть в качестве ключа используется группа из трех цифр – 314, тогда сообщение

С О В Е Р Ш Е Н Н О С Е К Р Е Т Н О

3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 

 

Ф П Ё С Ь З О С С А Х З Л Ф З У С С

 

В шифрах многоалфавитной замены для шифрования каждого символа исходного сообщения применяется свой шифр простой замены (свой алфавит).

 

 

Каждая строка в этой таблице соответствует одному шифру замены аналогично шифру Цезаря для алфавита, дополненного пробелом. При шифровании сообщения его выписывают в строку, а под ним ключ. Если ключ оказался короче сообщения, то его циклически повторяют. Зашифрованное сообщение получают, находя символ в колонке таблицы по букве текста и строке, соответствующей букве ключа. Например, используя ключ АГАВА, из сообщения ПРИЕЗЖАЮ ШЕСТОГО получаем следующую шифровку:

ПРИЕЗЖАЮ_ШЕСТОГО

АГАВААГАВААГАВАА

ПОИГЗЖЮЮЮШЕПТНГО

Такая операция соответствует сложению кодов ASCII символов сообщения и ключа по модулю 256.

 

Задание

Придумайте 3 фразы, каждая минимум из 7 слов. Реализуйте шифрование этой фразы всеми перечисленными видами шифрования.

 

Контрольные вопросы:

6.      В чем заключается система шифрования Цезаря?

7.      Как используется схема Вижинера?

8.      Объясните сущность алгоритма перестановки

9.      Из чего состоит Шифр Гронсфельда?

10.  Как производится расшифровка текста?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая работа № 6.

Решение задач с использованием оптимального кодирования информации

 

Цель: Познакомиться с различными кодировками символов, используя текстовые редакторы, выполнить задания в различных текстовых приложениях.

 

Краткие теоретические сведения

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

Пример:

Рассмотрим последовательность строчных букв русского алфавита: а, б, в, г, д, е, ё, ж, з, и, й. к, л, м. н. о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, в, э, ю, я. Присвоив каждой букве номер от 0 до 33. получим простейший способ представления символов. Последнее число - 32 в двоичной форме имеет вид 100000, то есть для хранения символа в памяти понадобится 6 бит.Так как с помощью шести бит можно представить число 2⁶ - 1 = 63, то шести бит будет достаточно для представления 64 букв.

Имеются разные стандарты для представления, символов, которые отличаются лишь порядком нумерации символов. Наиболее распространён американский стандартный код для информационного обмена - ASCII [American Standard-Code for Information Interchange] введён в США в 1963г. В 1977 году в несколько модифицированном виде он был принят в качестве всемирного стандарта Международной организации стандартов [International Standards Organization -. ISO] под названием ISO-646. Согласно этому стандарту каждому символу поставлено в соответствие число от 0 до 255. Символы от 0 до 127 - латинские буквы, цифры и знаки препинания - составляют постоянную часть таблицы. Остальные символы используются для представления национальных алфавитов. Конкретный состав этих символов определяется кодовой страницей. В русской версии ОC Windows95 используется кодовая, страница 866. В ОС Linux для представления русских букв более употребительна кодировка КОИ-8. Недостатки такого способа кодировки национального, алфавита очевидны. Во-первых, невозможно одновременное представление русских и ,например, французских букв. Во-вторых, такая кодировка совершенно непригодна для представления, китайских иероглифов. В 1991 году была создана некоммерческая организация Unicode, в которую входят представители ряда фирм (Borland. IBM, Noyell, Sun и др) и которая занимается развитием и внедрением нового стандарта. Кодировка Unicode использует 16 разрядов ,и может содержать 65536 символов. Это символы большинства народов мира, элементы иероглифов, спецсимволы, 5000 – мест для частного использования, резерв из 30000 мест.

Пример:

ASCII-код символа А= 65₁₀ =41₁₆= 01000111₂;

Unicode-код символа С= 67₁₀=0000000001100111₂

 

Задания                                                                                                                        

1.                      Закодируйте свое имя, фамилию и отчество с помощью одной из таблиц (win-1251, KOI-8)

2.                      Раскодируйте ФИО соседа

3.                      Закодируйте следующие слова, используя таблицы ASCII-кодов: ИНФОРМАТИЗАЦИЯ, МИКРОПРОЦЕССОР, МОДЕЛИРОВАНИЕ

4.                      Раскодируйте следующие слова, используя таблицы ASCII-кодов:

88 AD E4 AE E0 AC A0 E2 A8 AA A0

50 72 6F 67 72 61 6D

43 6F 6D 70 75 74 65 72 20 49 42 4D 20 50 43

5. Текстовый редактор Блокнот

Открыть блокнот.

а) Используя клавишу Alt и малую цифровую клавиатуру раскодировать фразу: 145 170 174 224 174 255 170 160 173 168 170 227 171 235; 

Технология выполнения задания: При удерживаемой клавише Alt, набрать на малой цифровой клавиатуре указанные цифры. Отпустить клавишу Alt, после чего в тексте появится буква, закодированная набранным кодом.

б) Используя ключ к кодированию, закодировать слово  – зима;

Технология выполнения задания: Из предыдущего задания выяснить, каким кодом записана буква а. Учитывая, что буквы кодируются в алфавитном порядке, выяснить коды остальных букв.

Что вы заметили при выполнении этого задания во время раскодировки? Запишите свои наблюдения.

6. Текстовый процессор  MS Word.

Технология выполнения задания: рассмотрим на примере: представить в различных кодировках слово Кодировка

Решение:

·  Создать новый текстовый документ в Word;

·  Выбрать  – Команда –  Вставка – Символ.          
В открывшемся окне «Символ» установить из: Юникод (шестн.),

·  В наборе символов находим букву  К и щелкнем на ней левой кнопкой мыши (ЩЛКМ).

·  В строке код знака  появится код выбранной буквы 041А (незначащие нули тоже записываем).

·  У буквы о код – 043Е и так далее: д – 0434, и – 0438, р – 0440, о – 043Е, в – 0432, к – 043А, а – 0430.

·  Установить Кириллица (дес.)

·  К – 0202, о – 0238, д – 0228, и – 0232, р – 0240, о – 0238, в –0226, к – 0202, а –0224.

7. Открыть Word.

Используя окно «Вставка символа» выполнить задания: Закодировать слово Forest

а) Выбрать шрифт Courier New, кодировку ASCII(дес.) Ответ: 70 111 114 101 115 116
б) Выбрать шрифт Courier New, кодировку Юникод(шест.) Ответ: 0046 006F 0072 0665 0073 0074

в) Выбрать шрифт Times New Roman, кодировку Кирилица(дес.) Ответ: 70 111 114 101 115 116

г) Выбрать шрифт Times New Roman, кодировку ASCII(дес.) Ответ: 70 111 114 101 115 116

Вывод: _________________________________________________________

Выполнение лабораторной работы оформить в виде таблицы.

 

8. Буква Z  имеет десятичный код 90, а z – 122. Записать слово «sport» в десятичном коде.

 

9. С помощью десятичных кодов зашифровано слово «info» 105 110 102 111. Записать последовательность десятичных кодов для этого же слова, но записанного заглавными буквами.

 

10. Буква Z  имеет десятичный код 90, а z – 122. Записать слово «forma» в десятичном коде.

 

11. С помощью десятичных кодов зашифровано слово «port» 112 111 114 116. Записать последовательность десятичных кодов для этого же слова, но записанного заглавными буквами. Ответ: 80 79 82 84

 

Контрольные вопросы:

11.  Правило цифрового представления символов

12.  Чем отличаются стандарты для представления символов?

13.  Какие кодировки символов вы знаете?

14.  Назовите самый распространённый код для информационного обмена?

15.  Назовите недостатки стандарта ISO-646?

 

 

Практическая работа № 7.

Использование закона аддитивности информации при решении задач на определение количества информации

 

Цель работы: научить решать задачи на количественное измерение информационного объема текстовой информации.

 

Краткие теоретические сведения.

В связи с разными подходами к определению информации выделяют два подхода к измерению информации.

Субъективный (содержательный) подход

При данном подходе информация – это сведения, знания, которые человек получает из различных источников. Таким образом,  сообщение информативно (содержит ненулевую информацию), если оно пополняет знания человека.

При субъективном подходе информативность сообщения определяется наличием в нем новых знаний и понятностью  для данного человека (определение 1). Разные люди, получившие одно и тоже сообщение, по-разному оценивают количество информации, содержащееся в нем. Это происходит оттого, что знания людей об этих событиях, явлениях до получения сообщения были различными. Сообщение информативно для человека, если оно содержит новые сведения, и неинформативно, если сведения старые, известные. Таким образом, количество информации в сообщении зависит от того, насколько ново это сообщение для получателя и  определяется объемом знаний, который несет это сообщение получающему его человеку.

При содержательном подходе возможна качественная оценка информации: достоверность, актуальность, точность, своевременность, полезность, важность, вредность…

С точки зрения информации как новизны мы не можем оценить количество информации, содержащейся в новом открытии, музыкальном стиле, новой теории развития.

Субъективный подход основывается на том, что получение информации, ее увеличение, означает уменьшение незнания или информационной неопределенности (определение 2).

Единица измерения количества информации называется бит (bit – binary digit), что означает двоичный разряд.

Количество информации – это количество бит в сообщении.

Сообщение, уменьшающее информационную неопределенность (неопределенность знаний) в два раза, несет для него 1 бит информации.

Что же такое «информационная неопределенность»?

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

Пример_1: Книга лежит на одной из двух полок – верхней или нижней. Сообщение о том, что книга лежит на верхней полке, уменьшает неопределенность ровно вдвое  и несет 1 бит информации.

Сообщение о том, что произошло одно событие из двух равновероятных, несет 1 бит информации.

Научный подход к оценке сообщений был предложен еще в 1928 году Р. Хартли.

Пусть в некотором сообщении содержатся сведения о том, что произошло одно из N равновероятных событий (равновероятность обозначает, что ни одно событие не имеет преимуществ перед другими). Тогда количество информации, заключенное в этом сообщении, - x бит и число N связаны формулой:

2^x = N

где x – количество информации или информативность события (в битах);

      N – число равновероятных событий (число возможных выборов).

Данная формула является показательным уравнением относительно неизвестной x. Решая уравнение,  получим формулу определения количества информации, содержащемся в сообщении о том, что произошло одно из N равновероятных событий, которая имеет вид:

x = log₂N

логарифм от N по основанию 2.

Если N равно целой степени двойки, то такое уравнение  решается легко, иначе справиться с решением поможет таблица логарифмов.

Если N = 2 (выбор из двух возможностей), то x = 1 бит.

Пример_4: Какое количество информации несет сообщение о том, что встреча назначена на июль?

Решение: В году 12 месяцев, следовательно, число равновероятных событий или число возможных выборов N = 12. Тогда количество информации x = log₂12. Чтобы решить это уравнение воспользуемся таблицей логарифмов или калькулятором.

Ответ:  x = 3,58496 бита.

Пример_5: При угадывании целого числа в диапазоне от1 до N было получено 8 бит информации. Чему равно N?

Решение: Для того, чтобы найти число, достаточно решить уравнение N=2^x , где x = 8. Поскольку 2⁸ = 256, то N = 256. Следовательно, при угадывании любого целого числа  в диапазоне от 1 до 256 получаем 8 бит информации.

Ситуации, при которых точно известно значение N, редки. Попробуйте по такому принципу подсчитать количество информации, полученное при чтении страницы книги. Это сделать невозможно.

Объективный (алфавитный) подход к измерению информации

Теперь познакомимся с другим способом измерения информации. Этот способ не связывает количество информации с содержанием сообщения, и называется объективный или алфавитный подход.

При объективном подходе к измерению информации мы отказываемся от содержания информации, от человеческой важности для кого-то.

Информация рассматривается как последовательность символов, знаков (определение3).

Количество символов в сообщении называется длиной сообщения.

Основой любого языка является алфавит.

Алфавит – это  набор знаков (символов), в котором определен их порядок.

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

Например, мощность алфавита из русских букв равна 33:

мощность алфавита из английских букв равна 26.

При алфавитном подходе к измерению информации количество информации от содержания не зависит. Количество информации зависит от объема текста (т.е. от числа знаков в тексте) и от мощности алфавита. Тогда информацию можно обрабатывать, передавать, хранить.

Каждый символ несет x бит информации. Количество информации x, которое несет один символ в тексте, зависит от мощности алфавита M, которые связаны формулой 2^x = M. Следовательно  x = log₂M бит.

Количество информации в тексте, состоящем из K символов, равно K*x  или

K* log₂M, где x – информационный вес одного символа алфавита.

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

Пример_6, в 2-символьном алфавите каждый символ несет 1 бит информации (2^x = 2, откуда x = 1 бит).

Если M=16, то каждый символ несет 4 бита информации, т.к. 2⁴ = 16.

Если M=32, то один символ несет 5 бит информации.

При M=64, один символ «весит» 6 бит и т.д.

 

Задания

1. Измерьте информационный объем сообщения «Ура! Скоро Новый год!» в битах, байтах, килобайтах (Кб), мегабайтах (Мб).

2. Измерьте примерную информационную емкость одной страницы любого своего учебника,  всего учебника.

3. Сколько таких учебников может поместиться на дискете 1,44 Мб, на винчестере в 1 Гб.

4. В детской игре «Угадай число» первый участник загадывает целое число от 1 до 32. Второй участник задает вопросы: «Загаданное число больше числа ___?». Какое количество вопросов при правильной стратегии гарантирует угадывание?

Указание: Вопрос задавайте таким образом, чтобы информационная неопределенность (чи сло вариантов)  уменьшалась в два раза.

5. Яд находится в одном из 16 бокалов. Сколько единиц информации будет содержать сообщение о бокале с ядом?

6. Сколько бит информации несет сообщение о том, что из колоды в 32 карты достали «даму пик»?

7. Проводят две лотереи: «4 из 32» и «5 из 64» Сообщение о результатах какой из лотерей несет больше информации?

8. Информационное сообщение объемом 1.5 Кбайта содержит 3072 символа. Сколько символов содержит алфавит, при помощи которого было записано это сообщение? (Объяснение решения задачи на доске).

9. Подсчитать в килобайтах количество информации в тексте, если текст состоит из 600 символов, а мощность используемого алфавита – 128 символов.

10. Скорость информационного потока – 20 бит/сек. Сколько времени потребуется для передачи информации объемом в 10 килобайт.

11. Сравните (поставьте знак отношения)

o          200 байт и 0,25 Кбайт.

o          3 байта и 24 бита.

o          1536 бит и 1,5 Кбайта.

o          1000 бит и 1 Кбайт.

o          8192 байта и 1 Кбайт.

12. В барабане для розыгрыша лотереи находится 32 шара. Сколько информации содержит сообщение о первом выпавшем номере (например, выпал номер 15)?

13. При игре в кости используется кубик с шестью гранями. Сколько бит информации получает игрок при каждом бросании кубика?

14. Книга, набранная с помощью компьютера, содержит 150 страниц; на каждой странице — 40 строк, в каждой строке — 60 символов. Каков объем информации в книге?

15. Подсчитайте объем информации, содержащейся в романе А. Дюма "Три мушкетера", и определите, сколько близких по объему произведений можно разместить на одном лазерном диске? (590 стр., 48 строк на одной странице, 53 символа в строке).

16. На диске объемом 100 Мбайт подготовлена к выдаче на экран дисплея информация: 24 строчки по 80 символов, эта информация заполняет экран целиком. Какую часть диска она занимает?

17. В школьной библиотеке 16 стеллажей с книгами. На каждом стеллаже 8 полок. Библиотекарь сообщил Пете, что нужная ему книга находится на пятом стеллаже на третьей сверху полке. Какое количество информации библиотекарь передал Пете?

18. В коробке лежат 7 цветных карандашей. Какое количество информации содержит сообщение, что из коробки достали красный карандаш?

19. Какое количество информации несет сообщение: “Встреча назначена на сентябрь”.

20. Сообщение занимает 3 страницы по 25 строк. В каждой строке записано по 60 символов. Сколько символов в использованном алфавите, если все сообщение содержит 1125 байтов?

 

Контрольные вопросы:

16.  Какой подход называется субъективным?

17.  Какой подход называется содержательным?

18.  Что называется информационной неопределенностью?

19.  Какой подход называется объективным (алфавитным)?

20.  Что называется длиной информации?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая  работа № 8.

Применение формулы Шенона.

 

Цель работы: выработать навыки применения формулы Шенона

 

Краткие теоретические сведения.

В первую очередь для решения задач такого типа нам необходимо знать формулу расчета вероятности исхода. Она выглядит так:

p=M/N,

где M – это величина, показывающая сколько раз произошло интересующее нас событие, N – это общее число возможных исходов какого-то процесса.

Необходимо знать, что в сумме все вероятности дают единицу или в процентном выражении 100%.

Далее для решения задач на количество информации необходимо знать, каким событие является: равновероятным или с разными вероятностями.

Если событие равновероятно, можно применить для решения формулу Хартли:

I=log₂N,

где N – это количество равновероятных событий; I - количество бит в сообщении

Иногда формулу Хартли записывают так:

I = log₂ N = log₂ (1 / р) = - log₂ р,

т. к. каждое из N событий имеет равновероятный исход р = 1 / N, то N = 1 / р.

Важно запомнить, что вероятность события и количество информации в сообщении имеют связь, которую можно выразить следующим образом: чем меньше вероятность некоторого события, тем больше информации содержит сообщение об этом событии.

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

Если в задаче дано событие с различными вероятностями, тогда следует использовать формулу Шеннона.

 

где I-количество информации,

N-количество возможных событий,

р_i - вероятности отдельных событий

 

Задание 1.

В классе 30 человек. За контрольную работу по информатике получено 15 пятерок, 6 четверок, 8 троек и 1 двойка. Какое количество информации несет сообщение о том, что Андреев получил пятерку?

 

Задание 2.

В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и 40 зеленых шариков. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика?

 

Задание 3.

Построить код Шеннона-Фано и вычислить его эффективность для источника с вероятностями букв 1/4; 1/4; 1/8; 1/8; 1/16; 1/16; 1/16; 1/16.

 

Задание 4.

Построить блочный код Шеннона-Фано с блоками длиной 3 и вычислить его эффективность для однородного марковского источника с матрицей переходных вероятностей .

Задание 5.

Декодировать полученное сообщение11011101. При кодировании использовался (7, 4) код Хэмминга с проверкой четности.

 

 

Контрольные вопросы:

1.          Код Шеннона-Фано.

2.          Код Хаффмана.

3.          Помехоустойчивое кодирование. Теорема Шеннона о кодировании для канала с шумом.

4.          Код с проверкой четности. Код с тройными повторениями.

5.          Код Хэмминга.