С.С. Марченков - Избранные главы дискретной математики (1124120), страница 17
Текст из файла (страница 17)
Ïóñòü ôóíêöèÿ f (x1 , . . . ,îïåðàöèè ñóïåðïîçèöèèñóïåðïîçèöèåé ôóíêöèé77xn ) ïîëó÷àåòñÿ èç (÷àñòè÷íûõ) ôóíêöèé (4.2) ñ ïîìîùüþ îïåðàöèè ñóïåðïîçèöèè (4.3). Äëÿ ëþáîãî íàáîðà (a1 , . . . , an ) èç N n ñ÷èòàåì çíà÷åíèåf (a1 , . . . , an ) îïðåäåëåííûì òîëüêî â òîì ñëó÷àå, êîãäà îïðåäåëåíû âñåçíà÷åíèÿg1 (a1 , . .
. , an ), . . . , gm (a1 , . . . , an )(4.4)è îïðåäåëåíî çíà÷åíèå ôóíêöèè g0 íà íàáîðå ñ êîìïîíåíòàìè (4.4).Ïåðåéäåì ê áîëåå ñëîæíîé îïåðàöèèÏóñòüèìåþòñÿ (÷àñòè÷íî îïðåäåëåííûå) ôóíêöèè g(x1 , . . . , xn−1 ) è h(x1 , . . . ,xn+1 ). Áóäåì ãîâîðèòü, ÷òî ôóíêöèÿ f (x1 , . . . , xn ) ïîëó÷åíà èç ôóíêöèég, h ñ ïîìîùüþ îïåðàöèè(ïî ïåðåìåííîé xn ), åñëè ïðè âñåõ çíà÷åíèÿõ ïåðåìåííûõ x1 , . . . , xn âûïîëíÿþòñÿ ñîîòíîøåíèÿïðèìèòèâíîé ðåêóðñèè.ïðèìèòèâíîé ðåêóðñèèf (x1 , . .
. , xn−1 , 0) = g(x1 , . . . , xn−1 ),f (x1 , . . . , xn−1 , xn + 1) = h(x1 , . . . , xn−1 , xn , f (x1 , . . . , xn )).(4.5)Òàê æå, êàê â ñëó÷àå îïåðàöèè ñóïåðïîçèöèè, íåîáõîäèìî ïîÿñíèòü,êàê áóäåò äåéñòâîâàòü îïåðàöèÿ ïðèìèòèâíîé ðåêóðñèè íà ÷àñòè÷íûåôóíêöèè. Äëÿ ëþáîãî íàáîðà (a1 , . .
. , an ) èç N n çíà÷åíèå f (a1 , . . . , an )ñ÷èòàåì îïðåäåëåííûì òîëüêî â òîì ñëó÷àå, êîãäà îïðåäåëåíî çíà÷åíèåg(a1 , . . . , an−1 ) è äëÿ ëþáîãî b < an îïðåäåëåíî òàêæå çíà÷åíèåh(a1 , . . . , an−1 , b, f (a1 , . . . , an−1 , b))(ðàçóìååòñÿ, çíà÷åíèÿ f (a1 , . . . , an−1 , b) ïðè ýòîì âû÷èñëÿþòñÿ ñîãëàñíîðàâåíñòâàì (4.5)). Íåòðóäíî âèäåòü, ÷òî äëÿ çàäàííûõ ôóíêöèé g è hñîîòíîøåíèÿ (4.5) îïðåäåëÿþò åäèíñòâåííóþ ôóíêöèþ f .Ðàññìîòðèì àëãîðèòìè÷åñêè íàèáîëåå ñèëüíóþ îïåðàöèþÏóñòü g(x1 , . . . , xn ) ÷àñòè÷íî îïðåäåëåííàÿ ôóíêöèÿ.
Îïðåäåëèìôóíêöèþ f (x1 , . . . , xn ) ðåçóëüòàò ïðèìåíåíèÿ îïåðàöèè ìèíèìèçàöèèµ ê ôóíêöèè g ,ìèíèìèçà-öèè.f (x1 , . . . , xn ) = (µy)(g(x1 , . . . , xn−1 , y) = xn ).(4.6)Ñ÷èòàåì, ÷òî äëÿ ïðîèçâîëüíîãî íàáîðà (a1 , . . . , an ) èç N n çíà÷åíèå f (a1 ,.
. . , an ) îïðåäåëåíî è ðàâíî ÷èñëó b â òîì è òîëüêî òîì ñëó÷àå, êîãäà:1) çíà÷åíèå g(a1 , . . . , an−1 , b) îïðåäåëåíî è ðàâíî an ;2) ïðè ëþáîì z < b çíà÷åíèå g(a1 , . . . , an−1 , z) îïðåäåëåíî è îòëè÷íîîò an .Ïîíÿòíî, ÷òî ñ ïîìîùüþ îïåðàöèè ìèíèìèçàöèè íàõîäèòñÿ íàèìåíüøåå (ïî y ) ðåøåíèå óðàâíåíèÿg(x1 , . . . , xn−1 , y) = xn .78Ñóùåñòâåííîå îãðàíè÷åíèå çäåñü ñîñòîèò â òîì, ÷òî â ïðîöåññå ïîèñêàòàêîãî ðåøåíèÿ (åñëè îíî, êîíå÷íî, èìååòñÿ) ìû íå ìîæåì ¾ïåðåñêàêèâàòü¿ ÷åðåç òå òî÷êè y , â êîòîðûõ ôóíêöèÿ g íå îïðåäåëåíà. Ìîæåòïîêàçàòüñÿ, ÷òî ýòî îãðàíè÷åíèå íîñèò èñêóññòâåííûé õàðàêòåð. Îäíàêîáåç ýòîãî îãðàíè÷åíèÿ îïåðàöèÿ ìèíèìèçàöèè ïåðåñòàåò áûòü ýôôåêòèâíîé îïåðàöèåé, à åå ïðèìåíåíèå ê àëãîðèòìè÷åñêè âû÷èñëèìîé ôóíêöèèìîæåò ïðèâåñòè ê àëãîðèòìè÷åñêè íåâû÷èñëèìîé ôóíêöèè.Íàïîìíèì, ÷òî â 1 ìû îáîñíîâàëè âû÷èñëèìîñòü ôóíêöèè Iin (1 6i 6 n), ðàâíîé çíà÷åíèþ ñâîåé i-é ïåðåìåííîé.
Ñîâîêóïíîñòü âñåõ ôóíêöèé Iin (n = 1, 2, . . .) îáîçíà÷èì ÷åðåç I . äàëüíåéøåì âàæíóþ ðîëü áóäåò èãðàòü íàáîð ïðîñòåéøèõ âû÷èñëèìûõ ôóíêöèé0,x + 1,I,(4.7)ãäå ôóíêöèþ-êîíñòàíòó 0 ìîæíî ñ÷èòàòü çàâèñÿùåé îò îäíîé ïåðåìåííîé. Ââåäåì îäíî èç öåíòðàëüíûõ ïîíÿòèé ýòîé ãëàâû.Íàçîâåì ôóíêöèþ, åñëè åå ìîæíî ïîëó÷èòü èçôóíêöèé (4.7) ñ ïîìîùüþ (êîíå÷íîãî ÷èñëà ïðèìåíåíèé) îïåðàöèé ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèè è ìèíèìèçàöèè. Êëàññ âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé îáîçíà÷èì ÷åðåç F÷ð .Ñäåëàåì íåñêîëüêî çàìå÷àíèé ïî ïîâîäó ââåäåííîãî ïîíÿòèÿ. Ïðåæäå âñåãî, êàê âèäíî èç ñàìîãî íàçâàíèÿ, ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿìîæåò áûòü ÷àñòè÷íîé ôóíêöèåé (ñëó÷àé âñþäó îïðåäåëåííîé ôóíêöèè, ðàçóìååòñÿ, òàêæå íå èñêëþ÷àåòñÿ).
Äàëåå, ìîæåò ñëîæèòüñÿ âïå÷àòëåíèå, ÷òî èìåþòñÿ âñþäó îïðåäåëåííûåôóíêöèè (òàêèå ôóíêöèè äåéñòâèòåëüíî åñòü, îíè íàçûâàþòñÿ),èç êîòîðûõ ÷àñòè÷íî ðåêóðñèâíûå ôóíêöèè ïîëó÷àþòñÿ ìåõàíè÷åñêèì¾óäàëåíèåì¿ íåêîòîðûõ çíà÷åíèé. Îäíàêî ýòî íå òàê. ×àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ ýòî åäèíûé îáúåêò, òàêîé, íàïðèìåð, êàê àíàëèòè÷åñêàÿ ôóíêöèÿ.
È ïîëó÷èòü ÷àñòè÷íî ðåêóðñèâíóþ ôóíêöèþ èç ¾áîëååïðîñòûõ¿ âñþäó îïðåäåëåííûõ ôóíêöèé ¾óäàëåíèåì¿ çíà÷åíèé, âîîáùåãîâîðÿ, íåâîçìîæíî.Çíà÷åíèå êëàññà F÷ð â ìàòåìàòèêå âîîáùå è â òåîðèè àëãîðèòìîâ â÷àñòíîñòè îïðåäåëÿåòñÿ.÷àñòè÷íî ðåêóðñèâíîéðåêóðñèâíûåîáùåðåêóðñèâíûìèòåçèñîì ×¼ð÷àÊëàññ àëãîðèòìè÷åñêè âû÷èñëèìûõ (îò íàòóðàëüíûõ àðãóìåíòîâ)ôóíêöèé ñîâïàäàåò ñ êëàññîì F÷ð.Äåòàëüíîå èññëåäîâàíèå êëàññà F÷ð ìû îòëîæèì äî ïîñëåäóþùèõ ïàðàãðàôîâ.
À ïîêà óñòàíîâèì îäíî èç âàæíûõ ñîîòíîøåíèé â òåîðèè âû79÷èñëèìûõ ôóíêöèé.Ëþáàÿ ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà íàìàøèíå Òüþðèíãà.Òåîðåìà 4.1.ïðîâåäåì èíäóêöèåé ïî ïîñòðîåíèþ êëàññà ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé.Âû÷èñëèìîñòü èñõîäíûõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé (4.7) îáñóæäàëàñü â 1. Îñòàåòñÿ ïîêàçàòü, ÷òî îïåðàöèè ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèè è ìèíèìèçàöèè ñîõðàíÿþò âû÷èñëèìîñòü ôóíêöèé íà ìàøèíàõ Òüþðèíãà.Èòàê, ïóñòü ôóíêöèè g0 , g1 , . . . , gm ïðàâèëüíî âû÷èñëèìû íà ìàøèíàõ Òüþðèíãà M0 , M1 , . . . , Mm , à ôóíêöèÿ f (x1 , .
. . , xn ) ïîëó÷àåòñÿ èçôóíêöèé g0 , g1 , . . . , gm ñ ïîìîùüþ îïåðàöèè ñóïåðïîçèöèè (4.3). Áóäåìïðåäïîëàãàòü, ÷òî âñå ìàøèíû M0 , M1 , . . . , Mm ðàáîòàþò â àëôàâèòå {0, 1}. Ñ ïðèíöèïèàëüíîé òî÷êè çðåíèÿ âû÷èñëèìîñòü ôóíêöèè fíå âûçûâàåò ñîìíåíèé: äîñòàòî÷íî ïîñëåäîâàòåëüíî ñ ïîìîùüþ ìàøèíM1 , . . . , Mm âû÷èñëèòü çíà÷åíèÿ ôóíêöèé g1 , . . . , gm (åñëè, êîíå÷íî, âñåâû÷èñëåíèÿ çàêàí÷èâàþòñÿ) è çàòåì ê ïîëó÷åííîìó íàáîðó çíà÷åíèéïðèìåíèòü ìàøèíó Òüþðèíãà M0 .
Îäíàêî ïðè ðåàëèçàöèè ýòîãî ïëàíàâîçíèêàþò òåõíè÷åñêèå òðóäíîñòè, êîòîðûå ìû ïîïûòàåìñÿ îáðèñîâàòüè ïðåîäîëåòü.Ïåðâàÿ òðóäíîñòü âîçíèêàåò ñðàçó æå, êàê òîëüêî ìû ïðèñòóïàåì êâû÷èñëåíèþ çíà÷åíèÿ ôóíêöèè g1 . Äåéñòâèòåëüíî, ïðè âû÷èñëåíèè çíà÷åíèÿ g1 (x1 , . . .
, xn ) îñíîâíîé êîä íàáîðà (x1 , . . . , xn ) áóäåò, âîîáùå ãîâîðÿ, óòåðÿí. Êàê ïîñëå ýòîãî âû÷èñëÿòü çíà÷åíèÿ ôóíêöèé g2 , . . . , gm ?Äëÿ ïðåîäîëåíèÿ ýòîé òðóäíîñòè íàì ïðèäåòñÿ âîñïîëüçîâàòüñÿ äîïîëíèòåëüíûìè ñèìâîëàìè íà ëåíòå. Íà÷íåì ñ òîãî, ÷òî íåñêîëüêî èçìåíèì ïðîöåññ âû÷èñëåíèÿ ôóíêöèé g1 , . . . , gm íà ìàøèíàõ M1 , . . . , Mm .Èìåííî, äîáàâèì ê ñèìâîëàì 0,1 ëåíòî÷íîãî àëôàâèòà ìàøèí M1 , .
. . ,Mm íîâûé ñèìâîë 2. Îí áóäåò èãðàòü ðîëü äîïîëíèòåëüíîãî ïóñòîãîñèìâîëà, îòìå÷àÿ â ïðîöåññå âû÷èñëåíèÿ òå êëåòêè ëåíòû, â êîòîðûõõîòÿ áû ðàç ïîáûâàëà ãîëîâêà ìàøèíû Òüþðèíãà è êîòîðûå ñîäåðæàòñèìâîë 0. ïðîãðàììå êàæäîé èç ìàøèí Òüþðèíãà M1 , . . . , Mm çàìåíèì ëþáóþ êîìàíäó âèäàÄîêàçàòåëüñòâîaqi → 0Dqjêîìàíäîéaqi → 2Dqj .80Ïîñëå ýòîãî ê êàæäîé êîìàíäå âèäà0qi → bDqjäîáàâèì ¾äóáëèðóþùóþ¿ êîìàíäó2qi → bDqj .Ïîëó÷åííûå â ðåçóëüòàòå ýòèõ ïðåîáðàçîâàíèé ìàøèíû Òüþðèíãà îáîçíà÷èì ÷åðåç M01 , . . . , M0m .Ïîíÿòíî, ÷òî ìàøèíû M01 , . . .
, M0m áóäóò âîñïðèíèìàòü ñèìâîëû 0 è2 îäèíàêîâî, êàê ðàíüøå âîñïðèíèìàëè ñèìâîë 0 ìàøèíû M1 , . . . , Mm .Ãëàâíîå îòëè÷èå âû÷èñëåíèé íà ìàøèíàõ M01 , . . . , M0m îò àíàëîãè÷íûõâû÷èñëåíèé íà ìàøèíàõ M1 , . . . , Mm ñîñòîèò â òîì, ÷òî ïîñëå îêîí÷àíèÿ âû÷èñëåíèÿ (åñëè îíî äåéñòâèòåëüíî çàêàí÷èâàåòñÿ) ñèìâîëîì 2áóäóò îòìå÷åíû âñå êëåòêè ëåíòû, ãäå õîòÿ áû ðàç ïîáûâàëà ãîëîâêà ìàøèíû Òüþðèíãà è êîòîðûå â ìîìåíò îêîí÷àíèÿ âû÷èñëåíèÿ ÿâëÿþòñÿïóñòûìè (ò.å.
íå ñîäåðæàò ñèìâîë 1). Ýòî ñâîéñòâî âû÷èñëåíèé íà ìàøèíàõ M01 , . . . , M0m ïîìîæåò íàì â äàëüíåéøåì ñîçäàòü îñíîâíîé êîäíàáîðà çíà÷åíèé ôóíêöèé g1 , . . . , gm äëÿ ïîñëåäóþùåãî ïðèìåíåíèÿ ìàøèíû M0 .Ïðåîáðàçîâàíèå ìàøèí M1 , . . . , Mm â ìàøèíû M01 , . . . , M0m ïîêà íåðåøàåò îñíîâíóþ çàäà÷ó: êàê íà îäíîé ëåíòå îðãàíèçîâàòü âû÷èñëåíèåíåñêîëüêèõ ôóíêöèé, ñîõðàíÿÿ ïðè ýòîì ðåçóëüòàòû ïðåäûäóùèõ âû÷èñëåíèé. Äëÿ ðåøåíèÿ ýòîé çàäà÷è ñëóæàò òàê íàçûâàåìûåíà ëåíòå ìàøèíû Òüþðèíãà.Ïðåäñòàâèì ñåáå, ÷òî êàæäàÿ êëåòêà ëåíòû ìàøèíû Òüþðèíãà ðàçäåëåíà íà m ¾ýòàæåé¿ òàê, ÷òî íà êàæäîì ¾ýòàæå¿ ìîæíî çàïèñàòü îäèíèç ñèìâîëîâ 0,1,2.
×àñòè êëåòîê ëåíòû, ïðèíàäëåæàùèå îäíîìó è òîìóæå ¾ýòàæó¿, îáðàçóþò. Ââåäåíèå äîðîæåê, ðàçóìååòñÿ, ïðåäñòàâëÿåò ñîáîé âñåãî ëèøü íàãëÿäíûé òåõíè÷åñêèé ïðèåì, ñ ïîìîùüþêîòîðîãî óäîáíî îïèñûâàòü ìîäåëèðîâàíèå íåñêîëüêèõ ìàøèí Òüþðèíãà íà îäíîé ëåíòå. Ôîðìàëüíî ïðè ââåäåíèè äîðîæåê ìû ïåðåõîäèì îòàëôàâèòà {0, 1, 2}, â êîòîðîì ðàáîòàþò ìàøèíû M01 , . . . , M0m , ê àëôàâèòó B , ñîñòîÿùåìó èç 3m áóêâ. Ýòè áóêâû ìîæíî ïðåäñòàâëÿòü ñåáå ââèäå íàáîðîâ (b1 , . . . , bm ) äëèíû m, ãäå êàæäàÿ êîìïîíåíòà bi åñòü áóêâààëôàâèòà {0, 1, 2}.
Êîìïîíåíòû bi áóêâ (b1 , . . . , bi , . . . , bm ) êàê ðàç çàïèñûâàþòñÿ íà i-é äîðîæêå ëåíòû.Èìåÿ òåïåðü m äîðîæåê íà ëåíòå (èëè, ÷òî ýêâèâàëåíòíî, àëôàâèòB èç 3m áóêâ), íåòðóäíî îðãàíèçîâàòü ïðîöåññ ïîñëåäîâàòåëüíîãî âû÷èñëåíèÿ çíà÷åíèé ôóíêöèé g1 , . . . , gm . Ñíà÷àëà îñíîâíîé êîä íàáîðàäîðîæêèäîðîæêó81(x1 , .
. . , xn ) ïåðåâîäèì íà âñå m äîðîæåê. Ïðè ýòîì ìîæíî ñ÷èòàòü, ÷òîñèìâîëàì 0 è 1 èñõîäíîãî àëôàâèòà îòâå÷àþò áóêâû (0, . . . , 0) è (1, . . . , 1)àëôàâèòà B . Çàòåì íà ïåðâîé äîðîæêå ¾çàïóñêàåì¿ ìàøèíó M01 . Îíàâîñïðèíèìàåò òîëüêî ñèìâîëû, çàïèñàííûå íà ïåðâîé äîðîæêå, ïîëíîñòüþ èãíîðèðóÿ âñå, ÷òî çàïèñàíî íà îñòàëüíûõ m − 1 äîðîæêàõ. Åñëèìàøèíà M01 çàêàí÷èâàåò âû÷èñëåíèå, çàïóñêàåì ìàøèíó M02 íà âòîðîéäîðîæêå. Âîò çäåñü íàì ïîíàäîáÿòñÿ ñèìâîëû 2, êîòîðûå ðàññòàâëÿåòìàøèíà M01 íà ïåðâîé äîðîæêå. Ñ èõ ïîìîùüþ (à òàêæå ñ ïîìîùüþñèìâîëîâ 1) ìû îòûñêèâàåì íà÷àëî îñíîâíîãî êîäà íà âòîðîé äîðîæêå äîñòàòî÷íî ïîñåòèòü ëèøü òå êëåòêè, ó êîòîðûõ ïåðâàÿ äîðîæêàñîäåðæèò ñèìâîëû 1 èëè 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
