Експериментальні методи оцінки часової та функціональної ефективності алгоритмів у програмно-апаратних середовищах

Размещено на http://www.allbest.ru/

1

Київський національний університет імені Тараса Шевченка

УДК 510.5:004.05

Автореферат

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

доктора технічних наук

Експериментальні методи оцінки часової та функціональної ефективності алгоритмів у програмно-апаратних середовищах

01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем

Шинкаренко Віктор Іванович

Київ-2010

Дисертацiєю є рукопис

Робота виконана на кафедрі комп'ютерних інформаційних технологій Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна. кваліфікація інформація програмний

Науковий консультант:

доктор фізико-математичних наук, професор Капустян Володимир Омелянович, Національний технічний університет України "КПІ", завідувач кафедри математичного моделювання економічних систем.

Офiцiйнi опоненти:

член-кореспондент Національної академії наук України, доктор фізико-математичних наук, професор Перевозчикова Ольга Леонідівна, Інститут кібернетики НАН України, зав. відділом автоматизації програмування;

доктор технічних наук, професор Симоненко Валерій Павлович, Національний технічний університет України "КПІ", професор кафедри обчислювальної техніки;

доктор технічних наук, професор Цейтлін Георгій Овсійович, Інститут програмних систем НАН України, провідний науковий співробітник відділу теорії комп'ютерних обчислень.

Захист вiдбудеться 23 грудня 2010 р. о 14 год. 00 хв. на засiданнi спецiалiзованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка, Київ, пр. Глушкова, 4д, факультет кібернетики, ауд. 40. Тел. 521-33-66. Факс 239-32-80, E-mail: rada@cyber.univ.kiev.ua

З дисертацiєю можна ознайомитися в науковій бiблiотецi ім. М. Максимовича Київського національного університету імені Тараса Шевченка, Київ, вул. Володимирська, 58

Автореферат розiсланий 22 листопада 2010 р.

Вчений секретар спецiалiзованої вченої ради В. П. Шевченко

Загальна характеристика роботи

Актуальність теми. Темпи розвитку обчислювальної техніки та відповідного системного та прикладного програмного забезпечення (ПЗ) постійно зростають. Якщо в 60-90 рр. минулого століття нові архітектури ЕОМ і операційні системи масового використання з'являлися з інтервалом 5...10 років, то зараз тільки фірма Intel забезпечує оновлення декількох серій процесорів щорічно, а Microsoft - щорічне оновлення ОС Windows. Крім того, розвивається декілька принципово різних платформ процесорів RISC, Гарвардської, Берклійської архітектури, асоціативні, матричні, нейронні, проблемно-орієнтовані архітектури та інші. Вагому конкуренцію OC Windows складають Unix-подібні ОС, такі як Linux, QNX та інші.

У процесі розвитку програмних та апаратних обчислювальних засобів набула застосування низка проектних рішень, що забезпечують прискорення обчислень. Це кешування даних та команд, конвеєрна обробка команд, паралельні обчислення тощо.

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

Переважна більшість теоретичних досліджень з аналізу алгоритмів ґрунтується на аспекті представлення алгоритмів і не враховує особливостей сучасних засобів їх виконання. Можна виділити три основні підходи до аналізу алгоритмів.

Перший підхід базується на теорії ймовірностей і комбінаториці. Розробкою методології аналізу алгоритмів та її застосуванням до конкретних алгоритмів починаючи з 1950 р. інтенсивно займалися багато вчених. Розроблені методи й більшість результатів зарубіжних дослідників узагальнено у відомій роботі Д. Кнута. Сучасні дослідження представлені великою кількістю монографій і підручників, серед яких праці А. В. Аха, Д. Гріна, Дж. Хопкрофта, Дж. Ульмана, Дж. Макконнелла, С. Гудмана, С. Хідетніемі, Т. Кормена, Ч. Лейзерсон, Р. Ривеста та інших, а також вітчизняних учених і вчених країн СНД В. К. Задираки, А. В. Анісімова, О. А. Павлова, М. М. Глибовця, Л. П. Лісовика, В. П. Симоненка, О. Л. Семенова, В. А. Успенського, О. Є. Андрєєва, В. Б. Алексєєва, Г. П. Кожевнікової, С. А. Абрамова, В. А. Носова, В. В. Воєводіна та інших.

Формальному аналізу алгоритмів та їх перетворенням присвячені роботи на основі відомих моделей: алгебр Глушкова, машин Тьюрінга, Колмогорова, Шйонхаге, систем Поста, нормальних алгоритмів Маркова, схем програм Янова, граф-схем Калужніна і т. ін. (другий підхід). Завдяки роботам В. М. Глушкова, А. А. Летичевського, Є. Л. Ющенко, Ю. В. Капітонової, Г. О. Цейтліна, В. Н. Редька, П. І. Андона, М. С. Нікітченка, Д. Б. Буя, А. Ю. Дорошенка та інших підтримується пріоритетність вітчизняної науки в алгебраїчному підході до аналізу алгоритмів.

Основою третього підхіду є аналіз складових і конструкцій алгоритмів. Він представлений роботами таких вчених, як M. Halstead, T. McCabe, C. McClure, W. Harrison, S. Henry, D. Kafula, C. Myere, E. Chen та інших.

Класичним підходом до оцінки часових характеристик алгоритмів є перший, який базується на ймовірнісно-комбінаторному аналізі алгоритмів та застосовується до формальних моделей другого підходу.

