Комментарии 3
А что с случаем, когда входные данные только ограничивают обьем выходных данных? Что происходит тогда в ракурсе теории?
Добрый день! Огромное спасибо за статью (хотела лайкнуть, но, увы, не получилось). Начала изучать питон, и как раз попалась ваша статья. Посмотрю как все эти алгоритмы на питоне пишутся, возьму за образец))
Сделаю несколько небольших замечания, раз уж мы этого коснулись.
1. Можно было в начале статьи упомянуть о разумных схемах кодирования - чтобы искусственное раздувание входа не превратило в NP-hard в P.
2. Можно было упомянуть отдельный подкласс NP-полных задач, которые решаются за псевдополиномиальное время динамическим программированием. Классический пример (собственно, задача тысячелетия) - набор заданной суммы B с помощью n заданных целых слагаемых. Сложность Ο(nB) - не экспоненциальная. Тут вот и разумные схемы кодирования пригодились бы.
3. Вы взяли для примера поиск в глубину и коммивояжера. Пример хороший, но он выглядел бы более эффектно, если бы коммивояжер был написан алгоритмом с возвратом (backtracking). Оказалось бы, что эти алгоритмы (глубина и алгоритм с возвратом на стратегии поиска в глубину), по сути, отличаются одной строчкой. В глубине при возврате вершина остается просмотренной, поэтому мы генерируем ровно один путь за линейное время. А в бэктрекинге при возврате вершина обновляется, поэтому генерируем все пути между двумя фиксированными вершинами за экспоненциальное время.
С другой стороны, если всё это написать, то получилась бы полуторачасовая лекция)) Еще раз спасибо за большое количество примеров программ на питоне.
Дико извиняюсь, но в статье всё смешалось в кучу, а теория систем, как мне кажется, так вообще притянута за уши и осталась не понятой автором. Например следующие фразы оставили в моей голове одни вопросы.
Примером эмерджентности в программировании ожет служить поведение распределенной системы, где простое взаимодействие отдельных узлов порождает новые паттерны работы.
Разве в этом примере сумма узлов не даёт ответ на вопрос, какая вариативность будет на выходе? По мне, так это просто конгломерат компонентов. Это как набор из 4-х ножек, одного сидения и одной спинки, сложенных рядом, нельзя считать стулом. В общем, не увидел здесь эмерджентных свойств.
Самоорганизация — это способность системы к спонтанной организации и адаптации.
А далее идёт фрагмент кода. О каких порождающихся новых паттернах речь, хотелось бы услышать. Как код смог адаптироваться к условиям внешней среды, мобилизовать свои ресурсы, измениться или создать внутри себя что-то новое, чтобы можно было говорить об адаптаци? Не уловил.
Ашби утверждает, что для эффективного управления системой ее внутренняя сложность должна соответствовать сложности ее окружения. В программировании это означает, что система должна быть достаточно гибкой и масштабируемой, чтобы адаптироваться к меняющимся требованиям и условиям.
Эшби предполагал, что сложность управляющей системы должна соответствовать сложности управляемой системы. В вашем примере есть абстрактная система, которая почему-то должна адаптироваться к внешним условиям, т.е. связи по управлению не прослеживается.
Влияние NP-полноты на системную аналитику
В ряде профильных пабликов за "системную аналитику" вообще могут предать анафеме))
Теория сложности