http://profbeckman.narod.ru/

где N – общее количество элементов в системе (N=m+n+...+z); H – шенноновская энтропия

n

- pi log2 pi (pi – вероятности элементов каждого типа при рA+рB+...+pС=1, например:

i 1

рA=m/N). В качестве систем вида АmВn...Сz, могут быть представлены разнообразные геологические объекты, например, химические составы горных пород по данным силикатного анализа (как совокупности атомов различных химических элементов), виды симметрии (как совокупности элементов симметрии), геологические разрезы (как совокупности слоев) и т. д. Величина удельной антиэнтропии может быть применена для сравнения структурной сложности систем в пределах единых структурных уровней. Она является обратной величиной по отношению к удельной энтропии, применяемой при решении некоторых кибернетических задач (энтропия, приходящаяся на одну букву многобуквенного текста). Единица измерения удельной антиэтропии бит-1. При обычном сравнении систем по величине Н учитывается только сложность дифференциации (относительная неравномерность распределения элементов различных типов; Н максимальна при равномерном распределении). Употребление удельной антиэнтропии даёт возможность, кроме того, учитывать и изменения сложности интеграции (сложности полимеризации), понимаемые в узком смысле как изменения общего количества элементов в устойчивых совокупностях – системах.

Энтропия — это то, как много информации вам не известно о системе Марк Айхенлау

7.4Алгоритмическая теория информации

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

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

Значительный прогресс в понимании взаимоотношений информатики и энтропии и их роли в неравновесной термодинамике внесли работы А.Н.Колмогорова, отдельно и с соавторами.

7.4.1 Энтропия Колмогорова

А.Н. Колмогоров превратил техническую теорию информации Шеннона в полноценную науку, строия её на другой аксиоматике, чем Шеннон. Он распространил понятие энтропии на эргодические случайные процессы через предельное распределение вероятности, имеющее плотность f(x). Колмогоров использовал понятие шенноновской энтропии при определении нового метрического инварианта сохраняющих меру преобразований вероятностных пространств, играющего фундаментальную роль в эргодической теории. Это определение было усовершенствовано Н.С. Крыловым и Я.Г. Синаем. Предложенная этой школой энтропия называется по-разному: энтропия Крылова- Колмогорова-Синая, КС-энтропия, К-энтропия, энтропия Колмогорова, а-энтропия и АГэнтропия.

КС-энтропия (SК) – характеристика хаотического движения в фазовом пространстве произвольной размерности; определяет среднее время, на которое можно предсказать состояние системы с динамическим хаосом. Вычисляется по формуле Шеннона.

http://profbeckman.narod.ru/

КС-энтропия используется для определения является ли исследуемый режим хаотическим или регулярным; это количественная мера хаотичности и неустойчивости.

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

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

Для символических динамических систем, т.е. сдвигов в пространствах последовательностей с конечным алфавитом, энтропия Колмогорова-Синая – это средняя условная энтропия настоящего при условии прошлого для стационарного случайного процесса (в другой терминологии – скорость создания информации источником). С геометрической точки зрения КС-энтропия рассматривается как скорость роста объёма границы множества в фазовом пространстве под действием динамики.

Пусть имеется динамическая система, которая задаётся обыкновенными уравнениями:

	(51)
x f (x), х(0)=х0

где х – N-мерный вектор состояний.

Выберем в фазовом пространстве в начальный момент t=0 две близкие фазовые точки х1 и х2, проведём из них траектории (х1(t) и х2(t)) и проследим, как при эволюции системы (40) будет изменяться расстояние L(t)=|x2(t)-x1(t)| между этими точками.

Если динамика системы (51) является хаотической, то L(t) с течением времени будет экспоненциально возрастать, причём при больших временах:

L(t) L(0)ekt.					(52)
Cредняя скорость экспоненциального расхождения траекторий:
	L t
	ln
k t	L 0				(53)

t

Однако так не может продолжаться вечно: при финитном движении L(t) не может всегда увеличиваться. Поэтому при больших t величина k(t) в любом случае независимо от режима – хаотического или регулярного – будет близка к нулю. Однако чем меньше начальное расстояние L(0)= |ξ(0)|, тем дольше можно следить за возрастанием L(t), т.е. в течение большего промежутка времени величина d(t), не достигнет максимального значения. Поэтому L(0)→0 и t→∞. Тогда КС-энтропия

		L t
		ln
SK	lim	L(0)			(54)
			t
	d(0) 0
	t

Производство КС-энтропии не является знакоопределенным: оно возрастает, если возрастает со временем среднее эффективное расстояние между траекториями, и уменьшается в противоположном случае.

Используя КС-энтропию, можно определить, каким является исследуемый режим движения – хаотическим или регулярным. Понятие КС-энтропии используется как характеристика хаоса динамического в системах с неустойчивостью движения –

http://profbeckman.narod.ru/

экспоненциальной расходимостью близких в начальный момент траекторий. В частности, если динамика системы является периодической или квазипериодической, то с течением времени расстояние L(t) не возрастает и КС-энтропия равна нулю (=0). При наличии в системе устойчивой неподвижной точки L(t) 0 и SK<0. В случае хаотической динамики системы КС-энтропия всегда положительна (SK>0). Величина КС-энтропии тем больше, чем быстрее разбегаются траектории, т. е. чем сильнее неустойчивость траекторий и хаотичнее система. КС-энтропия выражается через положительные показатели Ляпунова, характеризующими устойчивость динамической системы.

КС-энтропия – величина размерная ([SK]=c-1) и является не только качественной, но и количественной характеристикой режима движения: величина, обратная энтропии (при условии SK>0), определяет характерное время перемешивания tmix=SK-1 в системе; по прошествии промежутка времени t>>tmix начальная область расплывается по всей энергетически доступной гиперповерхности (в отсутствие диссипации или по предельному подмножеству фазового пространства – странному аттрактору (для диссипативных динамических систем); при t>>tmix описание системы может быть только вероятностным. Однако на малых временах t<<tmix поведение системы можно предсказать с достаточной точностью (не превышающей, естественно, точность задания начального положения фазовой точки).

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

Реализацией случайного процесса является временная последовательность значений параметра u(t). Для чисто случайного процесса прошлые значения ui никак не связаны и не несут никакой информации о настоящем и будущем (даже ближайшем) в значениях u. В этом случае все значения ui равновероятны и f(ui)=1/n. Откуда КС-энтропия SK(n)=ln(n). Для процесса «без памяти», SK→∞. В случае регулярного движения, когда SK→0, можно предсказать любые будущие значения u(t). Таким образом, чем меньше SK, тем более детерминированной является система. Напротив, высокие значения SK говорят о высокой стохастичности системы, короткой «памяти» и, соответственно, плохой прогнозируемости её будущих состояний. Роль KС-энтропии для нелинейных систем похожа на роль, которую играет автокорреляционная функция для линейных систем.

КС-энтропия используется при описании такого случайного процесса, как броуновское движение. Можно показать, что мера априорной неопределённости положения броуновской частицы даётся формулой

n

SK (n) f ui tn ln f ui tn ,	(55)
i 0

где u - некоторый измеряемый параметр случайного процесса (например, вектор положения броуновской частицы; f(ui(tn)) - вероятность данной выборки, т.е. совместная вероятность того, что в момент времени t0 броуновская частица находилась в ячейке с номером 0, в ячейке 1 – в момент времени t1=t0+tn,...,t0+ndt. Тогда мера априорной неопределённости положения броуновской частицы даётся формулой:

Разность энтропий SK(n+1)-SK(n) есть потерянная информация о положении

частицы на интервале dt. Скорость потери информации на						всём интервале ndt равна
	SK 0 SK	n
			. КС-энтропия определяется как предельное значение этой оценки при
	ndt
заданном начальном значении SK(0)=0:
	SK	lim limlim		SK n
						(56)
		dt 0 0 n ndt

http://profbeckman.narod.ru/

КС-энтропия даёт оценку скорости потери информации и является мерой памияти системы, или мерой скорости забывания начальных условий. Её можно таке рассматривать как меру хаотичности системы. Для процесса без памяти SK, в случае регулярного движения, когда SK0, можно предсказать будущие значения ut. Чем меньше SK, тем более детерминированной является система. Напротив, высокие значения SK говорят о высокой стохастичности системы, короткой «памяти» и, соответственно, плохой прогнозируемости ее будущих состояний. Роль KС-энтропии для нелинейных систем похожа на роль, которую играет автокорреляционная функция для линейных систем. KС- энтропия обладает и другими интересными свойствами. В частности, она связана с показателями Ляпунова, характеризующими устойчивость динамической системы.

7.4.2 Эпсилон-энтропия

Эпсилон-энтропия (ε-энтропия) – термин, введённый Колмогоровым для характеристики классов функций. Это мера сложности функции, минимальное количество знаков, необходимое для задания функции с точностью ε. Минимальное количество информации содержащейся в сообщении z(t) относительно u(t), при котором они еще оказываются эквивалентными, принято называть эпсилон-энтропией, Hε(u).

ε-Энтропия величины А – минимальное количество информации в одной случайной величины Y относительно другой В, при котором удовлетворяется заданное требование к верности воспроизведения величины А.

Hz	A min Y (A, B),					M a b 2 2.
			w(x/ y)			(57)
В случае Гауссового источника сигнала при наличии шума
	1			с2
H			log
		2		2		(58)
				,

где с2 – дисперсия (мощность) сигнала, 2 – дисперсия шума воспроизведения. Алгоритмическая теория информации занимается определением сложности

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

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

Пусть имеется двоичное n-разрядное число. Цифры "0" и "1" этого числа могут быть расположены в разрядах в определенном порядке или беспорядочно. При выборе критерия степени беспорядоченности расположения цифр в числе руководствуются правилом: хаоса больше всего там, где больше всего информации. (Не зря же энтропия и информация вычисляются по одинаковым формулам!). Действительно, из некоторой таблицы двоичных чисел, состоящей, например, из нулей и единиц, можно извлечь информации больше, чем из таблицы того же объёма, но содержащей в себе только нули. А ведь наличие только нулей – это порядок, а "разбросанные" по таблице нули и единицы

–хаос. И классическое определение понятия "информация" говорит о том же: информация

–это устраненная неопределенность ожидания того или иного символа (кода, сообщения и т.п.). Её мерой служит энтропия источника. Чем больше энтропия источника (хаос), тем больше информации можно получить от него. Если, например, ожидание появления

http://profbeckman.narod.ru/

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

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

вычислить знаки этого числа. Выглядит она следующим образом: 1 1 1 1 1 1 ...

4 3 5 7 9 11

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

Замечание. – иррациональное число, т.е. его десятичное выражение представляет собой бесконечный ряд цифр, следующих друг за другом без какой-либо регулярности. Невозможно сказать, какой будет следующая цифра числа на основе предыдущих, даже если их тысячи миллионов. Какова же энтропия Шеннона этого числа . В десятичном представлении ,14159265358979323846264338327950288419716939937510582097494459230781…

– бесконечное число случайных и равновероятных знаков: следующей цифрой с одинаковой вероятностью могут быть как ноль, так и, например, три. В двоичном выражении число выглядит как: 11,0010010000111111011010101000100010000101101000110000100011010011…,

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

Рис.5 . Визуализация первых 10000 цифр числа .

Пример 1. Представляет интерес исследование насколько случайно число . Число представляет собой отношение длины окружности к ее диаметру и его можно вычислить со сколь угодно большой точностью. Сейчас его значение известно с точностью до 500 миллиардов знаков, его первые цифры в десятичной системе 3,1415926535897932384626433832795..., в двоичной системе 11,00100100001111110110… В нем нет ни одной циклической последовательности и, вероятно, никогда не будет, сколько бы еще знаков ни вычислили. Любая последовательность цифр одинаковой длины встречается в нем с одинаковой частотой. Например, вероятность найти последовательность 234 равна вероятности обнаружить 876; а 23568 попадается так же часто, как 98427 (попутно заметим, что у имеются и другие интересные свойства, например, комбинация

http://profbeckman.narod.ru/

999999, в числе встречается на позиции 193034, 888888 - на позиции 222299,последовательность 12345678 - позиции 186557266, а последовательность 123456789 - только на позиции 523 551 502, последовательность цифр «141592», которая находится сразу после запятой, повторяется в позиции 821 582). Числа типа называются "нормальными". Нормальность числа доказана с помощью компьютерной программы, вычисляющей произвольную цифру числа , не вычисляя предыдущие. Алгоритм работает не целиком с числом, а с его фрагментами: берутся числа 0.314; 0.141; 0.415; 0.159 и т.д., которые составлены из трех последовательных цифр числа . Если цифры случайны, то все эти числа должны быть случайно распределены между 0 и 1 (расчёты идут не с десятичной, а с двоичной записью числа , т. е. с последовательностями из нулей и единиц). Было обнаружено, что цифры числа ведут себя в соответствии с теорией хаоса (теория хаоса предполагает, что в нормальных числах одни числовые последовательности неким образом зависят от соседних с ними чисел): их последовательность случайна. Другие примеры "нормальных" чисел: Неперово число или число e (основание натурального логарифма) в

десятичной системе 2,7182818284590452353602874713527… в двоичной системе 10,10110111111000010101000101100…, постоянная Эйлера ≈0,577215664901532860606512090...,

2 1,1414235623730950488 ...., 3 , 5 , ln2= 0,69314718055994530941723212145818, число Хайтина =0,0078749969978123844…, и много других. Возможные применения этих результатов - новые алгоритмы генератора случайных чисел и криптография.

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

Константа Хайтина, Ω, – действительное число, чьи цифры равнораспределены и которое выражает вероятность того, что произвольно взятая программа остановится. Константа Ω определимо, но не вычислимо.

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

Хотя существует бесконечное множество вероятностей остановки компьютерной программы, обычно используют букву Ω для обозначения их всех, как если бы существовало только одно такое число. Так как численное значение Ω зависит от используемого языка программирования, то если не ссылаются на какой-то определённый язык, её часто называют построением Хайтина, а не константой Хайтина. Всякое Ω является нормальным трансцентдентным числом, которое определимо, но невычислимо, что означает отсутствие алгоритма, который перечислял бы его цифры. Константа Ω - вероятность того, что случайно выбранная бесконечная последовательность нулей и единиц начинается со строки битов (некоторой конечной длины), которая принадлежит области определения. Оно определяет вероятность остановки. Ω алгоритмически случайна, это – нормальное число, т.е. её цифры равнораспределены, как если бы они были получены подбрасыванием уравновешенной монеты; Ω – невычислимое число; не существует вычислимой функции, перечисляющей её двоичное разложение; множество рациональных чисел q таких, что q<Ω – перечислимо; множество рациональных чисел q таких, что q>Ω – неперечислимо; Ω – арифметическое число. К настоящему времени вычислены первые 64 бита числа Хайтина. В двоичной записи: 0,0000001000000100000110001000011010001111110010111011101000010000… и в десятичной записи: 0,0078749969978123844…

Для любого непорядка Хайтина

01100111001011011010

01010010010010101111

http://profbeckman.narod.ru/

11001111010110010110

00111101111001100110

01110000101101011110

энтропия равна 20 бит Число – постоянная Хайтина – содержит бесконечное количество информации.

Важно, что эта постоянная не может порождаться кодом, содержащим меньше битов, чем она сама. Это означает, что все биты полностью случайны. Её можно использовать для решения проблемы остановки, которая заключается в том, чтобы определить, остановится ли какая-либо программа. Так, программа, вычисляющая 2+2, остановится, как только будет найдена требуемая сумма. Но программа, вычисляющая все простые числа, не остановится никогда. Способа решить проблему остановки для любой программы не существует: можно предсказать, остановится ли какая-то конкретная программа, но не для любого алгоритма. Например, представим себе программу, которой даны инструкции остановиться при нахождении четного числа, которое не может быть выражено как сумма двух простых. Программа остановится, если существует четное число с такими характеристиками, и никогда не остановится в противном случае. Постоянную Хайтина можно понимать как вероятность того, что программа, выбранная наугад, остановится. Предположим, что во Вселенной существуют только программы, содержащие три бита информации, т.е. всего таких программ восемь: 000, 001, 010, 011, 100, 101, 110, 111. Если бы останавливалась только программа 000, вероятность остановки составила бы 1/8. Можно вычислить вероятность того, что программа, выбранная наугад, остановится, если сложить вероятности выбора всех останавливающихся программ. Результат будет равен единице, деленной на число программ, содержащих 2n битов. Постоянная Хайтина:

	1
2		р	,	(59)

где р – вероятность остановки.

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

Алгоритмическая теория информации используется для сжатия текстов и кодирования.

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

Кодирование – важный раздел информатики, но в данному учебнике нет возможности этим заниматься.

Приведём несколько численных примеров расчёта энтропии в арифметике.

Пример: 000000000000000 и 1111111111111111111 (энтропия =0), 01101100110111100010 (энтропия =20), 10101010101010101010 имеет энтропию =1: вероятность последовательности из 1 и 0 = 0.5. Оба числа встречаются с одинаковой частотой. Энтропия последовательности