Аналіз статичних властивостей алгоритмів на основі аспекту представлення не дозволяє давати оцінки часу виконання алгоритмів з урахуванням зміни цього часу програмно-апаратним середовищем. Таким чином, виникає суперечність між методами оцінки часових характеристик окремого алгоритму і можливостями зміни цих характеристик під час його виконання в сучасних програмно-апаратних середовищах.

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

Окремо відзначимо роботи, пов'язані з дослідженням ефективності окремих алгоритмів на основі аналізу результатів їх виконання. Це праці вітчизняних вчених В. С. Михалевича, О. Л. Перевозчикової, В. К. Задираки, В. Л. Волковича, О. Ф. Волошина, Г. О. Цейтліна, С. Д. Погорілого, В. В. Пасічника та інших. Проте цей напрям потребує подальшого розвитку. Зараз відсутні узагальнюючі дослідження й універсальні методи. З іншого боку, існують значні потреби прикладного програмування з аналізу алгоритмів, що фукнціонують у реальних програмно-апаратних середовищах.

Розглянута проблематика є предметом вивчення як програмної інженерії, так і інженерії якості програмного забезпечення. Одним з ключових елементів програмної інженерії є розробка алгоритмів та їх аналіз. Рекомендації об'єднаної комісії ACM та IEEE з викладання програмної інженерії (Software Engineering) та інформатики (Computer Science) включають аналіз алгоритмів у ядро знань та пропонують обов'язковим до вивчення студентами університетів.

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

Значний внесок у дослідження задач інженерії якості як найважливішої складової програмної інженерії зробили П. І. Андон, Є. М. Лавріщева, В. В. Ліпаєв, S. H. Kan, J. Tian та інші.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною наукових робіт, що ведуться на кафедрі "Комп'ютерні інформаційні технології" Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна. Результати роботи різною мірою використані у госпдоговірних науково-дослідних роботах, що виконувались відповідно до планів науково-дослідних робіт Міністерства транспорту та зв'язку України, Укрзалізниці та Придніпровської залізниці. У семи з них дисертант є науковим керівником та співавтором звітів:

- „Розробка програмного забезпечення для виконання робіт по збору, обробці та аналізу інформації щодо діяльності закладів освіти”, ДР № 107U004387. Робота виконана згідно з планом науково-дослідних та конструкторських робіт (НДКР) Міністерства транспорту України на 2004 р.;

- „Розвиток системи багатокритеріального аналізу діяльності закладів освіти”, ДР № 0107U006737. Робота виконана згідно з планами НДКР Міністерства транспорту України на 2006 та 2007 р.;

- „Розробка АРС для працівників управління ЦКадри для збору інформації та формування звітності за сучасними інформаційними технологіями”, ДР № 0103U007779. Робота виконана згідно з планами НДКР Укрзалізниці на 2002 та 2003 р.;

- „Розробка автоматизованого робочого місця з аналізу діяльності вищих навчальних закладів”, ДР № 0106U011750. Робота виконана згідно з планом НДКР Укрзалізниці на 2006 р.;

- „Формування поточних та довгострокових планів підвищення кваліфікації керівників та фахівців Придніпровської залізниці”, ДР № 0103U007780. Робота виконана згідно з планами НДКР Придніпровської залізниці на 2003 та 2004 р.;

- „Впровадження системи навчання та контролю знань кадровиків структурних підрозділів на робочих місцях”, ДР № 0107U004386. Робота виконана згідно з планом НДКР Придніпровської залізниці на 2004 р.

- „Розробка методів та засобів розшифровки швидкостемірних стрічок для вантажного, пасажирського та приміського руху”, ДР № 0107U006736. Робота виконана згідно з планами НДКР Придніпровської залізниці на 2007 та 2008 р.

Результати дисертаційної роботи використані також під час проектування і супроводу програмно-апаратних комплексів систем управління базами даних автоматизованої системи керування вантажними перевезеннями Укрзалізниці, розробка і супровід якої виконується згідно з планами Укрзалізниці на 1990-2010 р.

Мета і задачі дослідження. Метою дослідження є розвиток експериментальних методів оцінки якості та підвищення ефективності алгоритмів, призначених для функціонування в програмно-апаратних середовищах.

Для досягнення мети були поставлені та вирішені задачі дисертаційного дослідження. Необхідно було:

- розробити методи виконання комп'ютерних експериментів для оцінки ефективності алгоритмів, а також відповідне алгоритмічне та програмне забезпечення;

- виділити найбільш суттєві експлуатаційні характеристики обчислювальних алгоритмів, визначити відповідні показники ефективності, розробити методики розрахунку їх достовірних оцінок на основі комп'ютерних експериментів;

- дослідити вплив архітектури сучасних ЕОМ і її модифікацій на ефективність алгоритмів і запропонувати методику оцінки впливу окремих елементів архітектури;

- запропонувати методи оцінки ефективності алгоритмів для вкрай великих (106...1010 операторів у представленні алгоритму) і вкрай малих алгоритмів (1…5 операцій);

- розробити методи та засоби адаптації алгоритмів, що функціонують у реальних програмно-апаратних середовищах, на основі вибору алгоритмів або їх частин із застосуванням розроблених показників та методів оцінки ефективності алгоритмів. Підготувати алгоритмічне і програмне забезпечення;

