1.2. јлгоритми. ѕон¤тт¤ алгоритму в математиц≥ таке ж давнЇ ≥ фун≠даментальне, ¤к, скаж≥мо, пон¤тт¤ числа. Ќаприклад, алгоритмов≥ ≈вкл≥да не менш ¤к 22 сотн≥ рок≥в. ѕод≥бно до того, ¤к розвивалось у¤вленн¤ про д≥йсн≥ числа, в≥д в≥дкритт¤ давньогрецькими математиками несп≥вм≥рност≥ довжин сторони квадрата ≥ його д≥агонал≥ ≥ аж до ч≥тких конструкц≥й та означень, розроблених у друг≥й половин≥ 19 стол≥тт¤ √.  антором, Ў. ћере, –. ƒедек≥ндом та  . ¬аЇрштрасом, пон¤тт¤ алгоритму теж уточнювалось ≥ було строго означене у перш≥й половин≥ нашого стол≥тт¤. ѕерш≥ формал≥зац≥њ запропонували у 1936 роц≥ ≈. ѕост ≥ ј. “ьюр≥нг, випередивши по¤ву обчислю≠вальноњ техн≥ки, ¤ка значною м≥рою грунтуЇтьс¤ на т≥й же ≥деолог≥њ. «годом були запропонован≥ й ≥нш≥ означенн¤, зокрема ј. ј. ћарковим та ј. ћ.  олмогоровим, ≥ вс≥ вони ви¤вились екв≥валентними м≥ж собою. ‘ормал≥зац≥¤ пон¤тт¤ алгоритму Ї видатним дос¤гненн¤м математичноњ лог≥ки, оск≥ль≠ки лише з по¤вою строгого означенн¤ алгоритму стало можливим доводити дл¤ певних задач, що жоден алгоритм не здатен њх розв'¤зати. “ак≥ задач≥ називаютьс¤ алгоритм≥чно нерозв'¤зними. “ак, задача розп≥знаванн¤, чи заданий многочлен в≥д к≥лькох зм≥нних з ц≥лими коеф≥ц≥Їнтами маЇ ц≥л≥ нул≥, Ї алгоритм≥чно нерозв'¤зною (дес¤та проблема √≥льберта). «азначимо дл¤ пор≥вн¤нн¤, що у випадку многочлен≥в в≥д одн≥Їњ зм≥нноњ дл¤ под≥бноњ задач≥ алгоритм в≥домий.

 оли йтиметьс¤ про алгоритм, то вважатимутьс¤ заф≥ксованими два алфав≥ти Ч вх≥дний †та вих≥дний . –обота алгоритму пол¤гаЇ в тому, що в≥н отримуЇ на вх≥д слово у вх≥дному алфав≥т≥ Ч вх≥д, ≥ ¤к результат виконанн¤ посл≥довност≥ елементарних операц≥й, подаЇ на вих≥д слово у вих≥дному алфав≥т≥ Ч вих≥д. ѕон¤тт¤ елементарноњ опе≠рац≥њ або кроку роботи Ї складовою формального означенн¤ алгоритму. ћи нe будемо уточнювати це пон¤тт¤, апелюючи до його побутово-програм≥стського розум≥нн¤.

јлгоритм розв'¤зув масову задачу, ¤кщо, отримавши на вх≥д будь-¤ку ≥ндив≥дуальну задачу , в≥н за ск≥нченну к≥льк≥сть крок≥в подаЇ на вих≥д њњ розв'¤зок. «алежно в≥д типу задач≥ говоримо, що алгоритм обчислюЇ функц≥ю, розп≥знаЇ множину чи мову, знаходить елемент ≥з певною властив≥стю. ” випадку задач≥ розп≥знаванн¤, ¤кщо алгоритм подаЇ на вих≥д 1, то кажемо, що в≥н приймаЇ вх≥д, а ¤кщо 0, то кажемо, що алгоритм в≥дхил¤Ї вх≥д.

ƒовжиною входу †називаЇтьс¤ к≥льк≥сть букв у слов≥ , ¤ку ми домовились позначати ¤к . Ќехай †Ч де¤ка функц≥¤. јлгоритм розв'¤зуЇ задачу за час , ¤кщо на кожному вход≥ †в≥н робить не б≥льше, н≥ж †крок≥в. якщо †дл¤ де¤коњ константи , то алгоритм розв'¤зуЇ задачу за пол≥ном≥альний в≥д довжини входу час. “акий алгоритм називають пол≥ном≥альним, а задачу пол≥ном≥ально розв '¤зною.

