Використання методу гілок і меж при адаптації робочого навантаження до параметрів обчислювального

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
«Гомельський державний університет імені Франциска Скорини»
Математичний факультет
Кафедра МПУ
Курсова робота
"Використання методу гілок і меж при адаптації робочого навантаження до параметрів обчислювального процесу"
Гомель 2002

Реферат
Курсова робота 25 сторінок, 10 джерел, 5 рисунків, 1 таблиця
Ключові слова: ІМІТАЦІЙНА МОДЕЛЬ, МЕТОД ГІЛОК І МЕЖ, напівмарковський процес, ОБЧИСЛЮВАЛЬНА СИСТЕМА, ОБЧИСЛЮВАЛЬНИЙ ПРОЦЕС, ПРОГРАМНИЙ МОДУЛЬ, ГРАФ, МАТРИЦЯ ІМОВІРНОСТЕЙ, МЕТОД МОНТЕ-КАРЛО
Об'єкт дослідження: імітаційна модель процесу обробки даних.
Предмет дослідження: застосування методу гілок і меж у процесі обробки даних.
Мета курсової роботи: знайти раціональний порядок проходження запитів, який забезпечить максимальний критерій ефективності використання компонентів обчислювального процесу в обчислювальній системі.
Завданнями курсової роботи є: вивчити метод гілок і меж і застосувати його до моделі машинного моделювання, що дозволяє знайти такий порядок проходження запитів, який забезпечить максимально швидке виконання обчислювального процесу.
Висновки: за допомогою методу гілок і меж вдається побудувати такий порядок виконання запитів, при якому час їх обслуговування буде мінімальним.

Зміст
Введення
1. Марковські процеси
2. Метод Монте-Карло
2.1 Загальна характеристика методу Монте-Карло
2.2 Точність методу
3. Метод гілок і меж
4. Побудова оптимальної послідовності завдань на обробку у вузлі обчислювальної системи
4.1 Формалізація обчислювального процесу і робочого навантаження
4.2 Особливості організації імітаційного експерименту
4.3 Модифікація послідовності вирішення завдань в пакеті за методом гілок і меж
Висновок
Список джерел

Введення
Вибором робочого навантаження під обчислювальний процес в обчислювальних системах займалися багато дослідників. Проте всі вони оперували інтегральними характеристиками вирішення завдань, не розглядаючи при цьому динаміку використання ресурсів обчислювальних систем в часі виконання завдань і просторі параметрів. Такий підхід іноді призводив до суттєвої помилку в оцінці продуктивності системи в умовах, коли завдання сильно конкурують за ресурси обчислювальної системи. Ця обставина визначила актуальність завдання адаптації робочого навантаження під можливості обчислювальних систем в умовах, коли технологія їх обробки розглядається на високому рівні деталізації. У даній роботі будемо виходити з таких припущень:
1. Кожне завдання імовірнісним чином використовує різні ресурси обчислювального процесу, а сам імовірнісний процес є напівмарковському.
2. Досліднику відомі заздалегідь характеристики напівмарковському процесу, реалізованого кожним із завдань, або ж є інструментальні засоби для вимірювання цих характеристик.
3. Потік завдань постійно використовується на даній обчислювальної системи і має практично незмінну структуру запитів ресурсів обчислювальної системи, що дозволяє говорити про принципову можливість знаходження такого порядку завдань, який є оптимальним при заданому складі ресурсів обчислювальної системи.

1. Марковські процеси
Нехай є система, яка в довільний момент часу t _k може перебувати в одному із станів s _i,

, З імовірністю

. Через деякі проміжки часу система переходить з одного стану в інший. Кожен такий перехід називається кроком процесу. Випадковий процес, що протікає в системі S, називається марковским, якщо для довільного моменту часу

ймовірність будь-якого стану системи в майбутньому (при

) Залежить тільки від її стану в сьогоденні (при

) І не залежить від того, коли і яким чином система прийшла в цей стан. Розрізняють марковські процеси з дискретними станами і дискретним часом (стохастична послідовність, або дискретна ланцюг Маркова) і марковські процеси з дискретним станом і неперервним часом (безперервний ланцюг Маркова). Обидва типи ланцюгів можуть бути однорідними і неоднорідними.
Для дискретної ланцюга Маркова зміни станів процесу відбуваються в дискретні моменти часу t _i з кроком

. Стан системи s _i в момент t _k необхідно характеризувати умовними ймовірностями

(1) того, що система за один крок перейде в яке-небудь стан s _j за умови, що в момент t _{k -1} вона перебувала в стані s _i. Ймовірності

(1) =

є основними характеристиками марковської ланцюга. Вони називаються ймовірностями переходу або перехідними ймовірностями. Оскільки система може перебувати в одному із станів, то для кожного моменту часу t _r необхідно задати n ² ймовірностей переходу

.

Ця матриця називається матрицею перехідних ймовірностей або матрицею переходів. Для неї справедливо вираз

. Матриця перехідних ймовірностей обов'язково є квадратною матрицею з невід'ємними елементами, що утворюють по рядках одиничну суму; матриця такого роду називається стохастичною. У випадку, коли ймовірності переходу не залежать від часу, а залежать тільки від величини τ і не змінюються при зсуві вздовж тимчасової осі, ланцюг Маркова називається однорідною. Для такого ланцюга задається матриця

.
Ймовірності переходу є найважливіші характеристики будь-якої марковської ланцюга. Однак вони за визначенням є умовними, і тому знання матриці перехідних ймовірностей не повністю визначає ланцюг Маркова. Якщо віднести матрицю переходів до першого кроку, який визначає початок роботи системи, то для виключення умовностей необхідно поставити ще ймовірності початкових станів.
Вірогідність початкових станів

, ...,

є безумовними ймовірностями і утворюють матрицю-рядок

, Сума елементів якої за умовою нормування повинна бути дорівнює 1.
Матриця переходів дає вичерпне уявлення про можливості можливих переходів за один крок. Природно виникає питання: як розрахувати ймовірності того, що система, що знаходиться в даний момент у стані s _i, переходить у стан s _j за r кроків. Матриця переходів за r кроків P (r) обчислюється як r-я ступінь матриці переходу за один крок P (r) = p ^r. Безумовні ймовірності системи на r-му кроці визначаються з виразів:

