13. Методы и модели оценки количества информации. Основные понятия теории

алгоритмов.

ЭНТРОПИЙНЫЙ

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

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

метод Хартли

H = log2 (m)

m - число возможных равновероятных выборов

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

Пример:

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

Для выбора из колоды карт имеем: H = log2 32 = 5.

Полученная оценка соответствует количеству вопросов, ответы на которые позволяют выбрать либо «да», либо «нет» для определения взятой из колоды карты:

1. Красной масти Ответ: «нет» 0

2. Трефы? Ответ: «нет» 0

3. Одна из четырех старших? Ответ: «да» 1

4. Одна из двух старших? Ответ: «нет» 0

5. Дама? Ответ: «да» 1

Этот выбор можно описать последовательностью из пяти символов (0- нет; 1 – да)

00101

Вероятностный подход

(когда исходы неравновероятны)

• где Pi – вероятность выбора i-того события.

Если алфавит состоит из двух неравновероятных знаков, например

P(0)=0,2P(1)=0.8,

• количество информации на один знак

H = 0,2*log2 5 +0,8* log2 1,25 0,72193 бит

• Если алфавит состоит из двух равновероятных знаков 0 и 1:

P(0)=P(1)=0.5,

• количество информации на один знак . H = log2 2 = 1 бит

• Количество информации заключенное в

двоичном слове равно числу знаков в нем.

Единицы измерения:

8-ми разрядный двоичный код =1 байт

1 байт = 8 бит

1 килобайт 1Кб= 210 = 1024 байт ≈ 103 байт

1 мегабайт 1 Мб = 220 = 1 048 567 байт ≈ 106 байт

1 гигабайт 1 Гб = 230 = 1 073 741 824 байт ≈ 109 байт

1 террабайт1 Тб = 240 = 1 099 511 627 766 байт ≈

1012 Байт

Объемный

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

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

• Теория алгоритмов – раздел математики, изучающий общие свойства алгоритмов.

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

Принципы построения алгоритмической модели

• Конкретный набор элементарных шагов

• Способы определения следующего шага

• Простота

• Универсальность

Первый класс алгоритмических моделей

• Арифметизация моделей: любой алгоритм можно закодировать числами, а всякое преобразование становится арифметическим вычислением

• Элементарные шаги – арифметические операции

Последовательность шагов

Суперпозиция Рекурсия

S(x) exp(1 sin(x ) ) Q!1,(n 1)!n!(n 1)

Второй класс алгоритмических моделей

• Машинизация алгоритма – для того, чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен так, чтобы его выполнять машина, которой предъявляются требования простоты и универсальности

Машина Тьюринга

• Лента бесконечна

• Одна ячейка – один символ

• Отсутствие символа – «»

• Головка может читать, писать, стирать, перемещать вдоль ленты символы

• Число возможных символов конечно и образует алфавит машины

• Головка в каждый такт (шаг) машины находится в одном состоянии

• Множество состояний определяется начальным и конечным состояниями

Элементарный шаг машины:

• Головка считывает символ, записанный в ячейке, над которой она находится

• Считанный символ ak и текущее состяние головки qj однозначно определяют состояние qi, новый обрабатываемый символ a1 и перемещение головки dp

• Устройство управления хранит и выполняет команды машины вида qjak → qi a1dp

Третий класс алгоритмических моделей (нормальные алгоритмы Маркова)

• Задается алфавит, множество допустимых подстановок и порядок их применения

Элементарный шаг:

• Проверить возможность подстановок в порядке возрастания номеров, и если она возможна, произвести подстановку

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

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

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

• Система счисления – принятый способ записи и сопоставления этим записям реальных значений.

• совокупность приемов наименования и записи чисел

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

• частный случай кодирования, где слово записанное определнным алфавитом по определенным правилам – код (код числа)

• Для записи чисел в различных системах счисления используют некоторое количество отличных друг от друга знаков.

• Число таких знаков в позиционной системе счисления – базисные числа (0,1…k-1), если основание системы – k

Непозиционная – значение знака не зависит от места расположения – аддитивная

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

РИМСКАЯ

БАЗИС:

I (1) V(5) X(10) L(50) C(100) D(500) M(1000)

- если цифра справа меньше или равна, чем слева (АВ), то (В-А)

- если цифра справа меньше или равна, чем слева (АВ), то (В+А)

Пример

14610 = CXLVI

C =100 III = 3

XL = 50-10 LIX = 59

VI = 5+1 DLV = 555

Позиционные системы счисления

• если значения цифры (вес) изменяется в зависимости от положения (позиции) в последовательности цифр

или

• число определяется и набором цифр и их местом (позицией в последовательности, изображающей число)

• аддитивно-мультикативные

X(k)= xn-1kn-1+ x n-2k n-2+ ...+ x 1k 1+x 0k 0+x -1k -1+...+x -mk -m =

где k – основание;