- розробити формальні засоби моделювання алгоритмів, які дозволяють встановити зв'язок між різними представленнями алгоритмів та їх виконанням, а також автоматизувати процеси синтезу адаптивних алгоритмів.

Об'єкт дослідження: процес виконання алгоритмів у програмно-апаратних середовищах.

Предмет дослідження: ефективність алгоритмів під час їх виконання в програмно-апаратних середовищах з наявністю засобів неявного розпаралелювання обчислень і кешування даних.

До таких середовищ належать сучасні програмно-апаратні середовища масового використання: ПЕОМ на основі процесорів Intel і їх аналогів під управлінням багатопотокових ОС різних версій Windows і Unix при спільному виконанні системних і прикладних програм.

Методи дослідження. Результати дослідження отримані на основі відомих та апробованих методів.

На основі методів системного аналізу сформований теоретичний базис експериментальних методів дослідження алгоритмів у програмно-апаратних середовищах.

Для оцінки показників ефективності алгоритмів застосовувалися методи теорії ймовірностей і математичної статистики, зокрема метод Монте-Карло, оцінка довірчих інтервалів за критерієм Стьюдента, а також методи імітаційного моделювання, регресійного аналізу та ін.

Для формалізації алгоритмів використані методи й засоби теорії множин, граматик, запропонованих алгоритмічних і граматико-алгоритмічних структур.

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

Наукова новизна отриманих результатів. У роботі вперше отримані такі результати:

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

- розроблені методи обґрунтування, підготовки, виконання, обробки та аналізу результатів комп'ютерних експериментів з дослідження ефективності алгоритмів;

- запропоновані статистичні показники й розроблені методи оцінки часової ефективності алгоритмів. На відміну від існуючих, вони дозволяють виконувати оцінку ефективності алгоритмів при функціонуванні в сучасних програмних і апаратних середовищах;

- запропоновані показники оцінки впливу кешування даних на часову ефективність алгоритмів, розроблена методика їх визначення. Це дозволяє вирішувати завдання підвищення ефективності алгоритмів у програмно-апаратному середовищі шляхом підбору відповідної апаратної складової;

- розроблена методика вибору структур даних на основі експериментальних досліджень мікроалгорітмов обміну даними, що дає можливість конструювати структури даних з урахуванням особливостей використання кеш-пам'яті;

- розроблена методика статистичної оцінки середнього часу конвеєрного виконання команд процесора, що дозволяє враховувати особливості виконавчого пристрою при низькорівневому програмуванні;

- розроблені методи оцінки часової ефективності великих програмних систем (106...1010 операторів). Вони можуть бути використані під час вибору програмних засобів з функціонально еквівалентних, а також для контролю часової ефективності в процесі розробки та супроводу ПЗ;

- сформульовані поняття нечітко специфікованих алгоритмів і функціональної ефективності, запропоновані статистичні показники й розроблені методи оцінки функціональної ефективності алгоритмів. Виконані дослідження функціональної ефективності деяких класів алгоритмів;

- розроблена метрична модель функціонально еквівалентних алгоритмів, що дозволило застосувати методи кластеризації та структурної адаптації алгоритмів.

Отримали подальший розвиток:

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

- засоби формального представлення алгоритмів, зокрема функціонально еквівалентних алгоритмів, що реалізують нескінченну множину методів вирішення певної задачі. Це дозволило побудувати моделі адаптивних алгоритмів і застосувати їх в процесах адаптації;

- формальні моделі природних та соціальних алгоритмів. Це дає можливість використовувати знання, накопичені в теоретичному та прикладному програмуванні, для вивчення природних і штучних алгоритмів, що застосовуються у різних сферах людської діяльності.

Достовірність та обґрунтованість отриманих результатів. Коректність та обґрунтованість наукових положень, висновків та результатів базується на застосуванні апарату системного аналізу, відомих методів теорії ймовірностей та математичної статистики, методів та засобів теорії множин, формальних граматик і розпізнавання образів, застосованих для вирішення коректно поставлених задач.

Обґрунтованість наукових положень і достовірність отриманих результатів підтверджується:

- апробацією розроблених методів на відомих та добре вивчених класах алгоритмів;

- багатократним виконанням комп'ютерних експериментів з аналізом узгодженості з відомими теоретичними результатами інших дослідників та накопиченим практичним досвідом;

- результатами практичного застосування під час вибору ефективних алгоритмів та їх частин із числа альтернативних у системах адаптації алгоритмів;

- позитивним досвідом застосування результатів роботи у проектах, виконаних під науковим керівництвом автора.

Достовірність оцінок ефективності алгоритмів забезпечується:

- застосуванням засобів вимірювань з необхідною точністю;

- обробкою експериментальних даних визнаними методами;

- наявністю отриманих статистичних оцінок точності.

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

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

Розроблені методи:

- дозволяють вирішувати задачу підбору раціональної конфігурації комп'ютера для конкретних алгоритмів і навпаки, підбору раціонального алгоритму для конкретного обчислювального середовища (технічних та системних програмних засобів);

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

Методологічна складова дисертаційного дослідження є суттєвим доповненням до теорії аналізу алгоритмів і може бути використана в процесі навчання студентів за напрямами "Програмна інженерія" і "Інформатика", апробована автором під час викладання ряду дисциплін.

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

Особистий внесок здобувача. Основні результати дисертаційної роботи отримані автором особисто.

