С.С. Марченков - Избранные главы дискретной математики (1124120), страница 23
Текст из файла (страница 23)
ÒîãäàXexpa (x) =g(x, i + 1).i6xÓÏÐÀÆÍÅÍÈßÌîæíî ëè â îïðåäåëåíèè ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèè îòêàçàòüñÿ îò íåêîòîðûõ ôóíêöèé Iin ?19. Äîêàçàòü, ÷òî ïðèìèòèâíî ðåêóðñèâíîé ÿâëÿåòñÿ ëþáàÿ ïåðèîäè÷åñêàÿ ôóíêöèÿ f (x) (ôóíêöèÿ f (x) íàçûâàåòñÿ ïåðèîäè÷åñêàÿ, åñëèñóùåñòâóåò òàêîå íàòóðàëüíîå ÷èñëî d, ÷òî ðàâåíñòâî f (x + d) = f (x)âûïîëíÿåòñÿ äëÿ ëþáîãî x èç N ).20. Ïóñòü d > 0. Äîêàçàòü, ÷òî êëàññ ïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé çàìêíóò îòíîñèòåëüíî ñëåäóþùåãî âàðèàíòà ðåêóðñèè ïî íåñêîëüêèì îñíîâàíèÿì:18.f (x1 , . .
. , xn−1 , 0) = g0 (x1 , . . . , xn−1 ), ....................................f (x1 , . . . , xn−1 , d) = gd (x1 , . . . , xn−1 ),f (x1 , . . . , xn−1 , xn + d + 1) == h(x1 , . . . , xn−1 , xn , f (x1 , . . . , xn ), . . . , f (x1 , . . . , xn + d)).Ïóñòü P (x1 , . . . , xn ), Q(x1 , . . . , xn ) ìíîãî÷ëåíû ñ íàòóðàëüíûìèêîýôôèöèåíòàìè, à f (x) ðàâíî ÷èñëó ðåøåíèé óðàâíåíèÿ21.P (x1 , . . . , xn ) = Q(x1 , . . .
, xn )107ïðè îãðàíè÷åíèÿõ 0 6 x1 6 x, . . . , 0 6 xn 6 x. Äîêàçàòü ïðèìèòèâíóþðåêóðñèâíîñòü ôóíêöèè f (x).22. Ïóñòü g(x) ïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ, à ôóíêöèÿ f (x, y)îïðåäåëÿåòñÿ ñîîòíîøåíèÿìè íàèìåíüøåìó ðåøåíèþ z óðàâíåíèÿ g(z) = y,f (x, y) =íå ïðåâîñõîäÿùåìó x, åñëè òàêîå ðåøåíèå z ñóùåñòâóåò,0 â ïðîòèâíîì ñëó÷àå.Äîêàçàòü, ÷òî ôóíêöèÿ f (x, y) ïðèìèòèâíî ðåêóðñèâíà.23. Ïóñòü p(x) ðàâíî (x + 1)-ó ïðîñòîìó ÷èñëó, ò.å. p(0) = 2, p(1) = 3,p(2) = 5, .
. .. Äîêàçàòü, ÷òî ôóíêöèÿ p(x) ïðèìèòèâíî ðåêóðñèâíà.24. Ïóñòü f (x) ðàâíî (x + 1)-ó äåñÿòè÷íîìó ðàçðÿäó ïîñëå çàïÿòîé â√ðàçëîæåíèè ÷èñëà 2. Äîêàçàòü ïðèìèòèâíóþ ðåêóðñèâíîñòü ôóíêöèèf (x). 9. Êëàññ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèéÏðèñòóïèì ê áîëåå äåòàëüíîìó èçó÷åíèþ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Ïîñìîòðèì íà ïðèìåðàõ, êàê äåéñòâóåò îïåðàöèÿ ìèíèìèçàöèè.Ïóñòü g1 (x) = x + 1 èf1 (x) = (µy)(g1 (y) = x).Òîãäà, êàê íåòðóäíî âèäåòü,f1 (x) =x − 1,åñëè x > 0,íå îïðåäåëåíî, åñëè x = 0.Ïóñòü g2 (x) åñòü ôóíêöèÿ-êîíñòàíòà a èf2 (x) = (µy)(g2 (y) = x).Òîãäàf2 (x) =0,åñëè x = a,íå îïðåäåëåíî, åñëè x 6= a.Èíòåðåñíûé ðåçóëüòàò ïîëó÷àåòñÿ, åñëè îïåðàöèþ ìèíèìèçàöèè ïðèìåíèòü ê ôóíêöèè f1 (x).
Èòàê, ïîëîæèìf3 (x) = (µy)(f1 (y) = x).108Òîãäà, êàê ëåãêî óáåäèòüñÿ, ôóíêöèÿ f3 (x) íå áóäåò îïðåäåëåíà íè ïðèêàêîì çíà÷åíèè x. Ýòî òàê íàçûâàåìàÿ.Îíà èãðàåò âàæíóþ ðîëü â òåîðèè àëãîðèòìîâ.  ñâÿçè ñ ýòèì îòìåòèì,÷òî ïðèìåíåíèå îïåðàöèè ìèíèìèçàöèè äàæå ê âåñüìà ïðîñòûì âñþäóîïðåäåëåííûì ôóíêöèÿì ìîæåò ïðèâåñòè ê ¾ñóùåñòâåííî¿ ÷àñòè÷íûìôóíêöèÿì.Ðàññìîòðèì åùå íåñêîëüêî ïðèìåðîâ ïðèìåíåíèÿ îïåðàöèè ìèíèìèçàöèè. Ïóñòüíèãäå íå îïðåäåëåííàÿ ôóíêöèÿf4 (x) = (µy)(y 2 = x),Òîãäàf5 (x) = (µy)(2y = x).√x,åñëè x åñòü ïîëíûé êâàäðàò,íå îïðåäåëåíî â ïðîòèâíîì ñëó÷àå,f4 (x) =f5 (x) =log2 x,åñëè x åñòü ñòåïåíü ÷èñëà 2,íå îïðåäåëåíî â ïðîòèâíîì ñëó÷àå.Ïðèìåíåíèå îïåðàöèè ìèíèìèçàöèè ê îäíîé è òîé æå ôóíêöèè, íî ïîðàçíûì ïåðåìåííûì, ìîæåò ïðèâåñòè ê ñóùåñòâåííî ðàçëè÷íûì ðåçóëüòàòàì.
Òàê, åñëèf6 (x, y) = (µz)(z −· x = y),òîf6 (x, y) =f7 (x, y) =f7 (x, y) = (µz)(x −· z = y),0,åñëè y = 0,x + y, åñëè y 6= 0,x − y,åñëè x > y,íå îïðåäåëåíî, åñëè x < y.Ïîìèìî ôîðìû (4.6) îïåðàöèÿ ìèèíèìèçàöèè ïðèìåíÿåòñÿ åùå â íåñêîëüêèõ ôîðìàõ. Ïðèâåäåì äâå èç íèõ:f (x1 , .
. . , xn−1 ) = (µy)(g(x1 , . . . , xn−1 , y) = 0),f (x1 , . . . , xn−1 ) = (µy)(g1 (x1 , . . . , xn−1 , y) = g2 (x1 , . . . , xn−1 , y)).Äîâîëüíî ÷àñòî îïåðàöèþ ìèíèìèçàöèè ïðèìåíÿþò äëÿ äîêàçàòåëüñòâà ÷àñòè÷íîé ðåêóðñèâíîñòè ôóíêöèè, çàäàííîé àëãîðèòìîì, ïîñëåäîâàòåëüíûå øàãè êîòîðîãî âûïîëíÿþòñÿ âåñüìà ïðîñòî. Ïðè ýòîì ÷èñëîøàãîâ àëãîðèòìà çàðàíåå íå ìîæåò áûòü îãðàíè÷åíî, íàïðèìåð, ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèåé. Òîãäà ìîæíî ïîñòóïèòü òàê: ïîñòóëèðîâàòü ñóùåñòâîâàíèå ¾äëèííîé¿ öåïî÷êè ÷èñåë (êîòîðûå ñîäåðæàòåëüíî109äîëæíû êîäèðîâàòü ðåçóëüòàòû ïîøàãîâîé ðàáîòû àëãîðèòìà) è çàòåì ñïîìîùüþ ïðîñòûõ ôóíêöèé ïðîâåðèòü, ÷òî äàííàÿ öåïî÷êà äåéñòâèòåëüíî óäîâëåòâîðÿåò óñëîâèÿì, âûòåêàþùèì èç îïèñàíèÿ àëãîðèòìà.
Ïðèýòîì ¾äëèííóþ¿ öåïî÷êó ÷èñåë ìîæíî áóäåò ïðåäñòàâèòü îäíèì ÷èñëî,à ñóùåñòâîâàíèå ýòîãî ÷èñëà âîçüìåò íà ñåáÿ îïåðàöèÿ ìèíèìèçàöèè. êà÷åñòâå èëëþñòðàöèè ýòîãî ïðèåìà ìû ïðèâåäåì íàáðîñîê äîêàçàòåëüñòâà ÷àñòè÷íîé ðåêóðñèâíîñòè âñþäó îïðåäåëåííîé ôóíêöèè F (x, y),çàäàííîé ñ ïîìîùüþ íåïðèìèòèâíîé ðåêóðñèè. Ýòà ôóíêöèÿ íå ÿâëÿåòñÿïðèìèòèâíî ðåêóðñèâíîé, îäíàêî äîêàçàòåëüñòâî ýòîãî ôàêòà äîñòàòî÷íî ãðîìîçäêî, è ìû åãî íå ïðèâîäèì.Èòàê, ïóñòü ôóíêöèÿ F (x, y) îïðåäåëÿåòñÿ ñëåäóþùèìè ðàâåíñòâàìè:F (0, y) = y + 2,F (x + 1, 0) = 1,F (x + 1, y + 1) = F (x, F (x + 1, y)).(4.20)Óáåäèìñÿ, ïðåæäå âñåãî, ÷òî ðàâåíñòâà (4.20) äåéñòâèòåëüíî îïðåäåëÿþòåäèíñòâåííóþ ôóíêöèþ F (x, y). ñàìîì äåëå, åñëè x = 0 èëè y = 0, òî çíà÷åíèÿ F (x, y) îäíîçíà÷íîíàõîäÿòñÿ èç ïåðâîãî èëè âòîðîãî ðàâåíñòâ ñèñòåìû (4.20).
Ðàññìîòðèìäàëåå çíà÷åíèÿ F (1, y + 1). Ïîëüçóÿñü òðåòüèì è ïåðâûì ðàâåíñòâàìè,íàõîäèì, ÷òîF (1, y + 1) = F (0, F (1, y)) = F (1, y) + 2.Ýòè ðàâåíñòâà âìåñòå ñ ðàâåíñòâîì F (1, 0) = 1 äàþò ñõåìó ïðèìèòèâíîéðåêóðñèè äëÿ îïðåäåëåíèÿ ôóíêöèè f1 (y) = F (1, y):f1 (0) = 1,f1 (y + 1) = f1 (y) + 2.Ïîíÿòíî, ÷òîf1 (y) = F (1, y) = 2y + 1.Åñëè ââåñòè îáîçíà÷åíèå f2 (y) = F (2, y), òî ðàâåíñòâà (4.20) âìåñòå ñóñòàíîâëåííûì ñîîòíîøåíèåì F (1, y) = 2y + 1 ïðèâîäÿò ê ñõåìå ïðèìèòèâíîé ðåêóðñèè äëÿ îïðåäåëåíèÿ ôóíêöèè f2 (y):f2 (0) = 1,f2 (y + 1) = 2f2 (y) + 1.Èç íåå íåòðóäíî ïîëó÷èòü, ÷òîf2 (y) = 2(.
. . 2(2 ·1 + 1) + 1 + . . .) + 1 = 2y + 2y−1 + . . . + 20 = 2y+1 − 1.| {z }y110Èòàê,F (2, y) = 2y+1 − 1.Ïðîäîëæàÿ â òîì æå äóõå è ââîäÿ îáîçíà÷åíèå f3 (y) = F (3, y), áóäåìèìåòü ñõåìó ïðèìèòèâíîé ðåêóðñèè äëÿ îïðåäåëåíèÿ ôóíêöèè f3 (y):f3 (0) = 1,f3 (y + 1) = f2 (f3 (y)) = 2f3 (y)+1 − 1.Âîîáùå, ðàññóæäàÿ ïî èíäóêöèè (îáû÷íàÿ èíäóêöèÿ ïî x), ìîæíîóáåäèòüñÿ â òîì, ÷òî äëÿ âñÿêîãî íàòóðàëüíîãî x ôóíêöèÿ fx+1 (y) =F (x + 1, y) (êàê ôóíêöèÿ îò y ) ÿâëÿåòñÿ èòåðàöèåé ôóíêöèè fx (y) âòî÷êå 1. Ýòè ñîîáðàæåíèÿ íàâîäÿò íà ìûñëü, ÷òî ôóíêöèÿ F (x, y) ðàñòåò ñëèøêîì áûñòðî, ÷òîáû áûòü ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèåé.Âìåñòå ñ òåì äîñòàòî÷íî ïîíÿòíî, ÷òî ôóíêöèÿ F (x, y) àëãîðèìè÷åñêèâû÷èñëèìà âûïîëíåíèå ðàâåíñòâ (4.20) íåòðóäíî çàïðîãðàììèðîâàòüíà ìàøèíå Òüþðèíãà.Èòàê, îáðàòèìñÿ ê ïðîöåññó âû÷èñëåíèÿ ôóíêöèè F (x, y).
Ïóñòü x > 0è y > 0. ×òîáû íàéòè çíà÷åíèå F (x, y), íàì íåîáõîäèìî ñîãëàñíî ðàâåíñòâàì (4.20) èìåòü îïðåäåëåííîå êîëè÷åñòâî çíà÷åíèé ôóíêöèè F âòî÷êàõ (s, v), ãäå ëèáî s < x è, âîîáùå ãîâîðÿ, v > y , ëèáî s = x èv < y . Çàðàíåå ìû íå ìîæåì ñêàçàòü, äëÿ êàêèõ èìåííî òî÷åê ïîòðåáóþòñÿ èìåòü çíà÷åíèÿ ôóíêöèè F .
Ïîýòîìó çàïèøåì èõ ïîêà â âèäåïîñëåäîâàòåëüíîñòè ñ íåîïðåäåëåííûìè âåëè÷èíàìè v0 , . . . , vx−1 :F (0, 0), F (0, 1), . . . , F (0, v0 );F (1, 0), F (1, 1), . . . , F (1, v1 ); . . . ;F (x − 1, 0), F (x − 1, 1), . . . , F (x − 1, vx−1 ); F (x, 0), F (x, 1), . . . , F (x, y − 1).(4.21)×àñòü çíà÷åíèé èç ïîñëåäîâàòåëüíîñòè (4.21) äàåòñÿ íåïîñðåäñòâåííî ðàâåíñòâàìè (4.20). ÈìåííîF (0, 0) = 2, F (0, 1) = 3, . . . , F (0, v0 ) = v0 + 2,F (1, 0) = F (2, 0) = .
. . = F (x, 0) = 1.(4.22)×òî êàñàåòñÿ îñòàëüíûõ çíà÷åíèé, òî äëÿ èõ ïîëó÷åíèÿ íàì ïðèäåòñÿâîñïîëüçîâàòüñÿ òðåòüèì èç ðàâåíñòâ (4.20).Èòàê, íàéòè çíà÷åíèå F (x, y) ìîæíî, åñëè ïðåäâàðèòåëüíî ñîçäàòü ïîñëåäîâàòåëüíîñòü (4.21) ñ äîñòàòî÷íî áîëüøèìè (è ïîêà íåîïðåäåëåííûìè) âåëè÷èíàìè v0 , . . .
, vx−1 , â êîòîðîé ÷àñòü çíà÷åíèé èçâåñòíà è äàåòñÿ111ðàâåíñòâàìè (4.22), à îñòàëüíàÿ ÷àñòü çíà÷åíèé îïðåäåëÿåòñÿ ðåêóðñèâíî ñ èñïîëüçîâàíèåì òðåòüåãî èç ðàâåíñòâ (4.20) (ïðåäïîëàãàåòñÿ, ÷òîíåîáõîäèìûå äëÿ ýòîãî çíà÷åíèÿ F (x, y − 1) è F (x − 1, F (x, y − 1)) ïðèñóòñòâóþò â ïîñëåäîâàòåëüíîñòè (4.21)). ïîñëåäîâàòåëüíîñòü (4.21) âõîäèò ñèìâîë ôóíêöèè F . Òåì ñàìûììû êàê áû ïðåäïîëàãàåì, ÷òî íóæíûå íàì çíà÷åíèÿ ôóíêöèè F óæåíàéäåíû.
Îäíàêî ýòî íå òàê. Ïîýòîìó ïîñëåäîâàòåëüíîñòü (4.21) èìååòñìûñë ïåðåïèñàòü íåñêîëüêî èíà÷å:(0, 0, b00 ), (0, 1, b01 ), . . . , (0, v0 , b0v0 ); (1, 0, b10 ), (1, 1, b11 ), . . . , (1, v1 , b1v1 ); . . .. . . ; (x − 1, 0, bx−1,0 ), (x − 1, 1, bx−1,1 ), . . . , (x − 1, vx−1 , bx−1,vx−1 );(x, 0, bx0 ), (x, 1, bx1 ), . .
. , (x, y − 1, bx,y−1 ).(4.23) ýòîé ïîñëåäîâàòåëüíîñòè ÷èñëà b00 , b01 , . . . , b0v0 è b10 , . . . , bx−1,0 îïðåäåëÿþòñÿ ñîãëàñíî ïåðâûì äâóì ðàâåíñòâàì (4.20), à îñòàëüíûå ÷èñëà ñ èñïîëüçîâàíèåì òðåòüåãî ðàâåíñòâà (4.20). Íàáîðû èç òðîåê ÷èñåë,ñîñòàâëÿþùèå ïîñëåäîâàòåëüíîñòü (4.23), ìû çàêîäèðóåì äàëåå ÷èñëàìè èç N (î ñïîñîáå êîäèðîâàíèÿ ÷óòü ïîçæå).  ðåçóëüòàòå îáðàçóåòñÿïîñëåäîâàòåëüíîñòü êîäîâc00 , c01 , . . . , c0v0 ; c10 , c11 , .
. . , c1v1 ; . . . ; cx−1,0 , cx−1,1 , . . . , cx−1,vx−1 ;(4.24)cx0 , cx1 , . . . , cx,y−1 .Íàêîíåö, ýòó ïîñëåäîâàòåëüíîñòü òàêæå çàêîäèðóåì îäíèì ÷èñëîì d (ñïîñîá êîäèðîâàíèÿ ïîêà îñòàâëÿåì â ñòîðîíå).Òåïåðü äëÿ âû÷èñëåíèÿ çíà÷åíèÿ F (x, y) ñëåäóåò íàéòè íàèìåíüøåå÷èñëî d, êîòîðîå åñòü êîä ïîñëåäîâàòåëüíîñòè âèäà (4.24), â êîòîðîé ÷èñëà cij â ñâîþ î÷åðåäü ÿâëÿþòñÿ êîäàìè òðîåê (i, j, bij ). Äàííûå òðîéêèäîëæíû îáðàçîâûâàòü ïîñëåäîâàòåëüíîñòü (4.23), ýëåìåíòû êîòîðîé ïîä÷èíÿþòñÿ èçâåñòíûì íàì ñîîòíîøåíèÿì.Ìîæíî ïîêàçàòü, ÷òî ñâîéñòâî ÷èñëà d, êîòîðîå èçëîæåíî â ïðåäûäóùåì àáçàöå, âûðàçèìî ñ ïîìîùüþ ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèè.Ðàçóìååòñÿ, íà ýòîì ïóòè åñòü îïðåäåëåííûå òåõíè÷åñêèå òðóäíîñòè (íîìû íå îñòàíàâëèâàåìñÿ íà èõ ðàçðåøåíèè, ïîñêîëüêó â ñëåäóþùåì ïàðàãðàôå áóäåò èçëîæåíî ðåøåíèå áîëåå îáùåé çàäà÷è). Òåì íå ìåíååïðåäëîæåííûé ïóòü äîêàçàòåëüñòâà ÷àñòè÷íîé ðåêóðñèâíîñòè ôóíêöèèF (x, y) ïðåäñòàâëÿåòñÿ îäíèì èç íàèáîëåå äîñòóïíûõ.Îáðàòèìñÿ òåïåðü ê âîïðîñó î êîäèðîâàíèè òðîåê.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
