Имя пользователя:

Пароль:


Список форумов КАНАДА Работа Образование и профучёба Просмотров: 294 Промотать вниз к быстрому ответу

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


Послешкольное обучение
Модератор: Mitridat
   Поделиться темой: 
  #1
Сообщение 21 ноя 2015, 19:37
Mitridat Аватара пользователя
СОЗДАТЕЛЬ ТЕМЫ
Canada, Ontario
Город: Оттава
Стаж: 4 года 2 месяца 10 дней
Постов: 5730
Лайкнули: 1934 раз
Карма: 34%
СССР: Киев, СПб
Пол: М
Заход: 09 дек 2016, 16:42

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

  #2     Вопрос на засыпку - что это такое?
Сообщение 21 ноя 2015, 20:45
Cth Аватара пользователя
Canada, British Columbia
Город: Vancouver
Стаж: 2 года 11 месяцев 18 дней
Постов: 1507
Лайкнули: 297 раз
Карма: 20%
Пол: М
Заход: 29 сен 2016, 10:53

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

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

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

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

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

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

  #3     Вопрос на засыпку - что это такое?
Сообщение 21 ноя 2015, 21:28
Mitridat Аватара пользователя
СОЗДАТЕЛЬ ТЕМЫ
Canada, Ontario
Город: Оттава
Стаж: 4 года 2 месяца 10 дней
Постов: 5730
Лайкнули: 1934 раз
Карма: 34%
СССР: Киев, СПб
Пол: М
Заход: 09 дек 2016, 16:42

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

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

  #4     Вопрос на засыпку - что это такое?
Сообщение 21 ноя 2015, 22:39
Cth Аватара пользователя
Canada, British Columbia
Город: Vancouver
Стаж: 2 года 11 месяцев 18 дней
Постов: 1507
Лайкнули: 297 раз
Карма: 20%
Пол: М
Заход: 29 сен 2016, 10:53

Mitridat написал(а) здесь:
А что именно за цифра находится в левом нижнем углу?

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

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

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

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

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

Изображение

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

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

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

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

  #5     Вопрос на засыпку - что это такое?
Сообщение 21 ноя 2015, 22:56
Mitridat Аватара пользователя
СОЗДАТЕЛЬ ТЕМЫ
Canada, Ontario
Город: Оттава
Стаж: 4 года 2 месяца 10 дней
Постов: 5730
Лайкнули: 1934 раз
Карма: 34%
СССР: Киев, СПб
Пол: М
Заход: 09 дек 2016, 16:42

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

Спасибо за ссылки. Посмотрю.
Парадокс католицизма: в разных местах хранятся 12 черепов Иоанна Крестителя, но подлинные из них - только 3.


Чтобы ответить в этой теме, зарегистрируйтесь или быстро войдите через соцсеть: