2.3. Класи алгоритмів

 

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

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

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

Третій, основний тип алгоритмів, призначений не для пошуку відповіді на поставлену задачу, а для моделювання фізичних систем з використанням комп‘ютера.

2.4. Документація алгоритмів

 

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

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

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

Лекція 3. Методи сортування .

 

3.1. Задача сортування

 

Загальна задача сортування полягає в наступному:

нехай дано множину елементів, яка є індексованою, тобто довільно пронумерованою від 1 до n . Необхідно індексувати цю множину елементів так, щоб з умовиi<j витікало a_i < а_j - для всіх i,j=1..n.

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

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

Нехай маємо вектор з n елементів R₁ ,R₂ ,…,R_n .. Задача сортування полягає у тому, щоб знайти таку перестановку елементів вектора, після якої вони розмістилися б у зростаючому порядку їх значень.

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

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