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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
âûáèðàåòñÿ êîíå÷íûé íàáîð ñïîñîáîâ ïîñòðîåíèÿ èç íèõ íîâûõ
îáúåêòîâ;
ôèêñèðóåòñÿ íàáîð ýëåìåíòàðíûõ øàãîâ;
ðàçðàáàòûâàåòñÿ ñïîñîá ñîçäàíèÿ ïàìÿòè è âûáîðêè èíôîðìàöèè
èç ïàìÿòè.
 ðåçóëüòàòå ýòèõ äåéñòâèé ñîçäàåòñÿ êîíêðåòíàÿ àëãîðèòìè÷åñêàÿ
ìîäåëü.
Ìîæíî âûäåëèòü òðè îñíîâíûõ òèïà àëãîðèòìè÷åñêèõ ìîäåëåé, êî-
òîðûå ðàçëè÷àþòñÿ ýâðèñòè÷åñêèìè ñîîáðàæåíèÿìè îòíîñèòåëüíî òîãî,
÷òî òàêîå àëãîðèòì.
1. Â ïåðâîé ìîäåëè ïîíÿòèå àëãîðèòìà ñâÿçûâàåòñÿ ñ íàèáîëåå òðà-
äèöèîííûìè ïîíÿòèÿìè ìàòåìàòèêè âû÷èñëåíèÿìè è ÷èñëîâûìè ôóí-
êöèÿìè. Íàèáîëåå øèðîêî èñïîëüçóåìàÿ ìîäåëü ýòîãî òèïà ðåêóðñèâ-
íûå ôóíêöèè. Ðåêóðñèâíàÿ ôóíêöèÿ îïèñûâàåòñÿ ïîñðåäñòâîì òàê íà-
çûâàåìûõ èíäóêòèâíûõ (èëè ðåêóððåíòíûõ) îïðåäåëåíèé, îñíîâàííûõ
íà ïåðåõîäå îò n ê n+1. Ñëîâî ðåêóððåíòíûé îçíà÷àåò âîçâðàòíûé
îò ëàòèíñêîãî ñëîâà recurso âîçâðàùàþñü, áåãó íàçàä. È åñëè àëãî-
ðèòì íîñèò âîçâðàòíûé õàðàêòåð, òî îí è íàçûâàåòñÿ ðåêóðñèâíûì. Ïðè-
ìåðîì ìîæåò ñëóæèòü àëãîðèòì ïîëó÷åíèÿ íàòóðàëüíîãî ðÿäà ÷èñåë:
÷òîáû îïðåäåëèòü ÷èñëî 4, íóæíî ñíà÷àëà îïðåäåëèòü ÷èñëî 3, à ÷òîáû
îïðåäåëèòü ÷èñëî 3, íóæíî ñíà÷àëà îïðåäåëèòü ÷èñëî 2 è ò.ä. âïëîòü äî 1.
Ðåêóðñèâíûå ôóíêöèè ìîãóò áûòü îïðåäåëåíû êàê íåêîòîðûå íîâûå
ôóíêöèè, ïîëó÷àåìûå èç óæå èìåþùèõñÿ ôóíêöèé ñ ïîìîùüþ îïåðàöèè
ñóïåðïîçèöèè.
Îïåðàòîðîì ñóïåðïîçèöèè
n
m
S
íàçûâàåòñÿ ïîäñòàíîâêà â ôóíêöèþ
îò m ïåðåìåííûõ m ôóíêöèé îò n îäíèõ è òåõ æå ïåðåìåííûõ. Íàïðè-
ìåð, åñëè èìååì ôóíêöèè h(x
1
, x
2
, ...,x
m
), g
1
(x
1
, x
2
,...x
n
), g
2
(x
1
, x
2
, ...x
n
), ...,
g
m
(x
1
, x
2
, ..., x
n
) , òî
n
m
S
(h,g
1
, g
2
, ..., g
m
) = h(g
1
(x
1
, x
2
, ..., x
n
), g
2
(x
1
, x
2
, ...,
x
n
), ..., g
m
(x
1
, x
2
, ...,x
n
)) =f(x
1
,x
2
,..., x
n
).
2. Âòîðîé òèï àëãîðèòìè÷åñêîé ìîäåëè îñíîâàí íà ïðåäñòàâëåíèè îá
àëãîðèòìå êàê î íåêîòîðîì äåòåðìèíèðîâàííîì óñòðîéñòâå, ñïîñîáíîì
âûïîëíÿòü â êàæäûé îòäåëüíûé ìîìåíò âðåìåíè ëèøü âåñüìà ïðèìè-
òèâíûå îïåðàöèè.
Ýâðèñòèêà ýòèõ ìîäåëåé áëèçêà ê ÝÂÌ è, ñëåäîâàòåëüíî, áëèçêà ê
èíæåíåðíîé èíòóèöèè. Îñíîâíîé òåîðåòè÷åñêîé ìîäåëüþ ýòîãî òèïà, ñî-
çäàííîé â 30-õ ãîäàõ, ÿâëÿåòñÿ ìàøèíà Òüþðèíãà.

Страницы