Алгоритмізація завдань
На першому етапі розробки комплексів програм АСУ визначають вимоги, виконання яких забезпечує вирішення поставлених завдань. Основними характеристиками є час і вартість обробки інформації, ймовірність помилки, допустимі обсяги пам'яті, неминучість виконання основних функцій і т.п. Вимоги до системи містяться в системних специфікаціях, які відображають передбачувану реалізацію системи з допомогою ЕОМ. Специфікації є основоположним документом у процесі розробки системи. Точність і докладність складання специфікацій визначають ймовірність виникнення помилки на подальших етапах розробки. Більшість сучасних методів створення програмного забезпечення допускає появу помилок у специфікаціях проекту, однак ціна виявлення та коригування помилок зростає в міру наближення розробки до завершення. У більшості випадків помилки в системі - результат неповних або суперечливих специфікацій (60-70% помилок). У зв'язку з цим виникає необхідність розробки і використання мов і формалізованих методів розробки специфікацій, їх аналізу і контролю.
В даний час відомий ряд методів формалізації визначення специфікацій. Першим кроком у напрямку формалізації процесу визначення специфікацій стало створення HOS-методології, заснованої на використанні аксіом програмного забезпечення вищого рівня, які визначають допустимі взаємодії між процедурами завдання. Ці аксіоми передбачають введення деяких обмежень на використання процедур. Наприклад, не допускаються ситуації, коли процедура контролює сама себе, тобто виключається використання рекурсії, процедура не може управляти простором своїх вхідних даних і т.п.
Ефективним засобом формалізації процесу визначення специфікацій є система PSL / PSA, яка включає мову визначення завдань (PSL) і аналізатор визначення завдань (PSA).
Мова визначення завдань призначений для відображення функціональних вимог до ресурсів. Мова містить набір засобів, що дозволяють визначати об'єкти системи, їх властивості та взаємозв'язки.
Аналізатор визначення завдань здійснює випробування пропозицій мовою PSL. Аналізатор генерує базу даних, що відображає системні вимоги, і здійснює перевірку послідовності і аналіз повноти даних.
Система PSL / PSA дозволяє отримати формалізоване уявлення проблеми, документування системних вимог в однаковій формі, забезпечує виявлення помилок, зумовлених неповнотою інформації.
Система структурного аналізу і проектування SADT представляє собою графічну систему, призначену для аналізу і проектування систем. Графічний мову системи SADT - це ієрархічний структурований набір діаграм, причому кожен блок діаграми розкривається більш детально за допомогою іншої діаграми. Таким чином, завдання видається все з більшим ступенем деталізації у міру розробки проекту. Система SADT дозволяє підвищити якість рішень на ранніх етапах проектування на основі легко доступних засобів контролю. Однак система не є автоматизованою.
Система SREM, використовувана для автоматизації аналізу вимог, включає язи до визначення вимог RSL для встановлення зв'язку між об'єктами. Перевірка послідовності пропозицій мовою RSL здійснюється за допомогою процесора REVS. Система виконує наступні операції: розробку вимог, що включає дескриптори даних та етапи їх розробки; розробку детальних проектів; моделювання окремих аспектів проектних рішень з урахуванням прийнятих припущень; перевірку користувачем вимог, що пред'являються до системи.
Система структурного проектування являє собою неавтоматизованих систему, використання якої забезпечує створення докладного проекту системи. Система складається з наступних рівнів: підсистема, процес (частина підсистеми, що представляє окрему функцію); робота (виконувана програма або крок завдання); модуль (частина роботи). Структурне проектування виконується на рівні процесу або роботи. Документація включає базисну схему кожного модуля і його повний опис за встановленою формою. Функція модуля описується так, щоб можна було здійснити його кодування без використання додаткової документації.
Наведені засоби визначення специфікацій дозволяють систематизувати процес формування вимог до системи, автоматизувати процес їх контролю та знизити ймовірність виникнення помилок, викликаних некоректністю або неповнотою обліку умов вирішуваних завдань управління.
Другим етапом процесу розробки програмного забезпечення є складання алгоритму рішення поставленої задачі.
При розробці алгоритму рішення завдання перш за все вирішуються такі питання:
а) чи варто використовувати імітаційне моделювання або який-небудь з методів оптимізації;
б) чи варто враховувати випадковий характер змінних чи процесів або використовувати детермінований підхід;
в) чи слід враховувати нелінійність деяких співвідношень або достатньо обмежитися їх лінійною апроксимацією;
г) чи можна використовувати існуючі методи рішення або потрібно розробити новий алгоритм;
д) чи припустимо в даному конкретному випадку використання відомих оптимізаційних методів або необхідно розробити евристичний алгоритм.
При вирішенні наведених питань виникає необхідність оцінки якості алгоритмів. Існує багато критеріїв. Найчастіше використовується критерій складності алгоритму, який характеризує час, що витрачається алгоритмом на одержання рішення в залежності від розміру задачі. При цьому під розміром завдання розуміється деяке число, яке виражає міру кількості вхідних або вихідних даних.
Межа часової складності при збільшенні розміру задачі називається асимптотичної тимчасової складністю. Аналогічно визначається емкостная складність і асимптотична емкостная складність. Саме асимптотична складність алгоритму визначає результаті розмір завдань, які можна вирішити цим алгоритмом. Якщо алгоритм обробляє входи розміру п за час з n 2, де с - деяка постійна, то говорять, що часова складність цього алгоритму є О (п 2) (читається "порядку n 2"). Точніше, кажуть, що невід'ємна функцiя g (n) є O (f (n)), якщо існує така постійна с, що g (n) ≤ cf (n) для всіх, окрім кінцевого (можливо порожнього) безлічі невід'ємних значень п.
Нехай дано п'ять алгоритмів А 1 - A 5 (табл. 1). Під тимчасової складністю тут розуміється число одиниць часу, необхідного для обробки входу розміру п. У табл. 5.1 наведені розміри завдань, які можна вирішити за 1 с, 1 хв і 1 год кожним з цих п'яти алгоритмів. Якщо за основу для порівняння взяти 1 хв, то, замінюючи алгоритм А 4 алгоритмом А 3, можна вирішити завдання в 6 разів більшу, а замінюючи А 4 на А 2, можна вирішити завдання, більшу у 125 разів. Якщо за основу для порівняння взяти 1 год, то відмінність алгоритмів стає ще значніше. Звідси можна зробити висновок, що асимптотична складність алгоритму служить важливим заходом його якості, причому такою мірою, яка набуває все більшого значення з збільшенням розміру обчислень.
Таблиця 1
Складність алгоритму визначає також те збільшення розміру задачі, якого можна досягти за збільшенням швидкості машини. Збільшення швидкості обчислень в 10 разів збільшує розмір задачі, яку можна вирішити, для алгоритму А 5 тільки на 3, тоді як для алгоритму А 3 - більш ніж утричі. Однак алгоритм з постійно зростаючою складністю може виявитися кращим для задач з малим розміром. Наприклад, якщо тимчасові складності алгоритмів А 1 - A 5 дорівнюють відповідно 1000 n, 100 n, log n, 10 n 2, n 3 і 2 n, то алгоритм А 5 буде найкращим для задач розміру 2 ≤ п ≤ 9, А 3 - для задач розміру 10 ≤ п ≤ 58, А 2 - при 59 ≤ n ≤ 1024, a A 1 - n> 1024.
Для того щоб показати, що не існує алгоритму, що виконує рішення задачі менш ніж за певний час, необхідне точне визначення того, що є алгоритм. Уточнення понять алгоритму і його складності вимагає прив'язки до деякої конкретної схемою обчислень. Звичайно як такої схеми розглядається машина Тюринга або так звана адресна машина. Проте можна прийняти модель, більш близьку до реального ходу обчислень в оперативній пам'яті машини з одним процесором, і вважати, що обчислення реалізуються програмою, написаною на деякому спрощенні (підмножині) мови АЛГОЛ.
На початкових етапах розвитку теорії складності в ній найчастіше розглядалися завдання, на які можна дати лише одну з двох відповідей: ТАК чи НІ. Наприклад, класична "сложностная" постановка відомої задачі про ранці (з обмеженням у вигляді рівності) полягатиме у з'ясуванні того, чи існують для заданих чисел a j, j = 1,2, ..., n і b значення булевих змінних x j , що задовольняють обмеження
(1)
Звичайна ж формулювання задачі про ранці полягає в максимізації суми
(2)
за умови (1). Проте легко помітити, що відповіді на послідовність завдань типу "чи існує набір булевих змінних x j, що задовольняють (1), такий, що z = k при k = 0, 1,2, ... "дадуть рішення задачі про ранці у звичній формулюванні. При цьому під завданням розуміється весь клас однотипних питань, що розрізняються вхідними даними. Наприклад, у задачі (1), (2) вхід являє собою набір { k, {а j}, {з j}, b}, так що завдання про ранці зводиться до вирішення питання, "чи існує значення цільової функції, рівне k, в ситуації, описуваної іншими вхідними даними". Конкретний набір вихідних даних визначає реалізацію завдання .
Позначимо завдання через П, її реалізацію - через π. Під розміром реалізації будемо розуміти кількість символів, необхідних для запису вхідних даних цієї реалізації. Розмір реалізації π буде позначатися . Під часом рішення t π реалізації π розуміється сума часів виконання всіх команд програми.
Введемо поняття класу задач Р, розв'язаних за поліноміальний час. Цей клас складається з усіх завдань П, що володіють наступною властивістю: для будь- існує АЛГОЛ-програма u П і поліном f П (·), такі, що будь-яка реалізація u П за час t π (u П) ≤ f П (
). Прикладами завдань з класу Р є задачі знаходження найкоротшого шляху між двома вершинами графа, мінімального розрізу в мережі, мінімального дерева.
Загальноприйнято, що якщо завдання не можна вирішити швидше, ніж за експоненційний час, то її слід розглядати як важко вирішити. Такі завдання утворюють клас задач, недетермінованим чином розв'язаних за поліноміальний час (NP-клас). Для визначення NP класу необхідно розширити мову, додавши до нього нову команду CHOOSE (x). Ця команда додає недетермінованим чином змінної х значення О або 1. Розширений за рахунок цієї команди мова назвемо N-АЛГОЛ. Будемо говорити, що програма на N-Алгол (N-програма) видає на деяку реалізацію завдання відповідь ТАК, якщо N-програма видає відповідь ТАК при деякій комбінації значень, що реалізувалися при виконанні команд CHOOSE (x). У цьому випадку під часом виконання N-програми будемо розуміти мінімальний час для всіх детермінованих програм, отриманих шляхом заміни CHOOSE (x) нулями або одиницями, які видають відповідь ТАК. Якщо N-програма дає відповідь НІ, то час її виконання для даної реалізації не визначається.
Зазначимо, що наведене визначення часу для реалізації з відповіддю ТАК є значною мірою умовним, так як будь-яка реальна схема обчислень є детермінованою і для неї необхідно переглянути всі послідовності реалізації CHOOSE (x), щоб визначити, видає чи хоч одна з них відповідь ТАК. Це потребує часу, що дорівнює сумі часів, необхідних для кожного набору реалізацій.
Визначимо клас NP як підклас всіх таких завдань П, для яких існує N-програма та П і поліном f π (·), такі, що для будь-якої реалізації π завдання П, для якої є відповідь ТАК, програма і П видає відповідь ТАК за час t π (U П) ≤ f П ( ). Так як будь-яка програма є N-програмою, то, очевидно,
.
Дамо визначення: безліч А поліноміальної зводиться до В (позначається А <В), якщо існує функція φ, обчислювана за поліноміальний час і така, що при
Якщо то А і В поліноміальної еквівалентні.
Безліч Е називається NP-повним (або універсальної переборного завданням), якщо і для будь-якого
маємо
. Безліч NP-повних задач позначається NPC,
.
Пошук поліноміальної розв'язаних підкласів NP представляє великий теоретичний і практичний інтерес. Клас NP-повних задач включає в себе багато класичні задачі комбінаторики, такі, як задачу про комівояжера, про гамильтоновой циклі, задачі цілочислового лінійного програмування. Багаторічне вивчення цих завдань не призвело до знаходження алгоритму поліноміальної складності, і завдання даного класу вважаються теоретично важко вирішити. Такими є не тільки комбінаторні задачі, але і звичайні завдання лінійного програмування. При вирішенні завдання лінійного програмування стандартним симплекс-методом неможливо дати верхню оцінку кількості ітерацій, у вигляді полінома від параметрів, що характеризують розмір задачі.
Результати машинних експериментів і досвід вирішення прикладних завдань показують, що можливості точних методів обмежені і не задовольняють потреб практики. Це підтверджується і теоретичним дослідженням ефективності точних методів. Потреби практики найчастіше покриваються наближеними рішеннями, що пояснюється неминучою неточністю завдання вихідної інформації в багатьох прикладних задачах і тим, що моделі відображають реальні ситуації лише з певним ступенем наближення.
Зазвичай розрізняють два рівні підвищення ефективності алгоритмів - локальний і глобальний. Під локальним рівнем розуміються будь-які прийоми, що дозволяють розширити наявні на сьогоднішній день можливості вирішення завдань. Глобальний рівень передбачає переведення певних класів задач на більш низький рівень (наприклад, з NP в Р). Такий перехід зазвичай означає перехід від точних методів до наближеним.
У тих випадках, коли розглянута задача не має характеру питання, а явним чином містить цільову функцію, доречно ставити питання про перебування неточних, а наближених рішень з оцінкою їх відхилення від оптимуму.
Розглянемо задачу знаходження оптимуму функції f (x) на допустимому безлічі G. Нехай х * - оптимальне рішення цієї задачі. Кажуть, що допустиме рішення х є -Наближеним, якщо
(3)
де > 0 - задане число (f (x * j ≠ 0).
Величина > 0 є гарантована характеристика наближеного алгоритму і, якщо для будь-якої реалізації завдання алгоритм дає наближене рішення х і виконується нерівність (3). Порівняння наближених алгоритмів проводиться на підставі гарантованих характеристик, які дозволяють вибрати оптимальний в певному сенсі евристичний алгоритм вирішення задачі.
Різні типи екстремальних задач з класу NPC ведуть себе при знаходженні -Наближеного рішення по-різному. Наприклад, пошук
-Наближеного рішення задачі комівояжера знову представляє собою завдання класу NPC; денний завдання ж про ранці та деяких інших наближених задач існують алгоритми пошуку
-Наближеного розв'язку з поліноміальної складністю. Таким чином, перспективним напрямом підвищення ефективності комбінаторних алгоритмів є виявлення підкласів завдань з класу NPC, для яких пошук
-Наближених рішень переводить їх у клас Р.
Для задач масового рахунку перспективним є застосування статистично ефективних алгоритмів. Такі алгоритми в переважній більшості випадків оптимальні ( -Наближене рішення). Інакше кажучи, із зростанням розмірності задачі частка точно оптимізуються завдань (
-Оптимізуються) серед всіх завдань прагне до 1.
При оцінці ефективності алгоритмів теоретичними методами слід мати на увазі, що отримані результати дають уявлення про поведінку завдань у найгірших можливих випадках, тоді як для обчислювальної практики істотно більш важливо їх поведінка в середньому. Дійсно, експериментально відомо, що для вирішення завдання лінійного програмування з m обмеженнями і п змінними зазвичай потрібно від m до 3т ітерацій; як правило, для завдань не дуже великих розмірів число ітерацій близько до 3 m / 2. Крім того, теоретичні результати практично нічого не говорять про те, як буде вести себе конкретний алгоритм на конкретному завданні. Наприклад, середній час прямого пошуку в списку пропорційно N / 2, де N - кількість елементів списку, а двійкового пошуку (список впорядкований по ключу) - пропорційно log 2 N. Однак двійковий пошук неефективний для невеликих списків, які підлягають частому зміни, тому що введення нового елемента може викликати переписування всіх елементів. Розробка алгоритмів є в основному творчою діяльністю, хоча існує безліч типових методів та алгоритмів, які можуть застосовуватися для вирішення завдань, що виникають в АСУ. До таких методів перш за все відносяться методи дослідження операцій.
Найбільш розробленими наближеними методами розв'язування екстремальних задач є комбінаторні методи, основна ідея яких полягає у використанні кінцівки безлічі рішень і в заміні повного перебору спрямованим перебором. При цьому головну роль у скороченні перебору грає оцінка і відкидання безперспективних (тобто свідомо не містять оптимуму) підмножин рішень. Загальна схема комбінаторних методів (методи типу схеми "гілок і кордонів") застосовна практично до всіх завданням дискретного програмування незалежно від їх лінійності чи інших властивостей. Ця схема може бути застосована безпосередньо до вихідної природної формулюванні екстремальної задачі, без відома її до целочисленной задачі лінійного програмування. Крім того, ці методи найчастіше забезпечують кінцівку обчислювального процесу по самому своєму побудови.
Довгий час єдиним способом оцінки ефективності комбінаторних методів було чисельне експериментування. Основною тенденцією, виявленої в досить представницьких серіях експериментів, є тенденція до експоненціального зростання трудомісткості обчислень при зростанні числа змінних. Теоретичні дослідження комбінаторних завдань також приводять до висновку про експоненційної трудомісткості рішення комбінаторних завдань. Однак практика показує, що комбінаторні методи дозволяють вирішувати задачі АСУ досить великих розмірів.
Використання комбінаторних методів типу "гілок і кордонів" покладено в основу стандартного пакета ЛП АСУ (для вирішення завдань лінійного програмування).