43. Теория хаоса
Это раздел математики, который занимается явно случайным или непредсказуемым поведением в детерминированных системах.
Хаотическое поведение обычно наблюдается вокруг нас в текущих жидкостях, погоде, дорожном движении, качающихся маятниках и многом другом.
Основатель современной теории хаоса Эдвард Лоренц заметил, что незначительные различия в начальных условиях могут привести к сильно расходящимся результатам для детерминированных систем (систем, будущее поведение которых полностью определяется их начальными условиями).
Это делает их непредсказуемыми в долгосрочной перспективе.
Лоренц заметил это во время своих расчетов прогноза погоды, если начальные условия были введены с 6 знаками после запятой, результаты сильно отличались бы от результатов, когда использовались 3 знака после запятой.
Другим примером хаотической, но детерминированной системы является маятник с двумя стержнями, как показано ниже.
Эффект бабочки
Это важный принцип теории хаоса, который гласит, что крошечные изменения в начальных условиях могут привести к резким изменениям в долгосрочном состоянии системы.
Как образно выразился Лоренц, взмах крыльев бабочки в Бразилии может повлиять на торнадо в Техасе.
Аттрактор
Аттрактор - множество состояний, к которым в конечном итоге приближаются соседние состояния.
В примере с качающимся маятником точка, к которой маятник в конце концов останавливается, является аттрактором этой динамической системы.
Лоренц Аттрактор
Лоренц описал земную атмосферу с помощью конвекции движущейся жидкости, используя три нелинейных уравнения.
Выходы этих уравнений образуют загадочную кривую, которая никогда не пересекается, никогда не достигает равновесия и демонстрирует хаос.
Эта кривая называется аттрактором Лоренца.
44. Задача о рюкзаке
Допустим, есть вор, у которого есть рюкзак/рюкзак, способный выдержать ограниченный вес.
Какие коробки из следующего следует выбрать, чтобы максимизировать денежную стоимость украденных вещей, сохраняя при этом общий вес меньше или равным 15 кг?
Это проблема оптимизации, обычно возникающая при распределении ресурсов в условиях ограничений.
Не существует известного алгоритма, который может дать правильное и быстрое (полиномиальное время) решение всех случаев задачи (Задача NP-полная).
Если мы проверим все возможные комбинации, чтобы найти оптимальное решение проблемы, этот алгоритм грубой силы займет O(2^n) времени, то есть неполиномиальное время.
45. Задача коммивояжера
Представьте, что есть продавец со списком городов для доставки посылок.
Проблема начинается с вопроса:
В каком порядке они должны ездить в разные города, чтобы их общее расстояние было минимальным?
Это NP-сложная задача, в которой для поиска решения используется компьютерный алгоритм грубой силы с временной сложностью Big O O(n!).
Решения проблемы описаны в замечательной статье Педрама Атаи в журнале Towards Data Science:
Новое решение этой проблемы было недавно опубликовано и хорошо объяснено в статье ниже:
Ученые-компьютерщики побили рекорд среди путешествующих продавцов
«Это результат, к которому я стремился всю свою карьеру, — сказал Дэвид Уильямсон из Корнельского университета, изучавший…www.quantamagazine.org»
Проблема также применялась в других областях, таких как астрономия и синтез ДНК.
Ознакомьтесь с другими частями этой серии ниже:
Это все, что нужно для этой статьи. Спасибо за прочтение!
Если вы новичок в Python или программировании в целом, ознакомьтесь с моей новой книгой под названиемThe No Bulls**t Guide To Learning Pythonниже:
