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

UptoLike

ВУЗ: 

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

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

Рубрика: 

9
 ÷àñòíîñòè, âñÿêèé, êòî ïðåäúÿâëÿåò àëãîðèòì ðåøåíèÿ íåêîòîðîé
çàäà÷è, íàïðèìåð âû÷èñëåíèÿ íåêîòîðîé ôóíêöèè f(x), îáÿçàí ïîêàçàòü,
÷òî àëãîðèòì îñòàíàâëèâàåòñÿ ïîñëå êîíå÷íîãî ÷èñëà øàãîâ (ñõîäèòñÿ)
äëÿ ëþáîãî õ èç îáëàñòè çàäàíèÿ ôóíêöèè f.
6. Àëãîðèòì äîëæåí óäîâëåòâîðÿòü òðåáîâàíèþ ìàññîâîñòè, ò. å. àë-
ãîðèòì äîëæåí áûòü òàêèì, ÷òîáû åãî ìîæíî áûëî ïðèìåíèòü äëÿ êëàññà
çàäà÷, ðàçëè÷àþùèõñÿ ëèøü èñõîäíûìè äàííûìè.
7.  ïðîöåññå ñîçäàíèÿ àëãîðèòìà ñëåäóåò ðàçëè÷àòü ïîíÿòèÿ:
îïèñàíèå àëãîðèòìà (íàïðèìåð, èíñòðóêöèþ èëè ïðîãðàììó);
ìåõàíèçì ðåàëèçàöèè àëãîðèòìà (íàïðèìåð, ÝÂÌ), êîòîðûé âêëþ÷à-
åò â ñåáÿ ñðåäñòâà óïðàâëåíèÿ õîäîì âû÷èñëåíèé, à èìåííî: ñðåäñòâà
ïóñêà, ñðåäñòâà îñòàíîâêè, ñðåäñòâà ðåàëèçàöèè ýëåìåíòàðíûõ øàãîâ,
ñðåäñòâà âûäà÷è ðåçóëüòàòîâ, îáåñïå÷åíèÿ äåòåðìèíèðîâàííîñòè;
ïðîöåññ ðåàëèçàöèè àëãîðèòìà, ïðåäñòàâëÿþùèé ñîáîé ïîñëåäîâà-
òåëüíîñòü øàãîâ, êîòîðàÿ áóäåò ïîðîæäàòüñÿ ïðè ïðèìåíåíèè àëãîðèò-
ìà ê êîíêðåòíûì äàííûì.
2.3. Áëîê-ñõåìû àëãîðèòìîâ, êîìïîçèöèÿ àëãîðèòìîâ
Äëÿ ïðåäñòàâëåíèÿ àëãîðèòìà è îðãàíèçàöèè ñâÿçè ìåæäó åãî øàãà-
ìè èñïîëüçóþòñÿ áëîê-ñõåìû. Áëîê ñõåìà àëãîðèòìà èçîáðàæàåòñÿ â
âèäå ãðàôà, â êîòîðîì âåðøèíàì ñîîòâåòñòâóþò øàãè àëãîðèòìà, à ðåá-
ðàì ïåðåõîäû ìåæäó øàãàìè. Âåðøèíû ìîãóò áûòü îïåðàòîðíûìè
èëè îïåðàòîðàìè (âûõîäèò îäíî ðåáðî), óñëîâíûìè èëè ïðåäèêàòàì è
(âûõîäèò äâà ðåáðà), ïåðåêëþ÷àòåëüíûìè (âûõîäèò íåñêîëüêî ðåáåð),
åäèíñòâåííûé îïåðàòîð íà÷àëà (âûõîäèò îäíî ðåáðî), åäèíñòâåííûé
îïåðàòîð êîíöà (íå âûõîäèò íè îäíîãî ðåáðà).
Âàæíîé îñîáåííîñòüþ àëãîðèòìà ÿâëÿåòñÿ òî, ÷òî ñâÿçè, îïèñûâàåìûå
áëîê-ñõåìîé, íå çàâèñÿò îò òîãî, ÿâëÿþòñÿ ëè øàãè àëãîðèòìà ýëåìåíòàð-
íûìè èëè ïðåäñòàâëÿþò ñîáîé ñàìîñòîÿòåëüíûå àëãîðèòìû (áëîêè).
 ïðîãðàììèðîâàíèè èçâåñòíî ïîíÿòèå ðàçáëî÷èâàíèÿ ñëîæíîãî
àëãîðèòìà, êîãäà îòäåëüíûå åãî áëîêè ïðîãðàììèðóþòñÿ ðàçíûìè ëè-
öàìè. È íàîáîðîò, ñ ïîìîùüþ áëîê-ñõåìû ìîæíî íåñêîëüêî îòäåëüíûõ
àëãîðèòìîâ ðàññìàòðèâàòü êàê áëîêè, êîòîðûå ìîãóò áûòü ñâÿçàíû â
îäèí áîëüøîé àëãîðèòì.
Íàïðèìåð, áëîê-ñõåìà, âû÷èñëÿþùàÿ ôóíêöèþ f = f
2
(f
1
(x)) , â êîòî-
ðîé â êà÷åñòâå àðãóìåíòà èñïîëüçóåòñÿ äðóãàÿ ôóíêöèÿ è êîòîðàÿ ïî-

Страницы