Принципи розробки алгоритмів і програм для вирішення прикладних завдань

ПРИНЦИПИ РОЗРОБКИ АЛГОРИТМІВ І ПРОГРАМ ДЛЯ ВИРІШЕННЯ ПРИКЛАДНИХ ЗАДАЧ

1. Операциональная ПІДХІД

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

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

1) мінімальні вимоги щодо оперативної пам'яті комп'ютера -. програма повинна була використовувати найменшу можливу кількість комірок оперативної пам'яті комп'ютера;

2) мінімальний час виконання (мінімальне число операцій). При цьому програми складалися з команд, безпосередньо або майже безпосередньо виконувалися комп'ютером (точніше кажучи, процесором):

• операції привласнення;

• найпростіших арифметичних операцій;

• операцій порівняння чисел;

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

• операторів виклику підпрограм (допоміжних алгоритмів).

Такий підхід у програмуванні (створенні алгоритмів), орієнтований на безпосередньо виконувані комп'ютером операції, можна назвати операційним.

Розглянемо докладніше операції, які виконуються комп'ютером і які є кроками програми при операциональном підході.

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

Набір найпростіших арифметичних операцій «додавання» (+), «вирахування» (-), «множення» (*) і «розподілу» (/) (причому у багатьох випадках слід ретельно відрізняти поділ, що виконується над цілими числами - в цьому випадку операція поділу розпадається на поділ без остачі і обчислення залишку від ділення) дозволяє записувати арифметичні вирази з використанням числових констант і ідентифікаторів змінних. Для визначення порядку операцій у виразах найчастіше використовують стандартне математичне угоду про старшинство операції, згідно з яким старшими та виконуваними в 1-у чергу є множення і ділення, а молодшими - додавання і віднімання. Для зміни «природного» порядку виконуваних операцій служать дужки. Порівняйте, наприклад, порядок операцій у виразах:

(А + 2) * х і а + 2 * х.

Що ж стосується порядку виконання операцій одного старшинства, то вони, як правило, виконуються в порядку запису у виразі.

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

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

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

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

n = 0,1,2, ...

Можна показати, що .

Будемо позначати через x0 нульове наближення (за нього в даному випадку можна прийняти будь-яке позитивне число), через e задану точність обчислень і через c0 яке-небудь число, яке задовольняє умові 0 <c0 < , Необхідне для оцінки досягнутої точності за допомогою нерівності

Алгоритм обчислення .

1) ввести числа а, e, x0, c0;

2) присвоїти змінної х значення у,

3) присвоїти змінної у значення а / х;

4) присвоїти змінної у значення х + у,

5) привласнити змінній x значення у / 2;

6) присвоїти змінної у значення x 2;

7) присвоїти змінної у значення y-а;

8) присвоїти змінної у значення у/c0;

9) присвоїти змінної d значення у / 2;

10) порівняти d і e; якщо d> e, то перейти до команди 3, інакше перейти до наступної команді;

11) вивести числа х, а і e;

12) стоп.

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

Пояснимо цю програму. Команда 2 поміщає значення початкового наближення x0 в комірку пам'яті, в якій зберігаються значення змінної х (на кожному етапі обчислень в цьому осередку зберігається значення х, рівне значенню одного з членів рекурентної послідовності xn).

Команди 3-5 обчислюють за кількістю х число (х + а / г) / 2. Результат поміщається в комірку пам'яті, в якій зберігається значення змінної х, при цьому старе значення «стирається» новим. Команди 6-9 обчислюють величину

,

за допомогою якої оцінюється зверху різниця х - . Важливе значення має команда 10. По ній не виробляються обчислення, а порівнюються між собою обчислене значення 5 і задана точність e. Якщо d> e, то керуючий пристрій поверне обчислювальний процес до команди 3 та змусить повторити процес.

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

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

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

• зловживання командою умовного і безумовного переходів часто призводило до дуже заплутаною структурі програми, яка нагадувала за образним порівнянням «блюдо спагетті»;

