Способи подання (опису) алгоритму

Системи програмування

 

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

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

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

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

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

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

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

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

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

Отже, для створення програми потрібні:

· текстовий редактор;

· компілятор;

· редактор зв'язків;

· бібліотеки функцій.

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

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

 

3 Загальний огляд технологій програмування

 

3.1 Алгоритмічне (модульне) програмування

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

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

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

 

Структурне програмування

 

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

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

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

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

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

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

 

3.3 Подієво-орієнтоване програмування

 

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

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

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

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

 

3.4 Об'єктно-орієнтоване програмування

 

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

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

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

 

3.5 Візуальне програмування

 

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

 

Запитання для контролю та самоконтролю

 

1. Дати роз’яснення наступним поняттям: машинний код процесора, алгоритм, програма, компілятор, інтерпретатор.

2. Дати роз’яснення термінам система програмування, інтегрована система програмування.

3. У чому полягає сутність та раціональність проектування зверху вниз?

4. Дати пояснення сутності технології програмування.

5. Дати стислу характеристику таким технологіям програмування як: алгоритмічне (модульне) програмування, структурне програмування, подієво-орієнтоване програмування, об'єктно-орієнтоване програмування, візуальне програмування.

II. ОСНОВНІ ПОНЯТТЯ АЛГОРИТМІЗАЦІЇ

 

Розробка програми, призначеної для розв’язання на ЕОМ деякої задачі, потребує попереднього складання алгоритму її розв’язання.

 

1. Алгоритми та їх властивості

 

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

Слово алгоритм походить від algorithmi, що є латинською транслітерацією арабського імені хорезмійського математика IX століття аль-Хорезмі (Мухаммед бен Муса аль-Маджус аль-Хорезмі). Завдяки латинському перекладові трактату цього вченого європейці в XII столітті познайомилися з індійською позиційною системою числення і у середньовічній Європі алгоритмом довго називали десяткову позиційну систему числення та обчислення за її правилами.

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

Алгоритм має відповідати наступним властивостям:

властивість	пояснення
Скінченність	полягає в тому, що результат буде отримано після виконання кінцевої кількості елементарних кроків алгоритму
Результативність	означає одержання необхідного результату після виконання алгоритму
Визначеність	складається в тому, що результати, незалежно від користувача алгоритму й засобів їх отримання, мають бути однаковими
Масовість	полягає в можливості застосування алгоритму до цілого класу однотипних задач, що розрізняються конкретними значеннями вхідних даних
Зрозумілість	припускає, що алгоритм викладений у виді елементарних інструкцій мовою виконавця цього алгоритму (людини, автомата, комп’ютера)

 

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

· набір об'єктів, що складають сукупність можливих вхідних даних, проміжних і кінцевих результатів;

· правило початку;

· правило безпосередньої переробки інформації (опис послідовності дій);

· правило виведення результатів;

· правило закінчення.

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

Способи подання (опису) алгоритму

 

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

Словесно-формульний спосіб - це запис алгоритму у виді тексту з формулами по пунктах. Наприклад, необхідно визначити значення виразу Y=2 a -(x +6). Словесно-формульним способом алгоритм розв’язування цієї задачі може бути записаний у наступному виді:

1. Увести значення змінних а та х.

2. Додати константу 6 до значення змінної х.

3. Збільшити значення змінної а у 2 рази.

4. Зменшити значення добутку 2 а на (х +6) та зробити результат значенням змінної Y.

5. Вивести Y як результат обчислення всього виразу.

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

3. Правила оформлення блок-схем алгоритмів

 

Оформлення програм повинне відповідати визначеним вимогам. В даний час діє єдина система програмної документації (ЄСПД), що встановлює правила розробки, оформлення програм і супутньої документації. Правила оформлення блок-схем алгоритмів визначені ДСТ 10.002-80 ЄСПД, ДСТ 10.003-80 ЄСПД. Операції обробки даних і носій інформації зображуються на схемі відповідними блоками. Велика частина блоків по побудові умовно вписана в прямокутник зі сторонами а і в. Мінімальне значення а = 10 мм, збільшення значення а можливе на число, кратне 5. Розмір в = 1.5 а. У межах однієї схеми рекомендується зображувати блоки однакових розмірів. Усі блоки нумеруються. Лінії, що з'єднують блоки та визначають послідовність зв'язків між ними, проводяться лініями рамки. Стрілка наприкінці лінії може не ставитися, якщо лінія спрямована праворуч або зверху вниз. З блоку (крім логічного) має виходити тільки одна лінія. Логічний блок може мати як продовження один із двох блоків, тобто з нього виходять дві лінії. Місця на схемі, де лінії зливаються, виділяються крапкою. У випадку, коли одна лінія підходить до іншої і злиття їх чітко виражене, крапку можна не ставити.

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

 

Блок Початок
Блок Кінець
Блок Введення інформації
Блок Виведення інформації
Блок Обчислення
Блок Перевірка умови (логічний)
Блок Виклик допоміжного процесу
Лінія з’єднання блоків

Таблиця. Зображення базових елементів блок-схем

 

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

 

4. Базові алгоритмічні конструкції

 

Можна виділити і наочно представити 3 найпростіші (базові) алгоритмічні структури: послідовність двох або більше операцій (конструкція послідовного виконання); вибір напрямку (умовна конструкція або конструкція розгалуження); повторення (цикл). Слід знати правила графічного зображення вказаних алгоритмічних структур (тут серія – група дій, ЛВ – логічний вираз, + - напрям виконання дій, якщо логічний вираз має значення Істина):

 

Конструкція послідовного виконання
Повне розгалуження	Неповне розгалуження
Цикл с передумовою (цикл ПОКИ)	Цикл с післяумовою (цикл ДО)

 

Будь-який обчислювальний процес може бути представлений як комбінація цих елементарних алгоритмічних структур. Відповідно, обчислювальні процеси, виконувані на ЕОМ по заданій програмі, можна розділити на 3 основних види: лінійні; розгалужені; циклічні.

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

 

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

 

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

· підготовка (ініціалізація) циклу;

· виконання обчислень циклу (тіло циклу);

· модифікація параметрів;

· перевірка умови завершення (продовження) циклу.

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

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

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

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

 

Запитання для контролю та самоконтролю

 

1. Що таке алгоритм вирішення задачі? Яка історія цього терміну?

2. Які властивості відповідають поняттю алгоритм?

3. Які існують способи подання (опису) алгоритму?

4. Які існують правила для оформлення блок-схем алгоритмів?

5. Що таке базові алгоритмічні конструкції?

6. Пояснити поняття лінійний, розгалужений, циклічний алгоритмічні процеси.

7. Які можна виділити етапи організації циклу? Які елементи виокремлюють у структурі циклу? Що таке інваріант циклу?

8. Які різновиди циклів використовують у програмуванні? У чому їх відмінності?

9. У чому різниця між передумовними та післяумовними циклами?

10. У чому різниця між детермінованими та ітераційними циклами?

11. Що таке вкладені цикли?

III. ЕТАПИ РОЗВ’ЯЗУВАННЯ ПРИКЛАДНИХ ЗАДАЧ

 

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

 

1. Постановка задачі

 

Задачі виникають у конкретних галузях наукової та практичної діяльності людини. Постановка задачі полягає в аналізі початкового формулювання задачі з метою чіткого уявлення щодо вхідних даних задачі і необхідних результатів (уточнення кількості та формату). Тобто потрібно відповісти на запитання «Що дано?» та «Що потрібно знайти, отримати?».

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

 

2. Побудова моделі

 

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

Для побудови моделі необхідно:

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

· відібрати описи, що підходять для розв'язання задачі;

· з відібраних описів побудувати опис, що забезпечує розв'язання поставленої задачі.

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

· Текстові описи;

· Графічні описи - малюнки, креслення, схеми, діаграми й інше;

· Опис у вигляді кількісних відношень, формул, рівнянь, обмежень.

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

 

Розробка алгоритму

 

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

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

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

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

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

 

4. Вибір структур даних

 

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

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

 

Розробка програми

 

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

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

Важливим питанням є також виправлення недосконалостей.

Можна виділити наступні класи недосконалості:

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

Приклад:

P+Q Т

T*T+T-T R

вдосконалюючи одержимо

P+Q T

T*T R

 

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

Приклад:

P+Q R

R*R R

вдосконалюючи одержимо

P+Q T

T*T R

 

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

Приклад:

P+Q TI

P+Q T2

Tl * Т2 R

вдосконалюючи одержимо

P+Q TI

TI*TI R

 

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

Приклад:

(P+Q)*(P+Q) R

вдосконалюючи одержимо

Р+Q T

T*T R

 

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

Приклад:

P+Q TI

TI 2 R

вдосконалюючи одержимо

(P+Q) 2 R

 

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

Приклад:

P*P+2*P*Q+Q*Q R

вдосконалюючи одержимо

(P+Q) 2 R

 

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

 

Тестування програми

 

Існує думка, що мета тестування - переконатися в правильності роботи програми. Це поширена помилка. Насправді мета тестування - знайти в програмі помилки.

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

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

При другому підході (знайти помилки) ситуація міняється. Мета тестера - «зламати» програму, довести її помилковість, знайти ситуацію, в якій результати невірні. У цьому випадку тестер святкує, якщо йому вдалося добитися свого і програма помилилася, а кожен вірний результат він сприймає як свою поразку. Зрозуміло, що тут справа не обмежується простими тестами. У хід йдуть найкаверзніші вхідні дані, найнесподіваніші їх комбінації. Тестер прагне знайти важкі для обробки випадки і запропонувати програмі саме їх. І якщо програма витримала подібний натиск, можна сподіватися, що вона дійсно написана правильно.

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

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

Всі методи тестування можна розділити на дві групи: тестування за принципом «чорного ящика» і за принципом «білого ящика».

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

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

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

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

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

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

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

По-друге, далеко не завжди у програміста є можливість доручити тестування комусь іншому.

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

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

 

7. Аналіз результатів роботи програми

 

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

Для ефективного вирішення всіх зазначених проблем необхідно постійно підтримувати зв'язок із замовником завдання.

 

8. Важливі та корисні технологічні правила

 

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

 

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

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

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

Часто (головним чином початківцям у програмуванні) рекомендують користуватися KISS-принципом (Keep It Single Stupid) - треба робити програму якомога простішою; це полегшить вам (та можливо іншим) справу пошуку/виправлення помилок і модифікації.

Необхідно пам’ятати й про такі правила:

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

Вибір ідентифікаторів. Ідентифікатори (імена) об’єктів програми (констант, змінних, функцій, процедур та ін.) треба обирати близькими до реальної назви відповідного об’єкта.

Дружній інтерфейс та термінологічне середовище. Програма повинна вести з користувачем коректний (з виконанням норм ввічливості) діалог, пояснювати свої дії, коригувати дії користувача; під час діалогу має використовуватися лише термінологія, зрозуміла користувачу та не використовуватися термінологія розробника.

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

Захист від некоректного введення. Введену користувачем інформацію програма повинна перевіряти на коректність (належність множині припустимих для введення даних) та давати можливість користувачу виправити можливі помилки введення.

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

 

Запитання для контролю та самоконтролю

 

1. У чому полягає технологічний ланцюжок розв’язування прикладної задачі з використанням комп’ютера? Які дії виконуються на кожному етапі?

2. Що таке технологія програмування?

3. Які головні засади технології структурного програмування?

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

5. Для чого потрібне тестування програм? Які методи тестування програм найчастіше використовуються?

6. Що розуміють під моделлю задачі?

7. Як обрати мову програмування для реалізації алгоритму?

8. У чому полягає сутність процесу відладки програми?

9. Які існують прості корисні правила розробки програми?

10. Що таке постановка задачі?

11. Як ефективно представити алгоритм?

12. Які існують вимоги до «дружності» інтерфейсу програми?

13. Що таке недосконалості програми? Які вони бувають, на що впливають?

14. Що визначає поняття алгоритмічної складності?

15. Яке існує правило для вибору типів даних для об’єктів задачі?

16. Що означає коректність постановки задачі?