Оцінка мінімальної і максимальної трудомісткості алгоритму.
Мінімально можливе і максимально можливе значення трудомісткості на момент закінчення виконання оператора Vi позначимо відповідно через Ai і Bi. Маємо A0 = 0, B0 = 0. Тоді для інших вершин з номерами i = 1,2,., K:
;;
де (j, i) - дуга, що виходить з вершини j і входить у вершину i;
D - безліч дуг графа програми.
Мінімальна min (Aj) і максимальне max (Bj) значення визначаються по відношенню до всіх вершин j з яких виходять дуги, що входять у вершину i.
Значення kimin і kimax характеризують мінімальну і максимальну трудомісткість оператора Vi.
Для кінцевої вершини К графа обчислюються значення
;; Ој
характеризують мінімальну і максимальну трудомісткість алгоритму.
Визначимо мінімальну і максимальну трудомісткість алгоритму, що не містить циклів (*).
Приймемо, що трудомісткість кожного оператора постійна і дорівнює 1.
Послідовно застосовуючи Ој, отримаємо:
В
Таким чином мінімальна трудомісткість алгоритму Ak = 5, а максимальна Bk = 7 операцій.
Мінімальна і максимальна трудомісткість алгоритмів, що містять цикли, знаходяться за аналогією з методом визначення середньої трудомісткості алгоритмів з циклами. При цьому виділяються цикли першого рангу. Знаходяться мінімальна А і максимальна У трудомісткість тіла циклу. Мінімальна і максимальна трудомісткість циклу визначається значеннями і, де nmin і nmax - мінімальне і максимальне число повторень циклу. Потім цикл замінюється оператором з трудомісткістю kmin = і kmax = і знову застосовується процедура виключення циклів. Процес повторюється до тих пір, поки граф алгоритму лише буде перетворений до форми без циклів. Мережеві моделі обчислювальних систем. p> Представлення ЗС у вигляді стохастичною мережі.
В
НД можна розглядати як сукупність пристроїв, процеси функціонування яких є процесами масового обслуговування і для їх опису використовують моделі теорії масового обслуговування. Основними моделями, що використовуються в теорії масового обслуговування, є одне - і багатоканальні системи масового обслуговування (СМО). У одноканальної СМО обслуговування заявок організується так. p> На вхід СМО надходять заявки з інтенсивністю l. Так як СМО містить один канал (прилад), то в кожен момент часу може обслуговуватися тільки одна заявка. Середній час обслуговування заявки одно V. Інші заявки, що надходять в систему, коли канал був зайнятий обслуговуванням, утворюють чергу О. З цієї черги по закінченні обслуговування заявки вибирається наступна заявка і так далі. Якщо канал вільний і в черзі немає заявок, то канал простоює. Новоприбула заявка відразу займає простоюючий канал, якщо в черзі немає інших заявок. br/>В
Багатоканальна СМО містить До однотипних каналів, середній час обслуговування заявок V в яких неодмінно однаково.
В системі одночасно ...
