Сложность

Из Википедии, бесплатной энциклопедии

Метафорическая иллюстрация сложности

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

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

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

Неупорядоченная и упорядоченная сложность[править | править код]

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

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

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

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

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

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

Источники и факторы[править | править код]

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

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

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

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

Конкретизация понятия сложности в различных областях науки[править | править код]

В различных областях науки применяются специализированные, более узкие определения сложности:

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

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

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

Изучение[править | править код]

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

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

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

Темы исследований[править | править код]

Поведение[править | править код]

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

Механизмы[править | править код]

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

Симуляции[править | править код]

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

Системы[править | править код]

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

Данные[править | править код]

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

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

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

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

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

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

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

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

В молекулярном распознавании[править | править код]

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

Приложения[править | править код]

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

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

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

Существует ещё одна форма сложности, которая называется иерархической[en]. Эта форма сложности отражает иерархический аспект систем, задач и проблем и ортогональна обсуждаемым ранее формам сложности, которые, соответственно, могут быть названы, горизонтальными формами сложности.

См. также[править | править код]

Примечания[править | править код]

  1. ↑ ISO/IEC/IEEE 24765:2017 Systems and software engineering — Vocabulary. Дата обращения: 31 мая 2022. Архивировано 31 марта 2022 года.
  2. ↑ Complexity (scientific theory) (англ.). Encyclopædia Britannica. Дата обращения: 14 января 2021.
  3. ↑ Johnson, Steven. Emergence: The Connected Lives of Ants, Brains, Cities. — New York : Scribner, 2001. — P. 19. — ISBN 978-3411040742.
  4. ↑ 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 Архивная копия от 30 января 2021 на Wayback Machine
  5. ↑ 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.
  6. ↑ Weaver, Warren (1948). "Science and Complexity" (PDF). American Scientist. 36 (4): 536—44. PMID 18882675. Архивировано из оригинала (PDF) 9 октября 2009. Дата обращения: 21 ноября 2007.
  7. ↑ Johnson, Steven. Emergence: the connected lives of ants, brains, cities, and software. — New York : Scribner, 2001. — P. 46. — ISBN 978-0-684-86875-2.
  8. ↑ Jacobs, Jane. The Death and Life of Great American Cities. — New York : Random House, 1961.
  9. ↑ Ulanowicz, Robert, «Ecology, the Ascendant Perspective», Columbia, 1997
  10. ↑ 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
  11. ↑ 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.
  12. ↑ 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.
  13. ↑ 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.
  14. ↑ 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.
  15. ↑ Пример из теории сложных сетей: «Complex Structures and International Organizations Архивная копия от 2 ноября 2017 на Wayback Machine» (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. См. также: французскую версию Архивная копия от 7 ноября 2017 на Wayback Machine).
  16. ↑ 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. Архивировано 6 марта 2023. Дата обращения: 14 января 2021.
  17. ↑ 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.
  18. ↑ Smith, M.R.; Martinez, T.; Giraud-Carrier, C. (2014). «An Instance Level Analysis of Data Complexity Архивная копия от 15 января 2021 на Wayback Machine». Machine Learning, 95(2): 225—256.
  19. ↑ 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.
  20. ↑ 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=134903796