• разом з різноманітними прийомами, спрямованими на підвищення ефективності програми (тобто мінімальних вимог до оперативної пам'яті і мінімального часу виконання), це призводило до незрозумілості програм, їх ненадійності, труднощів у налагодженні і модифікації, роблячи програмування трудомістким, складним і надзвичайно дорогим .

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

2. СТРУКТУРНИЙ ПІДХІД

З появою масових ЕОМ 3-го покоління застаріла технологія програмування виявилася основним фактором, що стримує розвиток і поширення комп'ютерних (інформаційних) технологій, що підштовхнуло провідні в цій сфері діяльності фірми, в першу чергу IBM, до розробки нових методологій програмування. З'явився на початку 1970-х років новий підхід до розробки алгоритмів отримав назву структурного.

З появою структурного програмування описані вище труднощі були багато в чому подолані. В основі технологічних принципів структурного програмування лежить твердження про те, що логічна структура програми може бути виражена комбінацією трьох базових структур: слідування, розгалуження і циклу (це зміст теореми Бема-Якопіні).

Дотримання - найважливіша із структур. Вона означає, що дії можуть бути виконані один за одним, рис.1. 19:

Рис.1. Структура «проходження»

Ці прямокутники можуть представляти як одну єдину команду, так і безліч операторів, необхідних для виконання складної обробки даних.

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

Ця структура називається також «ЯКЩО - ТО - ІНАКШЕ», або «розвилка». Кожен із шляхів (ТО або ІНАКШЕ) веде до загальної точки злиття, так що виконання програми продовжується незалежно від того, який шлях був обраний.

Ріс.1.0. Структура «розгалуження»

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

Рис.1.1. Структура «неповне розгалуження»

Цикл (або повторення) передбачає повторне виконання деякого набору команд програми. Якби цикли не існували, навряд чи заняття програмуванням було б виправданим: цикли дозволяють записати довгі послідовності операцій обробки даних за допомогою невеликого числа повторюваних команд. Різновиди циклу зображені на ріс.1.22 і ріс.1.23.

Цикл починається з перевірки логічного виразу. Якщо воно істинне, то виконується «a», потім все повторюється знову, поки логічне вираження зберігає значення «істина». Як тільки воно стає помилковим, виконання операцій «а» припиняється і керування передається за програмою далі.

Рис.1.2. Структура циклу «поки»

Рис.1.3. Структура циклу «до»

Рис.1.4. Знаходження суми трьох чисел

Рис.1.5. Знаходження найбільшого з трьох чисел.

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

Рис.1.6. Знаходження суми 100 чисел.

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

Так як вираз, що управляє циклом, перевіряється на самому початку, то у випадку, якщо умова відразу виявиться помилковим, оператори циклічної частини «a» можуть взагалі не виконуватись. Оператори циклічної частини «а» повинні змінювати змінну (або змінні), що впливають на значення логічного виразу, інакше програма «зациклиться» - буде виконуватися нескінченно. Розглянута циклічна конструкція називається також цикл «поки що», або «цикл з передумовою».

Існує й інша конструкція циклу, яка передбачає перевірку умови, за яким, навпаки, виконання команд циклічної частини припиняється, після команд циклічної частини (див. ріс.1.23).

Рис 1.7. Алгоритм типу розвилка, вкладена в цикл, для знаходження суми позитивних чисел з 100 можливих.

Схематичні зображення декількох суперпозицій базових алгоритмічних структур представлені нижче на ріс.1.28-1.31.

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

1) можливість створення програми декількома програмістами;

2) простота проектування і наступних модифікацій програми;

3) спрощення налагодження програми - пошуку та усунення у ній помилок;

4) можливість використання готових бібліотек найбільш уживаних модулів.

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

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

3. НОВІТНІ МЕТОДОЛОГІЇ РОЗРОБКИ ПРОГРАМ ДЛЯ ЕОМ

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

Тут ми обмежимося найкоротшою характеристикою цих напрямків, більш детально описаних у гл.3.

Саме структурне програмування, найбільш чітко виражене в мові Паскаль (PASCAL), виникло в ході розвитку процедурно-орієнтованого підходу, закладеного в історично першому з мов програмування - Фортрані (FORTRAN). У всіх мовах цього напряму розробник алгоритму (він же, як правило, і програміст) описує, якими діями слід реалізувати процес. В основі мов цієї групи лежать поняття команд (операторів) і даних. Окремі групи операторів можуть об'єднуватися у допоміжні алгоритми (процедури, підпрограми).

Об'єкт - основне поняття об'єктного програмування - у першому наближенні схожий на процедуру. Однак, процедура (підпрограма) "оживає» лише всередині тієї програми, до якої вона належить, а об'єкт може вести себе цілком незалежно. Він може відноситися до іншої предметної області ніж основна програма, бути виконаним в іншому стилі. Об'єкти досить химерно зв'язуються один з іншому, можуть переймати властивості один у одного («успадкування»). В об'єктно-орієнтованому підході вихідна задача подається як сукупність взаємодіючих об'єктів. Найбільш популярні реалізації об'єктного програмування створені на основі мов Паскаль, Бейсік (BASIC).

Декларативний підхід в розробці комп'ютерних програм з'явився на початку 70-х років. Він не отримав такого широкого застосування як процедурний, оскільки був спрямований на відносно вузьке коло завдань штучного інтелекту. При його застосуванні програміст описує властивості вихідних даних, їх взаємозв'язку, властивості, якими повинен володіти результат, а не алгоритм отримання результату. Зрозуміло, для отримання результату цей алгоритм все одно потрібен, але він повинен породжуватися автоматично тією системою, яка підтримує декларативно-орієнтована мова програмування. При логічному варіанті такого підходу (насамперед це стосується до мови Пролог, PROLOG) завдання описується сукупністю фактів і правил на деякій формальній логічною мовою, при функціональному варіанті - у вигляді функціональних співвідношень між фактами (мова Лісп, LISP).

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