Для решения системной задачи данные о системе объекта необходимо физически закодировать. Общим способом кодирования данных является их представление в виде энергетических уровней величиной ΔЕ энергии решения системной задачи данные о системе объекта Е, которой мы располагаем. Число энергетических уровней согласно принципу в этом случае будет равно N = E/ΔE. Максимальное число физически разрешимых уровней для заданного количества энергии определяется неопределенности Гейзенберга. Согласно этого принципа величина уровня должна удовлетворять условию ΔE•Δt ≥ h, где Δt — длительность интервала наблюдения h = 6•6,25•10-27 эрг/c — постоянная Планка. Из этого следует:
N ≥ E•Δt/h
Тогда с учетом формулы Энштейна Е = mc2 (где с = 3•1010 см/c — скорость света, m — количество массы), получим:
N = mc2•Δt/h
Отсюда следует, что измеритель массой 1 г за время 1 сек может обработать не более N = 1,36•1047 бит данных.
Представим гипотетический измеритель массой равной массе Земли m = 6•1027 г. Этот измеритель за время равное времени существования Земли q 10 лет смог бы обработать порядка 1093 бит данных. Это число обычно называют пределом Бреммермана.
Предел Бреммермана дает оценку сложности задачи с точки зрения объекта данных, который необходимо обработать для решения задачи. Однако возможны условия, при которых задача может находиться за пределом Бреммермана, но практически неразрешимой. Причиной этого является размерность временной и пространственной функцией вычисления, под которым понимается соответственно время и объект памяти ЭВМ, которые необходимы для реализации алгоритма.
Разбор этих вопросов выходит за пределы нашего предмета и рассматривается в общей теории алгоритмов.
Понятие «сложность объекта» как части внешнего мира (окружающей среды) широко используется в философии и естествознании. Следует различать две модификации сложности: (когда свойства целого сводится к сумме свойств составных элементов) и неоддитивную сложность-целостность, свойство которой не сводится к сумме свойств ее элементов. Та или другая модификация используется в зависимости от условий и задачи. Соответственно разработаны два основных принципа оценки сложности. В основе первого лежит оценка объекта информации необходимой для описания системы объекта. В основе второго — объекта информации необходимой для разрешения нечеткости (неопределенности) системы.
Описание аддитивной или иначе дескриптивной сложности сводится к оценке числа элементов системы, их состояний и отношений между ними. Информация необходимая для списания этой модификации сложности понимается в синтаксическом смысле. Поэтому эту модификацию иначе называют дескриптивная сложность. Мера дескриптивной сложности I(X1) должно удовлетворять следующим условиям
I(ф) = 0
Если X1 ⊂ X2, то I(X1) < I(X2)
Если X1 и X2 изоморфны, то I(X1) = I(X2)
Если X1 ∩ X2 = ∅,то I(X1 ∩ X2) = I(X1)+I(X2)
Дескриптивная мера сложности обеспечивает потребности решение системных задач, объектом которых являются детерменированные системы. Однако в классе недертеминированных систем эта мера сложности уже неприемлема, так как она не позволяет учесть сложность, которую вносит нечеткость стохастической системы. В этом случае необходимо использовать другой принцип оценки сложности в виде объема информации необходимого для разрешения нечеткости полного множества состояний. Здесь также имеется в виду синтаксическая информация. Однако оценка ее объекта основывается на мерах нечеткости. Сложность систем с этой позиции изучалась с разных сторон. Однако наиболее конструктивными представляются результаты, полученные в теории информации.
В теории информации достаточно хорошо разработан механизм оценки сложности вероятностных систем на основе статистической меры количества информации предложенной К.Шенноном. Здесь за количество информации необходимого для описания системы принимается величина равная энтропии системы. Рассмотрим ряд важных энтропийных оценок сложности на принципе решения задач.
1. Пусть система S содержит N переменных, каждая переменная имеет К состояний, и пусть все состояния системы равновероятны. У такой системы мощность полного множества состояний равна |C| = kN, вероятностная функция ограничений имеет вид P = {Pi = Pj = 1/kN}. В этом случае энтропия будет равна
H = N•log(K)
Нетрудно видеть следующее. Для систем S(N1,K) и S(N2,K), если N1 > N2, то H1 > H2, для системы S(N1+N2,K), H = H1+H2.Для систем S(N,K2), если K1 > K2, то H1 > H2.
Из этого следует, что энтропийная мера сложности обладает всеми свойствами дискриптивной сложности.
2. Пусть даны системы S1, S2, S3, состоящие из одной переменной с двумя состояниями, т.е. К=1, N=2. Вероятностные функции ограничения полного множества состояний соответственно имеют вид P1=(P1=0,2, P2=0,2), P2=(P1=0,5, P2=0,5), P3=(P2=0,7, P2=0,3).
На рис. показаны значения энтропий для этих систем.
Как видим три системы, обладающие одинаковым множеством элементов и состояний, имеют разные уровни энтропийной сложности. Следовательно, энтропийная мера сложности учитывает количественные свойства элементов, что не позволяет сделать дескриптивное.
