Так... Вычитал тута вот...
http://lenta.ru/news/2006/04/13/programmers/

Конкурс программистов!!!
Задача:
"найти самый дешевый способ создания системы, которая соединяет различные узлы корпоративной сети."

До сих пор я думал, что этим занимаются системотехники, а не программеры...

Ерунда, это просто single-source, single-destination shortest path problem in a DAG.

??? - DAG - терминология не понятна... Отошел я от этого уже давненько...

Ааа, это... DAG не покрывает указанную задачу - множественные истоки, множественные стоки... К тому же - переменные во времени... Не программерская это задача, это я тебе говорю как системотехник-по-диплому...

Кстати я соврал. Он у них с циклами.

Я тебе говорю про конкретную задачу на последнем ICPC. Им надо было всего лишь посчитать количество узлов в кратчайшем пути.

Программирование и развитие ЭВМ началось в США в 50-х для ускорения вычислений при проектировании и испытании атомных бомб.
Так что все сегодняшние программисты в определ╦нной меры инженеры-системотехники (то бишь АСУ) и даже.... физики-ядерщики.

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

Вообще-то - до 40-х. Именно тогда были использованы перфокарты с кодами, для управления вычислениями...

мы в Уни учили, что родоначальником был Zuse 8-)
http://de.wikipedia.org/wiki/Konrad_Zuse

Ну, во-первых Эниак это 1946 год. Во-вторых на западе на буковку Э вообще как-то не налегают, так что можно вспомнить и Цузю, а то и вообще калькулятор Лейбница... И кстати Эниак считал баллистику, а вовсе не параметры атомных бомб.

Чо к словам придираешься...
А ребята видимо вот отсюда :http://www.sgu.ru/faculties/computer_sciences/
Только грузится что-то медленно...

Бедные немцы... Честный, работящий народ... А у них все всё крадут. И ракты, и ядерную физику, и ЭВМ...
И вааще, первая ЭВМ - это счётные палачки, и позже, в усовершенствованом варианте - счёты.

Я вообще считаю этот конкурс дурью, и уж тем более за ним не слежу. Задачи я посмотрел полтора часа назад.
А с графами я сейчас работаю, в уни разрабатываем приближённые решения task scheduling'а эволюционными методами. Задача NP-полная, так что точное решение можно посчитать от силы для нескольких десятков узлов...

Наверное... Сейчас по инету много глупостей ходит. Не то, что раньше - в двух книгах разные цифирьки пропечатались - один из редакторов или корректоров идет на другую работу...

Хммм... Голубая мечта - получить доказанно-минимальный выход с генератора кода...
Увы, она хоть не НП-полная, но при наличии стека просто не решаемая...

Ты вроде занимался нейронками? Там что-то собралось? Может в природе (.нет, сбилдер) уже есть реализация узла, пригодного для посторения хотябы простых экспертных систем? самому что-то лениво писать...

А зачем эволюционными-то методами? Они особой эффициентнотью не отличаются. А для task scheduling есть куча аппроксимативных и рандомизированных решений.

С чего ты это взял-то? Вполне нормальные методы, ничем не хуже других эвристик. Или ты можешь подтвердить свои слова ссылками на научные работы?

Методы вполне нормальные, тут я не спорю. Только они слишком абстрактны и слишком слабо привязаны к конкретной проблеме. Это делает их универсальными, но имеет свою цену. А для task sceduling есть специализированные решения (например ILP-формулировка). Если количество данных невелико и время особой роли не играет, тогда один черт. Но если вежно найти быстрое решение, то IMHO за EA браться не стоит.

Почитай что-ли http://citeseer.ist.psu.edu/cache/papers/cs/15274/http:zSzzSzwww.eee.hku.hkzSz~y... и не пиши больше такую чушь...

Ну и вот ещё статья неплохо описывающая рассматриваемый нами алгоритм (ACO): http://citeseer.ist.psu.edu/cache/papers/cs/666/http:zSzzSzwww.csr.unibo.itzSz~m...
Собственно ACO на данный момент похоже является наилучшей эвристикой.

Ты вроде занимался нейронками? Там что-то собралось?
В принципе и то, и другое делалось в рамках определённого курса на один семестр, но если нейронки были чисто учебным заданием, то параллелизация ACO для task graph scheduling вливается в исследовательскую работу соответствующей кафедры. А о нейронках у меня осталось негативное мнение - чистый hype IMHO...