.
Розрізняють ланцюга Ергодіческіе і поглинаючі. Ця відмінність грунтується на класифікації станів. Стан s _i називається безповоротним, якщо існують такі стани s _j (

) І число кроків r, що p _ij (r)> 0, але p _ij (q) = 0 для всіх q. Всі інші стани називаються зворотними. Таким чином, з неповоротного стану завжди можна з позитивною ймовірністю і за будь-яке число кроків перейти в якийсь інший стан. У той же час повернутися з цього стану в початкове неможливо.
Якщо вибрати такі стани s _i і s _j, що для них при деяких r і q виконується нерівність p _ij (r)> 0, p _ji (r)> 0, то вони називаються сполученими. Якщо s _j повідомляється з s _i, а s _i з s _k, то s _j повідомляється з s _k. Ця обставина дозволяє розділити безліч зворотних станів на класи (підмножини) сполучених станів. Стани, що належать до різних класів, не повідомляються між собою. Якщо безліч зворотних станів складається з одного класу, то воно називається ергодичної. Існують так звані поглинаючі стану, наприклад якщо s _i - поглинає стан, то p _ii = 1, p _ij = 0. Ланцюги Маркова, що не містять зворотні множини і утворюють ергодичної безліч, називаються ергодичної. Властивості і методи розрахунків параметрів поглинаючих та ергодична ланцюгів різні.
Для безперервного ланцюга Маркова вводиться поняття щільності ймовірності переходу (інтенсивність потоку подій) як границі відношення ймовірності переходу системи за час Δt зі стану i в стан j до довжини проміжку:

(

).

Якщо λ _ij не залежить від t, тобто від того, в який момент починається Δt, то безперервний ланцюг Маркова називається однорідним, у противному випадку вона називається неоднорідною.
Однорідна ланцюг Маркова характеризується тим, що всі потоки, що переводять систему з одного стану в інший, є простими, тобто стаціонарними пуасонівськими потоками. При цьому час безперервного перебування ланцюга в кожному стані розподілено за експоненціальним законом.
Для неоднорідної ланцюга проміжки часу між сусідніми подіями розподілені не по показовому закону.
Якщо безперервний ланцюг Маркова є однорідною і між будь-якими її двома станами існує маршрут, то вона ергодичності. Крім того, якщо ймовірності станів системи p _j не залежать від часу спостереження системи і збігаються з її початковими ймовірностями станів

і стаціонарними ймовірностями, тобто

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

, Матрицею інтенсивностей [λ _ij] найпростіших потоків, де λ _ij = p _ij λ _i, вектором експоненціально розподілених часів перебування в станах з параметрами {1 / μ _{1, 1} / μ _2, ..., 1 / μ _n}.
Головна відмінність напівмарковському процесу від ланцюга Маркова полягає у відмові від вимоги, щоб розподілу часу перебування в кожному стані підпорядковувалися показовому закону. Зазвичай напівмарковському процес задається початковим розподілом ймовірностей

, Матрицею перехідних ймовірностей [p _ij] і сукупністю довільних функцій розподілу часу перебування в станах

.
У моменти переходів з одного стану в інший напівмарковському процес має марковским властивістю. Якщо розглядати напівмарковському процес тільки в моменти переходів, то виходить при цьому марковська ланцюг з дискретним часом називається вкладеною марковської ланцюгом (так як вона міститься в напівмарковському процесі). Вкладена ланцюг має той же простір станів S і той же вектор P ⁽⁰⁾ початкового розподілу ймовірностей станів, що і напівмарковському процес, а матрицею переходів вкладеної ланцюга є матриця P = [p _ij] напівмарковському процесу.
Для ергодичної напівмарковських процесів, як і для ергодичної марковських ланцюгів, характерна наявність стаціонарного режиму.

2. Метод Монте-Карло
Різні методи і прилади для визначення параметрів і характеристик випадкових процесів можна об'єднати у дві групи. Першу групу складають прилади для визначення кореляційних функцій (корелятори), спектральних густин (спектрометри), математичних сподівань, дисперсій, законів розподілу та інших випадкових процесів і величин.
Всі прилади першої групи можна розділити на дві підгрупи. Одні визначають характеристики записаних випадкових сигналів за досить великий час, набагато перевищує час реалізації самого випадкового процесу. Інші (вони останнім часом викликають найбільший інтерес) дозволяють отримувати характеристики випадкового процесу оперативно, в такт з надходженням інформації при натурних випробуваннях нових систем управління, так як, користуючись їх показаннями, можна безпосередньо змінювати процес управління і в ході експерименту спостерігати за результатами цих змін .
Друга група містить методи і прилади, призначені для дослідження випадкових процесів і головним чином систем управління, в яких присутні випадкові сигнали, на універсальних цифрових і аналогових обчислювальних машинах. Іноді для таких досліджень доводиться створювати спеціалізовані обчислювальні машини цифрового, аналогового або найчастіше аналого-цифрового (гібридного) типу, так як існуючі типові машини не пристосовані для вирішення деяких завдань.
Широко застосовується на практиці метод Монте-Карло (метод статичних випробувань). Його основна ідея надзвичайно проста і полягає по суті в математичному моделюванні на обчислювальній машині тих випадкових процесів і перетворень з ними, які мають місце в реальній системі управління. Цей метод в основному реалізується на цифрових і, рідше, на аналогових обчислювальних машинах.
Можна стверджувати, що метод Монте-Карло залишається чистим методом моделювання випадкових процесів, чистим математичним експериментом, у відомому сенсі позбавленим обмежень, властивим іншим методам. Розглянемо даний метод стосовно до вирішення різних завдань управління.
2.1 Загальна характеристика методу Монте-Карло
Як вже зазначалося, ідея методу Монте-Карло (або методу статистичного моделювання) дуже проста і полягає в тому, що в обчислювальній машині створюється процес перетворення цифрових даних, аналогічний реальному процесу. Імовірнісні характеристики обох процесів (реального і змодельованого) збігаються з якоюсь точністю.
Припустимо, необхідно обчислити математичне сподівання випадкової величини X, що підкоряється деяким законом розподілу F (x). Для цього в машині реалізують датчик випадкових чисел, що має дане розподіл F (x), і за формулою, яку легко запрограмувати, визначають оцінку математичного сподівання:

.
Кожне значення випадкової величини x _i представляється в машині двійковим числом, яке надходить з виходу датчика випадкових чисел на суматор. Для статистичного моделювання розглянутої задачі потрібно N-кратне повторення рішення.
Розглянемо ще один приклад. Проводиться десять незалежних пострілів по мішені. Ймовірність влучення при одному пострілі задана і дорівнює p. Потрібно визначити ймовірність того, що число влучень буде парних, тобто 0, 2, 4, 6, 8, 10. Імовірність того, що число влучень буде 2k, дорівнює:

