Паралельні процеси

Коли аналізуються паралельні процеси, які потребують синхронізації, часто важливо знати, які типи завдань можуть виконуватися одночасно. Розглянемо $n$ завдань $m$ типів. Два типи завдань називаються незалежними, якщо вони можуть виконуватися паралельно. Завдання одного типу завжди виконуються послідовно і не можуть бути незалежними.

Розглянемо послідовність завдань, що виконуються на $k$ процесорах. Щосекунди можна виконати до $k$ наступних завдань, якщо кожна пара з них може виконуватися паралельно. Зверніть увагу, що не можна пропускати завдання або відкладати їх на потім. Наприклад, якщо завдання типів A та B є незалежними, послідовність AABABBAB може бути виконана на двох процесорах за п'ять секунд. Один зі способів це зробити: (A−), (AB), (AB), (B−), (AB).

Інший спосіб виконати цю послідовність на двох процесорах: (A−), (AB), (AB), (BA), (B−). Ми кажемо, що два способи є суттєво різними, якщо існує така секунда, коли набори завдань, що виконуються, є різними. Можна побачити, що існує два суттєво різних способи виконати послідовність завдань AABABBAB на двох процесорах за мінімальний час. Якщо також враховувати, на якому процесорі виконується кожне завдання, існує $64$ способи виконати даний набір завдань (у кожному з двох суттєво різних способів ми можемо обмінювати завдання між процесорами щосекунди). Тому ми кажемо, що існує $64$ точних способи виконання набору завдань.

Знаючи типи завдань, які є незалежними, кількість процесорів та послідовність завдань, ви повинні визначити мінімальний час, необхідний для виконання завдань, кількість суттєво різних способів це зробити та кількість різних точних способів виконання.