Òåîðèÿ àëãîðèòìîâ — ðàçäåë ìàòåìàòèêè, èçó÷àþùèé îáùèå ñâîéñòâà àëãîðèòìîâ. Ïîíÿòèå «àëãîðèòì» ñôîðìèðîâàëîñü â ìàòåìàòèêå â 20-õ ãîäàõ XX â. Íà÷àëîì ñèñòåìàòè÷åñêîé ðàçðàáîòêè òåîðèè àëãîðèòìîâ ìîæíî ñ÷èòàòü 1936 ã. è ñâÿçûâàþò ýòî íà÷àëî ñ ïóáëèêàöèåé ðàáîòû À.À. ×åð÷à.
Ïîä àëãîðèòìîì âñåãäà (è äî âîçíèêíîâåíèÿ ñòðîãîé òåîðèè) ïîíèìàëàñü ïðîöåäóðà, êîòîðàÿ ïîçâîëÿëà ïóòåì âûïîëíåíèÿ ïîñëåäîâàòåëüíîñòè ýëåìåíòàðíûõ øàãîâ ïîëó÷àòü îäíîçíà÷íûé ðåçóëüòàò (íåçàâèñÿùèé îò òîãî, êòî èìåííî âûïîëíÿë ýòè øàãè) èëè çà êîíå÷íîå ÷èñëî øàãîâ ïðèéòè ê âûâîäó î òîì, ÷òî ðåøåíèÿ íå ñóùåñòâóåò.
Êîíå÷íî æå ýòî íåñòðîãîå îïðåäåëåíèå ïîíÿòèÿ àëãîðèòìà è èìåííî ïîïûòêè ñôîðìóëèðîâàòü òàêîå ïîíÿòèå ïðèâåëè ê âîçíèêíîâåíèþ òåîðèè àëãîðèòìîâ. Ïðè÷èíîé ðàçâèòèÿ ýòîé òåîðèè áûëè âíóòðåííèå ïðîáëåìû ìàòåìàòèêè è ëèøü ñ âîçíèêíîâåíèåì è ðàçâèòèåì âû÷èñëèòåëüíîé òåõíèêè è ñìåæíûõ íàóê âûÿñíèëîñü, ÷òî â îñíîâå ýòèõ íàóê äîëæíà ëåæàòü òåîðèÿ àëãîðèòìîâ. Òàê ñòàëî î÷åâèäíûì ïðèêëàäíîå çíà÷åíèå íîâîé íàóêè.
 îñíîâå ôîðìàëèçàöèè ïîíÿòèÿ «àëãîðèòì» ëåæèò èäåÿ ïîñòðîåíèÿ àëãîðèòìè÷åñêîé ìîäåëè. Ñîñòàâëÿþùèìè òàêîé ìîäåëè äîëæíû áûòü êîíêðåòíûé íàáîð ýëåìåíòàðíûõ øàãîâ, ñïîñîáû îïðåäåëåíèÿ ñëåäóþùåãî øàãà è ò.ä. Îò ìîäåëè òàêæå òðåáóåòñÿ ïðîñòîòà è óíèâåðñàëüíîñòü. Òðåáîâàíèå ïðîñòîòû âàæíî äëÿ òîãî, ÷òîáû âûäåëèòü äåéñòâèòåëüíî íåîáõîäèìûå ýëåìåíòû è ñâîéñòâà àëãîðèòìà è îáëåã÷èòü äîêàçàòåëüñòâà îáùèõ óòâåðæäåíèé îá ñâîéñòâàõ. Óíèâåðñàëüíîñòü íåîáõîäèìà äëÿ òîãî, ÷òîáû ìîäå ïîçâîëÿëà îïèñàòü ëþáîé àëãîðèòì.
