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

Меню сайта
Категории раздела
Рефераты (курсы КП, ПК, ИТ и Сети) [95]
Рефераты по курсу "Компьютерный практикум", "Применение персональных компьютеров", "Информационная техника" и "Сети ПК" в НИЯУ МИФИ
Аналитика (курсы КП, ПК, ИТ и Сети) [1]
ТЗ учебных проектов [7]
Виртуальные калькуляторы [2]
Пресс-релизы [4]
Материалы по итогам учебных проектов
Наш опрос
Оцените сайт олимпиады
Всего ответов: 120
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » Публикации студентов МИФИ » Рефераты (курсы КП, ПК, ИТ и Сети)

Невычислимые задачи

                     НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ                    

ЯДЕРНЫЙ УНИВЕРСИТЕТ

МОСКОВСКИЙ ИНЖИНЕРНО ФИЗИЧЕСКИЙ ИНСТИТУТ

(НИЯУ МИФИ)

Факультет автоматики и электроники

 

Предел Бреммерманна — невычислимые задачи    

 


 

Выполнил:

 Студент группы А4-11

 Смуров А.А.

mr.shine@li.ru

Преподаватель:

 Доцент Лапшинский В.А.

Москва 2011


Содержание

Введение 
Глава 1. Основы теоретико-множественного описания и анализа систем
1.1. Система объекта 
1.2. Структура системы
1.3. Полное множество состояний системы
1.4. Функция, ограниченная на полном множестве состояния
1.5. Мера нечеткости множества состояний системы
Глава 2. Системная сложность. Предел Бреммерманна
2.1. Системная сложность
2.2. Предел Бреммерманна
2.3. Доказательство предела Бреммерманна 
Заключение 
Список литературы  

Глава 1
Основы теоретико-множественного описания и анализа систем

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

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

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

D: Si = [Si,j, j={1,N}] → Xi = [Xi,j,j={1,N}],

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

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

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

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

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

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

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

    X1,j, X2,p, ..., Xk,c ∈ C1

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

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

    C2 ⊂ X×X

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

    D ⊂ X×T

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

    Э ⊂ C1×C2×D

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

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

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

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

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

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

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

Ci = [α1,k1, X2,k2, ..., XN, kN]

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

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

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

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

f0: C → P,

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

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

f0 = 1, если с ⊂ C^,

f0 = 0, если с П ¬in; C^,

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

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

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

f0 : C^ → Т, Т → C^

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

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

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

f0 = 1, если при t = ti, C = Ci

f0 = 0, если при t = ti, C ≠ Ci

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

f0 : |С| → [0,1]

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

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

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

где Pt< = Nk/∑Nk

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

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

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

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

Где Wk = Nk/max Ni, i ∈ |С|

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

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

CkО1О2О3NkPkWk1
1000100-10,532
200150,050,173
3010200,20,164
401150,050,175
51000006
6101300,31,07
7110100,10,338
8111200,20,61
 ∑Nk=100∑Pk=1SWk≠1

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

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

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

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

H : P → [0, ∞]

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

H = −∑p(Ci)logp(Ci)

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

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

0 ≤ Н ≤ log2|C|

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

H^ = H/log2|C|

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

0 ≤ Н^ ≤ 1

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

Рассмотрим систему на множестве интервалов наблюдения [T1, T2, T3, ...]. В этом случае возможно, что от интервала наблюдения Hi = Hj, уменьшает [H1 > H2 > H3 > ...] или возрастает [H1 < H2 < H3 < ...]. В зависимости от характера интервалов энтропии на множестве интервалов наблюдения различают системы:

  • закрытые, если [H1 < H2 < H3 < ...]
  • открытые, если [H1 ≥ H2 ≥ H3 ≥ ...]
Глава 2
Системная сложность. Предел Бреммерманна.

2.1. Системная сложность

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

Анализ системной сложности должен дать ответ на следующие фундаментальные вопросы. Во-первых, о разрешимости. Если задача неразрешима, то необходимо ее переформулировка. Во-вторых, следует определить класс сложности задачи. Класс сложности задачи можно определить следующим показателями: приделом Бремермана, приделом возможностей вычислительной техники, приделом сложности варианта системы объекта.


Рис. 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. Трансвычислительное биологическое устройство

Заключение

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

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


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

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

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

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



 





Категория: Рефераты (курсы КП, ПК, ИТ и Сети) | Добавил: mrShine (06.06.2011)
Просмотров: 1268 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа
Поиск
Друзья сайта