1. ВИЗНАЧЕННЯ СЕРЕДНЬОЇ ТРУДОМІСТКОСТІ АЛГОРИТМІВ ЗАЯВОК

Визначення середньої трудомісткості заявок необхідне для обчислення всіх параметрів комп`ютерної системи, зокрема мінімальної швидкодії процесора. Суть обчислення базується на тому, що ймовірності переходу по умовам в схемі заявки відомі.

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

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