Ðåçóëüòàòàìè òåîðåòè÷åñêèõ èññëåäîâàíèé ÿâèëèñü òðè îñíîâíûõ êëàññà àðèôìåòè÷åñêèõ ìîäåëåé.
Ïåðâûé êëàññ ìîäåëåé îñíîâàí íà àðèôìåòèçàöèè àëãîðèòìîâ. Ïðåäïîëàãàåòñÿ, ÷òî ëþáûå äàííûå ìîæíî çàêîäèðîâàòü ÷èñëàìè, êàê ñëåäñòâèå - âñÿêîå èõ ïðåîáðàçîâàíèå ñòàíîâèòñÿ â ýòîì ñëó÷àå àðèôìåòè÷åñêèì âû÷èñëåíèåì, àëãîðèòìîì â òàêèõ ìîäåëÿõ åå âû÷èñëåíèå çíà÷åíèÿ íåêîòîðîé ÷èñëîâîé ôóíêöèè, à åãî ýëåìåíò» òàðíûå øàãè - àðèôìåòè÷åñêèå îïåðàöèè. Ïîñëåäîâàòåëüíîñòü øàãîâ îïðåäåëÿåòñÿ äâóìÿ ñïîñîáàìè. Ïåðâûé ñïîñîá - ñóïåðïîçèöèÿ, ò.å. ïîäñòàíîâêà ôóíêöèè â ôóíêöèþ, à âòîðîé - ðåêóðñèÿ, ò.å. îïðåäåëåíèå çíà÷åíèÿ ôóíêöèè ÷åðåç «ðàíåå» âû÷èñëåííûå çíà÷åíèÿ ýòîé æå ôóíêöèè. Ôóíêöèè, êîòîðûå ìîæíî ïîñòðîèòü èç öåëûõ ÷èñåë è àðèôìåòè÷åñêèõ îïåðàöèé ñ ïîìîùüþ ñóïåðïîçèöèé ðåêóðñèâíûõ îïðåäåëåíèé, íàçûâàþòñÿ ðåêóðñèâíûìè ôóíêöèÿìè. Ïðîñòåéøèì ïðèìåðîì ðåêóðñèâíîé ôóíêöèè ÿâëÿåòñÿ ôàêòîðèàë.
Âòîðîé êëàññ ìîäåëåé ïîðîæäåí ñëåäóþùåé èäååé. Äëÿ òîã ÷òîáû àëãîðèòì ïîíèìàëñÿ îäíîçíà÷íî, à åãî êàæäûé øàã ñ÷èòàëñÿ ýëåìåíòàðíûì è âûïîëíèìûì, îí äîëæåí áûòü ïðåäñòàâëåí ÷òîáû åãî ìîãëà âûïîëíÿòü ìàøèíà, ê êîòîðîé ïðåäúÿâëÿþòñÿ óæå óïîìÿíóòûå òðåáîâàíèÿ ïðîñòîòû è óíèâåðñàëüíîñòè. Îäíîé èç ìàøèí ÿâèëàñü àáñòðàêòíàÿ ìàøèíà Òüþðèíãà. Ìàøèíà Òüþðèíãà ñîñòîèò èç òðåõ ÷àñòåé ëåíòû, ãîëîâêè è óïðàâëÿþùåãî óñòðîéñòâà (ÓÓ). Ëåíòà áåñêîíå÷íà â îáå ñòîðîíû è ðàçáèòà íà ÿ÷åéêè. Ýëåìåíòàðíûé øàã ìàøèíû Òüþðèíãà ñîñòîèò èç ñëåäóþùèõ äåéñòâèé:
ãîëîâêà ñ÷èòûâàåò ñèìâîë, çàïèñàííûé â ÿ÷åéêå, íàä êîòîðîé îíà íàõîäèòñÿ;
ñ÷èòàííûé ñèìâîë è òåêóùåå ñîñòîÿíèå ãîëîâêè îäíîçíà÷íî îïðåäåëÿþò íîâîå ñîñòîÿíèå, íîâûé çàïèñûâàåìûé ñèìâîë è ïåðåìåùåíèå ãîëîâêè (êîòîðîå ìîæåò èìåòü çíà÷åíèå íà ÿ÷åéêó âëåâî, íà ÿ÷åéêó âïðàâî, îñòàòüñÿ íà ìåñòå).
Óñòðîéñòâî óïðàâëåíèÿ õðàíèò è âûïîëíÿåò êîìàíäû ìàøèíû.
Òðåòèé êëàññ ìîäåëåé àëãîðèòìîâ î÷åíü áëèçîê ê ïðåäûäóùåìó, íî íå îïåðèðóåò êîíêðåòíûìè ìàøèííûìè ìåõàíèçìàìè. Íàèáîëåå èçâåñòíàÿ àëãîðèòìè÷åñêàÿ ìîäåëü ýòîãî òèïà - íîðìàëüíûå àëãîðèòìû Ìàðêîâà.
Äëÿ íîðìàëüíîãî àëãîðèòìà çàäàåòñÿ àëôàâèò, íàä êîòîðûì îí ðàáîòàåò, êîíå÷íîå ìíîæåñòâî äîïóñòèìûõ ïîäñòàíîâîê è ïîðÿäîê èõ ïðèìåíåíèÿ. Åñëè â êà÷åñòâå àëôàâèòà âçÿòü àëôàâèò ðóññêîãî ÿçûêà, à â êà÷åñòâå ìíîæåñòâà ïîäñòàíîâîê òî, èñïîëüçóÿ ïðàâèëà 1—3:
1) ïðîâåðèòü âîçìîæíîñòü ïîäñòàíîâîê â ïîðÿäêå âîçðàñòàíèÿ èõ íîìåðîâ, è åñëè îíà âîçìîæíà (ëåâàÿ ÷àñòü ïîäñòàíîâêè îáíàðóæåíà â èñõîäíîì ñëîâå), ïðîèçâåñòè ïîäñòàíîâêó (çàìåíèâ ëåâóþ ÷àñòü íà ïðàâóþ);
2) åñëè â ïðèìåíåííîé ïîäñòàíîâêå èìååòñÿ ñèìâîë «!», òî ïðåîáðàçîâàíèÿ ïðåêðàùàþòñÿ, à åñëè íåò, òî òåêóùåå ñîñòîÿíèå ñòàíîâèòñÿ èñõîäíûì è âåñü ïðîöåññ íà÷èíàåòñÿ çàíîâî;
3) åñëè íè îäíà ïîäñòàíîâêà íå ïðèìåíèìà, òî ïðîöåññ ïðåîáðàçîâàíèÿ çàâåðøåí, ìîæíî îáíàðóæèòü, ÷òî ïî çàäàííîìó àëãîðèòìó èñõîäíîå ñëîâî.
 òåîðèè àëãîðèòìîâ ñòðîãî äîêàçàíî, ÷òî ïî ñâîèì âîçìîæíîñòÿì ïðåîáðàçîâàíèÿ íîðìàëüíûå àëãîðèòìû ýêâèâàëåíòíûå ìàøèíå Òüþðèíãà è äðóãèì ìîäåëÿì, óòî÷íÿþùèì ïîíÿòèÿ àëãîðèòìà.
