Лупал А.М. Теория автоматов (часть 1)

Подождите немного. Документ загружается.

ÒÅÎÐÈß ÀÂÒÎÌÀÒÎÂ

Ó÷åáíîå ïîñîáèå

Ñàíêò-Ïåòåðáóðã

2000

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ

Ñàíêò-Ïåòåðáóðãñêèé

ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ

À. Ì. Ëóïàë

ÓÄÊ 519.7(075)

ÁÁÊ 32.815

Ë85

Ëóïàë À. Ì.

Ë77 Òåîðèÿ àâòîìàòîâ: Ó÷åá. ïîñîáèå/ ÑÏáÃÓÀÏ. ÑÏá., 2000. 119 ñ.: èë.

ISBN 5808800447

Â ïîñîáèè ïðèâîäÿòñÿ îñíîâíûå ïîíÿòèÿ òåîðèè àëãîðèòìîâ, ðàñêðû-

âàåòñÿ ñâÿçü ìåæäó àëãîðèòìàìè è âû÷èñëèòåëüíûìè ìàøèíàìè è ðàçëè-

÷èÿ ìåæäó ïðîöåññàìè, ïðîòåêàþùèìè â ìàøèíàõ Òüþðèíãà è àâòîìàòàõ

ôîí Íåéìàíà. Ðàññìàòðèâàþòñÿ òàêæå îñíîâû òåîðèè êîíå÷íûõ àâòîìà-

òîâ, ôîðìàëüíûå ìåòîäû ïðîåêòèðîâàíèÿ àâòîìàòîâ íà îñíîâå àáñòðàêò-

íîãî è ñòðóêòóðíîãî ñèíòåçà, ÿâëåíèå ñîñòÿçàíèé ýëåìåíòîâ ïàìÿòè è

ãîíîê â ñòðóêòóðíîì àâòîìàòå, ìåòîäû êîäèðîâàíèÿ ñîñòîÿíèé àâòîìà-

òîâ è ñèíõðîíèçàöèÿ àâòîìàòîâ. Ïðèâîäÿòñÿ ïðèìåðû ìîäèôèêàöèé ýëå-

ìåíòàðíûõ àáñòðàêòíûõ è ñòðóêòóðíûõ àâòîìàòîâ â àñèíõðîííîì è ñèíõ-

ðîíèçèðóåìîì èñïîëíåíèè.

Ó÷åáíîå ïîñîáèå ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ äèñòàíöèîííîé ôîð-

ìû îáó÷åíèÿ ïî ñïåöèàëüíîñòè Âû÷èñëèòåëüíûå ñèñòåìû, êîìïëåêñû è

ñåòè è ìîæåò áûòü èñïîëüçîâàíî ñòóäåíòàìè äíåâíîãî è âå÷åðíåãî ôà-

êóëüòåòà, îáó÷àþùèìèñÿ ïî ýòîé æå ñïåöèàëüíîñòè.

Ðåöåíçåíòû:

êàôåäðà àâòîìàòèêè è ïðîöåññîâ óïðàâëåíèÿ

Ñàíêò-Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî ýëåêòðîòåõíè÷åñêîãî óíèâåðñèòåòà;

êàíäèäàò òåõíè÷åñêèõ íàóê äîöåíò Ë. À. ×óãóíîâ

Óòâåðæäåíî

ðåäàêöèîííî-èçäàòåëüñêèì ñîâåòîì óíèâåðñèòåòà

â êà÷åñòâå ó÷åáíîãî ïîñîáèå

Ñàíêò-Ïåòåðáóðãñêèé

ãîñóäàðñòâåííûé óíèâåðñèòåò

àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ, 2000

À. Ì. Ëóïàë,2000

ISBN 5808800447

1. ÊÈÁÅÐÍÅÒÈÊÀ ÍÀÓÊÀ ÎÁ ÓÏÐÀÂËÅÍÈÈ

1.1. Ñîçäàíèå êèáåðíåòèêè

Êèáåðíåòèêà ýòî íàóêà îá îáùèõ çàêîíàõ ïîëó÷åíèÿ, õðàíåíèÿ è

ïåðåäà÷è èíôîðìàöèè, ò. å. î ïðîöåññàõ, êîòîðûìè õàðàêòåðèçóåòñÿ èí-

òåëëåêòóàëüíàÿ äåÿòåëüíîñòü êàê åñòåñòâåííàÿ, òàê è èñêóññòâåííàÿ.

Êèáåðíåòèêà ÿâèëàñü ôóíäàìåíòîì, íà êîòîðîì âûðîñëà âñÿ ñîâðåìåí-

íàÿ âû÷èñëèòåëüíàÿ òåõíèêà è äðóãèå íàóêè.

Âïåðâûå ïðåäñòàâëåíèå îá èñêóññòâåííîì èíòåëëåêòå ïîÿâèëîñü â

íàó÷íî-ôàíòàñòè÷åñêîé ëèòåðàòóðå, â ÷àñòíîñòè àìåðèêàíñêèé ó÷åíûé

è ïèñàòåëü Àéçåê Àçèìîâ â 1974 ãîäó ïèñàë: ß ïðèäóìàë â 1942 ãîäó

òðè çàêîíà ðîáîòîòåõíèêè è íàïèñàë íà èõ îñíîâå íåñêîëüêî äåñÿòêîâ

ðàññêàçîâ, îòíîñÿñü êî âñåì ýòèì ðîáîòàì è èñêóññòâåííûì èíòåëëåê-

òàì êàê ê ýêçîòè÷åñêèì ïëîäàì âîîáðàæåíèÿ. ß ñ÷èòàë, ÷òî ðîáîò (èëè

âû÷èñëèòåëüíàÿ ìàøèíà, èëè èñêóññòâåííûé èíòåëëåêò) íåîáõîäèì ÷å-

ëîâå÷åñòâó. Çàòåì ÿ îáíàðóæèë, ÷òî, â êîíöå êîíöîâ, âû÷èñëèòåëüíûå

ìàøèíû ñìîãóò äîñòè÷ü èíòåëëåêòóàëüíîãî óðîâíÿ, ñðàâíèìîãî ñ ÷å-

ëîâå÷åñêèì... è äàæå íàìíîãî ïðåâçîéòè åãî..., íî, òåì íå ìåíåå, ÿ äîë-

æåí îòêðûòü Âàì îäíî îáñòîÿòåëüñòâî: ÿ íèêîãäà íå âåðèë â ðåàëü-

íîñòü âñåãî ýòîãî â ýòîì îòíîøåíèè ìîå âîîáðàæåíèå îòêàçàëî. ß

íèêîãäà â äåéñòâèòåëüíîñòè íå ïðåäïîëàãàë, ÷òî èñêóññòâåííûé èíòåë-

ëåêò âîçìîæåí, è ÿ ñîâåðøåííî îïðåäåëåííî íèêàê íå ïðåäïîëàãàë, ÷òî

çàñòàíó âðåìÿ, êîãäà ëþäè áóäóò ñåðüåçíî ðàáîòàòü â ýòîé îáëàñòè [1].

Íàó÷íàÿ òåîðèÿ ïî ðàçðàáîòêå èñêóññòâåííîãî èíòåëëåêòà áûëà ïðî-

âîçãëàøåíà àìåðèêàíñêèì ó÷åíûì Íîðáåðòîì Âèíåðîì â 1948 ãîäó.

Òîãäà æå îí ââåë ïîíÿòèå êèáåðíåòèêè êàê íàóêè îá îáùèõ çàêîíîìåð-

íîñòÿõ ïðîöåññîâ óïðàâëåíèÿ è ïåðåäà÷è èíôîðìàöèè â ìàøèíàõ, æè-

âûõ îðãàíèçìàõ è èõ îáúåäèíåíèÿõ. Âìåñòå ñ ýòèì ñëîâîì áîëåå 50 ëåò

íàçàä â íàø ìèð âîðâàëñÿ öåëûé ïîòîê ñîâåðøåííî íîâûõ èäåé è ïðåä-

ñòàâëåíèé.

Â Ðîññèè ïåðâûå ðàáîòû ïî êèáåðíåòèêå ïîÿâèëèñü â 1956 ãîäó, ïðè-

÷åì ñíà÷àëà ýòî áûëè â îñíîâíîì ïåðåâîäû êíèã è ñòàòåé àìåðèêàíñ-

êèõ ó÷åíûõ, à ñïóñòÿ íåêîòîðîå âðåìÿ ïîÿâèëèñü è ñîáñòâåííûå ðàçðà-

áîòêè. Îäíèìè èç ïåðâûõ ðóññêèõ êèáåðíåòèêîâ áûëè ñîâåòñêèå ó÷å-

íûå Àêñåëü Èâàíîâè÷ Áåðã, Âèêòîð Ìèõàéëîâè÷ Ãëóøêîâ è Àëåêñàíäð

Àíäðååâè÷ Ëÿïóíîâ.

1.2. Ïðåäìåò è ìåòîäû èññëåäîâàíèÿ êèáåðíåòèêè

Â êà÷åñòâå îñíîâíûõ ðàçäåëîâ êèáåðíåòèêè ìîãóò áûòü âûäåëåíû:

1. Òåîðèÿ èíôîðìàöèè, èçó÷àþùàÿ ñïîñîáû âîñïðèÿòèÿ, õðàíåíèÿ,

ïðåîáðàçîâàíèÿ è ïåðåäà÷è èíôîðìàöèè.

2. Òåîðèÿ ïðîãðàììèðîâàíèÿ, èçó÷àþùàÿ è ðàçðàáàòûâàþùàÿ ìå-

òîäû ïåðåðàáîòêè èíôîðìàöèè è èñïîëüçîâàíèÿ åå äëÿ óïðàâëåíèÿ, ïðè-

÷åì ïðîãðàììèðîâàíèå ðàáîòû ëþáîé ñèñòåìû óïðàâëåíèÿ â îáùåì

