Добрый день. Очень интересная статья, добавила к себе в закладки. Я тоже интересуюсь этой тематикой (дискретной оптимизацией и графами). Замечу, что для графов обычно используют не матрицы, а списки инцидентности, особенно для разреженных графов. Для орграфа таких списков будет два: для входящих и выходящих дуг. И, к стыду своему, не знала, что минимальное множество обратных дуг - NP- полная задача. Когда один раз возникла подобная задача для орграфа расчета себестоимости продукции (брак отправляли в металлолом, возникали циклы), с помощью поиска в глубину сформировала множество обратных дуг, благо критерий обратной дуги известен. Спасибо за информацию))
О Яндексе и копейках. История примерно десятилетней давности. Много букв.
В городе Перми два маленьких ребенка на коммунальной кухне переворачивают на себя кастрюлю с пельменями, получают сильнейшие ожоги. Это было вскоре после "хромой лошади", в городе появилось специальное мед.оборудование, детей спасли. Мать детей - из детдома, родственников нет. Известный писатель, человек из википедии, Нина Викторовна Горланова, начинает сбор денег и подключает меня. На forum.sourse.ru (мой ник Swetlana) один человек анонимно (думаю, это был Алекс Лайн) каждый месяц переводит мне 2000 р., я перевожу Н.В на яндекс-кошелек. В какой-то момент Яндекс лишает Н.В. доступа к аккаунту и к кошельку. Я пропускаю это сообщение от Н.В. и успеваю перевести 4000. Н.В. пишет в поддержку Яндекса, выполняет их рекомендации - ничего не получается. В поддержку Яндекса пишу я. Об'ясняю, кто такая Н.В., прошу помочь ей восстановить доступ. Получаю вначале отписки, а затем ответ в стиле: она чё, деньги у вас украла?
Кошелек их тут же закрыла. Верю, что украденные у детей 4000 яндексу ещё аукнутся.
Здравствуйте. В книге Нильса Нильсона "Принципы искусственного интеллекта" минимакс очень понятно описан на примере крестиков-ноликов. Показано, как сделать оценочную эвристическую функцию. Потом можно было бы и о шахматах сказать. Что минимакс хорошо работает, когда идёт размен фигур. Ну и т.д.
Добрый день. Статью пока не осилила, хотя тема мне интересна. Пока не забыла, хочется сделать одно небольшое уточнение и одно пожелание. Унарная (именно так она называется) СС широко применяется для записи чисел на ленте детерминированной машины Тьюринга с последовательным доступом, см. Кузнецов, Адельсон-Вельский "Дискретная математика для инженера".
Теперь по существу дела. Статью (имхо) можно было сделать намного интереснее, если бы статья начиналась с обзора систем счисления различных т.н. "примитивных народов". Например, у народа пираха вообще не сформировалось то ли понятие числа, то ли языковые обозначения для чисел. Во всяком случае, слова для обозначения единицы у них нет.
Здравствуйте. "Паскаль в иллюстрациях" - моя первая книга по программированию. Чудесная книга! Потом у меня ее какой-то студент из Африки зачитал. Спасибо, что напомнили о ней.
Теперь хотелось бы раз'яснить связь между алгоритмами и структурами данных. От выбора структуры данных зависит все: и выбор модели, и, конечно, выбор и эффективность алгоритма. Например, т.н. "транспортные задачи". В матричном представлении решаются линейным программированием, в сетевом - потоковыми алгоритмами.
P.S О(f(n)) <= C*f(n), где C - положительная константа.
Здравствуйте. Сделаю маленькое замечание или, скорее, пожелание. Примеры у вас очень академические. Факториал, например. Если на лекции спросить: Заказчик требует перебрать все циклы в графе, близком к полному. Какова выч. сложность этой задачи? Сразу ответят "n квадрат". Про перестановки все знают, а что гамильтонов цикл тоже перестановка - не догадываются. Лучше бы иллюстрировать такую сложность модельными трудно решаемыми задачами.
Ещё раз спасибо за статью. Всё понятно, осталось только посмотреть пример использования счетчика. Я просто немного в шоке от питона, т.к. ранее писала только на двух простых языках: паскале и прологе. Да, и жду вторую часть))
Здравствуйте! Большое спасибо за статью, как раз разбираюсь с функциями, как и что туда передается.
Методом "научного тыка" обнаружила следующее. Если в функцию не передаём параметры, то конфликт имён (глобальная и локальная переменная с одним именем) вызывает ошибку. Если же глобальная переменная передается через параметр, а затем с именем параметра об'является локальная - никакого конфликта нет. Как-то нелогично.
Может быть, где-то можно про это прочитать, в чем профит?
Спасибо за ответ! Интересно, что сама задача до сих пор жива. Я, похоже, отстала от жизни. 20 лет назад, как теперь говорят, "топила" за графовые алгоритмы vs ЛП. Если задача допускает сетевую постановку, то построение потока будет эффективнее супротив более универсальных алгоритмов.
Получается, однако, что автор в чем-то прав. Все алгоритмы на сетях и графах - мало кому нужная роскошь, не говоря уж о их преподавателях))
Добрый день. Много лет назад я делала похожую задачу о взаимозачетах - нужно было погасить максимально возможный долг в сети предприятий. Делала это построением циркуляции минимальной стоимости алгоритмом дефекта. Который сама модифицировала методом фаз Диница. Но за секунду это работать не будет даже на современных компьютерах, только разложение циркуляции на циклы требует времени. Кстати, циклов тоже в худшем случае м.б. экспоненциальное количество, через одну вершину могут проходить разные циклы.
Не могли бы вы назвать алгоритм, которым можно это сделать за секунду? Очень любопытно))
Добрый день! Огромное спасибо за статью (хотела лайкнуть, но, увы, не получилось). Начала изучать питон, и как раз попалась ваша статья. Посмотрю как все эти алгоритмы на питоне пишутся, возьму за образец))
Сделаю несколько небольших замечания, раз уж мы этого коснулись.
1. Можно было в начале статьи упомянуть о разумных схемах кодирования - чтобы искусственное раздувание входа не превратило в NP-hard в P.
2. Можно было упомянуть отдельный подкласс NP-полных задач, которые решаются за псевдополиномиальное время динамическим программированием. Классический пример (собственно, задача тысячелетия) - набор заданной суммы B с помощью n заданных целых слагаемых. Сложность Ο(nB) - не экспоненциальная. Тут вот и разумные схемы кодирования пригодились бы.
3. Вы взяли для примера поиск в глубину и коммивояжера. Пример хороший, но он выглядел бы более эффектно, если бы коммивояжер был написан алгоритмом с возвратом (backtracking). Оказалось бы, что эти алгоритмы (глубина и алгоритм с возвратом на стратегии поиска в глубину), по сути, отличаются одной строчкой. В глубине при возврате вершина остается просмотренной, поэтому мы генерируем ровно один путь за линейное время. А в бэктрекинге при возврате вершина обновляется, поэтому генерируем все пути между двумя фиксированными вершинами за экспоненциальное время.
С другой стороны, если всё это написать, то получилась бы полуторачасовая лекция)) Еще раз спасибо за большое количество примеров программ на питоне.
Добрый день. Очень интересная статья, добавила к себе в закладки. Я тоже интересуюсь этой тематикой (дискретной оптимизацией и графами). Замечу, что для графов обычно используют не матрицы, а списки инцидентности, особенно для разреженных графов. Для орграфа таких списков будет два: для входящих и выходящих дуг. И, к стыду своему, не знала, что минимальное множество обратных дуг - NP- полная задача. Когда один раз возникла подобная задача для орграфа расчета себестоимости продукции (брак отправляли в металлолом, возникали циклы), с помощью поиска в глубину сформировала множество обратных дуг, благо критерий обратной дуги известен. Спасибо за информацию))
О Яндексе и копейках. История примерно десятилетней давности. Много букв.
В городе Перми два маленьких ребенка на коммунальной кухне переворачивают на себя кастрюлю с пельменями, получают сильнейшие ожоги. Это было вскоре после "хромой лошади", в городе появилось специальное мед.оборудование, детей спасли. Мать детей - из детдома, родственников нет. Известный писатель, человек из википедии, Нина Викторовна Горланова, начинает сбор денег и подключает меня. На forum.sourse.ru (мой ник Swetlana) один человек анонимно (думаю, это был Алекс Лайн) каждый месяц переводит мне 2000 р., я перевожу Н.В на яндекс-кошелек. В какой-то момент Яндекс лишает Н.В. доступа к аккаунту и к кошельку. Я пропускаю это сообщение от Н.В. и успеваю перевести 4000. Н.В. пишет в поддержку Яндекса, выполняет их рекомендации - ничего не получается. В поддержку Яндекса пишу я. Об'ясняю, кто такая Н.В., прошу помочь ей восстановить доступ. Получаю вначале отписки, а затем ответ в стиле: она чё, деньги у вас украла?
Кошелек их тут же закрыла. Верю, что украденные у детей 4000 яндексу ещё аукнутся.
Здравствуйте. В книге Нильса Нильсона "Принципы искусственного интеллекта" минимакс очень понятно описан на примере крестиков-ноликов. Показано, как сделать оценочную эвристическую функцию. Потом можно было бы и о шахматах сказать. Что минимакс хорошо работает, когда идёт размен фигур. Ну и т.д.
Добрый день. Статью пока не осилила, хотя тема мне интересна. Пока не забыла, хочется сделать одно небольшое уточнение и одно пожелание. Унарная (именно так она называется) СС широко применяется для записи чисел на ленте детерминированной машины Тьюринга с последовательным доступом, см. Кузнецов, Адельсон-Вельский "Дискретная математика для инженера".
Теперь по существу дела. Статью (имхо) можно было сделать намного интереснее, если бы статья начиналась с обзора систем счисления различных т.н. "примитивных народов". Например, у народа пираха вообще не сформировалось то ли понятие числа, то ли языковые обозначения для чисел. Во всяком случае, слова для обозначения единицы у них нет.
Борландовский Turbo Prolog 2.0 очень хорош для обучения прологу. Вижуал версии позаимствовали его синтаксис. И олдскульно, и прикольно - мышки нет.
Представьте себе научную статью (а исследование вполне тянет на статью), написанную в подобном тоне. Любопытно было бы почитать ответ рецензента))
Здравствуйте. "Паскаль в иллюстрациях" - моя первая книга по программированию. Чудесная книга! Потом у меня ее какой-то студент из Африки зачитал. Спасибо, что напомнили о ней.
Теперь хотелось бы раз'яснить связь между алгоритмами и структурами данных. От выбора структуры данных зависит все: и выбор модели, и, конечно, выбор и эффективность алгоритма. Например, т.н. "транспортные задачи". В матричном представлении решаются линейным программированием, в сетевом - потоковыми алгоритмами.
P.S О(f(n)) <= C*f(n), где C - положительная константа.
Здравствуйте. Сделаю маленькое замечание или, скорее, пожелание. Примеры у вас очень академические. Факториал, например. Если на лекции спросить: Заказчик требует перебрать все циклы в графе, близком к полному. Какова выч. сложность этой задачи? Сразу ответят "n квадрат". Про перестановки все знают, а что гамильтонов цикл тоже перестановка - не догадываются. Лучше бы иллюстрировать такую сложность модельными трудно решаемыми задачами.
Ещё раз спасибо за статью. Всё понятно, осталось только посмотреть пример использования счетчика. Я просто немного в шоке от питона, т.к. ранее писала только на двух простых языках: паскале и прологе. Да, и жду вторую часть))
Здравствуйте! Большое спасибо за статью, как раз разбираюсь с функциями, как и что туда передается.
Методом "научного тыка" обнаружила следующее. Если в функцию не передаём параметры, то конфликт имён (глобальная и локальная переменная с одним именем) вызывает ошибку. Если же глобальная переменная передается через параметр, а затем с именем параметра об'является локальная - никакого конфликта нет. Как-то нелогично.
Может быть, где-то можно про это прочитать, в чем профит?
Спасибо за ответ! Интересно, что сама задача до сих пор жива. Я, похоже, отстала от жизни. 20 лет назад, как теперь говорят, "топила" за графовые алгоритмы vs ЛП. Если задача допускает сетевую постановку, то построение потока будет эффективнее супротив более универсальных алгоритмов.
Получается, однако, что автор в чем-то прав. Все алгоритмы на сетях и графах - мало кому нужная роскошь, не говоря уж о их преподавателях))
Добрый день. Много лет назад я делала похожую задачу о взаимозачетах - нужно было погасить максимально возможный долг в сети предприятий. Делала это построением циркуляции минимальной стоимости алгоритмом дефекта. Который сама модифицировала методом фаз Диница. Но за секунду это работать не будет даже на современных компьютерах, только разложение циркуляции на циклы требует времени. Кстати, циклов тоже в худшем случае м.б. экспоненциальное количество, через одну вершину могут проходить разные циклы.
Не могли бы вы назвать алгоритм, которым можно это сделать за секунду? Очень любопытно))
Добрый день! Огромное спасибо за статью (хотела лайкнуть, но, увы, не получилось). Начала изучать питон, и как раз попалась ваша статья. Посмотрю как все эти алгоритмы на питоне пишутся, возьму за образец))
Сделаю несколько небольших замечания, раз уж мы этого коснулись.
1. Можно было в начале статьи упомянуть о разумных схемах кодирования - чтобы искусственное раздувание входа не превратило в NP-hard в P.
2. Можно было упомянуть отдельный подкласс NP-полных задач, которые решаются за псевдополиномиальное время динамическим программированием. Классический пример (собственно, задача тысячелетия) - набор заданной суммы B с помощью n заданных целых слагаемых. Сложность Ο(nB) - не экспоненциальная. Тут вот и разумные схемы кодирования пригодились бы.
3. Вы взяли для примера поиск в глубину и коммивояжера. Пример хороший, но он выглядел бы более эффектно, если бы коммивояжер был написан алгоритмом с возвратом (backtracking). Оказалось бы, что эти алгоритмы (глубина и алгоритм с возвратом на стратегии поиска в глубину), по сути, отличаются одной строчкой. В глубине при возврате вершина остается просмотренной, поэтому мы генерируем ровно один путь за линейное время. А в бэктрекинге при возврате вершина обновляется, поэтому генерируем все пути между двумя фиксированными вершинами за экспоненциальное время.
С другой стороны, если всё это написать, то получилась бы полуторачасовая лекция)) Еще раз спасибо за большое количество примеров программ на питоне.