Сложность: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Создано переводом страницы «Complexity»
(нет различий)

Версия от 09:36, 14 января 2021

Сложность характеризует единство поведения системы или модели, которое получается не на основе единых принципов, а в результате взаимодействий отдельных элементов, в которых каждый элемент действует на основании своих собственных локальных принципов[1].

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

По состоянию на 2010 год используются несколько подходов к характеристике сложности[2]. Нил Джонсон утверждает, что «даже среди ученых нет единого определения сложности - и научное понятие традиционно передавалось на конкретных примерах". В конечном итоге Джонсон принимает определение «науки о сложности» как «изучение явлений, возникающих из совокупности взаимодействующих объектов»[3].

Обзор

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

В 1948 году Уоррен Уивер провел различие между двумя формами сложности: дезорганизованной сложностью и организованной сложностью[4]. Явления «неорганизованной сложности» рассматриваются с использованием теории вероятностей и статистической механики, в то время как «организованная сложность» имеет дело с явлениями, которые требуют «одновременного рассмотрения значительного числа факторов, взаимосвязанных в единое целое». Работа Уивера 1948 года повлияла на последующие исследования сложности[5].


Дезорганизованная и организованная сложность

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

Уивер решал эту проблему тем, что проводил различие между «дезорганизованной сложностью» и «организованной сложностью».

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

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

Организованная сложность, с точки зрения Уивера, заключается в неслучайном или коррелированном взаимодействии между частями. Эти коррелированные взаимодействия создают скоординированную структуру, которая как система может взаимодействовать с другими системами. Скоординированная система проявляет свойства, не характерные для ее частей. Можно сказать, что организованный аспект этой системы «возникает» без какой-либо «направляющей руки».

Количество частей не должно быть очень большим, чтобы конкретная система имела эмерджентные свойства. Систему организованной сложности можно понять по ее свойствам (поведению) посредством моделирования и симуляции, в частности, моделирования и симуляции с помощью компьютеров . Примером организованной сложности является городской квартал как живой механизм, с его жителями как частями системы[6].

Источники и факторы

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

Источником дезорганизованной сложности является большое количество частей в системе и отсутствие корреляции между её элементами.

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

Сложность объекта или системы - свойство относительное. Например, для многих функций (задач) такая вычислительная сложность, как время вычислений, меньше, когда используются многоленточные машины Тьюринга, чем когда используются машины Тьюринга с одной лентой. Машины с произвольным доступом к памяти позволяют еще больше уменьшить временную сложность (Greenlaw and Hoover 1998: 226), в то время как индуктивные машины Тьюринга могут снизить даже класс сложности функции, языка или множества (Burgin 2005). Это показывает, что инструменты деятельности могут быть важным фактором сложности.

Другие значения