ñëó÷àå âêëþ÷àåò â ñåáÿ îïðåäåëåíèå è ðàçðàáîòêó óñëîâíîé ìàòåìàòè-

÷åñêîé ñõåìû (àëãîðèòìà) íàõîæäåíèÿ ðåøåíèé è ñîñòàâëåíèå ïðîãðàì-

ìû â êîäå, âîñïðèíèìàåìîì äàííîé ñèñòåìîé.

3. Òåîðèÿ ñèñòåì óïðàâëåíèÿ, êîòîðàÿ èçó÷àåò:

ñòðóêòóðó è ïðèíöèïû ïîñòðîåíèÿ ñèñòåì óïðàâëåíèÿ, ê êîòîðûì îò-

íîñÿòñÿ ëþáûå ôèçè÷åñêèå îáúåêòû, îñóùåñòâëÿþùèå öåëåíàïðàâëåí-

íóþ ïåðåðàáîòêó èíôîðìàöèè, òàêèå êàê íåðâíàÿ ñèñòåìà æèâîòíîãî,

ñèñòåìà àâòîìàòè÷åñêîãî óïðàâëåíèÿ äâèæåíèåì ñàìîëåòà, ýëåêòðîí-

íàÿ ïðîãðàììíî-óïðàâëÿåìàÿ âû÷èñëèòåëüíàÿ ìàøèíà, ñèñòåìà ïîä-

ðàçäåëåíèé áàíêà è ò. ï.;

ïðîöåññ óïðàâëåíèÿ ïîíÿòèå, êîòîðîå îïðåäåëÿåò, êàêèì òðåáîâà-

íèÿì äîëæíà óäîâëåòâîðÿòü ïîñëåäîâàòåëüíîñòü äåéñòâèé (èëè åå îïè-

ñàíèå), îñóùåñòâëÿåìûõ ñèñòåìîé óïðàâëåíèÿ.

Êèáåðíåòèêà èçó÷àåò àáñòðàêòíûå ñèñòåìû óïðàâëåíèÿ, êîòîðûå

ïðåäñòàâëåíû â âèäå ìàòåìàòè÷åñêèõ ñõåì (ìîäåëåé). Îñíîâíûì ñâîé-

ñòâîì ýòèõ ìîäåëåé ÿâëÿåòñÿ òî, ÷òî îíè ñîõðàíÿþò èíôîðìàöèîííûå

ñâîéñòâà ñîîòâåòñòâóþùèõ êëàññîâ ðåàëüíûõ ñèñòåì, ò. å. òåõ ñèñòåì,

êîòîðûå ìîäåëèðóþòñÿ ñ ïîìîùüþ ýòèõ ìîäåëåé. Â ðàìêàõ êèáåðíåòè-

êè ïîä âëèÿíèåì çàïðîñîâ òåõíèêè ÖÂÌ è óïðàâëÿþùèõ âû÷èñëèòåëü-

íûõ ìàøèí âîçíèêëà ñïåöèàëüíàÿ ìàòåìàòè÷åñêàÿ äèñöèïëèíà òåî-

ðèÿ àâòîìàòîâ, êîòîðàÿ èçó÷àåò ñïåöèàëüíûé êëàññ äèñêðåòíûõ (öèô-

ðîâûõ) ñèñòåì ïåðåðàáîòêè èíôîðìàöèè, âêëþ÷àþùèõ â ñåáÿ áîëüøîå

÷èñëî ýëåìåíòîâ. Äèñêðåòíûå àâòîìàòû, èçó÷àåìûå â òåîðèè àâòîìà-

òîâ, ÿâëÿþòñÿ àáñòðàêòíûìè ìîäåëÿìè ðåàëüíûõ ñèñòåì êàê òåõíè-

÷åñêèõ, òàê è áèîëîãè÷åñêèõ, êîòîðûå ïåðåðàáàòûâàþò öèôðîâóþ èí-

ôîðìàöèþ äèñêðåòíûìè âðåìåííûìè òàêòàìè.

Äëÿ òîãî ÷òîáû â âû÷èñëèòåëüíîé ìàøèíå ðåàëèçîâàòü íåêîòîðûé

ïðîöåññ óïðàâëåíèÿ, èíà÷å ãîâîðÿ, ñîîòâåòñòâóþùèé ïðîöåññ ïåðåðà-

áîòêè èíôîðìàöèè, íåîáõîäèìî ïîñòðîèòü òàêîé àëãîðèòì è îñóùåñòâèòü

òàêóþ æå èëè ïðèìåðíî òàêóþ æå ïåðåðàáîòêó èíôîðìàöèè, êàê è èñ-

õîäíûé ïðîöåññ, à çàòåì îöåíèòü êà÷åñòâî ïðèáëèæåíèÿ.

Èñïîëüçóåìûå â êèáåðíåòèêå ìåòîäû èññëåäîâàíèÿ ìîæíî ðàçäå-

