Системная сложность. Трансвычислительные задачи

Размещено на http://www.allbest.ru/

Министерство образования и науки Российско й Федерации

Севастопольский государственный университет

Кафедра ИТ

РЕФЕРАТ

«Системная сложность. Трансвычислительные задачи»

Выполнил: Лагутина Д.А.

Проверил: Голикова

Севастополь - 2014

СОДЕРЖАНИЕ

1. ТЕОРИЯ СЛОЖНОСТИ

1.1 ИСТОРИЯ

1.2 ТЕОРИЯ ХАОСА И СЛОЖНОСТИ

1.3 ФИЛОСОФИЯ

2. ТРАНСВЫЧИСЛИТЕЛЬНАЯ ЗАДАЧА

1. ТЕОРИЯ СЛОЖНОСТИ

1.1 ИСТОРИЯ

Пионером в теории сложности традиционно считают Эдварда Лоренца. Он работал над проблемами долгосрочных прогнозов погоды. Используя достаточно простую математическую модель, построенную всего на двенадцати формулах, он с помощью компьютера симулировал различные метеорологические условия. Однажды он протестировал модель с заданными условиями, а затем повторил ее с очень небольшими изменениями. Лоренц оставил все начальные условия старыми, но ввел данные не с точностью шесть цифр после запятой, как в предыдущем случае, а три цифры. Отклонения были ничтожными - менее одной тысячной. Лоренц предполагал, что эта модель ничем не будет отличаться от старой. К его удивлению развитие модели оказалось иным и привело к совершенно неожиданным результатам. Этот эксперимент привел к появлению известного в теории хаоса «принципа бабочки»: один хлопок крылышек бабочки в Амазонии может привести к тайфуну в Китайском море.

Продолжая исследования, Лоренц пришел к выводу о невозможности точного долгосрочного предсказания погоды, не только из-за множества переменных, которые надо принимать во внимание, сколько в необъяснимости последствий, вызываемых малейшими изменениями условий. Однако существуют определенные паттерны, называемые «странными аттракторами», которые в этом море непредсказуемости представляются островками стабильности, делающими возможным прогнозы. Например, погоды в Сахаре отличаются особой непредсказуемостью, однако можно быть уверенным в этой пустыне не пройдут тропические дожди. Результаты своих исследований Лоренц опубликовал в журнале по метеорологии в 1963 году.

Теория сложности и хаоса получила дальнейшее развитие в 70-е и в 1984 году был основан самый известный центр изучения хаоса и сложности - Институт Санта Фе, в котором собрались ученые, представляющие самые разные отрасли науки. С самого своего начала теория сложности развивалась как междисциплинарная наука, охватывающая не только метеорологию, химию или биологию, но и социальные науки: психологию, социологию, экономику.

1.2 ТЕОРИЯ ХАОСА И СЛОЖНОСТИ

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

В теории сложности существуют шесть основных теоретических понятий:

· чувствительность к первоначальным условиям,

· странные аттракторы,

· самотождественность,

· самоорганизация,

· край хаоса,

· холмистый ландшафт.

Исследования Лоренца и других ученых доказали, что долгосрочное прогнозирование невозможно во всех открытых сложных системах. Малейшее изменение первоначальных условий приводит к иным результатам. В то же время во всех этих результатах, как бы они ни отличались друг от друга, присутствовал единый, общий для всех паттерн. Кроме того, Лоренц продемонстрировал, как модели с разными начальными условиями приводили к одному и тому же результату. Казалось, что непредсказуемые системы тем не менее «тянутся» или «привлекаются» к определенным упорядоченным структурам. Отсюда происходит термин «аттрактор» от английского слова attract - «привлекать». Сначала этот феномен назывался «аттрактор Лоренца», но сегодня более распространенный термин - «странный аттрактор». Процессы, происходящие в системе, никогда в точности не повторяются, но они всегда остаются в рамках определенного паттерна. Последователи теории хаоса утверждают, что все открытые системы, изучаемые физикой, химией, биологией, следуют странным аттаркторам.

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

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

Феномен «грани хаоса» был независимо открыт Норманном Паккардом и Крисом Лэнгтоном. Грань хаоса - это узкая зона между системой, еще находящейся в состоянии порядка, и хаосом, разрушающим систему. Именно в этой зоне системы, находящиеся в шаге от смерти, вдруг проявляют неожиданные способности к созданию новых адаптивных структур, спасающих их от разрушения и восстанавливающих равновесие. Именно в системах, находящихся на грани хаоса, проявляются процессы самоорганизации, обнаруженные Пригожиным.

