Визначення, властивості та види алгоритмів

Визначення, властивості та види алгоритмів


У світі інформаційних технологій поняття алгоритму займає центральне місце. Сам термін стався від імені Аль-Хорезмі, узбецького середньовічного математика, який у 9 столітті зумів чітко описати правила виконання простих арифметичних дій - тобто склав перші алгоритми.

Алгоритм - визначення

У сучасній інформатиці та математиці цей термін має такі визначення:

- послідовність дій, в якій суворо визначені правила виконання;

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

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

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

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

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

Універсальним виконавцем алгоритму в інформатиці є комп'ютер.

Алгоритм і його властивості

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

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

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

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

Залежно від цілей, початкових умов, шляхів вирішення завдання, визначення дій виконавця, можна виділити такі види алгоритмів:

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

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

3) Лінійні види алгоритмів мають на увазі побудову набору команд або вказівок, що виконуються в суворій послідовності один за одним.

4) Алгоритми, що розгалужуються, містять щонайменше одну умову, після перевірки якої ЕВМ може перейти на один з декількох можливих кроків.

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