Вопрос на засыпку - что это такое?

Уважаемые форумцы, нужно компетентное мнение. Уже несколько раз подряд видел, как молодые канадцы, учащиеся колледжей, выполняют задачи некоего алгоритмического типа. Я так понимаю, речь идёт о расчёте оптимального времени и алгоритма. Что меня совершенно выбило из колеи: с их точки зрения, задача относится к элементарным, а я даже не могу чётко понять условие. Чувствую себя невероятно тупым. Есть ли в сети образцы подобных задач?
Cth, Вы не в курсе? Хотя бы по каким ключевым словам в сети искать, чтобы найти нечто подобное?

Тю, епт. Жене показал, она сразу сказала: Так это же PERT диаграмма. рассчет времени для проекта по задачам. это менеджерская штука. Только граф этот недоделан. Лол. А я и не подумал, я сразу на низком уровне смотрел.

Значит, все просто:

Каждая стрелочка - это атомарный процесс (задача). В таблице перечислены все процессы. У каждого процесса есть время выполнения, оно во второй колонке. Еще, у каждого процесса есть prerequisites. Пререквизиты - это те процессы, без которых текущий процесс не может начаться. Жена их почему-то predecessor'ами кличет

Так, теперь смотрим на граф.

Начинается проект с первого стейта, это кружочек с единичкой и ноликами. Нолики в правом нижнем углу значат количество времени, что было потрачено в этом потоке работы (каждая параллельная линия - это независимый поток работы). После того, как первая задача выполнена, мы начинаем задачу B, что занимает 6 времени. Во втором стейте мы отобразили, что у нас потрачено шесть времени. Дальше делаем задачу S за десять времени, которая требует по таблице задачу B выполненной. Ну и так далее до конца этой ветки... А параллельно, мы делаем другие потоки по тому же принципу.

Только автор сего чуда еще не просчитал обратные данные, в каждом кружочке должна быть циферка в левом нижнем углу, которая потом помогает находить критические пути всякие и прочую лабуду. Это обычная задача по системному анализу и software engineering, которые я недавно вспоминал уже на форуме. хе-хе.

Cth, спасибо большое. Хоть буду знать на старости, что такое оверлок.
А что именно за цифра находится в левом нижнем углу?

И можно ли, если не трудно, дать примеры подобных задач? Я поискал в сети, но нашёл только общие принципы построения (причём не совсем такие, а немного другие - с 5 секциями. Хоть порешаю на досуге - самому интересно стало.
Кроме того, такие задачи вроде бы входят в Public Service Exam.

Mitridat написал(а) здесь:

А что именно за цифра находится в левом нижнем углу?

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

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

- идти влево(по любому из путей)
- отнять от левой нижней предшественника длительность текущей задачи
- зписать значение в левую нижнюю ячейку текущей задачи
- повторить

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

Вот пример еще один, моей жены:



у нее в правом верхнем углу длительность задачи.

она рекоммендует еще вот этот мануал:

http://www.sce.carleton.ca/faculty/chinneck/po/Chapter11.pdf

В сети есть много примеров, можно гуглить PERT Excercises

Вот вроде бы порекомендовали хорошую ссылку:
http://edu.dvgups.ru/METDOC/ENF/VMATEM/WM/METOD/U_PO/frame/12.htm

Спасибо за ссылки. Посмотрю.