Ïîÿâëåíèå òî÷íîãî ïîíÿòèÿ àëãîðèòìà ïîçâîëèëî ñôîðìóëèðîâàòü àëãîðèòìè÷åñêè íå ðàçðåøèìûå ïðîáëåìû, ò.å. çàäà÷è, äëÿ; ðåøåíèÿ êîòîðûõ íåâîçìîæíî ïîñòðîèòü àëãîðèòì. Çàäà÷à íàçûâàåòñÿ àëãîðèòìè÷åñêè íåðàçðåøèìîé, åñëè íå ñóùåñòâóåò ìàøèíû Òüþðèíãà (èëè ðåêóðñèâíîé ôóíêöèè, èëè íîðìàëüíîãî àëãîðèòìå Ìàðêîâà), êîòîðàÿ åå ðåøàåò. Íàïðèìåð, íåðàçðåøèìîé îêàçàëàñü ïðîáëåìà ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè àëãîðèòìîâ: íåëüçÿ ïîñòðîèòü àëãîðèòì, êîòîðûé ïî ëþáûì äâóì àëãîðèòìàì (ïðîãðàììàì) âûÿñíÿë áû, âû÷èñëÿþò îíè îäíó è òó æå ôóíêöèþ èëè íåò. Çíàíèå îñíîâíûõ íåðàçðåøèìîñòåé òåîðèè àëãîðèòìîâ íåîáõîäèìî äëÿ ñïåöèàëèñòà ïî èíôîðìàòèêå. Îíî ïðåäîñòåðåæåò åãî îò óâëå÷åíèÿ ãëîáàëüíûìè ïðîæåêòàìè âñåîáùåé àëãîðèòìèçàöèè òî÷íî òàê êàê çíàíèå îñíîâíûõ çàêîíîâ ôèçèêè ïðåäîñòåðåãàåò îò ïîïûòîê ñîçäàíèÿ âå÷íîãî äâèãàòåëÿ.
|