алгорифм, Ч точне розпорядження, до-рої задає обчислювальний процес (званий в цьому випадку алгоритмическим), що починається з довільного вихідного даного (з деякої сукупності можливих для даного А. вихідних даних) і спрямований на отримання повністю визначається цим вихідним даним результату. А. є, напр. відомі з початкової школи правила додавання, віднімання, множення і ділення стовпчиком; в цих А. можливими результатами служать натуральні числа, записані в десятковій системі, а можливими вихідними даними - впорядковані пари таких чисел.
Взагалі кажучи, не передбачається, що результат буде обов'язково отриманий: процес застосування А. до конкретного можливого вихідного даного (т. Е. Алгорітміч. Процесом, який розгортається починаючи з цього даного) може також обірватися безрезультатно (в цьому випадку говорять, що сталася безрезультатна зупинка ) або не закінчиться зовсім. У разі, якщо процес закінчується (відповідно не закінчується) отриманням результату, кажуть, що А. застосуємо (відповідно непридатний) до розглянутого можливого вихідного даному. (Можна побудувати такий А.. Для догрого не існує А. розпізнає за довільним можливого для вихідного даного, застосуємо до нього чи ні, такий А. можна, зокрема, побудувати так, щоб сукупністю його можливих вихідних даних служив натуральний ряд. )
Поняття А. займає одне з центральних місць в сучасній математиці, перш за все обчислювальної. Так, проблема чисельного рішення рівнянь даного типу полягає в знаходженні А. к-рий всяку пару, складену з довільного рівняння цього типу і довільного позитивного раціонального числа. переробляє в число (або набір чисел), що відрізняється (що відрізняються) від кореня (коренів) цього рівняння менше, ніж на. Удосконалення цифрових обчислювальних машин дає можливість реалізувати на них все більш складні А. Однак зустрівся в описує поняття А. формулюванні термін "обчислювальний процес" не слід розуміти у вузькому сенсі тільки цифрових обчислень: вже в шкільному курсі алгебри говорять про буквених обчисленнях, та й в арифметич. обчисленнях з'являються відмінні від цифр символи (дужки, знак рівності, знаки арифметич. дій). Доцільно, таким чином, розглядати А. оперують з довільними символами і їх комбінаціями. Найпростішим випадком такої комбінації є лінійна послідовність символів, що утворює слово, проте можна розглядати і "нелінійні" комбінації - такі, як алгебраїч. матриці, знакосочетаній в сенсі Н. Бурбак (N. Bour-baki), фрази тієї чи іншої мови з розставленими стрілками синтаксич. управління і, взагалі, розмічені тим чи іншим способом графи. Найбільш загальне інтуїтивне розуміння полягає в тому, що вихідними даними і результатами А. можуть служити найрізноманітніші конструктивні об'єкти. Це відкриває можливість широкого застосування поняття А. Можна говорити про А. перекладу з однієї мови на іншу, про А. роботи поїзного диспетчера (переробного інформацію про рух поїздів до наказів) та ін. Прикладах алгорітміч. опису процесів управління; саме тому поняття А. є одним з центральних понять кібернетики.
Приклад алгоритму. Нехай можливими вихідними даними і можливими результатами служать всілякі слова в алфавіті. Домовимося називати перехід від слова xк слову Y "допустимим" в наступних двох випадках (нижче Робозначает довільне слово): 1) X має вигляд АР, а Y має вигляд Рb; 2) Xімеет вид bаР, a Y має вигляд Раbа. Формулюється припис: "взявши до.-л. слово в якості вихідного, роби допустимі переходи до тих пір, поки не вийде слово виду ААР; тоді зупинися, слово Рі є результат". Цей припис утворює А. к-рий позначимо. Візьмемо в якості вихідного даного слово bаbаа. Після одного переходу отримаємо bаааbа, після другого ааbааbа. В силу припису ми повинні зупинитися, результат є bааbа. Візьмемо в якості вихідного даного слово bааbа. Отримаємо послідовно аbааbа, bааbаb, аbаbаbа, bаbаbаb, bаbаbаbа ,. Можна довести, що процес ніколи не скінчиться (т. Е. Ніколи не виникає слово, що починається з аа, і для кожного з виходять слів можна буде зробити допустимий перехід). Візьмемо тепер в якості вихідного даного слово аbааb. Отримаємо bааbb, аbbаbа, bbаbаb. Далі ми не можемо зробити допустимий перехід, і в той же час немає сигналу зупинки. Відбулася безрезультатна зупинка. Отже, можна застосувати до слова bаbаа і непридатний до слів bааbа і аbааb.
Значення алгоритмів. А. зустрічаються в науці на кожному кроці: вміння вирішувати завдання "в загальному вигляді" завжди означає, по суті, володіння недо-рим А. Говорячи, напр. про вміння людини складати числа, мають на увазі не те, що він для будь-яких чисел рано чи пізно зуміє знайти їх суму, а то, що він володіє недо-рим однаковим прийомом складання, які можуть застосовуватися до будь-яких двох конкретних записів чисел, т. е. іншими словами, А. складання (прикладом такого А. і є відоме правило додавання чисел стовпчиком). Поняття завдання "в загальному вигляді" уточнюється за допомогою поняття масова алгоритмічна проблема (м. А. П.). М. а. п. задається серією окремих, одиничних проблем і полягає у вимозі знайти єдиний А. їх вирішення (коли такого А. не існує, кажуть, що розглянута м. а. п. нерозв'язна). Так, проблема чисельного рішення рівнянь даного типу і проблема автоматичного перекладу суть м. А. п. утворюють їх одиничними проблемами є в 1-му випадку проблеми чисельного рішення окремих рівнянь даного типу, а в 2-му випадку - проблеми перекладу окремих фраз. Роллю м. А. до слова baaba виникають послідовно baaba, abaaba, bааbаb і т. д. А при застосуванні, скажімо, А. віднімання стовпчиком до пари (307, 49) послідовно виникнуть такі к. о .:
При цьому в ряді змінюють один одного к. О. кожний наступний повністю визначається (в рамках даного А.) безпосередньо передує. При більш строгому підході передбачається також, що перехід від кожного к. О. до безпосередньо наступного досить "елементарний" - в тому сенсі, що те, що відбувається за один крок перетворення попереднього к. о: в наступний носить локальний характер (перетворенню піддається не весь к. о. а лише недо-раю, заздалегідь обмежена для даного А. його частина, і саме це перетворення визначається не всім попереднім к. о. а лише цієї обмеженою частиною).
Таким чином, поряд з сумами можливих вихідних даних і можливих результатів для кожного А. є ще сукупність можливих проміжних результатів, що представляє собою ту робочу середу, в якій розвивається алгоритми-мич. процес. Для А. все три сукупності збігаються, а для А. віднімання стовпчиком - немає: можливими вихідними даними служать пари чисел, можливими результатами - числа (все в десятковій системі), а можливі проміжні результати суть "триповерхові" записи виду де - запис числа в десятковій системі, - така ж запис або пусте слово, а р - запис числа в десятковій системі з допущенням крапок над нек-римі цифрами. Як правило, для цього А. можна виділити 7 характеризують його (не незалежні) параметрів: 1) сукупність можливих вихідних даних, 2) сукупність можливих результатів, 3) сукупність можливих проміжних результатів, 4) правило початку, 5) правило безпосередньої переробки, 6 ) правило закінчення, 7) правило вилучення результату.
"Уточнення" поняття алгоритму. Поняття А. в його загальному вигляді належить до числа основних первинних понять математики, що не допускають визначення в термінах більш простих понять. Можливі уточнення поняття А. призводять, строго кажучи, до відомого звуження цього поняття. Кожне таке уточнення у -тому, що для кожного із зазначених 7 параметрів А. точно описується недо-рий клас. в межах к-якого цей параметр може змінюватися. Вибір таких класів і відрізняє одне уточнення від іншого. Оскільки 7 параметрів однозначно визначають недо-рий А. то вибір 7 класів зміни цих параметрів визначає недо-рий клас А. Однак такий вибір може претендувати на назву "уточнення", лише якщо є переконання, що для довільного А. має допускаються даними вибором сукупності можливих вихідних даних і можливих результатів, то, можливо зазначений рівносильний йому А. з визначеного цим вибором класу А. Це переконання формулюється для кожного уточнення у вигляді основної гіпотези, к-раю - при сучасному рівні наших предст авленій - не може бути предметом математичного-докази.
Перші уточнення описаного типу запропонували в 1936 Е. Л. Пост (Е. L. Post, см. [5]) і А. М. Тьюринг (А. М. Turing, см. [3], [4]), їх конструкції багато в чому передбачили ідеї, закладені в основу сучасних цифрових обчислювальних машин. Відомі також уточнення, сформульовані А. А. Марковим (див. [10], [11], Нормальний алгорифм) .і А. Н. Колмогоровим (див. [12], [13]; останній запропонував трактувати конструктивні об'єкти як топологіч. комплекси певного виду, що дало можливість уточнити властивість "локальності" перетворення). Для кожного із запропонованих уточнень відповідна основна гіпотеза добре узгоджується з практикою. На користь цієї гіпотези говорить і те, що, як можна довести, всі запропоновані уточнення в недо-ром природному сенсі еквівалентні один одному.
Як приклад розглянемо уточнення, запропоноване А. М. Тьюрингом. У своєму оригінальному вигляді це уточнення полягало в описі деякої абстрактної обчислювальної машини, що складається з: 1) нескінченної стрічки, розбитою на наступні один за одним в лінійному порядку осередки, причому в кожному осередку записаний до.-л. символ з так зв. "Зовнішнього алфавіту" машини, і 2) каретки, що знаходиться в кожен момент в недо-ром "стані" (із заданого кінцевого списку станів), здатної переміщатися уздовж стрічки і змінювати вміст комірок; А. обчислень на такій машині ( "тиорінгов А.") задається у вигляді програми, що управляє діями каретки. Більш докладний і точний опис см. В статті Тьюрінга машина; тут наводиться модернізоване виклад конструкції Тьюринга в термінах, зазначених вище 7 параметрів. Щоб задати тиорінгов А. треба вказати: а) попарно непересічні алфавіти Б, Д, Ч з виділеної в Дбуквой і виділеними в Чбуквамі і. б) набір пар виду. де. а Тесть один з трьох знаків -. 0, +, причому передбачається, що в цьому наборі (наз. Програмою) немає 2 пар з однаковими першими членами. Параметри А. задаються так: можливими вихідними даними і можливими результатами служать слова в Б, а можливими проміжними результатами - слова в алфавіті містять не більше однієї літери з Ч. Правило початку: вихідне слово Рпереводітся в слово. Правило закінчення: заключним є проміжний результат, що містить зі. Правило вилучення результату: результатом оголошується ланцюжок всіх тих букв заключного проміжного результату, до-раю йде слідом за w і передує першій букві, яка не належить Б. правило безпосередньої переробки, що переводить. полягає в наступному. Приписуємо до Аслева і праворуч букву; потім в утворився слові частина виду. де. . замінюємо на слово Qпо наступним правилом: в програмі шукається пара з першим членом; нехай другий член цієї пари є; якщо є -, то; якщо Тесть 0, то; якщо Тесть +, то виникає після цієї заміни слово і є А '.
Літ. см. [3] - [5], [10] - [13] при СТ. Алгоритмів теорія, В. А. Успенський.
Математична енциклопедія. - М. Радянська енциклопедія. І. М. Виноградов. 1977-1985.