Алгоритм, алгорифм, одне з основних понять (категорій) математики, що не володіють формальним визначенням в термінах простіших понять, а абстрагуються безпосередньо з досвіду. А. є, наприклад, відомі з початкової школи правила складання, віднімання, множення і ділення стовпчиком. Взагалі, під А. розуміється всяке точне розпорядження, яке задає обчислювальний процес (званий в цьому випадку алгоритмічним), що починається з довільного вихідного даного (з деякої сукупності можливих для даного А. вихідних даних) і направленого на здобуття повністю визначуваного цим вихідним даним результату; наприклад, в згаданих А. арифметичних дій можливими результатами можуть бути натуральні числа, записані в десятковій системі, а можливими вихідними даними впорядковані пари таких чисел, і вміст розпорядження, т. о., окрім інструкції по розгортанню алгоритмічного процесу, повинно входити також: 1) вказівка сукупності можливих вихідних даних (ст і. д.) і 2) правило, по якому процес визнається таким, що закінчився зважаючи на досягнення результату. Не передбачається, що результат буде обов'язково отриманий: процес вживання А. до конкретного ст і. д. (тобто алгоритмічний процес, що розгортається починаючи з цього даного) може також обірватися безрезультатно або не закінчитися зовсім. У випадку, якщо процес закінчується (відповідно не закінчується) здобуттям результату, говорять, що А. застосуємо (відповідно непридатний) до даного ст і. д. (Можна побудувати такий А. Á, для якого не існує А., що розпізнає по довільному можливому для Á вихідному даному, застосовний до нього Á чи ні; такий А. Á можна, зокрема, побудувати так, щоб сукупністю його ст і. д. служив натуральний ряд.)
Поняття А. займає одне з центральних місць в сучасній математиці, перш за все обчислювальній. Так, проблема чисельного вирішення рівнянь даного типа зводиться до відшукання А., який всяку пару, складену з довільного рівняння цього типа і довільного раціонального числа e, переробляє в число (або набір чисел) менше, ніж на e, що відрізняється (що відрізняються) від кореня (коріння) цього рівняння. Удосконалення обчислювальних машин дає можливість реалізувати на них усе більш складні А. Однако що зустрівся в тій, що описує поняття А. формулюванню термін «обчислювальний процес» не слід розуміти у вузькому сенсі лише цифрових обчислень. Так, вже в шкільному курсі алгебри говорять про буквені обчислення, та і в арифметичних обчисленнях з'являються відмінні від цифр символи: дужки, знак рівності, знаки арифметичних дій. Можна піти далі і розглядати обчислення з довільними символами і їх комбінаціями; саме такий широким розумінням користуються при описі поняття А. Так, можна говорити про А. перекладу з однієї мови на іншій, про А. роботи поїздового диспетчера (що переробляє інформацію про рух поїздів в накази) і ін. прикладах алгоритмічного опису процесів управління; саме тому поняття А. є одним з центральних понять кібернетики. Взагалі, вихідними даними і результатами А. можуть служити найрізноманітніші конструктивні об'єкти; наприклад, результатами т.з. що розпізнають А. служать слова «так і ні».
Приклад алгоритму . Ст і. д. і можливими результатами хай служать всілякі кінцеві послідовності букв а і b («слова в алфавіті {а, b}») . Умовимося називати перехід від слова Х до слова Y «допустимим» в наступних двох випадках (нижче Р позначає довільне слово): 1) Х має вигляд аР, а Y має вигляд Pb; 2) X має вигляд bap, а Y має вигляд Paba. Формулюється розпорядження : «узявши яке-небудь слово як початковий, роби допустимі переходи до тих пір, поки не вийде слово вигляду aap; тоді зупинися, слово Р і є результат». Це розпорядження утворює А., який позначимо через Â. Візьмемо за вихідний даний слово babaa. Після одного переходу отримаємо baaaba, після другого aabaaba. Через розпорядження ми повинні зупинитися, результат є baaba. Візьмемо за вихідний даний слово baaba. Отримаємо послідовно abaaba baabab, abababa, bababab, babababa ... Можна довести, що процес ніколи не кінчиться (тобто ніколи не виникає слово, що починається з aa і для кожного із слів, що виходять, можна буде зробити допустимий перехід). Візьмемо тепер за вихідний даний слово abaab. Отримаємо baabb, abbaba, bbabab. Далі ми не можемо зробити допустимий перехід, і в той же час немає сигналу зупинки. Сталася т.з. «безрезультативна зупинка». Отже Â застосуємо до слова babaa і непридатний до слів baaba і abaab.
Значення А. А. у науці зустрічаються на кожному кроці; уміння вирішувати задачу «загалом віде"всегда означає, по суті, володіння деяким А. Кажучи, наприклад, про уміння людини складати числа, мають на увазі не те, що він для будь-яких двох чисел рано чи пізно зуміє знайти їх суму, а то, що він володіє деяким одноманітним прийомом складання, застосовним до будь-яких двом конкретним записам чисел, тобто іншими словами, А. складання (прикладом такого А. і є відоме правило складання чисел стовпчиком). Поняття завдання «в загальному вигляді» уточнюється за допомогою поняття масова проблема (м. п.). М.п. задається серією окремих, одиничних проблем і полягає у вимозі знайти загальний метод (тобто А.) їх рішення. Так, проблема чисельного вирішення рівнянь даного типа і проблема автоматичного переведення суть м. п.: створюючими їх одиничними проблемами є в 1-м-коді випадку проблеми чисельного вирішення окремих рівнянь даного типа, а в 2-м-коді випадку — проблеми переведення окремих фраз. Роллю м. п. і визначається як значення, так і сфера додатка поняття А. М. п. надзвичайно характерні і важливі для математики: наприклад, в алгебрі виникають м.п. перевірки рівності алгебри різних типів, в математичній логіці — м. п. розпізнавання виводимості пропозиції із заданих аксіом і тому подібне (для математичної логіки поняття А. істотно ще і тому, що на нього спирається центральне для математичної логіки поняття числення, що служить узагальненням і уточненням інтуїтивних понять «виводу» і «доказу»). Встановлення нерозв'зності якої-небудь масової проблеми (наприклад, проблеми розпізнавання істинності або довідності для якого-небудь логіко-математичної мови), тобто відсутність єдиного А., що дозволяє знайти вирішення всіх одиничних проблем даної серії, є важливим пізнавальним актом, що показує, що для вирішення конкретних одиничних проблем принципово необхідні специфічні для кожної такої проблеми методи. Існування нерозв'язних м. п. служить, т. о., проявом невичерпності процесу пізнання.
Змістовні явища, які лягли в основу освіти поняття «А.», відвіку займали важливе місце в науці. З прадавніх часів багато завдань математики полягали у пошуках тих або інших конструктивних методів. Ці пошуки, що особливо посилилися у зв'язку із створенням зручної символіки, а також осмислення принципової відсутності шуканих методів у ряді випадків (завдання про квадратуру круга і подібні до неї) — все це було потужним чинником розвитку наукових знань. Усвідомлення неможливості вирішити завдання прямим обчисленням привело до створенню в 19 ст теоретико-множинної концепції . Лише після періоду бурхливого розвитку цієї концепції (в рамках якої питання про конструктивні методи в сучасному їх розумінні взагалі не виникає) виявилося можливим в середині 20 в знов повернутися до питань конструктивності, але вже на новому рівні, збагаченому поняттям А. Ето, що викристалізувалося, поняття лягло в основу особливого конструктивного напряму в математиці.
Само слово «А.» походить від algorithmi, що є, у свою чергу, латинською транслітерацією арабського імені хорезмійського математика 9 ст аль-Хорезмі . У середньовічній Європі А. називається десяткова позиційна система числення і мистецтво рахунку в ній, оскільки саме завдяки латинському переведенню (12 ст) трактату аль-Хорезмі Європа познайомилася з позиційною системою.
Будова алгоритмічного процесу. Алгоритмічний процес є процес послідовного перетворення конструктивних об'єктів (до. о.), що відбувається дискретними «кроками»; кожен крок полягає в зміні одного до. о. іншим. Так, при вживанні А. Ã до слова baaba виникають послідовно baaba, abaaba, baabab і так далі А при вживанні, скажімо, А. віднімання стовпчиком до пари <307, 49> послідовно виникнуть такі до. о.:
При цьому у ряді тих, що змінюють один одного до. о. кожен подальший повністю визначається (в рамках даного А.) безпосередньо передуючим. При строгішому підході передбачається також, що перехід від кожного до. о. до безпосередньо наступному досить «елементарний» — в тому сенсі, що перетворення попереднього, що відбувається за один крок, до. о. в наступний носить локальний характер (перетворенню піддається не весь до. о., а лише деяка, заздалегідь обмежена для даного А. його частина і само це перетворення визначається не всім попереднім до. о., а лише цією обмеженою частиною).
Т. о., поряд з совокупностямі можливих вихідних даних і можливих результатів, для кожного А. є ще сукупність проміжних результатів (п. р.), що є тим робочим середовищем, в якому розвивається алгоритмічний процес. Для Ã всі три сукупності збігаються, а для А. віднімання стовпчиком — ні: можливими вихідними даними служать пари чисел, можливими результатами — числа (все в десятковій системі), а проміжні результати суть «триповерхові» записи вигляду
де q — є запис числа в десятковій системі, r — такий запис або порожнє слово, а р — запис числа в десятковій системі з допущенням крапок над деякими цифрами.
Робота А. починається підготовчим кроком, на якому можливе вихідне дане перетвориться в початковий член ряду проміжних результатів, що змінюють один одного; це перетворення відбувається на основі спеціального, такого, що входить до складу того, що розглядається А. «правила почала». Це правило для Ã полягає у вживанні тотожного перетворення, а для А. віднімання — в заміні пари<а, b> на запис
Потім застосовується «правило безпосередньої переробки», що здійснює послідовні перетворення кожного виникаючого проміжного результату в наступний. Ці перетворення відбуваються до тих пір, поки деяке випробування, якому піддаються всі проміжні результати у міру їх виникнення, не покаже, що даний проміжний результат є завершальним; це випробування виробляється на основі спеціального «правила закінчення». Наприклад, для Ã правило закінчення полягає в перевірці, чи не починається проміжний результат на aa. (Якщо ні для якого з виникаючих проміжних результатів правило закінчення не дає сигналу зупинки, то або до кожного з виникаючих проміжних результатів застосовно правило безпосередньої переробки, і алгоритмічний процес продовжується необмежено, або ж до деякого проміжного результату правило безпосередньої переробки виявляється непридатним, і процес закінчується безрезультатно.) Нарешті, із завершального проміжного результату — також на основі спеціального правила — витягується остаточний результат; для Ã це витягання полягає у відкиданні перших двох букв а, а для А. віднімання — у відкиданні всього, окрім самої нижньої строчки цифр. (У багатьох важливих випадках правило почала і правило витягання результату задають тотожні перетворення і тому окремо не формулюються.) Т. о., для кожного А. можна виділити 7 параметрів, що характеризують його (не незалежних!): 1) сукупність можливих вихідних даних, 2) сукупність можливих результатів, 3) сукупність проміжних результатів, 4) правило почала, 5) правило безпосередньою переробки, 6) правило закінчення, 7) правило витягання результату.
« Уточнення» поняття А. Можливі подальші «уточнення» поняття А., що приводять, строго кажучи, до відомого звуження цього поняття. Кожне таке уточнення полягає в тому, що для кожного з вказаних 7 параметрів А. точно описується деякий клас, в межах якого цей параметр може мінятися. Вибір цих класів і відрізняє одне уточнення від іншого. У багатьох уточненнях всі класи, окрім двох — класу совокупностей проміжних результатів і класу правил безпосередньої переробки, — вибираються одиничними, тобто всі параметри, окрім вказаних два, жорстко фіксуються. Оскільки 7 параметрів однозначно визначають деякий А., то вибір 7 класів зміни цих параметрів визначає деякий клас А. Однако такий вибір може претендувати на назву «уточнення», лише якщо є переконання, що для довільного А., що має що допускаються даним вибором сукупності можливих вихідних даних і можливих результатів, може бути вказаний рівносильний йому А. з визначеного даним вибором класу А. Ето переконання формулюється для кожного уточнення у вигляді основної гіпотези, яка, — при сучасному рівні наших вистав — не може бути предметом математичного доказу.
Перші уточнення описаного типа запропонували в 1936 американський математик Е. Л. Пост і англійський математик А. М. Тьюрінг (див. Т'юринга машина ) . Відомі також уточнення, сформульовані радянськими математиками А. А. Марковим (див. Нормальний алгоритм ) і А. Н. Колмогоровим (останній запропонував трактувати конструктивні об'єкти як топологічні комплекси певного вигляду, що дало можливість уточнити властивість «локальності» перетворення). Для кожного із запропонованих уточнень відповідна основна гіпотеза добре узгоджується з практикою. На користь цієї гіпотези говорить і те, що, як можна довести, всі запропоновані уточнення в деякому природному сенсі еквівалентні один одному.
Як приклад приведемо (у модернізованому вигляді) уточнення запропоноване Т'юрингом. Щоб задати тьюрінгов А., треба вказати: а) попарно алфавіти, що не перетинаються, Би, Д, Ч з виділеною в Д буквою l і виділеними в Ч буквами а і w, би) набір пар виду < рx, htq >, де р, qîЧ, x, hîБÈД, а Т є один із знаків —, 0 +, причому передбачається, що в цьому наборі (званою програмою) немає 2 пар з однаковими першими членами. Параметри А. задаються так: можливими вихідними даними і можливими результатами служать слова в Б, а проміжними результатами — слова в БèДÈЧ, що містять не більш за одну букву з Ч. Правіло почала: вихідне слово Р переводиться в слово laРl. Правило закінчення: завершальним є проміжний результат, w, що містить. Правило витягання результату: результатом оголошується ланцюжок всіх тих букв завершального проміжного результату, яка йде услід за w. і передує першій букві, не належною Б. Правіло безпосередньої переробки, що переводить А в А'', полягає в наступному. Приписуємо до А зліва і справа букву l; потім в слові, що утворилося, частина вигляду erx, де рîЧ, замінюємо на слово Q за наступним правилом: у програмі шукається пара з першим членом рx; хай другий член цієї пари є htq; якщо Т є - , то Q = qeh, Якщо Т є 0, то Q =eqh; якщо Т є +, то Про = ehq . слово, що Виникає після цієї заміни, і є А''.
Див. також ст. Алгоритмів теорія і літ.(літературний) при цій статті.