У наукових працях, виданих у співавторстві, дисертанту належать: [3, 5] - апробація запропонованих методів та алгоритмів, [4] - постановка задачі відновлення граматик засобами формальних структур, [6] - формальні засоби перетворення ієрархічних структур у реляційні, методологія підвищення функціональної ефективності автоматизованої системи, [7] - методологія адаптації алгоритмів навчання нейромереж, [10] - граматико-алгоритмічна модель множини алгоритмів сортування, [14] - постановка задачі, концепція розробки автоматизованої системи, [15] - показники якості моделей робочого навантаження СКБД, [18] - оцінка ефективності організації обчислень, [22] - постановка задачі, метод структурної адаптації алгоритмів стискання даних, оцінка функціональної ефективності адаптованого алгоритму, [23] - концепція формальних алгоритмічних структур та структурні моделі алгоритмів, [24] - формальні зв'язки між алгоритмами та представлення процесу розробки ПЗ як послідовності реструктуризацій алгоритмів, [42, 44] - постановка задачі, [43] - виокремлення єдиних властивостей процедур, алгоритмів, модулів, класів. У спільній монографії [1] матеріали всіх глав написані за участю дисертанта, а глави 5, 6 - в основному дисертантом.

Апробація результатів дисертації. Результати дисертаційної роботи представлені на міжнародних наукових і науково-практичних конференціях: УкрПРОГ (Київ, 2002, 2004, 2006, 2008), "Теоретичні та прикладні аспекти розробки програмних систем" (TAAPSD, Київ, 2004, 2005, 2006; Бердянськ, 2007; Київ - Тернопіль, 2008; Київ, 2009), "Комп'ютерні науки та інформаційні технології" (CSIT, Уфа, 2001; Патрас (Греція), 2002), "Інформаційні технології в освіті" (ІTO, Москва, 2001, 2002), "Проблеми і прийняття рішень в умовах невизначеності" (PDMU, Київ, 2001; Київ - Канів, 2002; Тернопіль, 2004; Бердянськ, 2005), "Штучний інтелект" (Кацивелі (Крим), 2002, 2008; Дивногорське (Росія), 2007, 2009), "Комп'ютерне моделювання" (Дніпродзержинськ, 2000, 2001), "Проблеми математичного моделювання" (Дніпродзержинськ, 2002, 2003, 2004, 2005, 2006, 2007), "Автоматика" (Одеса, 2001; Донецьк, 2002), "Теоретичні та прикладні питання сучасних інформаційних технологій" (Улан-Уде, 2001, 2002), "Інтернет - наука - освіта" (Вінниця, 2000), "Інформаційна техніка і електромеханіка на рубежі XXI століття" (Луганськ, 2001), "Інформаційні технології на виробництві та в освіті" (Хмельницький, 2002), "Комп'ютерне моделювання та інформаційні технології в науці, економіці та освіті" (Кривий Ріг, 2002; Черкаси, 2003), "Проблеми економіки транспорту" (Дніпропетровськ, 2002, 2003, 2005, 2009), "Сучасні інформаційні та електронні технології" (Одеса, 2002), "Проблеми та перспективи розвитку залізничного транспорту" (Дніпропетровськ, 2005), "Сучасні інформаційні технології на транспорті, в промисловості та освіті" (Дніпропетровськ, 2007, 2008, 2009), "Комп'ютерне моделювання та інтелектуальні системи" (Запоріжжя, 2007).

Результати роботи доповідались також на наукових семінарах "Проблеми управління та інформатики" (ДДТУЗТ, Дніпропетровськ, 2000; ДНТУЗТ, Дніпропетровськ, 2006), "Інформаційні технології та автоматизовані системи на транспорті" (Транспортна академія України, Дніпропетровськ, 2005) і науковому семінарі інституту програмних систем (Київ, 2001).

У повному обсязі матеріали дисертаційного дослідження доповідалися на республіканському семінарі "Програмологія та її застосування" на базі кафедри "Теорії та технології програмування" Київського національного університету імені Тараса Шевченка, науковому семінарі відділу теорії комп'ютерних обчислень Інституту програмних систем НАН України, міжкафедральному семінарі факультету "Технічна кібернетика" Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна, науковому семінарі відділу автоматизації програмування Інституту кібернетики НАН України, науково-методичному семінарі факультету кібернетики Київського національного університету імені Тараса Шевченка, науково-методичному семінарі кафедри "Програмне забезпечення ЕОМ" Харківського національного університету радіоелектроніки та міжкафедральному семінарі факультету кібернетики Київського національного університету імені Тараса Шевченка.

Публікації. За темою дисертації видано дві монографії. У журналах, рекомендованих ВАК для публікації результатів дисертацій, опубліковано 23 статті: «Проблеми програмування» - 9, «Штучний інтелект» - 5, «Математичні машини і системи» - 4, «Кібернетика і системний аналіз» - 2, «Наукові вісті КПІ» - 1, «Вісник Дніпропетровського національного університету залізничного транспорту» - 2, з них 11 одноосібно. Праць і тез доповідей наукових конференцій - 41.

Структура та обсяг роботи. Дисертаційна робота складається із вступу, семи розділів, висновків, трьох додатків і списку використаної літератури з 261 найменувань. Загальний обсяг роботи - 357 сторінка, 49 рисунків (1 на окремій сторінці), 35 таблиць (2 з них на 5 окремих сторінках), основний текст роботи викладено на 275 сторінках.