,
звідки шукана ймовірність

(1)
Якщо ця формула відома, то можна здійснити фізичний експеримент, провівши кілька партій пострілів (по десять у кожній) за реальною мішені. Але простіше виконати математичний експеримент на обчислювальній машині наступним чином. Датчик випадкових чисел видасть у цифровому вигляді значення випадкової величини ξ, що підкоряється рівномірному закону розподілу в інтервалі [0,1]. Імовірність нерівності ξ <p дорівнює p, тобто
P {ξ <p} = p.

Для пояснення доцільно звернутися до рис. 1, на якому весь набір випадкових чисел представляється у вигляді точок відрізка [0,1]. Імовірність попадання випадкової величини ξ, що має рівномірний розподіл в інтервалі [0,1], в інтервал [0, p] (де

) Дорівнює довжині цього відрізка, тобто p. Тому на кожному такті моделювання отримане число ξ порівнюють із заданою ймовірністю p. Якщо ξ <p, то реєструється попадання в мішень, в іншому випадку - промах. Далі проводять серію з десяти тактів і підраховують парне чи непарне число влучень. При великому числі серій (100-1000) виходить ймовірність, близька до тієї, яка визначається за формулою (1).
Розрізняють дві області застосування методу Монте-Карло. По-перше, для дослідження на обчислювальних машинах таких випадкових явищ і процесів, як проходження елементарних ядерних частинок (нейтронів, протонів тощо) через речовину, системи масового обслуговування (телефонна мережа, система перукарень, система ППО тощо), надійність складних систем, в яких вихід з ладу елементів та усунення несправностей є випадковими процесами, статистичне розпізнавання образів. Це - застосування статистичного моделювання до вивчення так званих імовірнісних систем управління.
Цей метод широко застосовується і для дослідження дискретних систем управління, коли використовуються кібернетичні моделі у вигляді імовірнісного графа (наприклад, мережеве планування з β-розподілом часу виконанням робіт) або імовірнісного автомата.
Якщо динаміка системи управління описується диференціальними або різницевими рівняннями (випадок детермінованих систем управління) і на систему, наприклад кутову систему, що стежить радіолокаційної станції впливають випадкові сигнали, то статичне моделювання також дозволяє отримати необхідні точності. У даному випадку з успіхом застосовуються як аналогові, так і цифрові обчислювальні машини. Однак, з огляду на більш широке застосування при статистичному моделюванні цифрових машин, розглянемо в даному розділі питання, пов'язані тільки з цим типом машин.

Друга область застосування методу Монте-Карло охоплює суто детерміновані, закономірні завдання, наприклад знаходження значень певних одновимірних і багатовимірних інтегралів. Особливо проявляється перевага цього методу в порівнянні з іншими чисельними методами у випадку кратних інтегралів.
При вирішенні алгебраїчних рівнянь методом Монте-Карло число операцій пропорційно числу рівнянь, а при їх вирішенні детермінованими чисельними методами це число пропорційно кубу числа рівнянь. Таке ж приблизно перевага зберігається взагалі при виконанні різних обчислень з матрицями і особливо в операції звернення матриці. Треба зауважити, що універсальні обчислювальні машини не пристосовані для матричних обчислень і метод Монте-Карло, застосований на цих машинах, лише дещо покращує процес вирішення, але особливо переваги імовірнісного рахунку проявляються при використанні спеціалізованих імовірнісних машин. Основною ідеєю, яка використовується при вирішенні детермінованих задач методом Монте-Карло, є заміна детермінованою завдання еквівалентної статистичної завданням, до якої можна застосовувати цей метод. Природно, що при такій заміні замість точного рішення задачі виходить наближене рішення, похибка якого зменшується зі збільшенням числа випробувань.
Ця ідея використовується в задачах дискретної оптимізації, які виникають при управлінні. Часто ці завдання зводяться до перебору великої кількості варіантів, що обчислюється комбінаторними числами виду N =

. Так, завдання розподілу n видів ресурсів між галузями для n> 3 не може бути точно вирішена на існуючих цифрових обчислювальних машинах (ЦОМ) і ЦВМ найближчого майбутнього з-за великого обсягу перебору варіантів. Однак таких задач виникає дуже багато в кібернетиці, наприклад синтез кінцевих автоматів. Якщо штучно ввести імовірнісну модель-аналог, то завдання істотно спроститься, правда, рішення буде наближеним, але його можна отримати за допомогою сучасних обчислювальних машин за прийнятний час рахунку.
При обробці великих масивів інформації та управлінні надвеликими системами, які налічують понад 100 тис. компонентів (наприклад, видів робіт, промислових виробів тощо), постає завдання укрупнення або еталонізаціі, тобто відомості надвеликого масиву до 100-1000 разів меншому масиву еталонів. Це можна виконати за допомогою імовірнісної моделі. Вважається, що кожен еталон може реалізуватися або матеріалізуватися у вигляді конкретного представника випадковим чином з законом ймовірності, визначеним відносної частотою появи цього представника. Замість вихідної детермінованої системи вводиться еквівалентна імовірнісна модель, яка легше піддається розрахунку. Можна побудувати кілька рівнів, будуючи еталони еталонів. У всіх цих імовірнісних моделях з успіхом застосовується метод Монте-Карло. Очевидно, що успіх і точність статистичного моделювання залежить в основному від якості послідовності випадкових чисел і вибору оптимального алгоритму моделювання.
Завдання отримання випадкових чисел звичайно розбивається на дві. Спочатку отримують послідовність випадкових чисел, що мають рівномірний розподіл в інтервалі [0,1]. Потім з неї отримують послідовність випадкових чисел, що мають довільний закон розподілу. Один із способів такого перетворення полягає у використанні нелінійних перетворень. Нехай є випадкова величина X, функція розподілу ймовірності для якої

.

Якщо y є функцією x, тобто y = F (x), то

і тому

. Таким чином, для отримання послідовності випадкових чисел, що мають задану функцію розподілу F (x), необхідно кожне число y з виходу датчика випадкових чисел, який формує числа з рівномірним законом розподілу в інтервалі [0,1], подати на нелінійне пристрій (аналогове чи цифрове), в якому реалізується функція, зворотна F (x), тобто

. (2)

