Здравствуйте, Andrew Simontsev, Вы писали:
AS>Меня всегда интересовал вопрос — а существует ли практические примеры NP-полных задач для которых бы нельзя было найти воркэраунда типа ограничения перебора, симплекс-метода или чего-нибудь в этом роде? Может на практике оно и не надо вовсе...
Да, разумеется есть.
Вот пожалуйста, Задача дистрибьюторской сети.
В городе есть несколько складов с продуктами. На каждом складе в каждый момент времени есть какое-то количество каких-то видов продуктов. Продукты доставляются на склады с заводов изготовителей по какому-то определенному расписанию. Есть потребительские точки в которые нужно развозить всякие разные товары к опреденному времени. Для развозки товара есть несколько грузовиков разной вместимости. Есть несколько ориентированных графов городских дорог (для каждого типа грузовиков свой граф — так как, например тяжеловозам нельзя ездить по некоторым мостам или по центру города). Есть такой фактор, как пробки на дорогах, который выражаетмся в пропускной способности дуг орграфа в зависимости от времени суток и габаритов грузовика. Ну, до кучи, у потребительских точек еще есть VIP фактор, то есть приоритет обслуживания (то есть если вдруг оказывается, что грузовик не успевает объехать все точки (задержался где-то), то какие-то из точек ему надо игнорировать, а ехать в первую очередь в более приоритетные потребительские точки. Ну еще добавьте к этому, что рабочий день водителя городского грузовика есть 8 часов + перерыв на обед. А, ну еще, само собой разумеется, что принято к одному клиенту груз целиком доставляеть все-таки одним грузовиком к какому-то одному времени, а не подвозить его частями на разных грузовиках в разные времена. Надо найти такие пространственно-временные траектории движения для всех грузовиков, и такое распределение разных сортов грузов по этим грузовикам, чтобы как можно больше клиентов обслужить и как можно мешьше бензина истратить. А еще как можно меньше грузовиков задействовать — это чтобы на зарплату водителям меньше тратить и на амортизацию дополнительного грузовика.
Реальные цифры:
1-2 склада
200-600 потребительских точек каждый день (вообще по городу их 10'000)
20-30 разных грузовиков (15 штатных — остальные вольнонаемные)
Каждый грузовик за рабочий день может объехать не больше 20-40 точек (либо не хватит 8-часового рабочего дня, либо вместимости).
Десяток VIP клиентов.
Здравствуйте, S.Yu.Gubanov, Вы писали:
SYG>Здравствуйте, Andrew Simontsev, Вы писали:
AS>>Меня всегда интересовал вопрос — а существует ли практические примеры NP-полных задач для которых бы нельзя было найти воркэраунда типа ограничения перебора, симплекс-метода или чего-нибудь в этом роде? Может на практике оно и не надо вовсе...
SYG>Да, разумеется есть.
SYG>Вот пожалуйста, Задача дистрибьюторской сети.
[...]
А разве симплекс метод тут не поможет? Понятно, что условия и ограничения тяжко все сформулировать, но думаю это возможно...
VVB>Самые важные и больные проблемы в IT связаны с организацией труда, причем нормальной. VVB>Нет хорошего понимания, как организовывать производство (или проект отдельный) для выполнения VVB>тех или иных задач в IT и чтобы резылтаты при этом были повторяемые, как в рамках одного предприятия, VVB>так и в рамках всей отрасли. Честного нормального понимания, я имею в виду, а не маркетинговых песен VVB>и плясок с бубном.
VVB>-- VVB>Vitaly Belekhov
Полностью согласен!
Слова не мальчика — но мужа!
От себя добавлю — бубен, конечно, сила — но не решение.
По мимо правильной (т.е. эффективной) организации труда в IT (что есть, была и будет первой задачей IT от момента творения и до конца света) — следующая важнейшая задача — это как раз выделения наиболее приоритетных задач. Всю дорогу можно наблюдать, как огромные средства бухаются чёрти-знает куда, а довольно интересные и переспективные (как потом показывает будущее) направления игнорируются. Вспомним хотя бы историю с ADA и объектным программированием.
Здравствуйте, Andrew Simontsev, Вы писали:
AS>А разве симплекс метод тут не поможет? Понятно, что условия и ограничения тяжко все сформулировать, но думаю это возможно...
Вот если бы не было зависимости от времени, то, быть может, можно было бы как-нибудь извернуться. А так, задача, мало того что комбинаторная, но еще и динамическая — полные кранты...
Re: 10 самых важных нерешенных задач IT
От:
Аноним
Дата:
30.08.04 11:53
Оценка:
1. Патенты на алгоритмы и идеи ( реально экономически выгодная и не тормозящая ИТ индустрию).
2. Бизнес система распостранения программ с отрытыми исходниками ( реально экономически выгодная ).
3. Авто оптимизация кода и трансляция из одного аппаратно программного окружения в другое.
4. Контроль качества программного обеспечения.
Здравствуйте, Andrew Simontsev, Вы писали:
AS>Меня всегда интересовал вопрос — а существует ли практические примеры NP-полных задач для которых бы нельзя было найти воркэраунда типа ограничения перебора, симплекс-метода или чего-нибудь в этом роде? Может на практике оно и не надо вовсе...
Военные динамические задачи. Ну типа как в Civilization, War/StarCraft, C&C, Периметр, HomeWorld. Я правда не вкурсе доказывал ли кто-нибудь что они NP, но, например, лично у меня по этому поводу сомнений нет.
Здравствуйте, descartes, Вы писали:
D>Коллеги, D>долго думал в какой из форумов запостить свой вопрос, в итоге остановился на Проектировании. Имхо близко.
Skip..... D>Думаю что обсуждение будет интересным, полезным и не перерастет в флейм. D>Просьба отнестись серьезно.
Увеличение производительности труда разработчиков. Особенно в софтверной области.
На лицо глобальное отставание развития ПО от железа
Здравствуйте, descartes, Вы писали:
D>Здравствуйте, flax, Вы писали:
F>>2) AI (диллема между символами и мыслью ), а если вспомнить, что @"AI — это то, что сейчас нет", то это всегда нерешенная задача
D>интересное определение AI D>можно поподробнее? это кто сказал что AI — то чего нет и всегда нерешенная задача?
Понятие искусственный интеллект преждевременно, плод спекуляций...
По одной простой причине: не понятно, что такое естественный интеллект.
Речь может идти только об имитации некоторых функций которые приписываются интеллекту человека.
Здравствуйте, descartes, Вы писали:
D>Итак, известно что в математике есть некий Top10 нерешенных задач очень основопологающих, важных, будоражущих умы и проч. Про то же в ИТ мне не известно но суть не в этом. Итак, коллеги, какие глобальные проблемы ИТ вы могли бы обозначить?
1. Менеджмент. Давно известный факт, что программистами управляют люди, слабо представляющие как расшифровывается сама аббревиатура IT.
2. Сертификация. Не в смысле экзамены типа от MS, которые может зазубрить по дампам любой индус. А в смысле, как у докторов — чтобы начать самостоятельно практиковать, нужно сдать экзамен своим практикующим коллегам. Если же IQ не хватает, то будешь всю жизнь подносить патроны. Сейчас же ситуация такова, что при достаточной шероховатости языка любой Click-click Anyhow VBeloper может легко превратиться в Senior Enterprise Blah-blah-blah Architect и начать принимать судьбоносные решения.
... << RSDN@Home 1.1.4 beta 3 rev. 185>>
Если нам не помогут, то мы тоже никого не пощадим.
Здравствуйте, IT, Вы писали:
IT>Давно известный факт, что программистами управляют люди, слабо представляющие как расшифровывается сама аббревиатура IT.
Игорь Ткачев?
За все IT не скажу, благо не знаю. А вот некоторые проблемы разработки от себя:
1. Проблема художника. Где кончается работа и начинается творчество. Граница непонятна. Все стараются уменьшить последнее, да вот эффект обратный.
2. Проблема маленькой головы. Как впихнуть всю информацию накопленную в сфере, в бедную голову конкретного разработчика. Кто это должен делать, и главное как, и как часто.
3. Проблема количества. При развитии IT возникает большее количество инструментов и повышается сложность работы с ними. А не наоборот. Нет процесса сходимости, особенно в области их взаимодействия. Жить становится не легче.
4. Проблема Microsoft vs Sun. Высокая степень монополизации. В этом есть и плюс, в этом есть и минус. Монополизация позволяет как устанавливать стандарты, так и нарушать их. Мир IT разделен на монополии. Причем эти миры стараются не контактировать.
5. Проблема велосипедов. В этом участвуют п1,п2,п3,п7. Во многом работа — изобретение велосипедов о которых мы ничего не знали. Иногда велосипеды получаются с 10 колесами, с одной педалью и к тому-же все находится сверху оного.
6. Деньги vs Качество. Процесс разработки настроен на получение максимума прибыли, а не на увеличении качества продукта. Недостатки буржуазного строя.
7. Проблема индийцов. Низкая квалификация. Особенно если индиец становится архитектором, team manager'ом и т.д. Пускай граждане индийской национальности не обижаются, но имя просто стало нарицательным. Надеюсь здесь все понятно.
С уважением, Gleb.
PS:Ессно, тут такое IMHO — мама не горюй.
AS>Меня всегда интересовал вопрос — а существует ли практические примеры NP-полных задач для которых бы нельзя было найти воркэраунда типа ограничения перебора, симплекс-метода или чего-нибудь в этом роде? Может на практике оно и не надо вовсе...
Игру в шахматы можно свести к переборной задаче. Оптимальное расположение (например с наименьшей площадью ) фигур на плоскости, или в пространстве, а это сосставляющая часть многих задач. Наконец криптоанализ.
Вообще-то многие задачи можно к ним свести.
Здравствуйте, borka, Вы писали:
D>> Итак, коллеги, какие глобальные проблемы ИТ вы могли бы обозначить?
B>Навскидку:
B>Повторное использование кода. B>Параллельные и распределенные вычисления — семантика. B>Пиринговые системы — эффективность, безопасность. B>Хранилища данных, добыча данных.
Где можно подробнее узнать о семантических проблемах параллельных программ?
dimon0981,
AS>>Меня всегда интересовал вопрос — а существует ли практические примеры NP-полных задач для которых бы нельзя было найти воркэраунда типа ограничения перебора, симплекс-метода или чего-нибудь в этом роде? Может на практике оно и не надо вовсе...
D> Игру в шахматы можно свести к переборной задаче. Оптимальное расположение (например с наименьшей площадью ) фигур на плоскости, или в пространстве, а это сосставляющая часть многих задач. Наконец криптоанализ. D> Вообще-то многие задачи можно к ним свести.
Задача нахождения оптимальной стратегии в шахматах точно в PSPACE, а вот в NP — крайне маловероятно. Здесь тоже ещё открытая проблема PSPACE =? NP, и в данном случае равенство ещё более сомнительно, ежели в случае проблемы NP =? P.
Вообще есть класс задач RE — рекурсивно перечислимые задачи, их всего лишь счетное множество. Так вот, самые интересные задачи — в ¬RE, и там их — континуум.
Здравствуйте, GlebZ, Вы писали:
GZ>Здравствуйте, descartes, Вы писали:
GZ>За все IT не скажу, благо не знаю. А вот некоторые проблемы разработки от себя: GZ>1. Проблема художника. Где кончается работа и начинается творчество. Граница непонятна. Все стараются уменьшить последнее, да вот эффект обратный. GZ>2. Проблема маленькой головы. Как впихнуть всю информацию накопленную в сфере, в бедную голову конкретного разработчика. Кто это должен делать, и главное как, и как часто. GZ>3. Проблема количества. При развитии IT возникает большее количество инструментов и повышается сложность работы с ними. А не наоборот. Нет процесса сходимости, особенно в области их взаимодействия. Жить становится не легче. GZ>4. Проблема Microsoft vs Sun. Высокая степень монополизации. В этом есть и плюс, в этом есть и минус. Монополизация позволяет как устанавливать стандарты, так и нарушать их. Мир IT разделен на монополии. Причем эти миры стараются не контактировать. GZ>5. Проблема велосипедов. В этом участвуют п1,п2,п3,п7. Во многом работа — изобретение велосипедов о которых мы ничего не знали. Иногда велосипеды получаются с 10 колесами, с одной педалью и к тому-же все находится сверху оного. GZ>6. Деньги vs Качество. Процесс разработки настроен на получение максимума прибыли, а не на увеличении качества продукта. Недостатки буржуазного строя. GZ>7. Проблема индийцов. Низкая квалификация. Особенно если индиец становится архитектором, team manager'ом и т.д. Пускай граждане индийской национальности не обижаются, но имя просто стало нарицательным. Надеюсь здесь все понятно.
Прикол всех твоих пунктов в том, что они суть п.6:
Миллионы людей по всему миру пишут одно и то же, пишут настолько минимально, насколько это возможно, а потому ужасно. И потому пишут снова и снова, и опять одно и то же. Всевозможные известные пособия по управлению проектами учат как правильно реализовать лишь минимально необходимое путем "правильной" расстановки приоритетов. "Провалить проект" в современном мире зачастую означает "выйти за бюджет",а не только лишь "сделать бездарно".
При найме команды берут программистов минимально необходимого уровня для каждой из позиций, т.е. максимально дешевых для конкретного проекта. Эдакое сознательное балансирование на грани фола.
Отсюда имеем распространенные сейчас подходы, типа "писать надо так, чтобы и дебил разобрался". Мое имхо, далеко не обязательно так писать. Писать надо так, как это наиболее отвечает задаче. Уровень "дебила" тоже должен соответствовать задаче. А вот с этим напряг, обычно... и т.д. и т.п. и еще тонна следствий из главного п. №6. (палата №6 )
Здравствуйте, vdimas, Вы писали:
V>Прикол всех твоих пунктов в том, что они суть п.6:
V>Миллионы людей по всему миру пишут одно и то же, пишут настолько минимально, насколько это возможно, а потому ужасно. И потому пишут снова и снова, и опять одно и то же.
Не соглашусь. Универсальных решений не бывает. Точнее сказать для одной и той же задачи существует большое количество решений. И каждое решение имеет свои бенефиты. А некоторые решения вообще до сих пор не решены, и их решения просто нет в обозримом будуйщем.
V>Всевозможные известные пособия по управлению проектами учат как правильно реализовать лишь минимально необходимое путем "правильной" расстановки приоритетов. "Провалить проект" в современном мире зачастую означает "выйти за бюджет",а не только лишь "сделать бездарно".
+1
V>При найме команды берут программистов минимально необходимого уровня для каждой из позиций, т.е. максимально дешевых для конкретного проекта. Эдакое сознательное балансирование на грани фола.
+1. Хотя бывает и по другому, но в большинстве своем(почему-то многие здесь с этим не согласны), к сожалению это так.
V>Отсюда имеем распространенные сейчас подходы, типа "писать надо так, чтобы и дебил разобрался". Мое имхо, далеко не обязательно так писать. Писать надо так, как это наиболее отвечает задаче. Уровень "дебила" тоже должен соответствовать задаче.
Вот с тем, что надо писать так, чтобы дебил разобрался, я абсолютно согласен.
Во-первых, библиотеки и решения пишутся не для собственного пользования. Существует люди которые видят и оценивают твой код. Точно так же будут люди которые будут использовать и работать с твоим кодом. И от того, как они оценят его и смогу быстро врубиться в него зависит долгота жизни этого кода. Я не один раз встречался с кодом который выбрасывался только из-за того, что в нем сам черт ногу сломит. Кстати, я встречался со случаями когда клиент просил показать код, чтобы просто оценить его качество.
Во-вторых, я заметил (и я думаю я не один), что существует зависимость от визуального качества кода, и количества ошибок который он несет. И к сожалению, я редко вижу код хорошего качества поскольку приходится обращать внимание не низкое качество визуализации кода.
Здравствуйте, IT, Вы писали:
IT>1. Менеджмент. Давно известный факт, что программистами управляют люди, слабо представляющие как расшифровывается сама аббревиатура IT. IT>2. Сертификация. Не в смысле экзамены типа от MS, которые может зазубрить по дампам любой индус. А в смысле, как у докторов — чтобы начать самостоятельно практиковать, нужно сдать экзамен своим практикующим коллегам.
Такой экзамен есть — вступительное interview. Без него трудно "практиковать" И оно по-определению серьезней, чем сдача какого-нить кандидатского диссера — экзаменующий материально заинтересован в результате.
Опыт — это такая вещь, которая появляется сразу после того, как была нужна...
.
Если нам не помогут, то мы тоже никого не пощадим.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
