Алгоритм
Алгори́тм ― набір правил (інструкцій) або керувальних впливів, виконання яких завершується бажаним результатом. Прикладами алгоритмів є рецепти приготування кулінарних страв, правила виконання арифметичних операцій, комп’ютерні програми.
Історична довідка
Назву «алгоритм» пов’язують з ім’ям Аль-Хорезмі, який близько 825 написав науковий трактат про арифметичні дії над числами, що задані в десятковій позиційній системі числення. У 12 столітті трактат з’явився в Європі в перекладі з арабської на латину. Ім’я перекладача невідоме. У перекладі часто трапляється фраза «Dixit algorizmi» ― так сказав Аль Хорезмі. Це зумовило появу назви поняття алгоритм, яке почали вточнювати ще з часів античності в зв’язку з неможливістю розв’язання деяких геометричних задач у межах фіксованих, дозволених умовами задачі, засобів.
Класична математична теорія алгоритмів виникла в математичній логіці у 1930-х як інструмент для доведення алгоритмічної нерозв’язності певного класу математичних проблем. Додатковим стимулом для її розвитку були дослідження в конструктивній математиці.
Інтерес до уточнення поняття алгоритму посилився після того, як Д. Гільберт у 1928 сформулював проблему можливості розв’язання. Йдеться про визначення алгоритму, який за описом будь-якого математичного твердження, записаного певною формалізованою мовою, після виконання скінченної кількості кроків може надавати відповідь про істинність або хибність цього твердження.
Важливий етап у розвитку алгоритмічних моделей обчислень пов’язаний з працями В. М. Глушкова в 1970-х. В основу підходу В. Глушкова було покладено подання алгоритму у вигляді взаємодії керувального та інформаційного автоматів. Таке подання може бути реалізовано апаратно (центральний процесор, пам’ять ЕОМ) або описане в конструкціях алгоритмічної мови. Автоматична форма задавання дискретних перетворювачів дає змогу застосовувати їх як моделі не лише програм в інформаційних технологіях, а й технічних приладів.
Особливу роль як засобу для вираження алгоритму в обчислювальних системах відведено програмуванню, одним із важливих завдань якого є надання розробникам реальних алгоритмів низки потужних та різноманітних засобів як для подання інформації, так і для вираження процесів її оброблення. Прагнення позбавити користувача зайвої деталізації та кодування під час складання програм привело до появи цілого сімейства алгоритмічних мов високого рівня. Цей процес продовжує бурхливо розвиватися та є визначальним у програмуванні.
Характеристика
Є багато традиційних математичних визначень алгоритму, що зорієнтовані на той чи інший спосіб обчислень: функції, вирази в арифметичному численні предикатів (К. Гедель, 1936), λ-визначені функції (А. Черч, 1936), частково-рекурсивні функції (С. Кліні, 1936), машини Поста (1936) і Тюрінга (1937), нормальні алгоритми (А. Марков (молодший), 1951). Фундаментальною логічною основою, визначеною в теорії алгоритмів, є той факт, що всі ці визначення еквівалентні в сенсі можливості моделювання обчислень (теза Черча ― Тюрінга). Використавши точне визначення алгоритму, вдалося довести існування так званих алгоритмічно нерозв’язних проблем. Так, наприклад, немає алгоритму, який за скінченне число кроків визначає, чи зупиниться однострічкова машина Тюрінга, якщо початкова стрічка порожня.
Поняття алгоритму пов’язують із обробленням інформації. У такому розумінні алгоритм ― це задання в певних виразних засобах процесу перетворення інформації. Під час задавання алгоритму уточнюють: спосіб подання (кодування) інформації, початкову інформацію, допустимі перетворення в заданому поданні, спосіб організації процесу виконання алгоритму. Результат роботи алгоритму ― інформація після закінчення його роботи. Спосіб подання інформації та допустимі її перетворення залежать від вибраної обчислювальної моделі, у якій реалізовано алгоритм. Наприклад, інформація може бути закодована бітовими рядками або рядками символів, числами, масивами, списками записів із покажчиками, файлами тощо. Перетворення інформації можуть бути визначені функціями, математичними операторами, командами обчислювального пристрою або іншим чітко визначеним способом.
Важливим у понятті алгоритму є спосіб організації процесу його виконання. У послідовних алгоритмах виконання локальних перетворень інформації проходить покроково. У детермінованих алгоритмах перетворення інформації на кожному кроці виконання й наступний крок однозначно визначено попередніми кроками виконання алгоритму. У недетермінованому алгоритмі на кожному кроці виконання допускають вибір декількох можливостей його продовження. В імовірнісних алгоритмах кожному можливому вибору наступного кроку приписано деяку ймовірність. Для паралельних алгоритмів характерне одночасне виконання декількох процесів перетворення інформації та їхня взаємодія. Було вивчено також еволюційні, квантові, генетичні, мультиагентні, лінгвістичні та інші численні класи алгоритмів, що відображають ті чи ті аспекти розмаїття обчислювальних моделей, створених за аналогією з фізичними процесами навколишнього світу.
У класичній теорії алгоритмів основний наголос зроблено на понятті принципової обчислюваності, а форма задання алгоритмів менш важлива. Характерною особливістю традиційних класичних визначень алгоритму є вибір мінімальних засобів для подання та перетворення інформації, щоби забезпечити зручність формалізації поняття алгоритму для доведення математичних фактів. Процедури конкретних обчислень, записані за допомогою таких мінімальних засобів, зведено до складного кодування та моделювання перетворення інформації, вони зазвичай такі громіздкі та складні для розуміння, що не можуть бути використані в реальній практиці програмування для електронно-обчислювальних машин (ЕОМ).
Значення
Поняття алгоритму активно використовуване в таких галузях, як обчислювальна математика, математична та технічна кібернетика, проектування ЕОМ і програмування. Так, обчислювальна математика потребує створення паралельних, матричних і надточних обчислень та є одним з основних споживачів спеціалізованих обчислювальних структур. Технічні прилади обробки інформації є конкретним утіленням різноманітних моделей алгоритмів, що відображають архітектуру та фізичні закони, на яких засновано ці прилади.
Література
- Глибовець М. М. Основи комп'ютерних алгоритмів. Київ : Києво-Могилянська академія, 2003. 450 с.
- Кнут Д. Э. Искусство программирования : в 4 т. / Пер. с англ. 3-е изд., испр. и допол. Москва : Вильямс, 2010. Т. 1: Основные алгоритмы. 720 с.
- Кормен Т. Х. и др. Алгоритмы: построение и анализ / Пер. с англ. 3-е изд. Москва : Вильямс, 2013. 1324 с.
- Дасгупта С. и др. Алгоритмы / Пер. с англ. Москва : МЦНМО, 2014. 320 с.
Автор ВУЕ
Покликання на цю статтю: Анісімов А. В. Алгоритм // Велика українська енциклопедія. URL: https://vue.gov.ua/Алгоритм (дата звернення: 6.05.2024).
Статус гасла: Оприлюднено
Оприлюднено: 26.12.2017
Важливо!
Ворог не зупиняється у гібридній війні і постійно атакує наш інформаційний простір фейками.
Ми закликаємо послуговуватися інформацією лише з офіційних сторінок органів влади.
Збережіть собі офіційні сторінки Національної поліції України та обласних управлінь поліції, аби оперативно отримувати правдиву інформацію.
Отримуйте інформацію тільки з офіційних сайтів
Офіс Президента України
Верховна Рада України
Кабінет Міністрів України
Служба безпеки України
Міністерство оборони України
Міністерство внутрішніх справ України
Національна поліція України
Покликання на цю статтю: Анісімов А. В. Алгоритм // Велика українська енциклопедія. URL: https://vue.gov.ua/Алгоритм (дата звернення: 6.05.2024).