Отримана таким способом випадкова величина X буде мати функцію розподілу F (x). Розглянута вище процедура може бути використана для графічного способу отримання випадкових чисел, що мають заданий закон розподілу. Для цього на міліметровому папері будується функція F (x) і вводиться в розгляд інша випадкова величина Y, яка пов'язана з випадковою величиною X співвідношенням (2) (рис. 2).
Так як будь-яка функція розподілу монотонно неспадними, то

.
Звідси випливає, що величина Y має рівномірний закон розподілу в інтервалі [0,1], тому що її функція розподілу дорівнює самій величині

.
Щільність розподілу ймовірності для Y

.
Для отримання значення X береться число з таблиць випадкових чисел, що мають рівномірний розподіл, який відкладається на осі ординат (рис. 2), і на осі абсцис зчитується відповідне число X. Повторивши неодноразово цю процедуру, отримаємо набір випадкових чисел, що мають закон розподілу F (x). Таким чином, основна проблема полягає в отриманні рівномірно розподілених в інтервалі [0,1] випадкових чисел. Один з методів, який використовується при фізичному способі отримання випадкових чисел для ЕОМ, полягає у формуванні дискретної випадкової величини, яка може приймати тільки два значення: 0 або 1 з ймовірностями

Далі будемо розглядати нескінченну послідовність z _1, z _2, z _3, ... як значення розрядів двійкового числа ξ ^* виду

Можна довести, що випадкова величина ξ ^*, укладена в інтервалі [0,1], має рівномірний закон розподілу

.
У цифрової обчислювальної машині є кінцеве число розрядів k. Тому максимальна кількість незбіжних між собою чисел дорівнює 2 ^k. У зв'язку з цим у машині можна реалізувати дискретну сукупність випадкових чисел, тобто кінцеве безліч чисел, що мають рівномірний закон розподілу. Такий розподіл називається квазіравномерним. Можливі значення реалізації дискретного псевдовипадкового числа

в обчислювальній машині з k розрядами будуть мати вигляд:

. (3)
Імовірність кожного значення (3) дорівнює 2 ^{- k.} Ці значення можна отримати наступним чином

.
Випадкова величина

має математичне очікування

.

Враховуючи, що

і вираз для кінцевої суми геометричної прогресії

, (4)
отримуємо:

. (5)
Аналогічно можна визначити дисперсію величини

,
де

,
звідки

,
або, використовуючи формулу (4), отримуємо:

. (6)

Відповідно до формули (5) оцінка

величини ξ ^* виходить зміщеною при кінцевому k. Цей зсув особливо позначається при малому k. Тому замість

вводять оцінку

, (7)
де

.
Очевидно, що випадкова величина ξ відповідно до співвідношення (3) може приймати значення

, I = 0,1,2, ..., 2 ^k -1
з імовірністю p = 1 / 2 ^k.
Математичне сподівання і дисперсію величини ξ можна отримати з співвідношень (5) і (6), якщо врахувати (7). Дійсно,

;

.
Звідси отримуємо вираз для середньоквадратичного значення у вигляді

. (8)

Нагадаємо, що для рівномірно розподіленої в інтервалі [0,1] величини x маємо

З формули (8) випливає, що при

середньоквадратичне відхилення σ квазіравномерной сукупності прагне до

. Нижче наведені значення відносини середньоквадратичних значень двох величин ξ і η в залежності від числа розрядів, причому величина η має рівномірний розподіл в інтервалі [0,1] (табл. 1).
Таблиця 1

k	2	3	5	10	15
σ _ξ / σ _η	1,29	1,14	1,030	1,001	1,00

З таблиці. 1 видно, що при k> 10 розходження в дисперсіях неістотно.
На підставі вищевикладеного завдання отримання сукупності квазіравномерних чисел зводиться до отримання послідовності незалежних випадкових величин z _i (i = 1,2, ..., k), кожна з яких приймає значення 0 або 1 з ймовірністю 1 / 2. Розрізняють два способи отримання сукупності цих величин: фізичний спосіб генерування та алгоритмічне одержання так званих псевдовипадкових чисел. У першому випадку потрібна спеціальна електронна приставка до цифрової обчислювальної машини, в другому випадку завантажуються блоки машини.
При фізичному генеруванні найчастіше використовуються радіоактивні джерела або шумливі електронні пристрої. У першому випадку радіоактивні частинки, випромінювані джерелом, надходять на лічильник часток. Якщо показання лічильника парне, то z _i = 1, якщо непарне, то z _i = 0. Визначимо ймовірність того, що z _i = 1. Число часток k, яке випускається за час Δt, підпорядковуються закону Пуассона:

.
Імовірність парного числа частинок

.
Таким чином, при великих λΔt ймовірність P {Z _i = 1} близька до 1 / 2.
Другий спосіб отримання випадкових чисел z _i більш зручний і пов'язаний з власними шумами електронних ламп. При посиленні цих шумів виходить напруга u (t), яке є випадковим процесом. Якщо брати його значення, досить віддалені один від одного, так щоб вони були некорельованих, то величини u (t _i) утворюють послідовність незалежних випадкових величин. Зазвичай вибирають рівень відсічення a і вважають

причому рівень a слід вибрати так, щоб

.
Також застосовується більш складна логіка освіти чисел z _i. У першому варіанті використовують два сусідніх значення u (t _i) і u (t _{i +1),} і величина Z _i будується за таким правилом:

Якщо пара u (t _i) - a і u (t _{i +1)} - a одного знака, то береться наступна пара. Потрібно визначити ймовірність при заданій логіці. Будемо вважати, що P {u (t _i)> a} = W і постійна для всіх t _i. Тоді ймовірність події

дорівнює за формулою подій A ₁ H _v. Тут H _v - це ймовірність того, що v раз з'явилася пара однакового знака
u (t _i) - a; u (t _{i +1)} - a. (9)
Тому ймовірність події A ₁ H _v
P {A ₁ H _v} = W (1-W) [W ² + (1-W) ^{2] v.}
Це - імовірність того, що після v пар вигляду (9) з'явилося подія A _1. Воно може з'явитися відразу з імовірністю W (1-W), воно може з'явитися і після однієї пари виду (9) з ймовірністю
W (1-W) [W ² + (1 + W) ^2]
і т.д. У результаті

або

.

Звідси випливає, що якщо W = const, то логіка забезпечує хорошу послідовність випадкових чисел. Другий спосіб формування чисел z _i полягає в наступному:

Нехай
W = P {u (t _i)> a} = 1 / 2 + ξ.
Тоді
P {Z _i = 1} = 2W (1-W) = 1/2-2ξ ^2.
Чим менше ξ, тим ближче ймовірність P {Z _i = 1} до величини 1 / 2.
Для отримання випадкових чисел алгоритмічним шляхом за допомогою спеціальних програм на обчислювальній машині розроблено велику кількість методів. Так як на ЦВМ неможливо отримати ідеальну послідовність випадкових чисел хоча б тому, що на ній можна набрати кінцеве безліч чисел, такі послідовності називаються псевдовипадковими. Насправді повторюваність або періодичність у послідовності псевдовипадкових чисел наступає значно раніше і обумовлюється специфікою алгоритму отримання випадкових чисел. Точні аналітичні методи визначення періодичності, як правило, відсутні, і величина періоду послідовності псевдовипадкових чисел визначається експериментально на ЦВМ. Більшість алгоритмів виходить евристично і уточнюється в процесі експериментальної перевірки. Розгляд почнемо з так званого методу скорочення. Нехай задана довільна випадкова величина u, що змінюється в інтервалі [0,1], тобто

. Створюємо з неї іншу випадкову величину
u _n = u [mod ^2-n], (10)

де u [mod 2 ^{- n]} використовується для визначення операції отримання залишку від ділення числа u на 2 ^{- n.} Можна довести, що величини u _n в межі при

мають рівномірний розподіл в інтервалі [0,1].
По суті за допомогою формули (10) здійснюється усікання вихідного числа з боку старших розрядів. При залишенні далеких молодших розрядів природно виключається закономірність в числах і вони більше наближаються до випадковим. Розглянемо це на прикладі.
Приклад 1. Нехай u = 0,10011101 ... = 1 · 1 / 2 + 0 · 1 / ² 2 + 0 · 1 / 2 ³ + 1 · 1 / 2 ⁴ + 1 · 1 / 2 ⁵ + 1 · 1 / 2 ⁶ + 0 · 1 / 2 ⁷ + 1 · 1 / 2 ⁸ + ...
Виберемо для простоти n = 4. Тоді {u mod 2 ^-4} = 0,1101 ...
З розглянутого властивості ясно, що існує велика кількість алгоритмів отримання псевдовипадкових чисел. При цьому після операції усічення з боку молодших розрядів застосовується стандартна процедура нормалізації числа в цифровій обчислювальній машині. Так, якщо усічене зліва число не вміщується по довжині в машині, то проводиться усікання числа справа.
При перевірці якості псевдовипадкових чисел насамперед цікавляться довжиною відрізка аперіодічності і довжиною періоду (рис. 3). Під довжиною відрізка аперіодічності L розуміється сукупність послідовно отриманих випадкових чисел α _1, ..., α _L таких, що α _i

α _j при

, Але α _{L +1} дорівнює одному з α _k (

).
Під довжиною періоду послідовності псевдовипадкових чисел розуміється T = L-i +1. Починаючи з деякого номера i числа будуть періодично повторюватися з цим періодом (рис. 3).

Як правило, ці два параметри (довжини аперіодічності і періоду) визначаються експериментально. Якість збіги закону розподілу випадкових чисел з рівномірним законом перевіряється за допомогою критеріїв згоди.
2.2 Точність методу Монте-Карло
Метод Монте-Карло застосовується там, де не потрібно високої точності. Наприклад, якщо визначають ймовірність ураження мішені при стрілянині, то різниця між p ₁ = 0,8 і p ₂ = 0,805 несуттєва. Зазвичай вважається, що метод Монте-Карло дозволяє отримати точність приблизно 0,01-0,05 максимального значення визначається величини.
Отримаємо деякі робочі формули. Визначимо за методом Монте-Карло ймовірність перебування системи в деякому стані. Ця ймовірність оцінюється відношенням

,
де M - число перебувань системи в цьому стані внаслідок N моделювань. Враховуючи вираз для дисперсії величини M / N

і нерівність Чебишева

, (11)
напишемо

. (12)
Величина

є ні що інше, як помилка моделювання за методом Монте-Карло. За допомогою формули (11) можна написати наступну формулу для величини (12):

,
або

,
де p ₀ - імовірність невиконання цієї оцінки. За допомогою частоти M / N може бути отримана оцінка математичного сподівання m _x деякої випадкової величини X. Помилка цієї оцінки

знаходиться за допомогою співвідношення

.

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

. (13)
Приклад 2. Припустимо, що визначається математичне сподівання помилки x ураження мішені. Процес стрільби і поразки моделюється на ЦВМ за методом Монте-Карло. Потрібна точність моделювання δ = 0,1 м з вірогідністю p = 1-p ₀ = 0,9 при заданій дисперсії σ _x = 1 м. Необхідно визначити кількість моделювань N. За формулою (13) отримуємо:

.
При такій кількості реалізацій забезпечується δ = 0,1 м з вірогідністю p = 0,9.

3. Метод гілок і меж
Всі комбінаторні методи вирішення завдань цілочисельного програмування засновані на тій чи іншій ідеї спрямованого перебору варіантів, в результаті якого шляхом перебору скороченого числа допустимих рішень відшукується оптимальне рішення. Перебір здійснюється за допомогою певного комплексу правил, які дозволяють виключати підмножини варіантів, що не містять оптимальної точки.
У цілому ці методи легше справляються з проблемою заокруглень, ніж методи відсікання, як правило, не використовують симплекс-процедуру лінійного програмування і мають більш «просту арифметику» і більш «складну логіку».

Основний зміст цих методів складають динамічне програмування та сукупність способів вирішення, об'єднаних загальним терміном - метод «гілок і меж».
Комплексний підхід за схемою розгалужень об'єднує цілий ряд близьких комбінаторних методів, як-то: метод гілок і меж, метод послідовного конструювання, аналізу та відсіву варіантів і ін Загальна ідея методу вкрай проста. Безліч допустимих планів деяким способом розбивається на підмножину. У свою чергу кожне з підмножин з цього ж або іншого способу знову розбиваються на підмножини до тих пір, поки кожна підмножина не буде являти собою крапку в багатовимірному просторі. У силу кінцівки наборів значень змінних дерево підмножин (схема розгалуження) звичайно.
Побудова схеми розгалуження є ні що інше, як формування процедури перебору. Перебір може здійснюватися різними способами. Перетин вихідної припустимою області G ₀ гиперплоскостью на частини G ₁₁ і G ₁₂ з наступним поділом G ₁₁ на G ₂₁ і G ₂₂ являє собою побудова дерева розгалужень з відповідними подмно-дружність, як це показано на рис. 4.

Можливість оцінки утворених підмножин по найбільшому (найменшому) значенню для задач мінімізації (максимізації) дозволяє скоротити перебір у силу того, що одне з підмножин при виконанні певних співвідношень виключається і не потребує подальшого аналізу.
Зрозуміло, що вибір оцінок і схеми розгалуження взаємопов'язані і важко вказати загальні рекомендації з використання на практиці цього методу.
Схема розгалуження ілюструється рішенням узагальненої задачі одновимірного розкрою (приклад 3) з конкретними числовими даними.
Приклад 3.
Є заготовки довжиною a ₁ = 18, a ₂ = 16, a ₃ = 13. Розрізаючи їх на частини, але не склеює, можна отримувати деталі довгою b ₁ = 12, b ₂ = 10, b ₃ = 8, b ₄ = 6, b ₅ = _5, b ₆ = 4. Вартість кожної деталі відома і в умовних одиницях чисельно дорівнює їх довжині. Перераховані деталі представляють собою "портфель замовлень», який бажано забезпечити в першу чергу. У тому випадку, якщо це неможливо, максимізує вартість одержуваних деталей із заданої номенклатури. Якщо ж портфель замовлень забезпечується, необхідно максимізувати вартість додаткової продукції.
Величину

будемо називати дефіцитом. Заперечність дефіциту ще не означає існування варіанти розкрою, при позитивному дефіциті розкрій неможливий. Ця властивість може бути використано для вказівки перспективності варіанту. Так, якщо заготівля a ₂ розкроюється на b ₂ і b _5, то незалежно від комбінацій інших відрізків розкрій нездійсненний, оскільки для решти відрізків дефіцит позитивний.
Перші етапи наведеній нижче схеми розгалуження, що використовує комбінаторні відносини підмножин варіантів, показані на рис. 5. На першому етапі формуються розбиття першої групи відрізків (заготовок) на другу групу (деталей) незалежно від того, який саме відрізок першої групи розрізається. Кількість гілок першого етапу можна обчислити лише за рекурентним співвідношенням. Сенс підмножини {1, 2, 3} полягає в тому, що один з відрізків першої групи в результаті розкрою дає один відрізок другої групи, один з решти відрізків першої групи розкроюється на два відрізки другої групи з-поміж решти і, нарешті, останній відрізок першу групи поділяється на три частини, утворюючи три відрізки другої групи. На другому етапі формуються всі перестановки (з урахуванням порядку) елементів першого етапу. Скажімо, варіант {2, 1, 3} означає, що саме перший елемент першої групи a ₁ розрізається на дві частини і т.д.

Черговий етап розгалуження утворюється фіксацією відрізків другої групи при вказаному на попередньому етапі числі частин, на яке розрізається перший елемент. Іншими словами, формуємо поєднання за кількістю розділень першого елемента першої множини на число елементів другого множини. Надалі фіксуємо відрізки другої групи при другому елементі першої групи і, нарешті, при залишився елементі першої групи отримуємо варіанти розкрою, всього 447 варіантів. У докладно описаною схемою розгалуження на відміну від часто вживаних на жодному етапі не використовується конкретний числовий матеріал. Рекомендується побудувати для цього ж прикладу іншу схему розгалуження, починаючи з третього етапу, за наступним ознакою: відрізки другої групи фіксуються при елементі першої групи, розрізаємо на менше число частин. Потім треба порівняти схеми. Неважко переконатися, що на кожному етапі розгалуження здійснюється за регулярною процедурою, що дозволяє запам'ятовувати лише один варіант. Порівняння дефіцитів попереднього і подальшого варіантів дозволяє виділити перспективну галузь. Остаточний результат має вигляд:
{(B _2, b _3), (b _4, b _5, b _6), (b _1)};
{(B _1, b _4), (b _2, b _5), (b _3, b _6)};
{(B _1, b _4), (b _2, b _6), (b _3, b _5)};
{(B _1, b _5), (b _2, b _4), (b _3, b _6)};
{(B _2, b _3), (b _1, b _6), (b _4, b _5)};
{(B _1, b _6), (b _2, b _4), (b _3, b _5)};
{(B _2, b _4), (b _1, b _6), (b _3, b _5)}.
Формально завдання можна було б звести до загального вигляду лінійної задачі цілочисельного програмування, але таке зведення призведе до значного збільшення кількості змінних та іншим труднощів. Матриця коефіцієнтів при цьому набуває квазіблочний вигляд з нещільним заповненням її відмінними від нуля елементами. Як правило, завдання многоіндексние з великим числом умов і складної впорядкованістю рекомендується вирішувати за схемою розгалужень, використовуючи специфіку умов і обмежень.
Для задач дискретного типу цей метод набув найбільшого поширення в силу простоти та доступності самого методу і, крім того, найбільш природною форми опису систем умов і обмежень, що є, як правило, відправним пунктом побудови дерева розгалуження. По суті більшість оригінальних алгоритмів (Балаша-Фора-Мальгранжа, Череніна, Джефферсона, Хіллієр тощо) є модифікаціями методу гілок і кордонів з урахуванням специфіки умов завдання.

