Виконав:
Студент групи СІ 22
Никорчук Володимир
Перевірив:
Хомів Богдан Арсенович
Тернопіль2011
Возможно вы искали - Дипломная работа: Основы программирования
Частина 1 . Засвоєння засобів аналізу трудомісткості обчислювальних алгоритмів
Короткі теоретичні відомості:
Задача, що підлягає вирішенню на ПК, може бути охарактеризована кількістю даних, складністю алгоритму та його трудомісткістю. Під трудомісткістю алгоритму розуміється кількість обчислювальної роботи,необхідної для його реалізації. Трудомісткість характеризує витрати часу для реалізації алгоритму на деякій сукупності технічних засобів. Звичайно, трудомісткість оцінюється кількістю процесорних операцій та операцій введення-виведення. В загальному випадку, трудомісткість алгоритму є випадковою величиною, що залежить від вхідних даних. Тому, трудомісткість алгоритму може бути визначена тільки наближено, в термінах теорії ймовірностей: математичним сподіванням, дисперсією і т. д.
Трудомісткість алгоритму в першому наближенні може бути охарактеризована набором параметрів:
ϴ - середня кількість процесорних операцій, необхідних для однієї реалізації алгоритму;
Похожий материал - Курсовая работа: Основные вопросы проектирования баз данных, принципы работы с Microsoft Office Access 2003
N1 ,N2 ,…NH – середня кількість запитів до файлів за один прогін програми;
L1 ,L2 ,…LH - середня кількість інформації, що передається за одне звернення до файлів F1 ,F2 ,…FH .
При необхідності набір параметрів, що характеризують трудомісткістю алгоритму може бути доповнений. Вхідна інформація для розрахунку трудомісткості алгоритму може бути одержана з блок-схеми алгоритму.
Для розрахунку трудомісткості алгоритму необхідно знати ймовірності переходів з логічних вершин при одиничному значенні логічної умови. Якщо відповідну ймовірність визначити через p, тоді ймовірність виходу з логічної вершини при нульовому логічному значенні умови, що перевіряється буде дорівнювати l-p . Для подальших розрахунків схему алгоритму раціонально зображати в вигляді графа алгоритму. Для цього пропонується перенумерувати всі оператори схеми алгоритму. У логічних операторів замість логічних умов «1» і «0» будемо записувати відповідну даному виходу ймовірність. Ймовірність виходу з операторної вершини дорівнює 1. Граф алгоритму можна істотно спростити, якщо трудомісткість виконання логічних вершин незначна в порівнянні з трудомісткістю виконання операторних вершин. Тоді стани, що відповідають логічними вершинами, можна злити з станами, що випереджають відповідні операторні вершини.
Хід роботи:
Очень интересно - Курсовая работа: Разработка информационно-поисковой системы "Результаты соревнований" на языке программирования Паскаль
1. Побудова блок-схеми за логічною схемою алгоритмів.
Поч. X1 ↑1 А
В X2 ↑2 С X3 ↑3 
Е X4 ↑4 К 
М Кін.
Блок-схема даного алгоритму зображена на рис.1.
Рисунок 1
Вам будет интересно - Курсовая работа: Полный факторный эксперимент
2. Побудова графа даного алгоритму з отриманої вище блок-схеми, що показано на рис.2.
Рисунок 2
3. Мінімізація графа даного алгоритму, що показано на рис. 3.
Похожий материал - Курсовая работа: Имитационная модель операционного зала банка
Рисунок 3
4. Подання графа у вигляді стохастичної матриці зображено в таблиці1.
алгоритм граф трудомісткість excel
Таблиця1
| S1 | S2 | S3 | S4 | S5 | S6 | S7 | Sk |
| S0 | 0.8 | 0.2 | |||||
| S1 | 1 | ||||||
| S2 | 0.2 | 0.8 | |||||
| S3 | 0.3 | 0.7 | |||||
| S4 | 1 | ||||||
| S5 | 0.8 | 0.2 | |||||
| S6 | 1 | ||||||
| S7 | 1 |