Зміст роботи

Вступ дисертаційної роботи містить: обґрунтування її актуальності, інформацію про зв'язок з науковими програмами, мету і завдання дослідження, сформульовані об'єкт і предмет дослідження, застосовані методи дослідження, характеристику наукової новизни і практичного значення отриманих результатів, інформацію про особистий внесок автора, апробації результатів і публікації.

У першому розділі наведено огляд літератури та виконано аналіз наукових досягнень та наявних проблем у теорії аналізу, формалізації і адаптації алгоритмів.

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

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

З метою виявлення суттєвої залежності часу виконання алгоритмів від архітектури ЕОМ було проведено комп'ютерний експеримент 1. На двох ПЕОМ з різними процесорами Intel виконувалися алгоритми сортування. На вхід подавалися однакові масиви випадкових чисел, що містилися в оперативній пам'яті. Виконання здійснювалося під управлінням ОС Windows, усі системні й прикладні процеси, крім життєво необхідних для ОС, були зупинені.

У ряді випадків стійко повторювалася ситуація, коли один алгоритм виконувався швидше за інший на одному комп'ютері й повільніше на іншому. Також виявлені випадки, коли на одній ПЕОМ алгоритми з більшою кількістю команд виконувалися швидше, ніж з меншою за однакових вхідних даних і однакових інших умов.

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

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

У другому розділі описані розроблені формальні моделі алгоритмів. На основі формальних структур, які задаються впорядкованою трійкою з множиною сигнатурою та аксіоматикою :

,	(1)

запропоновані моделі алгоритмічних структур (АС):

,	(2)

де - скінченна множина утворюючих алгоритмів, які задані на носії, у загальному випадку неоднорідній множині , X(A), Y(A) - множини визначень та значень алгоритму A.

Множина може складатися з базових алгоритмів одного або декількох виконавців. Якщо множина утворюючих алгоритмів збігається з множиною базових алгоритмів деякого виконавця, то така алгоритмічна структура є базовою алгоритмічною структурою.

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

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

У рамках алгоритмічних структур визначені дві моделі. Модель, пов'язана з аспектом представлення алгоритму, - структура алгоритму або структурна модель і модель, пов'язана з аспектом виконання алгоритму, - шляхова модель. Структурою алгоритму є - послідовний запис утворюючих алгоритмів, де "" - довільна операція сигнатури . Шляхова модель - це множина всіх можливих шляхів алгоритму.

Ці моделі та їх міжмодельні перетворення дозволяють відстежити алгоритми від розробки до виконання, розглядати процеси перетворень алгоритмів як послідовність реструктуризацій, пов'язати представлення алгоритмів з їх виконанням у різних середовищах. На прикладах показані можливості структурного моделювання алгоритмів, зокрема рекурсивних алгоритмів.

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

Третій розділ є основним. Тут вводяться статистичні показники часової ефективності алгоритмів, які враховують усі фактори, які впливають на час їх виконання. Такими факторами є вхідні дані, програмно-апаратні середовища підготовки й виконання алгоритмів.

Часова ефективність алгоритму визначається функцією

	(3)

де - обсяг, t - тип, - значення вхідних даних відповідно, - програмне середовище створення та функціонування *. exe файла, - архітектура ЕОМ.

За наявності декількох функціонально еквівалентних алгоритмів слід порівняти функції

	(4)

Для порівняння часової ефективності двох алгоритмів у деякій цілком визначеній області дослідження та експлуатації необхідно встановити:

- наскільки в середньому один з алгоритмів перевершує інший;

- чи у всій області дослідження спостерігається перевага одного алгоритму, якщо ні - то як співвідносяться розміри областей переваги кожного алгоритму;

- якою буде перевага одного з алгоритмів за межами досліджень (за обсягом даних).

Нехай - множина можливих значень обсягу даних, - множина можливих типів даних, - множина можливих значень даних, - множина можливих програмних середовищ, - множина архітектур ЕОМ, на яких можлива реалізація алгоритмів. Тоді для порівняння часової ефективності альтернативних обчислювальних алгоритмів необхідно визначити такі показники:

- ступінь переваги одного (i-го) алгоритму над іншим (j-м) на обмежених множинах, що є підмножинами зазначених вище множин як функціонал:

	(5)

де N - загальна кількість доданків, - ступінь переваги i-го алгоритму над j-м в точці, яка визначається як

,	(6)

де - час виконання i-го алгоритму;

- область переваги:

	(7)

де - ознака переваги i-го алгоритму над j-м у точці

	(8)

- перевагу за межами:

.	(9)

Вважаючи, що множини - дискретні й обмежені, їх можна відобразити на множину натуральних чисел = {1,2, ... }, ... ={1,2, ... } відповідно, при цьому:

.

Оцінку показників виконуємо за допомогою методу Монте-Карло, для чого перейдемо від суми до інтегрування ступінчастої функції.

В області =[1…+1][1…+1]…[1…+1] визначимо:

,	(10)

де , і замінимо суму інтегралом:

	(11)

Якщо або є безперервними, відповідні суми в (5), (7) і (9) спочатку замінюються інтегралами і відпадає необхідність у переході до (10).

В області виберемо випадковим чином точок Р= і обчислимо значення випадкової величини . Інтеграл (11) при цьому є математичним сподіванням випадкової величини , тобто .

