Поняття алгоритму, його властивості

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

Алгоритм. Властивості алгоритму.

Саме слово «алгоритм» виникло з назви латинського перекладу книги арабського математика IX століття Аль-Хорезмі «Algoritmi de numero Indoru», що можна перекласти як «Трактат Аль-Хорезмі про арифметичному мистецтві індусів». Складання алгоритмів і питання їх існування є предметом серйозних математичних досліджень.

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

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

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

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

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

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

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

Опис алгоритмів природною мовою.

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

Припустимо, що програма, складена для такого процесора, містить числові дані і символи арифметичних дій над цими даними. Ось приклад такої програми, призначеної для обчислення сум двох чисел 2 і 3:

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

Було розглянуто приклад найпростішої програми. Вона є записом алгоритму рішення деякого класу задач - задач обчислення суми двох чисел. Позначимо ці числа a і b. Тоді алгоритм можна записати наступним чином:

1. Вважати число a.

3. Виконати підсумовування c: = a + b.

4. Вивести число c.

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

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

сприймається програмістом цілком природно, а рівняння

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

Залишимо алгоритм вирішення наступного завдання. Нехай задані два значення x і y. Необхідно порівняти ці значення і надрукувати ім'я більшої змінної. Для цього завдання досить порівняти обидва значення і в залежності від результату порівняння вивести на друк символ «х» і символ «у»:

1. Ввести значення x.

2. Ввести значення y.

3. Якщо x

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

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

Опис алгоритмів за допомогою блок-схем.

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

, то речових коренів немає.

Блок схема алгоритму наведена на малюнку:

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

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

Розроблений програмістом алгоритм повинен давати правильну відповідь. Перевірка алгоритму може виявитися непростою справою. У простих випадках така перевірка може бути виконана за допомогою заповнення трасування таблиці. Кожен стовпець такої таблиці відповідає певній змінної, а кожен рядок - одному кроці алгоритму. Для заповнення таблиці необхідно крок за кроком простежити виконання алгоритму, записуючи в таблицю поточні значення вибраних для трасування змінних. Такий метод дозволяє виявити логічні помилки, допущені при складанні або запису алгоритму, і визначити, чи вірний остаточну відповідь. Складемо за приклад трасувальні таблицю для алгоритму Герона обчислення квадратного кореня з числа 2.

Як видно з таблиці, вже після третьої ітерації наближене значення квадратного кореня відрізняється від точного 1,414213 лише в шостому знаку після коми.

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

попередні статті

наступні статті

Всі матеріали в розділі "Інформатика і програмування"