Структурний підхід до проектування алгоритмів
Для розробки алгоритму складних задач використовується метод структурного проектування алгоритмів, який забезпечує легкість читання алгоритму, простоту перевірки правильності виконання алгоритму, зручність у його модифікації. При цьому методі складна задача розбивається на кілька простих. Він отримав назву "метод покрокової деталізації (розробки) алгоритму".
Цей метод передбачає:
• конструювання алгоритму з використанням трьох базових алгоритмічних структур;
• використання методу покрокової деталізації, тобто подрібнення задачі на більш прості задачі, потім подрібнення цих задач на ще більш прості складові і т. д. (розробка алгоритму "зверху вниз");
• аналіз алгоритму, тобто контроль правильності кожної структури алгоритму і взаємозв’язків структур.
Перевагою структурного підходу є його модульність.
Модуль – це послідовність логічно пов’язаних команд, яка оформлена у вигляді окремого (допоміжного) алгоритму. Кожному допоміжному алгоритму дається своє унікальне ім’я, за яким його можна розпізнати серед інших допоміжних алгоритмів. Ці допоміжні алгоритми можна конструювати й аналізувати окремо та незалежно, використовуючи їх потім в основному алгоритмі або інших допоміжних алгоритмах.
Для реалізації цього методу потрібно виконати такі дії:
· Розбити складну задачу на кілька простих.
· Якщо задачі чергового рівня стають досить простими для незалежного розв’язання – закінчити процес деталізації.
· Скласти для кожної простої задачі свій допоміжний алгоритм.
· Скомпонувати результати проектування простих задач в єдиний алгоритм.
· Проаналізувати роботу алгоритму.
При цьому слід, звичайно, розуміти, що якщо на етапі аналізу задачі був обраний невірний підхід до її вирішення, то навіть сама акуратна подальша деталізація вже не дозволить отримати правильний алгоритм.
Процес покрокової деталізації вважається закінченим, коли задачі чергового рівня стають досить простими для незалежного розв’язання. Потім результати проектування простих задач компонуються в загальний алгоритм.
Поряд з використанням методу покрокової деталізації необхідно також мати на увазі наступні чинники, які можуть істотно вплинути на алгоритм, що розробляється:
1. Засоби, що надаються тією мовою, якою алгоритм буде запрограмований. При використанні різних мов є можливість розробляти істотно різні алгоритми.
2. Структура даних, на які орієнтований алгоритм. Цей фактор робить винятково великий вплив на ефективність алгоритму, що розробляється.
3. Наближеність подання дійсних чисел у пам'яті ЕОМ. Це вимагає того, щоб при розробці алгоритму усюди, де проводиться порівняння дійсних чисел, використовувався деякий рівень точності, що задається програмістом.
Суворий математичний доказ правильності роботи алгоритму зазвичай є дуже складною задачею, головним чином через те, що важко довести правильність роботи циклів і рекурсивних процедур. Разом з тим демонстрація правильної роботи алгоритмів на деякому наборі тестів ще не означає, що він завжди буде працювати правильно.
Слід пам'ятати, що різних комбінацій вхідних даних буває, як правило, нескінченно (або "практично" нескінченно) багато. Тому необхідно супроводжувати алгоритм деяким міркуванням, яке, навіть не будучи суворим доказом, в досить повній мірі переконує в правильності алгоритму. Звичайно, воно не повинно бути міркуванням в такому, наприклад, стилі: "алгоритм перебирає всі варіанти, тому він правильний". Адже тоді цілком слушним виникає питання, а як переконатися, що алгоритм дійсно перебирає всі варіанти.
Використовуючи метод покрокової розробки, не слід забувати про такий потужний засіб доказового програмування, як анотування програми твердженнями, розміщеними в коментаріях. Анотації описують властивості обчислень у відповідних точках програми. Вони допомагають уникнути помилок при кроках деталізації та в обґрунтуванні їх правильності. Крім того, анотована програма може виступати як доказ своєї правильності.
Зазначимо, що алгоритм, який записаний алгоритмічною мовою, – це програма для комп'ютера. Кожне речення в програмі - це оператор.
Перед початком розробки алгоритму необхідно чітко усвідомити задачу, з’ясувати, що потрібно отримати як результат, які вихідні дані необхідні та які є в наявності, які існують обмеження на ці дані. Далі потрібно записати, які дії необхідно зробити для отримання з вихідних даних необхідного результату.
ТЕМА 2. ПОХИБКИ ОБЧИСЛЕНЬ