Як відомо, оцінкою математичного сподівання є величина

.	(12)

S- оцінку ступеня переваги i-го алгоритму над j-м (5) визначимо як

.	(13)

Проводиться оцінка довірчих інтервалів:

.	(14)

Значення визначаються експериментально.

Оцінка R- показника розраховується аналогічно оцінці S- показника. Для оцінки L- показника застосовуються методи регресійного аналізу.

З метою перевірки порівнянності запропонованих показників часової ефективності алгоритмів з відомими результатами виконано три комп'ютерних експерименти.

В експерименті 2 дослідження виконувалося на восьми відомих алгоритмах сортування, які наведені в роботі Н. Вірта "Алгоритми + структури даних = програма". На одній ПЕОМ в однаковому і стабільному програмному середовищі виконано 44-54 реалізації кожного алгоритму з елементами масивів та 12 різними типами даних. Результати показали значну перевагу алгоритмів швидкого і пірамідального сортування над іншими алгоритмами (значення всіх S-R-L- показників близько 100 %), що повністю узгоджується з відомими даними.Водночас відзначено незначну перевагу швидкого сортування над пірамідальним () майже в усій області дослідження ().

В експерименті 3 ці самі алгоритми досліджувалися при , експериментальній базі з чотирьох ПЕОМ різних модифікацій і двома модифікаціями середовища формування і виконання *.exe файла. В експерименті 4, на відміну від попереднього, при однаковому програмному середовищі досліджувалося 12 модифікацій комп'ютерів з процесорами Intel. Визначені S-R-L- показники часової ефективності алгоритмів частково наведені у табл. 1. Результати експериментів 2, 3 та 4 досить добре узгоджуються між собою - відповідні показники в основному не виходять за довірчі інтервали і практично не розходяться більше, ніж на 10 %.

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

Таблиця 1 S-R-L- показники часової ефективності алгоритмів сортування

Алгоритми сортування
Швидке сортування	Х	-9	100 100	100 100	100 100
Пірамідальне сортування	9	Х	100 100	100 100	100 100
Прямим включенням	0,0 -100	0,0 -100	Х	33	22
Шейкер - сортування	0,0 -100	0,0 -100	-33	Х	-11
Простим вибором	0,0 -100	0,0 -100	-22	11	Х

Порівнюючи ступінь переваги алгоритму швидкого сортування над алгоритмами з обчислювальною складністю в досліджуваній області, яка склала 98...99,9 %, і ступінь переваги паралельно виконуваних алгоритмів у кращому випадку над послідовно виконуваними, що для 30 ЕОМ (процесорів) становить 96 %, черговий раз переконуємося в пріоритетній необхідності якісної алгоритмізації. Це, у свою чергу, передбачає наявність відповідних критеріїв, показників і оцінок ефективності, чому і присвячений даний розділ.

У четвертому розділі визначено поняття нечітко специфікованих алгоритмів, для яких запропоновані показники функціональної ефективності.

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

У роботі проаналізовано два класи алгоритмів: стиснення даних та кластеризації. На основі аналізу виділено основні джерела нечіткості:

- заздалегідь невідомі особливості вхідних даних;

- множинність показників якості результатів;

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

Визначення 1. Специфікація алгоритму є нечіткою, якщо вона задає відображення із X в Y і при цьому кожному елементу з X може ставитись у відповідність будь-який елемент із множини , який задовольняє користувача різною мірою.

Нечітка специфікація допускає неоднозначність. Принциповим є те, що цю неоднозначність не можна усунути на етапі специфікації. Результати виконання алгоритму не завжди будуть задовольняти користувача. Кардинальна відмінність нечіткої специфікації від неповної в тому, що нечіткість не можна усунути.

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

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

Пропонується два показники функціональної ефективності алгоритмів, за формою узгоджених з показниками часової ефективності:

- ступінь переваги одного (i-го) алгоритму над іншим (j-м) на обмеженій множині :

,	(15)

де N - загальна кількість доданків, - оцінка якості отриманих алгоритмом результатів, - функція, яка реалізує i-й алгоритм, наприклад розмір стисненого файла;

- область переваги:

.	(16)

S-R- оцінки показників функціональної ефективності та їх довірчі інтервали визначаються аналогічно відповідним оцінками часової ефективності.

З метою дослідження можливості застосування показників функціональної ефективності алгоритмів у задачах вибору з ряду альтернативних для вирішення конкретних завдань виконано експеримент 6. На вибірці з 14 000 файлів загальним обсягом 4Гб форматів *.doc, *.xls, *.bmp, *.tif досліджувалася функціональна ефективність архіваторів. Встановлено, що при стисненні файлів формату *.doc і *.xls явну перевагу має архіватор 7-Zip (стискає файли *.doc на 10 ... 20 % краще за інших, файли *.xls - на 7 ... 13 %), для файлів * .bmp архіватори WinRAR, WinACE, 7-Zip приблизно рівноцінні й кращі за інших на 5...10 %, файли *.tif всі архіватори стискають приблизно однаково.

Для оцінки можливостей вибору алгоритмів на основі показників функціональної ефективності з урахуванням структури та обсягу даних виконано експеримент 7. Його можна вважати уточненням попереднього. Доповнюючи методику попереднього експерименту, під час стиснення файлів формату MS Word враховувався різний ступінь заповнення файлів такими складовими, як текст, вставлені об'єкти, таблиці, рисунки та рисунки, створені засобами MS Word. Встановлено, що архіватор 7-Zip 3.12 має перевагу над іншими архіваторами за S-оцінкою. При цьому вміст файлів майже не позначається на його перевазі. Лише наявність таблиць та рисунків MS Word деякою мірою знижує цю перевагу, однак у межах довірчих інтервалів.

