Олимпиада "Наноэлектроника"
Неофициальный сайт

1.1. Система объекта

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

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

D: S_i = [S_i,j, j={1,N}] → X_i = [X_i,j,j={1,N}],

где S_i — i-ое свойство, X_i — переменная.

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

Формально система может быть представлена в виде множества:

S = (X, T, R, Z),

где X — множество переменных, T — множество параметров, R — отношения на множества X и T, Z — цель исследований.

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

1. Отношения эквивалентности, имеющее смысл «соседства» значений переменных системы на полном множестве состояний;

   X_1,j, X_2,p, ..., X_k,c ∈ C1

   где X_k,n — значение k-ой переменной.

2. Отношения упорядоченности переменных по роли, вкладу и т. д в достижение цели

   C2 ⊂ X×X

3. Отношения упорядоченности переменных на множестве параметров

   D ⊂ X×T

4. Отношения упорядоченности вида

   Э ⊂ C1×C2×D

Эти виды отношения отражают соответственно структурные (C₁,C₂), динамические (X) и интегративные свойства системы (Э), которые объединяют структурные и динамические (качество, эффективность, безопасность, живучесть и т.д.).

1.2. Структура системы

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

Для приведенных уровней разнообразия справедливо соотношение S4CS3CS2CS1.

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

1.3, Полное множество состояний системы

В системе заданной на множестве переменных X = [X_n, i={1,N}], каждая переменная изменяет свое значение в некоторой области значений заданной множеством физически различных значений X_n ={1,N}[X_n,k, k={1,N}]. Зафиксированное значение всех переменных относительно одного значения параметра представляет вектор состояния системы

C_i = [α_1,k1, X_2,k2, ..., X_N, k_N]

Множество всех возможных векторов состояний C = [C_i , i={1,|C|}], образует полное множество состояний, где |C| = ∏k_n

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

1.4. Функция ограничения на полном множестве состояния

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

f₀: C → P,

где Р — заданное множество.

Предположим, что на множестве интервалов наблюдений объекта для функции ограничения справедливо условие:

f₀ = 1, если с ⊂ C^,

f₀ = 0, если с П ¬_in; C^,

где с — вектор состояния системы, C^ — подмножество полного множества состояний.

В этом случае функция ограничения образует замкнутое множество состояний C^. Такие системы будем называть замкнутыми. В обратном случае, когда от интервала к интервалу наблюдения состав элементов C^ меняется, т.е. функция ограничена для интервалов наблюдений, f₀ⁱ ≠ f₀^j не множественны, то система будет разомкнутой.

Рассмотрим отображение в интервале наблюдения Т множества моментов времени измерений примененных на множестве наблюдаемых состояний C^.

f₀ : C^ → Т, Т → C^

Здесь возможны два случая. В одном отображение однозначно, в другим — многозначно.

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

Для детерминированной системы функция ограничения имеет вид:

f₀ = 1, если при t = t_i, C = C_i

f₀ = 0, если при t = t_i, C ≠ C_i

У стохастической системы в момент наблюдения t = t_i состояние системы С ∈ C^ является случайным. Ограничение полного множества состояний системы в этом случае задается нечеткими функциями типа вероятности, возможности, правдоподобности и др. В общем случае они представляют отображения вида:

f₀ : |С| → [0,1]

При выборе функции ограничения исходят из соотношения мощности полного множества состояний |С| и мощности множества моментов наблюдения |Т|. Если |С| ≤ |Т|, то предпочтительной является функция вероятности. В обратном случае |С| ≥ |Т|, предпочтительней функция возможностей.

Функция вероятности задается в следующем виде:

Р = [P_t , t = {1,|T|}],

где P_t< = N_k/∑N_k

N_k — число наблюдаемых состояний C_k.

|Т| = ∑N_k — общее число наблюдений

Функция возможности определяется следующим образом:

W = [W_k, k={1,k}]

Где W_k = N_k/max N_i, i ∈ |С|

Из приведенных формул видно, что в первом случае наблюденное число состояний системы C_k нормируется относительно общего числа наблюдения |Т|, во втором относительное число состояний с наибольшим значением.

Таблица 1. Число наблюдаемых состояний.

1.5. Мера нечеткости множества состояний системы

У стохастических систем полное множество состояния с позиции их допустимости представляет собой нечеткое множество.

При этом уровень нечеткости может меняться в значительных приделах. Например, если вероятности состояний P(C_i) = P(C_j) равны, то он максимальный, а при уровне P(C_i) = 1 он минимален. Поэтому естественно надо ввести меру нечеткости полного множества состояний уровня нечеткости.

Для вероятностных систем нечетность задается через множество вероятностей состояния системы в виде отображения

H : P → [0, ∞]

В качестве меры уровня нечеткости принята энтропия [ ]. Она определяется по формуле:

H = −∑p(C_i)log_p(C_i)

Из этой формулы видно, что если p(C_i) = 1, то Н = 0, при p(C_i) = 1/|C| H = log₂|C|.

Таким образом, величина энтропии монотонно меняется в пределах:

0 ≤ Н ≤ log₂|C|

Для систем с поперечным множеством состояний можно ввести нормированную энтропию:

H^ = H/log₂|C|

Ее величина меняется в области значений

0 ≤ Н^ ≤ 1

Для возможностных систем аналогично нечеткость вводится через множество возможностей. А мера уровня нечеткости через возможностную энтропию. С формулами расчета этой энтропии можно познакомиться в работе [ ].

Рассмотрим систему на множестве интервалов наблюдения [T₁, T₂, T₃, ...]. В этом случае возможно, что от интервала наблюдения H_i = H_j, уменьшает [H₁ > H₂ > H₃ > ...] или возрастает [H₁ < H₂ < H₃ < ...]. В зависимости от характера интервалов энтропии на множестве интервалов наблюдения различают системы:

• закрытые, если [H₁ < H₂ < H₃ < ...]
• открытые, если [H₁ ≥ H₂ ≥ H₃ ≥ ...]

Рис. 1. О системологии и пределе Бреммерманна

2.2. Предел Бреммерманна

Шутки шутками, но что, если задуматься об объеме такого «жесткого» диска?

В 1964 году Ханс Бреммерман опубликовал статью «Optimization through
evolution and recombination», главный вывод который
заключается в следующем:

Не существует системы обработки данных, искусственной
или естественной, которая бы могла бы обрабатывать более чем 2×10^47 бит
в секунду на грамм своей массы.

Масса Земли оценивается примерно в 6×10^27 г, а возраст 10^10 лет, год
состоит из приблизительно 3.14×10^7 секунд.
Наша воображаемая компьютерная система смогла бы обработать
2,56×10^93 бит, округляя до порядка 10^93 бит. (рис.2)

Рис.2. Генезисы законов роста
производительности компьютерных технологий

Задачи, требующие обработки более чем 10^93 бит информации называются трансвычислительными
задачами. К сожалению, комбинаторика говорит нам, что что такой предел
может быть достигнут для задач даже относительно небольшого размера.
Например, в распознавании образов: пусть есть массив q*q, каждый элемент
которого может быть раскрашен одним из k цветов,
тогда всего вариантов раскраски может быть k^(q*q). Если массив 18×18,
то задача трансверсальна при двух цветах, для массива 10×10
становится трансверсальной при 9 цветах. Понятно, что рассмотреть все
варианты образов сетчатки глаза, имеющий
порядка миллиона светочувствительных колбочек, невозможно. Еще один
пример такой задачи — тестирование микросхемы, у которой 308
входов и всего 1 выход.


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

2.3. Доказательство предела Бреммерманна

Бреммерманн пришел к своему выводу, исходя из следующих соображений.
Для обработки информация должна быть закодирована. Предположим, что она закодирована в виде энергетических уровней в интервале [0, E]. Пусть энергетические уровни измеряются с точностью до dE. Таким образом на всем интервале будет N = E/dE подинтервалов, каждый из которых может быть занят или нет (1 или 0).
Максимальное число битов будет равно log2 (N+1)

Для того, чтобы представить больший объем информации, необходимо сокращать dE. По принципу неопределенности Гейзенберга энергия может быть измерена с точностью до dE, если выполняется dE*dt >= h, где dt — длительность времени измерения, h = 6.625×10^-27 эрг/с (постоянная Планка)

Получаем, N<= Edt/h
Если представить имеющуюся энергию E соответствующим количеством массы согласно формуле Эйнштейна E = mc^2 (Рис.3)

Рис.3. E=mc^2

N = mc^2*dt/h

Подставив с и h, имеем N = 1.35×10^47*m*dt
Для массы 1 г (m = 1) и времени 1с (dt = 1) получаем указанное значение N = 2×10^47 бит.

Рис.4. Трансвычислительное биологическое устройство

Заключение

Великий Эшби пишет:

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

Список литературы

1.       Предел Бреммермана – Невычисливые задачи // http://habrahabr.ru/blogs/personal/54190/

2.       И.Б. Родионов «Системный анализ» // http://victor-safronov.narod.ru/systems-analysis/lectures/rodionov/06.html

3.       Клир Дж. Системология. Автоматизация решения системных задач /Пер. с англ. – М.: Радио и
связь, – 1990, 544 с.