Определение количества информации по Колмогорову - Методы информационного анализа материальных процессов
Рассмотрим основные идеи, лежащие в основе колмогоровского определения количества информации.
Введение колмогоровской меры имеет основной целью уточнение понятий энтропии и количества информации, во-первых, без привлечения теоретико-вероятностного подхода, во-вторых, применительно к индивидуальным объектам, а не ко множествам объектов. Кратко сформулируем идею подхода Колмогорова [12].
Будем считать, что мы обладаем информацией о некотором объекте тогда и только тогда, когда мы сможем воспроизвести объект по конечному набору его признаков. Получить полную уверенность в том, что мы располагаем всей необходимой информацией, можно только восстановив объект по его описанию.
Построение меры Колмогорова основывается на таких понятиях, как алгоритм, вычислимая функция, машина Тьюринга и т. д. Можно сказать, что алгоритм - это правило или совокупность правил, с помощью которого решение некоторой задачи или класса задач, достигается чисто механическим путем, если это решение существует. Внимательное рассмотрение понятия "алгоритм", позволяет построить следующий набор характеристик, которыми он должен обладать.
- - Для алгоритма определяются множества возможных исходных данных, возможных промежуточных и возможных конечных результатов. При этом для представления исходных данных, промежуточных и конечных результатов могут быть заданы соответственно входной, рабочий и выходной алфавиты. Объекты, которыми оперирует алгоритм, должны быть конструктивными. Конструктивный объект характерен тем, что он строится из конечного числа исходных элементарных объектов за конечное число шагов, т. е. он должен быть конечным и весь доступен для рассмотрения. - Правила, или инструкции, согласно которым выполняется преобразование данных, должны иметь конечную длину, причем каждое правило, должно быть сформулировано таким образом, чтобы процесс его выполнения был осуществим, строго однозначно, то есть полностью детерминирован. В частности, для выполнения правила не должна требоваться какая-либо внешняя информация. Таким образом, для реализации алгоритма нужны лишь исходные данные и набор правил. - Существенно наличие некоторого операционного устройства, способного воспринимать и выполнять инструкции алгоритма (в роли такого "устройства" может выступать человек). В процессе реализации алгоритма этому устройству может потребоваться память, на объем которой не накладывается никаких конкретных ограничений. - Следует заметить, что алгоритм не обязательно должен давать должен давать результат для каждого возможного исходного данного. Кроме случая получения результата возможны еще два исхода. Во-первых, процесс поэтапного выполнения инструкций может прекратиться, не приведя к результату. Во-вторых, процесс выполнения инструкций может оказаться состоящим из бесконечно большого числа этапов. Таким образом, в множестве в множестве возможных исходный данных целесообразно выделить область применимости алгоритма - применение алгоритма к принадлежащему этой области объекту приводит к результату за конечное число шагов [13].
В пределах существующих математических представлений понятию "алгоритм" не может быть дано строгого определения. Однако предпринимались многочисленные попытки уточнить понятие алгоритма. Среди таких уточнений можно указать на общерекурсивные функции, машины Тьюринга и т. д. Известно, что все эти уточнения в определенном смысле эквивалентны друг другу, а согласно так называемому тезису Черча понятие алгоритма в интуитивном смысле можно отождествить с одним из строгих определений.
С понятием алгоритма тесно связано понятие вычислимой функции. Пусть - множество возможных исходных данных, - множество возможных конечных результатов применения алгоритма, причем и состоят, только из конструктивных объектов, а - область применимости алгоритма. Пусть также функция задает отображение, такое, что совпадает с результатом применения алгоритма к объекту. Тогда называют вычислимой функцией, которая задается данным алгоритмом.
Раскроем основное содержание понятия "машина Тьюринга", которая состоит из:
- - операционного устройства, которое может принимать одно из конечного множества состояний ; в выделяются начальное и конечное состояния; - бесконечной ленты, разделенной на ячейки, в каждой из которых может содержаться не более одного символа конечного алфавита ; - головки, которая способна выполнять считывание и запись символов алфавита и перемещать ленту вправо и влево на одну ячейку;
- программы, состоящей из конечного набора правил вида, где определяет характер перемещения ленты.
В процессе последовательного выполнения правил машины Тьюринга, можно изменять содержимое ячеек на ленте, сдвигать ее, переходить на новые состояния. При переходе в конечное состояние работа машины заканчивается. Таким образом, в процессе работы машины происходит преобразование исходных данных, записанных на ленте, причем в результате не обязательна остановка машины - может произойти ее зацикливание.
В результате проведенных рассуждений можно сказать, что понятие машины Тьюринга адекватно понятию алгоритма. Другими словами, всякий алгоритм может быть реализован на соответствующей машине Тьюринга (тезис Тьюринга). Если с помощью машины Тьюринга строится отображение некоторого множества слов алфавита в другое множество таких слов, то об этом отображении говорят как о функции, вычислимой по Тьюрингу. С учетом тезиса Тьюринга и сделанных выше замечаний о связи вычислимых функций с алгоритмами можно сказать, что понятия вычислимой функции и функции, вычислимой по Тьюрингу, в некотором смысле эквивалентны.
Пусть рассматривается некоторое исходное множество объектов, причем устанавливается взаимно-однозначное соответствие между этим множеством и множеством двоичных слов конечной длины, то есть слов вида, где есть 0 или 1 (). Установленное соответствие между множествами позволит в дальнейшем в качестве объектов без существенного ограничения общности рассматривать только двоичные слова; будет обозначать длину слова. Ясно, что конечное двоичное слово можно описать так, что это слово возможно будет восстановить по его описанию. Разные слова имеют разные описания, но одно слово может иметь бесконечно много описаний. Итак, возникает вопрос, как сравнивать между собой описания двоичного слова для того, чтобы выбрать из этих описаний самое простое.
Будем считать, что описание двоичного слова задается не в произвольной словесной форме, а в виде двоичного слова - аргумента некоторой (пока фиксированной) вычислимой функции. Пока на не накладывается никаких ограничений: она может быть определена не на всех двоичных аргументах; не для каждого двоичного слова, как может оказаться, имеется двоичный прообраз (такое слово, что ). Для некоторого двоичного слова рассмотрим множество всех двоичных слов, таких, что. Пусть
Назовем сложностью слова по. Таким образом, сложность слова по - это длина самого короткого двоичного слова, в котором содержится полное описание слова при фиксированном способе восстановления слов по их описаниям. Если для данного способа восстановления такого описания не существует, то сложность слова по считается бесконечно большой.
Недостатком данного определения сложности является произвол в выборе вычислимой функции. Избавиться от этого недостатка можно с помощью следующей теоремы: существует вычислимая функция (оптимальная), такая, что для любой другой вычислимой функции при любом выполняется неравенство
,
Где - соответствующая функции и не зависящая от константа. С учетом этой теоремы определение сложности можно скорректировать следующим образом: сложностью слова называется сложность слова по некоторой фиксированной оптимальной вычислимой функции слова. Таким образом определение сложности стало инвариантным.
Аналогичным образом строится определение относительной сложности слова при заданном слове - это минимальная длина такого двоичного слова, что пара слов содержит всю информацию, необходимую для восстановления при фиксированном оптимальном способе восстановления. Способ восстановления задается вычислимой функцией от двух аргументов. Среди всех таких функций существует оптимальная, позволяющая брать самые короткие слова, добавляемые к и дающие вместе с полное описание [14].
Назовем и обозначим величины, соответственно алгоритмической энтропией и условной алгоритмической энтропией. Алгоритмическим количеством информации в индивидуальном объекте относительно индивидуального объекта называют
.
Определение колмогоровской меры информации не требует привлечения вероятностных понятий.
Похожие статьи
-
Анализировать общие механизмы энтропийно-информационных закономерностей материальных процессов, являющихся фундаментальной основой всех самопроизвольно...
-
Энтропия по Клаузиусу. Формулы Больцмана и Планка Во второй половине XX века произошли два события, которые в значительной мере определяют дальнейшие...
-
В общем случае все этапы кластерного анализа взаимосвязаны, и решения, принятые на одном из них, определяют действия на последующих этапах. Аналитику...
-
Определение количества кластеров - Кластерный анализ
Существует проблема определения числа кластеров. Иногда можно априорно определить это число. Однако в большинстве случаев число кластеров определяется в...
-
Введение - Методы информационного анализа материальных процессов
Обоснование необходимости проведения данной дипломной работы. Использование меры определенности и неопределенности информации позволяет анализировать...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Предварительная обработка исходного числового ряда направлена на решение следующих задач (всех или части из них): снизить влияние случайной составляющей...
-
Итеративные методы, Алгоритм k-средних (k-means) - Кластерный анализ
При большом количестве наблюдений иерархические методы кластерного анализа не пригодны. В таких случаях используют неиерархические методы, основанные на...
-
Методы определения корреляционной связи - Корреляционно-регрессионный анализ
Корреляцию и регрессию принято рассматривать как совокупный процесс статистического исследования, поэтому их использование в статистике часто именуют...
-
Общая схема исследования: 1. Составление среднего образца. 2. Извлечение пестицидов из пробы. 3. Очистка экстракта. 4. Анализ экстракта. Прием образцов в...
-
Вещество [Co] Лиганды и Комплексообразователь Координационное число 6 Для комплексов с координационным числом 6 характерно октаэдрическое расположение...
-
ОПРЕДЕЛЕНИЕ МЕТОДА ФАКТОРНОГО АНАЛИЗА И ЧИСЛА ФАКТОРОВ - Многомерный статистический анализ
Определение метода факторного анализа. Различные методы факторного анализа различаются в зависимости от подходов, которые используются для выделения...
-
На выполнение данной НИР по смете необходимы следующие затраты: - расчет материальных затрат; - затраты на заработную плату научно-исследовательского...
-
Для ХОП характерна неблагоприятная "триада": -высокая устойчивость во внешней среде; -куммуляция; -способность выделять с молоком лакирующих животных...
-
Существует два способа разработки компьютерных моделей с помощью специализированных программных средств и программирования. Специализированные...
-
Моделирование начинается с объекта изучения. На 1 этапе формируются законы, управляющие исследованием, происходит отделение информации от реального...
-
Методы Кластерного Анализа, Иерархические методы - Кластерный анализ
Иерархические методы С понятием кластеризации мы познакомились в первом разделе курса. В этом мы опишем понятие "кластер" с математической точки зрения,...
-
Регрессионный метод оценки, апроксимационные модели - Корреляционно-регрессионный анализ
При изучении любого процесса (физического, социального) прихоится сталкиваться с необходимостью представлять его в качестве некоторой модели, т. е. в...
-
Компьютерное моделирование по сравнению с натурным экспериментом дает возможность: § получать наглядные динамические иллюстрации физических экспериментов...
-
Информация - это все данные, являющиеся объектом сбора, хранения, обработки, передачи и преобразования. Землеустроительная информация - это особый вид...
-
В основе метода площадей лежит предположение, что объект может быть описан линейным дифференциальным уравнением с постоянными коэффициентами, а его...
-
Правила построения рядов динамики - Методы анализа основной тендеции развития в рядах динамики
При построении динамических рядов необходимо соблюдать определенные правила: основным условием для получения правильных выводов при анализе рядов...
-
Сравнительный анализ иерархических и неиерархических методов кластеризации - Кластерный анализ
Перед проведением кластеризации у аналитика может возникнуть вопрос, какой группе методов кластерного анализа отдать предпочтение. Выбирая между...
-
Для моделирования случайных событий и процессов используется метод статистического моделирования. Сущность метода статистического моделирования. Таким...
-
Первый этап - определение целей моделирования. Основные из них таковы: 1. модель нужна для того, чтобы понять как устроен конкретный объект, какова его...
-
К числу приближенных методов оптимизации задач календарного планирования относятся: частичный и направленный перебор, метод Монте-Карло,...
-
Понятие модель, моделирование. Разные взгляды и классификация Слова модель и моделирование в последние годы стали часто использоваться в учебной...
-
Функции и ее свойства - Методы решения системы линейных уравнений
В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...
-
В основе моделирования лежит теория подобия, которая утверждает, что абсолютное подобие может иметь место лишь при замене одного объекта другим точно...
-
Важным для системного подхода является определение структуры системы -- совокупности связей между элементами системы, отражающих их взаимодействие....
-
Кластерный анализ - Кластерный анализ
Кластерный анализ -- способ группировки многомерных объектов, основанных на представлении результатов отдельных наблюдений точками подходящего...
-
1. Нормальные алгоритмы Маркова Для формализации понятия алгоритма российский математик А. А. Марков предложил использовать ассоциативные исчисления....
-
Описание процессов, происходящих на поверхности, изобилует специальными терминами, и при рассмотрении адсорбционных явлений приходится говорить на языке,...
-
Применение информационно-компьютерных технологий позволяет наиболее эффективно реализовать следующие функции урока: Вооружение учащихся глубокими и...
-
Процесс административного сопровождения является вспомогательным процессом и включает в себя: Расчет текущей учебной нагрузки Управление учебным...
-
Использование современных информационно-коммуникационных технологий в образовательном учреждении позволяет решить ряд фундаментальных задач: Внедрить...
-
Химизм процесса гидроочистки - Сравнительный анализ методов обессеривания
Превращение серосодержащих соединений В неуглеводороных соединениях связи C-S и S-S менее прочны, чем связи С-С и С-Н, усредненные энергии связи которых...
-
"Репетитор. Физика" - мультимедийный электронный учебник по физике, содержащий демонстрацию физических явлений методами компьютерной анимации,...
-
Целью расчета насадочных абсорберов является определение диаметра (сечения) аппарата; определение высоты насадки (а также нахождение высоты аппарата);...
-
Итак, в первых двух разделах курсовой работы мы использовали модуль Excel "Поиск решении" для решения задачи общего линейного программирования (1 раздел)...
Определение количества информации по Колмогорову - Методы информационного анализа материальных процессов