ѕон¤тт¤ пол≥ном≥ального часу е центральною концепц≥Їю теор≥њ складност≥ обчислень. ¬ рамках ц≥Їњ концепц≥њ вважаЇтьс¤, що пол≥ном≥альн≥ алгоритми в≥дпов≥дають швидким, ефективним на практиц≥ алгоритмам; а пол≥ном≥ально розв'¤зн≥ задач≥ в≥дпов≥дають легким за≠дачам, ¤к≥ можуть бути розв'¤заними за прийн¤тний час на входах довжини, що маЇ практичний ≥нтерес. „асто пол≥ном≥альний алгоритм справд≥ задовольн¤Ї вс≥ практичн≥ проблеми. ¬ г≥ршому ж випадку його можна вважати швидким лише асимптотично, а на в≥дносно неве≠ликих входах алгоритм може працювати довго.

—л≥д п≥дкреслити, що клас пол≥ном≥ально розв'¤зних задач не зале≠жить в≥д того, ¤ка саме з багатьох можливих формал≥зац≥й алгоритму вибрана. ÷ей факт можна строго довести ¤к теорему дл¤ будь-¤ких двох означень алгоритму.

 лас пол≥ном≥ально розв'¤зних задач найчаст≥ше не залежить ≥ в≥д способу, в ¤кий задача сформульована. Ќаприклад, задача множенн¤ натуральних чисел ефективно розв'¤зуЇтьс¤ ¤к у дв≥йков≥й, так ≥ в де≠с¤тков≥й системах численн¤. ¬икористанн¤ ≥ншого алфав≥ту не здатне суттЇво прискорити обчисленн¤ (тобто зменшити час ¤к функц≥ю в≥д довжини входу). ¬ин¤тком е формулюванн¤ задач≥ в односимвольному алфав≥т≥. ћи виключаЇмо цей випадок з нашого розгл¤ду ¤к такий, що не маЇ застосувань.

јлгоритм, ¤кий на неск≥нченн≥й посл≥довност≥ вход≥в робить б≥льше ¤к крок≥в, де †довжина входу, а †> 0 - де¤ка константа, назива≠Їтьс¤ експоненц≥йним. ѕро такий алгоритм кажуть, що в≥н вимагаЇ експоненц≥йного часу. ≈кспоненц≥йн≥ алгоритми в≥дпов≥дають загаль≠ним у¤вленн¤м про пов≥льн≥, неефективн≥ на практиц≥ алгоритми. як приклад згадаЇмо алгоритм ламанн¤ шифру повним перебором ключ≥в. «адачу, ¤ка може бути розв'¤зана лише експоненц≥йним алгоритмом, сл≥д визнати важкою. “иповою Ї ситуац≥¤, коли дл¤ задач≥ в≥дом≥ ли≠ше експоненц≥йн≥ алгоритми, але не вдаЇтьс¤ довести, що кращих не ≥снуЇ. Ќа практиц≥ така задача теж вважаЇтьс¤ важкою (до моменту, поки дл¤ нењ не буде знайдено ефективного алгоритму, ¤кщо такий все ж ви¤витьс¤). як приклад наведемо задачу пошуку, на важкост≥ ¤коњ грунтуЇтьс¤ чимало сучасних криптосистем:

«адано: .

«найти: нетрив≥альний д≥льник числа .

¬арто уточнити, що експоненц≥йний алгоритм Ї пов≥льним у найг≥ршому випадку Ч досить, щоб в≥н затрачав час †хоча б на одному з †вход≥в довжини , де †к≥льк≥сть букв у вх≥дному алфав≥т≥. ћоже трапитись, що пов≥льний в найг≥ршому випадку алгоритм Ї досить швидким у середньому, тобто дл¤ переважноњ б≥льшост≥ вход≥в довжини . («ауважимо, що можуть розгл¤датис¤ р≥зн≥ ймов≥рн≥сн≥ розпод≥ли на множин≥ вход≥в довжини †Ч р≥вном≥рний розпод≥л не завжди найприродн≥ший.) ’оч ≥ експоненц≥йний, але швидкий у середньому алгоритм може бути ц≥лком придатним дл¤ практич≠них потреб. ѕоказовим прикладом Ї симплекс-метод дл¤ задач≥ л≥н≥йного програмуванн¤. Ќа¤вн≥сть алгоритм≥в, ¤к≥ добре працюють в середньому, сл≥д враховувати при оц≥нц≥ складност≥ задач≥.

ЌагадаЇмо, що множина ≥ндив≥дуальних задач Ї множиною вс≥х сл≥в у де¤кому алфав≥т≥ . ≤нколи Ї сенс розгл¤дати звуженн¤ масовоњ за≠дач≥ на де¤ку п≥дмножину ≥ндив≥дуальних задач . јлгоритм розв'¤зуЇ звужену задачу, ¤кщо в≥н видаЇ правильний розв'¤зок дл¤ ≥н≠див≥дуальних задач ≥з множини †(а на вс≥х ≥нших входах може подавати на вих≥д будь-що, або й взагал≥ не зупин¤тись).