Виконані експерименти показують можливості застосування запропонованих S-R- показників функціональної ефективності для розв'язання задачі вибору раціональних алгоритмів у процесі розробки програмних засобів.

У п'ятому розділі подані дослідження часової ефективності алгоритмів. Мова йде про спеціалізацію оцінок часової ефективності алгоритмів при всіх фіксованих чинниках впливу на час виконання алгоритмів (3), за винятком одного з елементів архітектури ЕОМ - кеш-пам'яті.

Час виконання операції обробки даних мов програмування визначається таким чином:

	(17)

де - час виконання операції мови програмування, - час виконання відповідної (них) команди процесора, - час виконання операції обробки посилання, - час доступу до позиції операндів, - час доступу до даних операндів.

У процесорах Intel доступ до даних виконується через кеш-пам'ять, і, якщо дані відсутні в кеші, необхідний деякий час на пересилання даних з оперативної пам'яті до кешу.

Суть методики вимірювання часу доступу до позиції та до даних така. Вимірюється час виконання циклу з досить великою кількістю повторень (=5... 100 млн), що забезпечує високу точність вимірювань і практично знімає вплив вимірювальної систем. Для очищення кешу перед циклом виконується інтенсивна робота з великим стороннім масивом, кеш заповнюється його елементами. Всередині циклу міститься послідовність команд для стабілізації конвеєра (виключення затримок) і команд, що досліджуються. З дев'яти паралельних вимірювань часу виконання циклу вибиралося найменше.

Метою експерименту 8 була оцінка часу доступу до позиції та до даних. Різниця в часі виконання циклу з оператором присвоювання структурованих даних (елемента масиву) і неструктурованих дозволяє визначити час доступу до позиції.

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

У циклі перебувала лише одна операція для дослідження, а саме: i:= x [i]. При цьому по-різному формувався масив х. У першому випадку . При цьому в циклі постійно йшло звернення до одного елемента масиву, який після перших проходів циклу вже потрапляв у кеш. Можна вважати, що перший випадок відповідає ситуації, коли структуровані дані постійно містяться в кеші. Виміряний час виконання циклу позначимо .

У другому випадку . При цьому в циклі виконувалася послідовна вибірка елементів масиву. Якщо час виконання цього циклу позначити , то - мінімальний час доступу до елементів масиву.

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

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

Експеримент виконувався на восьми комп'ютерах з процесорами Intel і AMD різних модифікацій.

Встановлений час доступу до позиції знаходився в межах 0...4 такти процесора, час доступу до даних - 130...360 тактів. Враховуючи той факт, що час доступу до даних не можна оцінити апріорно через складність архітектурних рішень, множинність і частоту їх модифікацій, результати експерименту ще раз переконують в необхідності статистичних оцінок часової ефективності алгоритмів.

Для оцінки часу доступу до динамічних даних виконано експеримент 9. На тій самій експериментальній базі визначений час доступу до елемента даних становить 0...325 тактів при чотирибайтових адресах. Для доступу до елемента в динамічному ланцюжку потрібно багаторазове виконання операції доступу до даних для всіх проміжних елементів. У найгіршому випадку час доступу до даних може на декілька порядків перевищувати час обробки даних.

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

Якщо попередні експерименти цього розділу стосувалися одиничних операцій доступу до даних, то наступні експерименти спрямовані на дослідження алгоритмів зі значною часткою операцій доступу до даних. Досліджувалися ті самі вісім алгоритмів сортування.

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

,

з визначеними коефіцієнтами та тим самим способом.

Рис. 1. Залежність часу сортування від кількості елементів масиву

Для оцінки чутливості алгоритмів до кешування даних (ефект нестатку кешу) запропоновано два показники:

- - на скільки (на яку частину), в середньому, покращиться час виконання алгоритму при подвоєнні кешу, якщо обсяг оброблюваних даних перебуває в межах ;

- - на скільки мінімально покращиться час виконання алгоритму при подвоєнні кешу, якщо обсяг оброблюваних даних перевершує .

Показано, що ці показники є спеціалізацією запропонованого в третьому розділі S-показника часової ефективності алгоритмів.

В експерименті 12 на алгоритмах сортування виконана апробація методики оцінки показників ефекту нестатку кешу. Аналіз результатів показав, що для ЕОМ з великим розміром кешу показники і нижчі, ніж з малим, тобто подвоєння розмірів кешу в цьому випадку менш ефективно. Теоретично цього слід було очікувати, тому що при збільшенні розміру кешу в ньому міститься більше даних і ймовірність промаху знижується. Проте цю залежність можна розглядати лише як тенденцію. Встановлено також, що алгоритми по-різному реагують на подвоєння кешу: деякі алгоритми значно прискорюються, деякі практично на таку зміну не реагують.

