Алгоритм

АЛГОРИ́ТМ (лат. algorithmi, algorithmus — сукупність дій, правил) — система правил (програма), що вказує, у якій послідовності треба виконати кожне з цих правил, щоб після певної кількості операцій розв’язати будь-яку задачу даного типу. Термін «А» походить від араб. імені узб. математика аль-Хорезмі. Для складання А. застосовують алгоритмічну мову. Характер. рисами А. є дискретність, яка полягає в розчленуванні процесу на окремі послідовні етапи; детермінованість, тобто повне й однозначне визначення на кожному етапі проміж. показників за даними, одержаними на поперед. етапі; масовість, що означає застосовність А. до множини вихід. даних (потенційно нескінченної). А. — одне з осн. понять алгебри та кібернетики. Розрізняють А. з навчанням, зміст якого змінюється з урахуванням вхідної інформації і застосовується переважно в інтелектуальних комп’ютер. системах; послідовного обслуговування — за яким на обслуговування насамперед приймається запит, що надійшов першим; розв’язування задачі — точний припис про виконання у певній послідовності арифмет. і логіч. перетворень первинних даних у результативну інформацію. А. — це задання в певних виразних засобах процесу перетворення інформації. При заданні А. уточнюються: спосіб представлення (кодування) інформації, початкова інформація, допустимі перетворення в заданому представленні, спосіб організації процесу виконання А. Результат роботи А. — інформація після закінчення його роботи. Спосіб представлення інформації та допустимі її перетворення залежать від обраної обчислюв. моделі, в якій реалізується А. Так, напр., інформація може кодуватися бітовими рядками або рядками символів, числами, масивами, списками записів з покажчиками, файлами і т. ін. Перетворення інформації може визначатися функціями, матем. операторами, командами обчислюв. пристрою або ін. чітко визначеним способом. Важл. у понятті «А.» є спосіб організації процесу виконання А. У послідовних А. локальні перетворення інформації виконуються крок за кроком. У детермінованих А. перетворення інформації на кожному кроці виконання А. і наступ. крок однозначно визначаються поперед. кроками виконання А. У недетермінованому А. на кожному кроці виконання припустимий вибір декількох можливостей його продовження. У ймовірнісних А. кожному можливому вибору наступ. кроку приписується деяка ймовірність. Дистрибутивні, або паралельні, А. характеризуються одночас. виконанням декількох процесів перетворення інформації і їхньою взаємодією. У найпоширеніших сучас. персон. ЕОМ реалізуються лише послідовні детерміновані А., записані в одній із мов програмування. Вивчалися також еволюційні, квантові, генетичні, мультиагентні, лінгвістичні та ін. багаточисленні класи А., що відображають ті або ін. аспекти різноманіття обчислюв. моделей, що запозичалися за аналогією з фіз. процесами довкілля.

Поняття «А.» стали уточнювати ще з часів античності у зв’язку з неможливістю вирішення деяких геом. задач у межах фіксованих, дозволених умовами задачі, засобів. Класична матем. теорія А. виникла в матем. логіці в 30-х рр. 20 ст. як інструмент для доказу алгоритміч. нерозв’язності певного класу матем. проблем. Додатк. стимулом для її розвитку стали дослідж. в галузі конструктив. математики. Існує велика кількість традиц. матем. визначень А., що орієнтувалися на той або ін. спосіб обчислень: функції, що виражаються в арифмет. численні предикатів (К. Ґьодель, 1936),– визначені функції (А. Чьорч, 1936), частково-рекурсивні функції (С. Кліні, 1936), машини Поста і Тьюрінґа (Е. Пост, 1936; А. Тьюрінґ, 1937), нормальні А. (А. Марков, 1951). Фундам. логіч. основою, встановленою в теорії А., є той факт, що всі ці визначення еквівалентні в сенсі можливості моделювання обчислень. Використовуючи точне поняття А., вдалося довести наявність т. зв. алгоритмічно-нерозв’язних проблем.

У класич. теорії А. осн. наголос робиться на понятті принципової обчислюваності, а форма задання А. особл. ролі не грає. Характер. особливістю традиц. класич. визначень А. є вибір мін. засобів для представлення та перетворення інформації, що було продиктовано міркуваннями зручності формалізації поняття «А.» та доведення матем. фактів. Процедури конкрет. обчислень, записані за допомогою подіб. мін. засобів, зводяться до складного кодування та моделювання перетворення інформації і, зазвичай, настільки громіздкі та складні для розуміння, що не можуть бути використані в реал. практиці програмування для ЕОМ. Подальший розвиток математики та техніки поширив та збагатив поняття «А.», що стало використовуватися в таких галузях, як обчислювальна математика, математична та технічна кібернетика, проектування ЕОМ і програмування. Кожна з цих галузей робить свій істот. внесок у розвиток поняття «А.» Так, обчислюв. математика вимагає створення паралел., матрич. та надточних обчислень та є одним з осн. споживачів спеціаліз. обчислюв. структур. Тех. прилади опрацювання інформації є конкретним втіленням різноманіт. моделей А., що відображають арх-ру та фіз. закони, на яких засновані ці прилади. Важл. етап у розвитку алгоритміч. моделей обчислень пов’язаний з роботами в 70-х рр. 20 ст. засновника укр. школи кібернетиків В. Глушкова. В основі його підходу лежить представлення А. у вигляді взаємодії керуючого і інформ. автоматів, назване дискрет. перетворювачем. Таке представлення може бути реалізоване апаратно (центр. процесор, пам’ять ЕОМ) або описане в конструкціях алгоритміч. мови. Автоматна форма задання дискрет. перетворювачів дозволяє застосовувати їх як моделі не тільки програм, але і тех. приладів. Програмуванню відводиться особл. роль як засобу для вираження А. в обчислюв. системах. Сучасне програмування прагне надати розробнику реальних А. багатий арсенал потужних та різноманіт. засобів як для представлення інформації, так і для вираження процесів її опрацювання. Прагнення позбавити користувача зайвої деталізації та кодування при складанні програм призвело в наш час до появи цілого сімейства алгоритміч. мов високого рівня. Цей процес продовжує бурхливо розвиватися та є визначальним у сучас. програмуванні. Повсюдна обчислюв. алгоритмізація виявилася плідною і для внутр. розвитку відповід. галузей науки та техніки. Виникли нові обчислюв. методи, були знайдені зв’язки між окремими ланками складних глобал. явищ у природі та суспільстві, з’явилися нові засоби автомат. керування та проектування, виник новий рівень розуміння складності процесів мислення та розвитку. Приклад. напрямок у теорії А. змусив по новому поглянути на поняття «А.», що призвело до поставлення нового кола нетрадиц. проблем, пов’язаних із засобами виразності, ефективності та адекватності А.

Розмір шрифту

Алгоритм

Рекомендована література

Інформація про статтю