4. Побудова оптимальної послідовності завдань на обробку у вузлі обчислювальної системи
4.1 Формалізація обчислювального процесу і робочого навантаження
Вузол обчислювальної системи представляється у вигляді сукупності обладнання та програмних компонент. Обладнання включає в себе: центральний процесор (CPU), зовнішню пам'ять (HDD), пристрої введення-виведення інформації (IOI). Програмними компонентами в обчислювальній системі є операційна система (OS) і безліч завдань, що реалізуються за запитами робочого навантаження. Для моделювання робочого навантаження на вузлах обчислювальної системи необхідно провести декомпозицію кожного завдання пакету робочого навантаження на окремі програмні модулі (ПМ _j). Кількість і типи програмних модулів залежать від наявного складу обладнання та програмних засобів вузла обчислювальної системи. При цьому можна виділити наступні типи програмних модулів: введення інформації; обробки інформації; реалізація обчислень на центральному процесорі; виведення інформації. Модуль обробки інформації звертається до бази даних обчислювальної системи.
У свою чергу реалізація звернення до бази даних також має певну структуру, що характеризується графом GBD зв'язків модулів в базі даних (MDB _k). Передбачається, що характер проходження один за одним модулів бази даних при виконанні запитів в модулі обробки інформації також є напівмарковському.
Оскільки реалізація завдання i з робочої навантаження характеризується напівмарковському процесом, то для визначення характеру цього процесу необхідно визначити такі характеристики:
· Матрицю ймовірності переходів i-го завдання від одного (j-го) програмного модуля до іншого (l-му) програмного модулю МР _i = | | Р _ijl | |;
· Матрицю, елементами якої є функції розподілу часу обробки завдання i в i-му програмному модулі за умови отримання ним управління від j-го програмного модуля (MF _i = | | F _i (t _jl )||);
· Тип j-го програмного модуля, з якого починається напівмарковському процес завдання i (j _Oi) і кількість j-х програмних модулів, реалізованих ланцюжком j-х програмних модулів (N _Oi).
Аналогічним способом визначаються характеристики напівмарковському процесу реалізації обміну. В якості вихідної інформації задаються:
· Матриця ймовірностей прямування один за одним MDB _jk (Mq _j = | | q _jks | |);
· Матриця, елементами якої є функції розподілу обсягів інформації при виконанні MDB _js за умови того, що перед цим використовувався модуль MDB _jk (МФ _j = | | F _j (V _objs )||);
· Тип MDB _jk, з якого починається звернення до бази даних (k _O), і кількість MDB _jk, що реалізується у разі даному зверненні j-го програмного модуля до бази даних (m _Oj).
4.2 Особливості організації імітаційного експерименту
Динаміка виконання завдань користувачів на обладнанні вузла обчислювальної системи відбивається послідовністю j-х програмних модулів і має імовірнісний характер. Кожен j-й програмний модуль вузла захоплює ресурс центрального процесора, частина ресурсу оперативної пам'яті (V _oni) і звертається до зовнішньої пам'яті (HDD). Ресурс центрального процесора завжди виділяється j-м програмним модулем повністю. Розподіл ресурсу центрального процесора організує операційна система. Ресурс центрального процесора розподіляється по всіх j-м програмним модулям і для його виділення на певний квант часу (Δt) використовується система керуючих сигналів, які формуються за заявками, які надходять від j-х програмних модулів. Зовнішня пам'ять моделюється як місце розміщення бази даних, і тому виділення ресурсу зовнішньої пам'яті для j-х програмних модулів здійснюється до завершення виконання завдання. Функціонування пристроїв інформації введення виведення і модуля виведення інформації моделюються як звичайні пристрої масового обслуговування з дисципліною FIFO.
Час, витрачений на виконання завдання i, позначимо через Т _{ж i.} Причому, в Т _{ж i} включається сума часу обслуговування завдання i на всіх пристроях обчислювальної системи, а також сума часів витрат виконання запитів завдань через зайнятість необхідних ресурсів іншими завданнями.
Метою моделювання обчислювального процесу в обчислювальних системах є мінімізація

за рахунок оптимізації порядку входу завдань робочої навантаження в обчислювальній системі при незмінному складі ресурсів системи. Для одержання оптимальної послідовності завдань робочої навантаження необхідно знати: перелічені раніше характеристики напівмарковському представлення процесу розв'язання задач; ресурсні характеристики обчислювальної системи; можливі реакції обчислювальної системи на завдання робочої навантаження з метою підрахунку часу обробки i-го завдання в обчислювальній системі.
Передбачається, що перші дві умови задаються до постановки імітаційного експерименту. Тому нижче розглядаються особливості моделювання варіантів обробки завдань в обчислювальній системі.
Оскільки кожне завдання використовує ресурс обчислювальної системи імовірнісним чином, то для розрахунку найбільш ймовірного часу обробки вузлом обчислювальної системи i-го завдання T _{ж i,} а також коефіцієнтів завантаження центрального процесора (η _CPU) і зовнішньої пам'яті (η _HDD) використовується метод Монте-Карло . Кількість реалізацій (N) i-го завдання i = 1, ..., n в обчислювальній системі визначається з точності моделювання (

) Для отримання оцінок вектора (Т _{ж i,} η _CPUi, η _HDDi). Після закінчення N реалізацій імітаційного експерименту всіх n завдань робочої навантаження виходить матриця для кожного відгуку (Т _{ж i,} η _CPUi, η _HDDi). Методика розрахунку компонент цього вектора реалізується наступною послідовністю кроків.
Крок 1. Знаходження часу розв'язання задач (Т _{ж i)} та визначення коефіцієнтів завантаження (η _CPU, η _HDDi) для різних рівнів мультипрограмування. Зауважимо, що звичайно число рівнів мультипрограмування рідко перевищує величину 5, тому в нашому дослідженні будемо орієнтуватися на максимальний рівень мультипрограмування рівний 5. Алгоритм реалізації кроку 1 заснований на методі Монте-Карло для кожного рівня мультипрограмування.
Після N реалізацій імітаційного експерименту з моделлю обчислювального процесу для h-го рівня мультипрограмування (h-й варіант обчислювального процесу, h = 0, ..., 5) за методом Монте-Карло буде сформовано три матриці, компонентами якої будуть пари значень:
M _{1 ih} = | | (MT _{ж ih,} DT _{ж ih)} | |; M _{2 ih} = | | (Mη _CPUih, D _CPUih) | |; M _{3 ih} = | | (Mη _HDDih, Dη _HDDih) | |.
Крок 2. За матрицям M _{1 ih,} M _{2 ih,} M _{3 ih} для h-го рівня мультипрограмування визначають математичні очікування і дисперсії обчислень кожного з відгуків: часу вирішення всього пакету (МТ _{ПАК h,} МТ _{ПАК h);} загальної завантаження центрального процесора (Mη _HDDh, Dη _HDDh); загальної завантаження зовнішньої пам'яті (Mη _HDDh, Dη _HDDh) за формулами:
MY _{ПАК h} =

, DY _{ПАК h} =

,
де 0