Висунуто гіпотезу про те, що в разі збільшенні тривалості операцій обробки даних та збереження порядку доступу до даних слід очікувати зниження показників і , та навпаки: зі збільшенням розмірів елементарних даних (підвищення частки операцій доступу до даних) показники і повинні збільшуватися. Ця гіпотеза підтверджена теоретичними дослідженнями й експериментально (експерименти 13 та 14). Таким чином показано, що в деяких випадках для визначення граничних статистичних оцінок не обов'язково проводити комп'ютерні експерименти, а можна скористатися результатами раніше проведених.

Усі експерименти дисертаційного дослідження виконані у багатозадачній ОС Windows різних версій. Тільки експерименти 12-14 - у MS DOS. Передбачалося, що в багатозадачній ОС кеш різною мірою використовується всіма задачами і прикладному алгоритму (реалізованому в деякій програмі-процесі) буде виділятися лише частка кешу даних, розмір якої буде динамічно змінюватися. Нестаток кешу буде посилюватися, і тим більше, чим вище показники і . Показники, отримані за результатами експериментів у однозадачній ОС, можна розглядати як нижню границю відповідних оцінок.

Для оцінки ступеня впливу багатозадачних ОС на показники і виконаний експеримент 15. Порівняння залежностей часу виконання алгоритмів сортування від обсягів даних в ОС Windows і MS DOS показало, що при достатньому розмірі кешу залежності завжди практично збігаються. У разі нестачі кешу час сортування в ОС Windows завжди більше, ніж в MS DOS і залежності в ОС Windows можуть мати суттєві спотворення. Отже, показники і доцільно визначати в однозадачних ОС.

Ще одним архітектурним рішенням для прискорення обчислень апаратними засобами є багатоядерність процесорів. Метою наступного експерименту 16 було дослідження можливості оцінки впливу кешування даних на часову ефективність алгоритмів у разі їх виконанні на багатоядерних процесорах (без планування розпаралелювання). На двох ядрах процесора виконувався однаковий експеримент з визначення часу сортування даних восьмома алгоритмами з покроковою зміною обсягів даних.

Якщо обчислення на одному ядрі (при другому незавантаженому) тривало 67 годин, то при одночасному виконанні - на одному ядрі 89 годин, на другому - 247 годин. Зниження ефективності алгоритмів пояснюється конкуренцією за кеш-пам'ять, необхідністю додаткових завантажень даних, витіснених конкуруючим процесом, у кеш. Попутно експериментально встановлено нерівноправне обслуговування ядер процесора кеш-пам'яттю.

Особливості оцінки часової ефективності гранично малих (одна команда процесора) і досить великих (умовно більше 106 складових) алгоритмів розглянуті в шостому розділі.

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

Для оцінки часу виконання команд обробки даних процесора Intel з урахуванням конвеєризації проведений експеримент 17. Методика експерименту близька до експерименту 8. Вимірювався час виконання циклу, у який по черзі вставлялося 30...80 повторень досліджуваної команди. Результати експерименту свідчать про те, що збільшення кількості команд у циклі не завжди приводить до збільшення часу його виконання. Для деяких команд збільшення кількості на 3-6 не змінює час виконання циклу, наступна додана команда цей час стрімко збільшує. У окремих випадках додавання однієї команди призводить до зниження часу виконання циклу, однак завжди спостерігається певна циклічність. Типові приклади наведені на рис. 2.

Для оцінки часу виконання команди визначалася параметрична періодична функція залежності часу виконання циклу від кількості вставлених досліджуваних команд. Час виконання команди в тактах процесора визначався як

	(18)

де - кількість проходів циклу, - на скільки змінена кількість команд за період, - тактова частота процесора, - середні зміни за період по осях (кількість повторень команд) та (час виконання циклу) при випробуваннях:

.	(19)

Для ряду команд отримані оцінки часу виконання команд з довірчими інтервалами. Наприклад, операція пересилки без затримок конвеєра виконувалася на восьми комп'ютерах експериментальної бази за половину, третину або четвертину такту.

Рис. 2. Залежність часу виконання циклу від кратності досліджуваних команд

Для оцінки впливу багатозадачності ОС на чистоту експерименту виконано подібний експеримент 18 у MS DOS. Аналіз результатів показує, що отримані значення експериментів 17 та 18 добре корелюють між собою, що свідчить про можливість отримання вказаних оцінок у більш доступних середовищах багатозадачних ОС.

Складність оцінки часової ефективності макроалгоритмів, реалізацією яких є прикладні та системні програмні засоби, наприклад, такі як Windows, MS Word, зумовлена цілою низкою причин. До залежності від вхідних даних та програмно-апаратних середовищ функціонування додаються такі чинники, як багатофункціональність, інтегрованість з ОС та іншими ПЗ, розподіленість коду. Мабуть, тому, відсутні навіть підходи і спроби оцінки часової ефективності ПЗ. А такі оцінки необхідні для вирішення задач вибору ПЗ, моніторингу якості у процесі їх розробки та інших потреб.

Запропоновано такі методи оцінки часової ефективності ПС.

Метод S-R- оцінок. Метод ґрунтується на статистичних дослідженнях алгоритмів методом Монте-Карло. Оцінюється ступінь і область переваги однієї ПЗ над іншими. Метод досить ефективний, якщо ПС використовує один або декілька "важких", з точки зору часу виконання, обчислювальних алгоритмів. Основна ідея методу полягає в приведенні сукупності алгоритмів до єдиного алгоритму послідовного виконання всіх "важких" функцій з подальшим застосуванням методології S-R- оцінок часової ефективності алгоритмів, запропонованих у третьому розділі.

...