6. Способы измерения информации Формула Хартли. Формула Шеннона.

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

Объемный является самым простым и грубым способом измерения информации. Соответствующую количественную оценку информации естественно назвать объемом информации.

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

Поскольку, например, одно и то же число может быть записано многими разными способами (с использованием разных алфавитов): "двадцать один", 21, 11001, XXI, то этот способ чувствителен к форме представления (записи) сообщения.

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

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

При этом процесс получения информации рассматривается как выбор одного сообщения из конечного наперёд заданного множества из т равновероятных сообщений, а количество информации Н, содержащееся в выбранном сообщении, определял как двоичный логарифм т (формула Хартли):

Н = log₂ m.

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

Каждый согласится, что слово 0101... 01 сложнее слова 00... 0, а слово, где 0 и 1 выбираются экспериментально, например бросанием монеты (где 0 — герб, 1 — решка), сложнее обоих предыдущих.

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

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

Это формула Шеннона считает кол-во информации

-вероятность события

N-кол-во событий

7, 8, 9. Понятие алгоритма. Основные алгоритмические модели.

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

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

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

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

Результатами исследований в данной области явились три основных класса арифметических моделей.

Первый класс моделей основан на арифметизации алгоритмов.

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

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

Последовательность этих шагов определяется двумя способами.

Первый способ — суперпозиция, т.е. подстановка функции в функцию, а второй — рекурсия, т.е. определение значения функции через ранее вычисленные значения этой же функции.

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

Простейшим примером рекурсивной функции является факториал:

0! = 1, (n+1)! = n!(n+1)

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

Одной из таких машин явилась абстрактная машина Тьюринга.

Машина Тьюринга состоит из трех частей (рис. 2): ленты, головки и управляющего устройства (УУ). Лента бесконечна в обе стороны и разбита на ячейки, в каждой из которых может быть записан только один символ.

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

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

А = {а₁...,а_т}.

Головка в каждый такт работы машины находится в одном из состояний. Множество таких состояний конечно Q = {g₁,..., q_n} и среди них выделяют начальное q₁ и конечное q_z состояния.

Элементарный шаг машины Тьюринга состоит из следующих действий:

продолжение

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

- считанный символ а_k и текущее состояние головки q_j, однозначно определяют новое состояние q_i: новый записываемый символ a_l и перемещение головки d_p (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).

УУ хранит и выполняет команды машины вида qjak —> qialdp.

Конкретная машина Тьюринга (и алгоритм соответственно) задается перечислением элементов А и Q и командами машины.

Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Наиболее известная алгоритмическая модель этого типа — нормальные алгоритмы Маркова.

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

Этими средствами было показано, что имеются математические проблемы, для решения которых в принципе не может быть построен алгоритм. Такие проблемы были названы алгоритмически нера­зрешимыми.

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

Пример такой задачи может служить одна из древних геометрических проблем на построение с помощью циркуля и линейки — "о квадратуре круга" (построить квадрат, равновеликий данному кругу) и ряд других.

Знание основных неразрешимостей теории алгоритмов необходимо,

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