Алгоритм

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

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

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

Літ.: Селін О. М. Алгоритми та структури даних: Кон­спект лекцій. К., 1995; Ющенко К. Л., Суржко С. В. та ін. Алгоритмічні алгебри: Навч. посіб. К., 1997; Лиман Ф. М. Математична логіка і теорія алгоритмів. С., 1998; Салпагарова А. А. Вероятностный анализ задачи и статистически эф­фективный алгоритм. К., 1998.

А. В. Анисимов

Завантажити статтю