Теория автоматов. Лупал А.М. - 6 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

6
2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÀËÃÎÐÈÒÌÎÂ
2.1. Îïðåäåëåíèå àëãîðèòìà
Ïîíÿòèÿ òåîðèè àëãîðèòìîâ âñåãäà òðàäèöèîííî îòíîñèëèñü ê âû-
ñîêîé íàóêå, ñ÷èòàëèñü ñëàáî ñâÿçàííûìè ñ ïðàêòèêîé è òðóäíûìè äëÿ
ïîíèìàíèÿ. Îäíàêî æèçíü îïðîâåðãëà ýòè ïðåäñòàâëåíèÿ, è ýòî äîêàçû-
âàåòñÿ òåì, ÷òî âîçíèêëè ïðèêëàäíûå îòâåòâëåíèÿ ýòîé òåîðèè, à èìåí-
íî, àëãîðèòìè÷åñêèå ÿçûêè ïðîãðàììèðîâàíèÿ è òåîðèÿ ôîðìàëüíûõ
èñ÷èñëåíèé, çíàíèå êîòîðûõ ñòàëî ñîâåðøåííî íåîáõîäèìûì äëÿ ëþáî-
ãî èññëåäîâàòåëÿ, èìåþùåãî îòíîøåíèå ê àëãîðèòìèçàöèè ïðîöåññîâ
óïðàâëåíèÿ.
Ïî ñóùåñòâó çíàíèå ýòèõ âîïðîñîâ äàåò ïîíèìàíèå òîãî, ÷òî ìîæíî
è ÷åãî íåëüçÿ ñäåëàòü ñ ïîìîùüþ âû÷èñëèòåëüíîé ìàøèíû. Ñåé÷àñ,
êîãäà âû÷èñëèòåëüíûõ ìàøèí áîëüøå ÷åì ëþäåé, óìåþùèõ ïðàâèëüíî
èõ èñïîëüçîâàòü, òàêîå ïîíèìàíèå îñîáåííî âàæíî.
Àëãîðèòì ìîæåò áûòü îïðåäåëåí êàê ýôôåêòèâíàÿ ïðîöåäóðà, îä-
íîçíà÷íî ïðèâîäÿùàÿ ê ðåçóëüòàòó. Ïðè ðàçðàáîòêå àëãîðèòìà íåîáõî-
äèìî ôîðìàëèçîâàòü ïðîöåññ ðåøåíèÿ çàäà÷è, ñâåäÿ åãî ê ïðèìåíåíèþ
êîíå÷íîé ïîñëåäîâàòåëüíîñòè äîñòàòî÷íî ïðîñòûõ ïðàâèë. Òàê, ìû ðå-
ãóëÿðíî ïîëüçóåìñÿ àëãîðèòìàìè âûïîëíåíèÿ îñíîâíûõ àðèôìåòè÷åñ-
êèõ îïåðàöèé íàä ìíîãîçíà÷íûìè ÷èñëàìè, ðàçðàáîòàííûìè åùå â IX â.
äðåâíåâîñòî÷íûì ìàòåìàòèêîì Àëü-Õîðåçìè (òåðìèí àëãîðèòì ïðî-
èçîøåë îò èìåíè ýòîãî ó÷åíîãî). Äî ñåðåäèíû ÕIX â. âñå àëãîðèòìû
áûëè âû÷èñëèòåëüíûìè è èìåëè äåëî, â îñíîâíîì, ñ ÷èñëàìè. Ïîýòîìó
âñå ìíîãîîáðàçèå âû÷èñëåíèé êîìáèíèðîâàëîñü èç 1015 ÷åòêî îïðåäå-
ëåííûõ îïåðàöèé àðèôìåòèêè, òðèãîíîìåòðèè è àíàëèçà. Âñå áûëî î÷å-
âèäíî è íå òðåáîâàëî ñïåöèàëüíûõ èññëåäîâàíèé.
Ïîÿâëåíèå âî âòîðîé ïîëîâèíå XIX â. ìàòåìàòèêè, èìåþùåé äåëî ñ
íå÷èñëîâûìè îáúåêòàìè (íåýâêëèäîâà ãåîìåòðèÿ, òåîðèÿ ãðóïï, òåîðèÿ
ìíîæåñòâ) ïîêàçàëî, ÷òî âñå íå òàê ïðîñòî è î÷åâèäíî. Îêàçàëîñü, ÷òî
ïðèâû÷íûå ðàññóæäåíèÿ, ïðèìåíÿåìûå ê ýòèì òåîðèÿì, îñíîâàííûå íà
ñîäåðæàòåëüíîì îïèñàíèè àëãîðèòìà, ïðèâîäÿò ê íåðàçðåøèìûì ïðî-
òèâîðå÷èÿì (ïðèìåð òàê íàçûâàåìûå ïðîòèâîðå÷èÿ òåîðèè ìíîæåñòâ).
Ñîâåðøåííî îñîáûì îáðàçîì è êðàéíå îñòîðîæíî ñëåäóåò îáðàùàòüñÿ
ñ òàêèì ïîíÿòèåì, êàê áåñêîíå÷íîñòü. Áûëè ñîçäàíû òàê íàçûâàå-
ìûå ôèíèòíûå ìåòîäû èññëåäîâàíèé, ñóùíîñòü êîòîðûõ çàêëþ÷àåòñÿ
â òîì, ÷òî îíè äîïóñêàþò òîëüêî êîíå÷íûå êîìïëåêñû äåéñòâèé íàä

Страницы