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

Історичні відомості.

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

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

Перший алгоритм, призначений для виконання на автоматичному обчислювальному пристрої (комп'ютері), описала Ада Лавлейс в 1843 році. Алгоритм мав обчислювати числа Бернуллі й працювати на аналітичній машині Беббіджа. Цей алгоритм вважається першою комп'ютерною програмою, а його розробниця, Ада Лавлейс — першим програмістом.

З 1930-тих років починається бурхливий розвиток галузі дослідження алгоритмів та становлення інформатики в її сучасному вигляді. В 1935 році Стівен Кліні розробив перше формулювання теорії рекурсії, та показав еквівалентність розробленої системи частково рекурсивним функціям. В 1936 році незалежно були опубліковані роботи Алана Тюринга та Еміля Поста, в яких наведено схожі системи для визначення поняття алгоритму. А вже в 1937 році було доведено еквівалентність різних визначень. Протягом 1935—1960 років було розроблено численні ідеї та технології, які лягли в основу сучасної інформатики.

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

До основних властивостей алгоритму відносять наступні характеристики:

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

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

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

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

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

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

Поиск по сайту: