Как стать автором
Обновить

Комментарии 3

Добрый день! Огромное спасибо за статью (хотела лайкнуть, но, увы, не получилось). Начала изучать питон, и как раз попалась ваша статья. Посмотрю как все эти алгоритмы на питоне пишутся, возьму за образец))

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

1. Можно было в начале статьи упомянуть о разумных схемах кодирования - чтобы искусственное раздувание входа не превратило в NP-hard в P.

2. Можно было упомянуть отдельный подкласс NP-полных задач, которые решаются за псевдополиномиальное время динамическим программированием. Классический пример (собственно, задача тысячелетия) - набор заданной суммы B с помощью n заданных целых слагаемых. Сложность Ο(nB) - не экспоненциальная. Тут вот и разумные схемы кодирования пригодились бы.

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

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

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

Примером эмерджентности в программировании ожет служить поведение распределенной системы, где простое взаимодействие отдельных узлов порождает новые паттерны работы.

Разве в этом примере сумма узлов не даёт ответ на вопрос, какая вариативность будет на выходе? По мне, так это просто конгломерат компонентов. Это как набор из 4-х ножек, одного сидения и одной спинки, сложенных рядом, нельзя считать стулом. В общем, не увидел здесь эмерджентных свойств.

Самоорганизация — это способность системы к спонтанной организации и адаптации.

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

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

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

Влияние NP-полноты на системную аналитику

В ряде профильных пабликов за "системную аналитику" вообще могут предать анафеме))

Зарегистрируйтесь на Хабре, чтобы оставить комментарий