Кауфман, занимавшийся исследованиями в области медицины в Институте Санта Фе, является автором еще одной концепции теории сложности, которая называется «холмистым ландшафтом». В основе этой концепции лежит понимание, что отрытые системы живут только благодаря среде, которая в свою очередь состоит из других систем. Кауфман представлял среду сосуществования систем, как холмистый ландшафт, география которого являются непредсказуемой для каждой из систем. Каждый из холмов ландшафта, символизирующий успех и высокую эффективность, отделен от другого низинами, отличающимися нестабильностью, низкой эффективностью и дисбалансом. Жизнь любой системы - это путешествие по такому холмистому ландшафту. Забраться на вершину помогает или случай или целенаправленная деятельность. Однако, достижение новых вершин может быть чрезвычайно рискованным, т.к. для этого приходится проходить через предательские низины. Любая вершина будет опускаться и постепенно превращаться в низин, если на ней находятся слишком много систем. Точно также низина, покрываясь толстым слоем, может подрасти и превратиться в холм.

1.3 ФИЛОСОФИЯ

Когда Черчмен формулировал свои взгляды на социальные системы, он опирался на общие западные философские традиции и американский прагматизм, в особенности Э.А. Сингера. Наиболее полно свои принципы он изложил в книге «Системный подход» (1968), выраженные в четырех афоризмах (ниже приведем только два):

В области системного мышления не может быть экспертов

Не может существовать какой-либо определенной области науки, которая могла бы претендовать на то, что может разрешать проблем с помощью системного подхода. Возможно лишь представления взглядов с различных точек зрения, которые стремятся к объединению в процессе научного познания. Специалисты в области системного мышления могут стать слишком самонадеянными, так как они ищут пути взглянуть на систему как на целое. Необходимо очень внимательно относиться к взглядам «врагов». Ведь только таким образом можно реально расширить объективное представление о системе.

Системный подход - это неплохая идея

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

Мейсон и Митрофф (1981) существенно дополнили теорию Черчмена. Они признали необходимость взгляда на системные проблемы в целом. Необходимо, чтобы большее количество участников в процессе решения проблемы, каждый из которых принесет свое отношение к проблеме и свой взгляд на мир. По мнению Мейсона и Митроффа проблема с современной теорией планирования заключается в том, что она отвергает возможность включить в процесс планирования разные, а порой и диаметрально противоположные взгляды. Большинство организаций просто игнорирует проблемы, которые не согласуются с принятым планом действий. План может быть утвержден лишь после того, как стало понятно, что он отвечает на все вопросы, поставленные с альтернативных точек зрения. Кроме того, сам по себе план должен быть достаточно гибким, чтобы существовала возможность его изменения под воздействием не только новых обстоятельств, но и новых альтернативных точек зрения. Организация только тогда начинает обучаться, когда ее взгляды постоянно подвергаются атакам со стороны конкурирующих взглядов на жизнь. Обучение - это не умение твердо отстаивать свою «единственно правильную» точку зрения, а способность органически включать в себя новые взгляды, совершенствуясь в таланте видеть мир как целое.

хаос аттрактор философский трансвычислительный

2. ТРАНСВЫЧИСЛИТЕЛЬНАЯ ЗАДАЧА

Трансвычислительная задача -- в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации. Число 1093, называемое «пределом Бремерманна», согласно Гансу Бремерманну, представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю за период времени, равный общему времени существования Земли. Термин «трансвычислительность» был предложен Бремерманном.

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

Ханс Бремерманн

Если задача трансвычислительная, то чтобы ее можно было решать, она должна быть переформулирована.

Примеры трансвычислительных проблем

· Задача коммивояжёра (коммивояжер, который должен посетить ряд населенных пунктов так, чтобы в каждом побывать только раз. Необходимо найти кратчайшую дорогу для путешествия. Если имеется n городов, то количество вариантов путей составит n!. Таким образом, на машине с четырёхядерным процессором 2,67 ГГц 10 узлов обсчитывается в среднем за 5 миллисекунд, 20 узлов - за 15 минут, а на расчёт оптимального пути для 60 узлов уйдёт более 6 триллионов лет…).

· Тестирование интегральных схем (например, тестирование интегральной схемы с 308 входами и 1 выходом требует проверки 2308 комбинаций).

· Распознавание образов (рассмотрим массив qxq, каждый квадрат раскрашен в один из k цветов. Всего возможно kn цветных узоров (образов), где n=q2. Для двух цветов и массива 18*18 число узоров равно 2324 1).

· Проблема анализа систем (система с n переменными, каждая из которых может принимать k значений может иметь kn состояний. Задача становится трансвычислительной, если система, например, имеет 102 переменных, которые могут принимать 8 значений).

Размещено на Allbest.ru