δ _i 1 - ваговий коефіцієнт завдань i-го типу в пакеті;
m ₀ - загальне число завдань у пакеті;
m _i - кількість завдань i-го типу в пакеті;
Y _{ПАК h} - відгук, зміст якого відповідає одній з характеристик обчислювального процесу в обчислювальній системі (Т _ж, η _CPU, η _HDD).
4.3 Модифікація послідовності вирішення завдань в пакеті за методом гілок і меж
Описана вище структура пакету робочої навантаження дозволяє виділити наступні можливі випадки кількості типів завдань.
1. Всі завдання пакету робочої навантаження мають один і той же тип (i = 1).
2. У пакеті є різні типи завдань і кількість типів (1 <i <m _0).
3. Всі завдання пакету мають різні типи (i = m _0).
Найбільший інтерес для дослідження пошуку оптимального розташування завдань у пакеті робочого навантаження представляє третій випадок. Тому розглянемо застосування методу гілок і меж для цього випадку.
Крок 0. Обчислюється загальний час обробки всього ще не упорядкованого пакету Tξ (STR).
Крок 1. Розмірність безлічі STR дорівнює n (| STR | = n). На першому рівні розгалуження обчислюються оцінки Tξ (STR _i ^1), i = 1, ..., n. Вони обчислюються за умови, що i-е завдання починає оброблятися першим, а що залишилися n-1 завдань входять у розклад по мірі зростання Т _{ж i.} Серед цих оцінок вибирається оцінка з найменшим Tξ (STR _i ¹⁾ і відповідне i-е завдання (i ₁₎ вставляється у розклад першим. При цьому інші оцінки відкидаються і відповідні їм порядки проходження завдань завдань вважаються свідомо неоптимальними.
Крок 2. Розмірність масиву STR дорівнює n-1 (| STR | = n-1). Цей рівень розгалуження здійснюється за умови, що одне із завдань i (i ₁₎ вже вставлено в розклад для обробки першим. Для інших n-1 завдань, ще не вставлених у розклад, обчислюються оцінки Tξ (STR _i ^2), i = 1, ..., n-1, за умови, що завдання i завантажується для обробки другим, а що залишилися n-2 завдань входять до розкладу в міру зростання Т _{ж i.} Серед цих оцінок вибирається оцінка з найменшим Tξ (STR _i ²⁾ і відповідне i-е завдання (i ₂₎ вставляється у розклад другим. При цьому інші оцінки відкидаються і відповідні їм порядки проходження завдань завдань вважаються свідомо неоптимальними. В результаті другого кроку в оптимальний розклад будуть вставлені вже два завдання.
Крок k (k> 2). Розмірність масиву STR дорівнює n-k +1 (| STR | = n-k +1). Цей рівень розгалуження здійснюється за умови, що k-1 завдання вже вставлено в розклад. Для інших n-k +1 завдань, ще не вставлених у розклад, обчислюються оцінки Tξ (STR _i ^k), i = 1, ..., n-k +1. Серед цих оцінок вибирається оцінка з найменшим Tξ (STR _i ^k) і відповідне i-е завдання (i _k) вставляється у розклад k-им. При цьому інші оцінки відкидаються і відповідні їм порядки проходження завдань завдань вважаються свідомо неоптимальними. У результаті k-го кроку в оптимальний розклад будуть вставлені вже k завдань.
Крок n. Розмірність безлічі STR дорівнює 1 (| STR | = 1). На цьому кроці залишилося лише одне завдання, не вставлене в розклад. Воно вставляється в розклад останнім, і обчислюється оцінка Tξ (STR _i ^n), i = 1, яка і буде підсумковою оцінкою (часом) обробки завдань пакету робочої навантаження при відповідному їй розкладі.
Після одержання оптимальної послідовності порядку завдань за допомогою методу гілок і меж необхідно порівняти цей час обробки пакета з часом, отриманим при початковому розташуванні завдань у пакеті робочого навантаження.

Висновок
Проблема адаптації робочого навантаження до параметрів обчислювального процесу представляється актуальною через необхідність підвищення ефективності використання ресурсів обчислювальної системи і якості обслуговування запитів користувача. Крім того, на практиці часто безперервно змінюються і склад, і структура робочого навантаження, що ускладнює ситуацію вибору оптимального варіанту обчислювального процесу.
Вивчивши і проаналізувавши ряд наукових статей, присвячених даній проблемі, слід зазначити, що найбільш простим і розповсюдженим способом її вирішення є метод гілок і меж. Було встановлено, що більшість існуючих оригінальних алгоритмів є модифікаціями даного методу. Вперше метод гілок і меж був запропонований Ленд і Дойг в 1960 році для вирішення загальної задачі цілочисельного лінійного програмування. Інтерес до цього методу і фактично його «друге народження» пов'язане з роботою Літтла, Мурті, Суїні і Керела, присвяченій завданню комівояжера. Починаючи з цього моменту, з'явилася велика кількість робіт, присвячених методу гілок і меж і різних його модифікацій.
Можна стверджувати, що проблема адаптації робочого навантаження буде залишатися актуальною і в найближчому майбутньому у зв'язку з тим, що її можна вирішувати і в умовах локальних обчислювальних мереж.
Таким чином, розглянуте застосування методу гілок і меж до побудови оптимальної послідовності завдань на обробку в обчислювальній системі дозволяє говорити про можливу ефективність залучення цього методу до такого типу завдань.

Список джерел
1. Галієв Р.С. Експериментальні методи дослідження обчислювального процесу ЄС ЕОМ. - Дис., Гомель, 1987.
2. Демиденко О.М., Максимей І.В., Імітаційне моделювання взаємодії процесів в обчислювальних системах. - Мн.: Білоруська наука, 2000.
3. Корбут А.А., Фінкельштейн Ю.Ю., Дискретне програмування. - М.: Наука, 1969.
4. Максимей І.В., Серьогіна В.С. Завдання та моделі дослідження операцій. Частина 2. - Гомель, 1999.
5. Максимей І.В. Імітаційне моделювання на ЕОМ. - М.: Радіо і зв'язок, 1988.
6. Грек В.В., Максимей І.В. Стандартизація та метрологія систем обробки даних. - Мн.: Вища школа, 1994.
7. Бишік Т.П., Маслович С.Ф., Мережа В.Л. Про побудову оптимальної послідовності завдань на обробку у вузлі ЛВС / / Известия Гомельського державного університету імені Ф. Скорини. - 2002. - № 6 (15) - С. 7-9.
8. Кузін Л.Т. Основи кібернетики. Том 1. - М.: Енергія, 1973.
9. Land AH, and Doig AG An automatic method of solving discrete programming problems. Econometrica. v28 (1960), pp.497-520.
10. Little JDC, Murty KG, Sweeney DW, and Karel C. An algorithm for the traveling salesman problem. Operations Research. v11 (1963), pp. 972-989.