ëèòü íà ìàòåìàòè÷åñêèå è ýêñïåðèìåíòàëüíûå, ïðè÷åì èìåííî ê ïîñëå-

äíèì îòíîñÿòñÿ ëîãè÷åñêèé àíàëèç è ñèíòåç ñèñòåì óïðàâëåíèÿ. Ïîýòî-

ìó äèñöèïëèíû Äèñêðåòíàÿ ìàòåìàòèêà, è Òåîðèÿ àâòîìàòîâ ÿâëÿ-

þòñÿ ñîñòàâíûìè ÷àñòÿìè íàóêè êèáåðíåòèêè.

2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÀËÃÎÐÈÒÌÎÂ

2.1. Îïðåäåëåíèå àëãîðèòìà

Ïîíÿòèÿ òåîðèè àëãîðèòìîâ âñåãäà òðàäèöèîííî îòíîñèëèñü ê âû-

ñîêîé íàóêå, ñ÷èòàëèñü ñëàáî ñâÿçàííûìè ñ ïðàêòèêîé è òðóäíûìè äëÿ

ïîíèìàíèÿ. Îäíàêî æèçíü îïðîâåðãëà ýòè ïðåäñòàâëåíèÿ, è ýòî äîêàçû-

âàåòñÿ òåì, ÷òî âîçíèêëè ïðèêëàäíûå îòâåòâëåíèÿ ýòîé òåîðèè, à èìåí-

íî, àëãîðèòìè÷åñêèå ÿçûêè ïðîãðàììèðîâàíèÿ è òåîðèÿ ôîðìàëüíûõ

èñ÷èñëåíèé, çíàíèå êîòîðûõ ñòàëî ñîâåðøåííî íåîáõîäèìûì äëÿ ëþáî-

ãî èññëåäîâàòåëÿ, èìåþùåãî îòíîøåíèå ê àëãîðèòìèçàöèè ïðîöåññîâ

óïðàâëåíèÿ.

Ïî ñóùåñòâó çíàíèå ýòèõ âîïðîñîâ äàåò ïîíèìàíèå òîãî, ÷òî ìîæíî

è ÷åãî íåëüçÿ ñäåëàòü ñ ïîìîùüþ âû÷èñëèòåëüíîé ìàøèíû. Ñåé÷àñ,

êîãäà âû÷èñëèòåëüíûõ ìàøèí áîëüøå ÷åì ëþäåé, óìåþùèõ ïðàâèëüíî

èõ èñïîëüçîâàòü, òàêîå ïîíèìàíèå îñîáåííî âàæíî.

Àëãîðèòì ìîæåò áûòü îïðåäåëåí êàê ýôôåêòèâíàÿ ïðîöåäóðà, îä-

íîçíà÷íî ïðèâîäÿùàÿ ê ðåçóëüòàòó. Ïðè ðàçðàáîòêå àëãîðèòìà íåîáõî-

äèìî ôîðìàëèçîâàòü ïðîöåññ ðåøåíèÿ çàäà÷è, ñâåäÿ åãî ê ïðèìåíåíèþ

êîíå÷íîé ïîñëåäîâàòåëüíîñòè äîñòàòî÷íî ïðîñòûõ ïðàâèë. Òàê, ìû ðå-

ãóëÿðíî ïîëüçóåìñÿ àëãîðèòìàìè âûïîëíåíèÿ îñíîâíûõ àðèôìåòè÷åñ-

êèõ îïåðàöèé íàä ìíîãîçíà÷íûìè ÷èñëàìè, ðàçðàáîòàííûìè åùå â IX â.

äðåâíåâîñòî÷íûì ìàòåìàòèêîì Àëü-Õîðåçìè (òåðìèí àëãîðèòì ïðî-

èçîøåë îò èìåíè ýòîãî ó÷åíîãî). Äî ñåðåäèíû ÕIX â. âñå àëãîðèòìû

áûëè âû÷èñëèòåëüíûìè è èìåëè äåëî, â îñíîâíîì, ñ ÷èñëàìè. Ïîýòîìó

âñå ìíîãîîáðàçèå âû÷èñëåíèé êîìáèíèðîâàëîñü èç 1015 ÷åòêî îïðåäå-

ëåííûõ îïåðàöèé àðèôìåòèêè, òðèãîíîìåòðèè è àíàëèçà. Âñå áûëî î÷å-

âèäíî è íå òðåáîâàëî ñïåöèàëüíûõ èññëåäîâàíèé.

Ïîÿâëåíèå âî âòîðîé ïîëîâèíå XIX â. ìàòåìàòèêè, èìåþùåé äåëî ñ

íå÷èñëîâûìè îáúåêòàìè (íåýâêëèäîâà ãåîìåòðèÿ, òåîðèÿ ãðóïï, òåîðèÿ

ìíîæåñòâ) ïîêàçàëî, ÷òî âñå íå òàê ïðîñòî è î÷åâèäíî. Îêàçàëîñü, ÷òî

