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

Поняття алгоритму є основним при складанні будь-якого виду програм для ПК.

Термін «алгоритм» походить від латинської форми написання імені видатного математика й історика Мухаммеда бен Муси ал-Хорезмі (783 - бл. 850), який описав правила виконання основних арифметичних дій над числами в десятковій системі. Спочатку тільки ці правила (додавання, віднімання, множення й ділення) називали в Європі алгоритмами. Потім тривалий час ним користувалися лише математики, розуміючи під ним правила розв’язування задач.

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

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

Задача

Послідовність дій

Вхідні дані Вихідні дані

Звичайно потрібно, щоб алгоритм мав наступні властивості:

1. Визначеність.

2. Дискретність.

3. Цілеспрямованість.

4. Закінчуваність.

5. Масовість.

6. Результативність.

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

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

Цілеспрямованість – кожен етап алгоритму виконується в строго запланованій послідовності і не допускає перестановок.

Закінчуваність – алгоритм повинен завжди закінчуватися після визначеного числа кроків.

Масовість – будь-який набір припустимих даних задовольняє алгоритмові.

Результативність – виконання алгоритму завжди має результат.

Особливості алгоритму:

1. Дії в алгоритмі виконуються в порядку їхнього запису.

2. Не можна змінювати місцями ніякі дві дії алгоритму.

3. Не можна не закінчивши однієї дії переходити до наступної.

4. Один і той же алгоритм можна представити кількома способами.

5. Для розв’язання однієї і тієї ж задачі може існувати кілька алгоритмів.

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

Основи алгоритмізації обчислювальних процесів Етапи вирішення задач на еом

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

2. Математичне формулювання (модель) опису задачі, формалізація.

3. Вибір чи розробка методів обчислень.

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

4. Розробка алгоритмів:

• математичного;

• машинного.

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

5. Складання (кодування) програми.

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

Розглянемо задачу знаходження найбільшого спільного дільника (НСД). Як і для розв’язання більшості задач існує декілька алгоритмів обчислення НСД. Розглянемо три способи розв’язку цієї задачі. Нехай дано два невід’ємні числа mтаn(для НСД знак не має значення, тому розглядаємо додатні числа). Функцію обчислення НСД позначимо якgcd(m,n) (від англ. greatest common divisor)