В нескольких областях науки «сложность» имеет иное, точно определенное значение:

  • В теории сложности вычислений изучается количество ресурсов, необходимых для выполнения алгоритмов. Самыми распространёнными типами вычислительной сложности являются:
    • временная сложность задачи, равная количеству шагов, необходимых для решения отдельной задачи, в зависимости от размера входных данных (обычно измеряемых в битах) с использованием наиболее эффективных алгоритмов,
    • пространственная сложность задачи, равная объему памяти, используемой алгоритмом (например, ячейки ленты), которая требуется для решения отдельной проблемы, как функция размера входных данных (обычно в битах), при использовании наиболее эффективного алгоритма. Это позволяет классифицировать вычислительные задачи по классам сложности (например, P, NP и т. д.). Аксиоматический подход к вычислительной сложности был разработан Мануэлем Блюмом . Он позволяет вывести многие свойства мер вычислительной сложности, таких как временная сложность или пространственная сложность, из свойств аксиоматически определенных мер.
  • В алгоритмической теории информации колмогоровская сложность (также называемая описательной сложностью, алгоритмической сложностью или алгоритмической энтропией ) строки - это длина самой короткой двоичной программы, которая выводит эту строку. Минимальная длина сообщения - это практическое применение этого подхода. Изучаются различные виды колмогоровской сложности: равномерная сложность, префиксная сложность, монотонная сложность, ограниченная по времени сложность по Колмогорову и ограниченная по пространству сложность по Колмогорову. Аксиоматический подход к колмогоровской сложности, основанный на аксиомах Блюма (Blum 1967), был предложен Марком Бургином в статье, представленной для публикации Андреем Колмогоровым[8]. Аксиоматический подход охватывает другие подходы к колмогоровской сложности. Можно рассматривать различные виды колмогоровской сложности как частные случаи аксиоматически определенной обобщенной колмогоровской сложности. Вместо того, чтобы доказывать аналогичные теоремы, такие как основная теорема инвариантности, для каждой конкретной меры, можно легко вывести все такие результаты из одной соответствующей теоремы, доказанной в аксиоматической ситуации. Это общее преимущество аксиоматического подхода в математике. Аксиоматический подход к сложности Колмогорова получил дальнейшее развитие в книге (Burgin 2005) и был применен к программным метрикам (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
  • В теории информации сложность информации - это флуктуация информации по отношению к информационной энтропии. Он выводится из флуктуаций преобладания порядка и хаоса в динамической системе и используется в качестве меры сложности во многих различных областях.
  • При обработке информации сложность - это мера общего количества свойств, передаваемых объектом и обнаруживаемых наблюдателем. Такой набор свойств часто называют состоянием.
  • В физических системах сложность - это мера вероятности вектора состояния системы. Её не следует путать с энтропией; это особая математическая мера, в которой два различных состояния никогда не объединяются и не считаются равными, как это делается с понятием энтропии в статистической механике .
  • В динамических системах статистическая сложность измеряет размер минимальной программы, способной статистически воспроизвести шаблоны (конфигурации), содержащиеся в наборе данных (последовательности)[9][10]. В то время как алгоритмическая сложность подразумевает детерминированное описание объекта (оно измеряет информационное содержание отдельной последовательности), статистическая сложность, такая как сложность прогнозирования[11], подразумевает статистическое описание и относится к ансамблю последовательностей, генерируемых определенным источником. Формально статистическая сложность воссоздает минимальную модель, содержащую совокупность всех траекторий, имеющих одинаковое вероятностное будущее, и измеряет энтропию распределения вероятностей состояний в этой модели. Это вычислимая и независимая от наблюдателя мера, основанная только на внутренней динамике системы, которая использовалась в исследованиях возникновения и самоорганизации[12].
  • В математике сложность Крона – Родса является важной темой при изучении конечных полугрупп и автоматов.
  • В теории сетей сложность является продуктом многообразия связей между компонентами системы[13] и определяется очень неравномерным распределением определённых показателей (некоторые элементы сильно связаны, а некоторые связаны очень мало, см. сложная сеть).
  • В программной инженерии сложность программирования - это мера взаимодействия различных элементов программного обеспечения. Это понятие отличается от описанной выше вычислительной сложности тем, что является мерой дизайна программного обеспечения.
  • В абстрактном смысле - абстрактная сложность, основана на восприятии визуальных структур[14]. Это сложность двоичной строки, определяемая как квадрат количества признаков, делённый на количество элементов (нулей и единиц). Признаки здесь включают в себя все отличительные расположения нулей и единиц. Хотя количество признаков всегда определяется приблизительно, определение является точным и отвечает интуитивным критериям.

Другие области науки вводят менее точно определённые понятия сложности:

  • Сложная адаптивная система имеет некоторые или все следующие атрибуты[3]:
    • Количество частей (и типов частей) в системе и количество отношений между частями нетривиально - однако нет общего правила, чтобы отделить «тривиальное» от «нетривиального»;
    • Система имеет память или обратную связь;
    • Система может адаптироваться в зависимости от своей истории или обратной связи;
    • Отношения между системой и ее окружением нетривиальны или нелинейны;
    • На систему может влиять окружающая среда или она может адаптироваться к ней;
    • Система чувствительна к начальным условиям.

Изучение

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

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

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

Темы исследований

Поведение

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

Механизмы

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

Симуляции

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

Системы

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

Данные

В теории информации алгоритмическая теория информации занимается сложностью строк данных.

Сложные строки сложнее сжать. Хотя интуиция подсказывает нам, что это может зависеть от кодека, используемого для сжатия строки (кодек теоретически может быть создан на любом произвольном языке, включая тот, в котором очень маленькая команда «X» может заставить компьютер выводить очень сложную строку, например «18995316»), любые два полных по Тьюрингу языка могут быть реализованы друг в друге, а это означает, что длина двух кодировок на разных языках будет варьироваться не более чем на длину «языка перевода», что в конечном итоге будет незначительным для достаточно длинных строк данных.

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

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

Недавняя работа в области машинного обучения исследовала сложность данных, поскольку она влияет на производительность контролируемых алгоритмов классификации. Хо и Басу представляют набор мер сложности для задач бинарной классификации[16].

Меры сложности в целом охватывают:

  • наложения в значениях признаков из разных классов
  • делимость классов
  • меры геометрии, топологии и плотности многообразий; жёсткость событий (instance hardness) - это ещё один подход, который стремится охарактеризовать сложность данных с целью их правильной классификации и не ограничивается двоичными проблемами[17].

Жёсткость событий (instance hardness) - это новый подход, который в первую очередь направлен на выявление событий, которые могут быть неправильно классифицированы (или, другими словами, на выявление событий, которые могут быть наиболее сложными). Характеристики событий, которые могли быть классифицированы неправильно, затем измеряются на основе показателей жёсткости. Меры жёсткости основаны на нескольких методах обучения с учителем, таких как измерение количества несовместимых соседей или вероятности присвоенной метки класса с учётом входных характеристик. Информация, предоставляемая мерами сложности, была исследована на предмет использования в метаобучении, чтобы определить, для каких наборов данных фильтрация (или удаление подозрительных зашумленных экземпляров из обучающего набора) является наиболее выгодной[18] и может быть расширена на другие области.

В молекулярном распознавании

Недавнее исследование, основанное на молекулярном моделировании и константах соответствия, описывает молекулярное распознавание как явление организации[19]. Даже для небольших молекул, таких как углеводы, процесс распознавания невозможно предсказать или спроектировать, в том числе если предположить, что сила каждой отдельной водородной связи точно известна.

Приложения

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

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

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

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

См. также

 

Примечания

  1. ↑ Ошибка: не задан параметр |заглавие = в шаблоне {{публикация}}. — ISBN 978-3411040742.
  2. ↑ J. M. Zayed, N. Nouvel, U. Rauwald, O. A. Scherman. Chemical Complexity – supramolecular self-assembly of synthetic and biological building blocks in water. Chemical Society Reviews, 2010, 39, 2806–2816 http://pubs.rsc.org/en/Content/ArticleLanding/2010/CS/b922348g
  3. ↑ 1 2 Johnson, Neil F. Chapter 1: Two's company, three is complexity // Simply complexity: A clear guide to complexity theory. — Oneworld Publications, 2009. — P. 3. — ISBN 978-1780740492.
  4. ↑ Weaver, Warren (1948). "Science and Complexity" (PDF). American Scientist. 36 (4): 536—44. PMID 18882675. Дата обращения: 21 ноября 2007.
  5. ↑ Ошибка: не задан параметр |заглавие = в шаблоне {{публикация}}. — ISBN 978-0-684-86875-2.
  6. ↑ Jacobs, Jane. The Death and Life of Great American Cities. — New York : Random House, 1961.
  7. ↑ Ulanowicz, Robert, "Ecology, the Ascendant Perspective", Columbia, 1997
  8. ↑ Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Notices of the Russian Academy of Sciences, v.25, No. 3, pp. 19–23
  9. ↑ Crutchfield, J.P. (1989). "Inferring statistical complexity". Physical Review Letters. 63 (2): 105—108. Bibcode:1989PhRvL..63..105C. doi:10.1103/PhysRevLett.63.105. PMID 10040781.
  10. ↑ Crutchfield, J.P. (1999). "Thermodynamic depth of causal states: Objective complexity via minimal representations". Physical Review E. 59 (1): 275—283. Bibcode:1999PhRvE..59..275C. doi:10.1103/PhysRevE.59.275.
  11. ↑ Grassberger, P. (1986). "Toward a quantitative theory of self-generated complexity". International Journal of Theoretical Physics. 25 (9): 907—938. Bibcode:1986IJTP...25..907G. doi:10.1007/bf00668821.
  12. ↑ Prokopenko, M. (2009). "An information-theoretic primer on complexity, self-organisation and emergence". Complexity. 15 (1): 11—28. Bibcode:2009Cmplx..15a..11P. doi:10.1002/cplx.20249.
  13. ↑ A complex network analysis example: "Complex Structures and International Organizations" (Grandjean, Martin (2017). "Analisi e visualizzazioni delle reti in storia. L'esempio della cooperazione intellettuale della Società delle Nazioni". Memoria e Ricerca (2): 371—393. doi:10.14647/87204. See also: French version).
  14. ↑ Mariusz Stanowski (2011) Abstract Complexity Definition, Complicity 2, p.78-83
  15. ↑ Bastardas-Boada, Albert. "Complexics as a meta-transdisciplinary field". Congrès Mondial Pour la Pensée Complexe. Les Défis d'Un Monde Globalisé. (Paris, 8-9 Décembre). Unesco.
  16. ↑ Ho, T.K.; Basu, M. (2002). "Complexity Measures of Supervised Classification Problems". IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (3), pp 289–300.
  17. ↑ Smith, M.R.; Martinez, T.; Giraud-Carrier, C. (2014). "An Instance Level Analysis of Data Complexity". Machine Learning, 95(2): 225–256.
  18. ↑ Sáez, José A. (2013). "Predicting Noise Filtering Efficacy with Data Complexity Measures for Nearest Neighbor Classification". Pattern Recognition. 46: 355—364. doi:10.1016/j.patcog.2012.07.009.
  19. ↑ Jorg Grunenberg (2011). "Complexity in molecular recognition". Phys. Chem. Chem. Phys. 13 (21): 10136—10146. Bibcode:2011PCCP...1310136G. doi:10.1039/c1cp20097f. PMID 21503359.

Литература

 

Ссылки

Источник — https://ru.wikipedia.org/w/index.php?title=Сложность&oldid=111719135