ïðèâû÷íûå ðàññóæäåíèÿ, ïðèìåíÿåìûå ê ýòèì òåîðèÿì, îñíîâàííûå íà

ñîäåðæàòåëüíîì îïèñàíèè àëãîðèòìà, ïðèâîäÿò ê íåðàçðåøèìûì ïðî-

òèâîðå÷èÿì (ïðèìåð òàê íàçûâàåìûå ïðîòèâîðå÷èÿ òåîðèè ìíîæåñòâ).

Ñîâåðøåííî îñîáûì îáðàçîì è êðàéíå îñòîðîæíî ñëåäóåò îáðàùàòüñÿ

ñ òàêèì ïîíÿòèåì, êàê áåñêîíå÷íîñòü. Áûëè ñîçäàíû òàê íàçûâàå-

ìûå ôèíèòíûå ìåòîäû èññëåäîâàíèé, ñóùíîñòü êîòîðûõ çàêëþ÷àåòñÿ

â òîì, ÷òî îíè äîïóñêàþò òîëüêî êîíå÷íûå êîìïëåêñû äåéñòâèé íàä

êîíå÷íûì ÷èñëîì îáúåêòîâ. Âñå ýòî ïîòðåáîâàëî óòî÷íåíèÿ ïîíÿòèÿ

àëãîðèòì.

2.2. Ïðåäìåò òåîðèè àëãîðèòìîâ

Â òåõíèêó òåðìèí àëãîðèòì ïðèøåë âìåñòå ñ êèáåðíåòèêîé. Åñëè

ïîíÿòèå ìåòîäà âû÷èñëåíèé íå íóæäàëîñü â ïîÿñíåíèÿõ, òî ïîíÿòèå

ïðîöåññà óïðàâëåíèÿ ñ ïîìîùüþ àëãîðèòìîâ ïðèøëîñü âûðàáàòûâàòü

ïðàêòè÷åñêè çàíîâî. Íåÿñíîñòü ñîäåðæàòåëüíîãî îïèñàíèÿ àëãîðèòìà

ïîñëóæèëà ïðè÷èíîé óòî÷íåíèÿ ïîíÿòèÿ àëãîðèòìà, â ðåçóëüòàòå ÷åãî

áûë ñäåëàí âûâîä î ñóùåñòâîâàíèè òàê íàçûâàåìîé àëãîðèòìè÷åñêîé

íåðàçðåøèìîñòè, ò. å. î íåñóùåñòâîâàíèè åäèíîãî àëãîðèòìà ðåøåíèÿ

çàäà÷ íåêîòîðîãî êëàññà ïðè âîçìîæíîñòè ðåøåíèÿ îòäåëüíûõ çàäà÷

ýòîãî êëàññà.

Ïîýòîìó ïðåäìåòîì òåîðèè àëãîðèòìîâ, ðåøàþùåé çàäà÷ó óòî÷íå-

íèÿ ïîíÿòèÿ àëãîðèòì, ÿâëÿåòñÿ â ïåðâóþ î÷åðåäü óòî÷íåíèå òàêèõ

ïîíÿòèé, êàê îáúåêò, êîòîðûé ïîäâåðãàåòñÿ ïðåîáðàçîâàíèþ è äåé-

ñòâèå, ñîâåðøàåìîå íàä ýòèì îáúåêòîì. Ïîýòîìó, ðàçðàáàòûâàÿ àëãî-

ðèòì, íåîáõîäèìî ïðåäâàðèòåëüíî âûÿñíèòü:

êàêèå îáúåêòû ñëåäóåò ñ÷èòàòü òî÷íî îïðåäåëåííûìè;

êàêèå ýëåìåíòàðíûå äåéñòâèÿ íàä íèìè ñëåäóåò ñ÷èòàòü òî÷íî îï-

ðåäåëåííûìè;

êàêèìè ñâîéñòâàìè è âîçìîæíîñòÿìè îáëàäàþò êîìáèíàöèè ýëåìåí-

òàðíûõ äåéñòâèé, ò. å. ÷òî ìîæíî è ÷åãî íåëüçÿ ñäåëàòü ñ ïîìîùüþ

ýòèõ äåéñòâèé;

êàêèì òðåáîâàíèÿì äîëæíà óäîâëåòâîðÿòü ïîñëåäîâàòåëüíîñòü äåé-

ñòâèé, ÷òîáû ñ÷èòàòüñÿ êîíñòðóêòèâíî çàäàííîé, ò. å. èìåòü ïðàâî íà-

çûâàòüñÿ àëãîðèòìîì.

Â ýòîì îñîçíàíèè îãðîìíóþ ðîëü ñûãðàëà ïðàêòèêà èñïîëüçîâàíèÿ

âû÷èñëèòåëüíûõ ìàøèí, ñäåëàâøàÿ ïîíÿòèå àëãîðèòìà îùóòèìîé ðå-

àëüíîñòüþ. Ïîýòîìó ïðèìåíèòåëüíî ê âû÷èñëèòåëüíîé òåõíèêå ìîæíî

