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

Саме слово алгоритм походить від латинського слова algoritm, яке є латинським зображенням арабського імені Хорезмійського математика V ст. Аль- Хорєзмі.

Термін „алгоритм” звичайно використовується для позначення деякої послідовності дій, що приводять до досягнення певного результату.

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

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

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

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

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

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

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

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

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

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

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

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

Розробка алгоритму більш чи менш складної задачі вимагає високої кваліфікації виконавця і розуміння змісту задачі. З реалізацією алгоритму безпосередньо пов’язане вміння застосувати цей алгоритм для конкретних вхідних даних розв’язуваної задачі. Таке застосування називається алгоритмічним процесом. Цей процес полягає у перетворенні вхідних даних за правилами визначеними заданим алгоритмом.

З поняттям алгоритмічного процесу тісно пов’язане і поняття обчислювального процесу.

Суть алгоритмізації обчислювального процесу полягає в наступному:

- виокремлення автономних етапів обчислювального процесу;

- формальний запис змісту кожного з них;

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

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

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

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

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

 

Приклад: у =

Словесний опис

№ п/п	дія
	Помножити число 2 на число х.
	До результату дії 1 додати число 3.
	Число 3 помножити на число х.
	Від результату дії 3 відняти число 4.
	Результат 2 дії поділити на результат 4 дії.

 

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

Математичний опис

№ п/п	дія
	а: = 2 * х
	в: = а + 3
	с: = 3 * х
	d: = с – 4
	у:= b: d

 

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

1) Геометричні фігури різної конфігурації;

2) Словесний опис;

3) Математична символіка.

Алгоритм виконання у вигляді блок схем не можна ввести в ЕОМ.

 

Блок схема.

 

Циклічний тип

 

Обчислити суму чисел від 1 до 100

S = S + C; C = C + 1

Блок - схема алгоритму обчислення суми від 1 до100.

 

Алгоритми сортування

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

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

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

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

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

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

а) перший крок

б) другий крок

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

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

Загальна кількість операцій порівняння в алгоритмі сортування простим

вибором дорівнює