ñôîðìóëèðîâàòü áîëåå êîððåêòíîå îïðåäåëåíèå àëãîðèòìà: àëãîðèòì

ýòî òî÷íîå ïðåäïèñàíèå î âûïîëíåíèè â îïðåäåëåííîì ïîðÿäêå íå-

êîòîðîé ñèñòåìû îïåðàöèé äëÿ ðåøåíèÿ âñåõ çàäà÷ íåêîòîðîãî

çàäàííîãî òèïà.

Òåì íå ìåíåå, íåëüçÿ ñ÷èòàòü àëãîðèòìîì ëþáóþ èíñòðóêöèþ, ðàç-

áèòóþ íà øàãè. Ïîýòîìó íåîáõîäèìî îïðåäåëèòü îñíîâíûå òðåáîâàíèÿ,

ïðåäúÿâëÿåìûå ê àëãîðèòìàì.

1. Àëãîðèòì ïðèìåíÿåòñÿ ê èñõîäíûì äàííûì è âûäàåò ðåçóëüòàòû.

Â ïðèâû÷íûõ òåõíè÷åñêèõ òåðìèíàõ ýòî îçíà÷àåò, ÷òî àëãîðèòì èìååò

âõîäû è âûõîäû. Êðîìå òîãî, â õîäå ðàáîòû àëãîðèòìà ïðîÿâëÿþòñÿ

ïðîìåæóòî÷íûå ðåçóëüòàòû, êîòîðûå èñïîëüçóþòñÿ â äàëüíåéøåì. Òà-

êèì îáðàçîì, êàæäûé àëãîðèòì èìååò äåëî ñ äàííûìè âõîäíûìè, ïðî-

ìåæóòî÷íûìè è âûõîäíûìè.

2. Íåîáõîäèìî óòî÷íèòü ïîíÿòèå äàííûå, ò. å. óêàçàòü, êàêèì òðå-

áîâàíèÿì äîëæíû óäîâëåòâîðÿòü îáúåêòû, ÷òîáû àëãîðèòì ìîã ñ íèìè

ðàáîòàòü. Äëÿ ýòîãî îáúåêòû äîëæíû áûòü ÷åòêî îïðåäåëåíû è îòëè-

÷èìû êàê äðóã îò äðóãà, òàê è îò íåîáúåêòîâ.

Ïîñêîëüêó òî÷íîå è ïîëíîå ñëîâåñíîå îïðåäåëåíèå îáúåêòà äàòü

äîñòàòî÷íî ñëîæíî, â òåîðèè àëãîðèòìîâ ôèêñèðóþò êîíêðåòíûå êîíå÷-

íûå íàáîðû èñõîäíûõ îáúåêòîâ, íàçûâàåìûõ ýëåìåíòàðíûìè è êîíê-

ðåòíûé íàáîð ñðåäñòâ ïîñòðîåíèÿ äðóãèõ îáúåêòîâ èç ýëåìåíòàðíûõ

îáúåêòîâ. Íàáîð ýëåìåíòàðíûõ îáúåêòîâ îáðàçóåò êîíå÷íûé àëôàâèò èñ-

õîäíûõ ñèìâîëîâ (öèôð, áóêâ è äð.), èç êîòîðûõ ñòðîÿòñÿ äðóãèå îáúåêòû.

Íàèáîëåå ðàñïðîñòðàíåííûé òèï àëãîðèòìè÷åñêèõ äàííûõ ñëî-

âà êîíå÷íîé äëèíû â êîíå÷íûõ àëôàâèòàõ (íàïðèìåð, ÷èñëà), ïðè÷åì

÷èñëî ñèìâîëîâ â ñëîâàõ (äëèíà ñëîâà) åñòåñòâåííàÿ åäèíèöà èç-

ìåðåíèÿ îáðàáàòûâàåìîé èíôîðìàöèè. Áîëåå ñëîæíûé ñëó÷àé àëãî-

ðèòìè÷åñêèõ îáúåêòîâ ôîðìóëû. Îíè òàêæå ÿâëÿþòñÿ ñëîâàìè

êîíå÷íîé äëèíû â äàííîì êîíå÷íîì àëôàâèòå, îäíàêî íå êàæäîå ñëî-

âî åñòü ôîðìóëà.

3. Äàííûå äëÿ ñâîåãî ðàçìåùåíèÿ òðåáóþò ïàìÿòè, êîòîðàÿ ñîñòîèò

èç ÿ÷ååê è êàæäàÿ ÿ÷åéêà ìîæåò ñîäåðæàòü îäèí ñèìâîë àëôàâèòà äàí-

íûõ. Òàêèì îáðàçîì, åäèíèöû èçìåðåíèÿ îáúåìà äàííûõ è ïàìÿòè ñî-

ãëàñîâàíû.

4. Àëãîðèòì äîëæåí áûòü äèñêðåòíûì, ò. å. äîëæåí ñîñòîÿòü èç ìíî-

æåñòâà ýëåìåíòàðíûõ øàãîâ èëè äåéñòâèé, ïðè÷åì ìíîæåñòâî ðàçëè÷-

íûõ øàãîâ êîíå÷íî. Ïðèìåðîì ìíîæåñòâà ýëåìåíòàðíûõ äåéñòâèé ÿâ-

ëÿåòñÿ ñèñòåìà êîìàíä ÝÂÌ.

Ïîñëåäîâàòåëüíîñòü øàãîâ àëãîðèòìà äîëæíà áûòü äåòåðìèíèðî-

âàíà, ò. å. ïîñëå êàæäîãî øàãà óêàçûâàåòñÿ, êàêîé øàã äåëàòü äàëüøå

ëèáî äàåòñÿ êîìàíäà îñòàíîâêè.

5. Àëãîðèòì äîëæåí áûòü ðåçóëüòàòèâíûì, ò. å. äîëæåí îñòàíîâèòü-

ñÿ ïîñëå êîíå÷íîãî ÷èñëà øàãîâ ñ îäíîâðåìåííûì óêàçàíèåì òîãî, ÷òî

ñ÷èòàòü ðåçóëüòàòîì.

Â ÷àñòíîñòè, âñÿêèé, êòî ïðåäúÿâëÿåò àëãîðèòì ðåøåíèÿ íåêîòîðîé

çàäà÷è, íàïðèìåð âû÷èñëåíèÿ íåêîòîðîé ôóíêöèè f(x), îáÿçàí ïîêàçàòü,

÷òî àëãîðèòì îñòàíàâëèâàåòñÿ ïîñëå êîíå÷íîãî ÷èñëà øàãîâ (ñõîäèòñÿ)

äëÿ ëþáîãî õ èç îáëàñòè çàäàíèÿ ôóíêöèè f.

6. Àëãîðèòì äîëæåí óäîâëåòâîðÿòü òðåáîâàíèþ ìàññîâîñòè, ò. å. àë-

ãîðèòì äîëæåí áûòü òàêèì, ÷òîáû åãî ìîæíî áûëî ïðèìåíèòü äëÿ êëàññà

çàäà÷, ðàçëè÷àþùèõñÿ ëèøü èñõîäíûìè äàííûìè.

7. Â ïðîöåññå ñîçäàíèÿ àëãîðèòìà ñëåäóåò ðàçëè÷àòü ïîíÿòèÿ:

îïèñàíèå àëãîðèòìà (íàïðèìåð, èíñòðóêöèþ èëè ïðîãðàììó);

ìåõàíèçì ðåàëèçàöèè àëãîðèòìà (íàïðèìåð, ÝÂÌ), êîòîðûé âêëþ÷à-

åò â ñåáÿ ñðåäñòâà óïðàâëåíèÿ õîäîì âû÷èñëåíèé, à èìåííî: ñðåäñòâà

ïóñêà, ñðåäñòâà îñòàíîâêè, ñðåäñòâà ðåàëèçàöèè ýëåìåíòàðíûõ øàãîâ,

ñðåäñòâà âûäà÷è ðåçóëüòàòîâ, îáåñïå÷åíèÿ äåòåðìèíèðîâàííîñòè;

ïðîöåññ ðåàëèçàöèè àëãîðèòìà, ïðåäñòàâëÿþùèé ñîáîé ïîñëåäîâà-

òåëüíîñòü øàãîâ, êîòîðàÿ áóäåò ïîðîæäàòüñÿ ïðè ïðèìåíåíèè àëãîðèò-

ìà ê êîíêðåòíûì äàííûì.

2.3. Áëîê-ñõåìû àëãîðèòìîâ, êîìïîçèöèÿ àëãîðèòìîâ

Äëÿ ïðåäñòàâëåíèÿ àëãîðèòìà è îðãàíèçàöèè ñâÿçè ìåæäó åãî øàãà-

ìè èñïîëüçóþòñÿ áëîê-ñõåìû. Áëîê ñõåìà àëãîðèòìà èçîáðàæàåòñÿ â

âèäå ãðàôà, â êîòîðîì âåðøèíàì ñîîòâåòñòâóþò øàãè àëãîðèòìà, à ðåá-

ðàì ïåðåõîäû ìåæäó øàãàìè. Âåðøèíû ìîãóò áûòü îïåðàòîðíûìè

èëè îïåðàòîðàìè (âûõîäèò îäíî ðåáðî), óñëîâíûìè èëè ïðåäèêàòàì è

(âûõîäèò äâà ðåáðà), ïåðåêëþ÷àòåëüíûìè (âûõîäèò íåñêîëüêî ðåáåð),

åäèíñòâåííûé îïåðàòîð íà÷àëà (âûõîäèò îäíî ðåáðî), åäèíñòâåííûé

îïåðàòîð êîíöà (íå âûõîäèò íè îäíîãî ðåáðà).

Âàæíîé îñîáåííîñòüþ àëãîðèòìà ÿâëÿåòñÿ òî, ÷òî ñâÿçè, îïèñûâàåìûå

áëîê-ñõåìîé, íå çàâèñÿò îò òîãî, ÿâëÿþòñÿ ëè øàãè àëãîðèòìà ýëåìåíòàð-

íûìè èëè ïðåäñòàâëÿþò ñîáîé ñàìîñòîÿòåëüíûå àëãîðèòìû (áëîêè).

Â ïðîãðàììèðîâàíèè èçâåñòíî ïîíÿòèå ðàçáëî÷èâàíèÿ ñëîæíîãî

àëãîðèòìà, êîãäà îòäåëüíûå åãî áëîêè ïðîãðàììèðóþòñÿ ðàçíûìè ëè-

öàìè. È íàîáîðîò, ñ ïîìîùüþ áëîê-ñõåìû ìîæíî íåñêîëüêî îòäåëüíûõ

àëãîðèòìîâ ðàññìàòðèâàòü êàê áëîêè, êîòîðûå ìîãóò áûòü ñâÿçàíû â

îäèí áîëüøîé àëãîðèòì.

Íàïðèìåð, áëîê-ñõåìà, âû÷èñëÿþùàÿ ôóíêöèþ f = f

(x)) , â êîòî-

ðîé â êà÷åñòâå àðãóìåíòà èñïîëüçóåòñÿ äðóãàÿ ôóíêöèÿ è êîòîðàÿ ïî-

ýòîìó íàçûâàåòñÿ êîìïîçèöèåé ôóíêöèé, áóäåò èìåòü âèä, ïðåäñòàâ-

ëåííûé íà ðèñ. 2.1.

Â òàêîé áëîê-ñõåìå âõîäíûå äàííûå (âõîäû) àëãîðèòìà À2 åñòü ðå-

çóëüòàòû (âûõîäû) àëãîðèòìà À1.Òàêîå ñîåäèíåíèå àëãîðèòìîâ íàçû-

âàåòñÿ êîìïîçèöèåé àëãîðèòìîâ.

Íà áëîê-ñõåìå àëãîðèòìà õîðîøî âèäíà ðàçíèöà ìåæäó îïèñàíèåì

àëãîðèòìà è ïðîöåññîì åãî ðåàëèçàöèè. Îïèñàíèå ýòî ãðàô, à ïðîöåññ

ðåàëèçàöèè ýòî ïóòè â ãðàôå, êîòîðûå îïðåäåëÿþòñÿ ëîãè÷åñêèìè óñ-

ëîâèÿìè. Åñëè â ïðîöåññå ðåàëèçàöèè âû÷èñëåíèé íå ïîÿâëÿåòñÿ óñëî-

âèé, âåäóùèõ ê êîíöó, è ïðîöåññ çàöèêëèâàåòñÿ, ýòî îçíà÷àåò îòñóòñòâèå

ñõîäèìîñòè àëãîðèòìà.

2.4. Àëãîðèòìè÷åñêèå ìîäåëè

Â êëàññè÷åñêîì âàðèàíòå áëîê-ñõåìû àëãîðèòìîâ, ïðè âñåé ñâîåé

íàãëÿäíîñòè, îòðàæàþò ñâÿçè ëèøü ïî óïðàâëåíèþ (÷òî äåëàòü â ñëåäó-

þùèé ìîìåíò, êàêîìó áëîêó ïåðåäàòü óïðàâëåíèå), à íå ïî èíôîðìàöèè

(íå ñîäåðæàò ñâåäåíèé íè î äàííûõ, íè î ïàìÿòè, íè îá èñïîëüçóåìîì

íàáîðå ýëåìåíòàðíûõ øàãîâ). Òàêèì îáðàçîì, ïðåäñòàâëåíèå àëãîðèò-

ìà â âèäå áëîê-ñõåìû íå óäîâëåòâîðÿåò ïåðå÷èñëåííûì âûøå òðåáî-

âàíèÿì.

Ïîýòîìó â òåîðèè àëãîðèòìîâ ïðèíèìàåòñÿ è äðóãîé ïîäõîä ê ïðåä-

ñòàâëåíèþ àëãîðèòìà, ïîçâîëÿþùèé ïîñòðîèòü àëãîðèòìè÷åñêóþ ìî-

äåëü ïðîöåññà, êîãäà óäàåòñÿ óäîâëåòâîðèòü âñåì òðåáîâàíèÿì, ïðåäúÿâ-

ëÿåìûì ê àëãîðèòìàì. Ïðè ïîñòðîåíèè àëãîðèòìè÷åñêîé ìîäåëè ïðî-

èçâîäèòñÿ óòî÷íåíèå äåòåðìèíèçìà àëãîðèòìà:

âûáèðàåòñÿ êîíå÷íûé íàáîð èñõîäíûõ îáúåêòîâ, êîòîðûå íàçûâà-

þòñÿ ýëåìåíòàðíûìè;

À1  àëãîðèòì âû÷èñëåíèÿ ôóíêöèè B



(N),

B

(N).

À2À1 ÊîíåöÍà÷àëî

Ðèñ. 2.1