OK-metodichka-2010-part3 (С.А. Ложкин - Лекции по основам кибернетики (2009))

Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåòèìåíè Ì. Â. ËîìîíîñîâàÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. À. ËîæêèíËåêöèè ïî îñíîâàìêèáåðíåòèêè(âàðèàíò 2010 ã., ãëàâà 3)Ìîñêâà 2010ÎãëàâëåíèåÂâåäåíèå43 Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåì7Ÿ1Ÿ2Ÿ3Ÿ4Ÿ5Ÿ6Ÿ7Çàäà÷à ñèíòåçà. Ïðîñòåéøèå ìåòîäû ñèíòåçàñõåì è ñâÿçàííûå ñ íèìè âåðõíèå îöåíêèñëîæíîñòè ôóíêöèé. . . .

. . . . . . . . . . . . 7Ïðîñòåéøèå íèæíèå îöåíêè ñëîæíîñòè ÔÀË.Íèæíèå ìîùíîñòíûå îöåíêè ôóíêöèéØåííîíà . . . . . . . . . . . . . . . . . . . . . . 14Ìåòîä êàñêàäîâ äëÿ êîíòàêòíûõ ñõåì èñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ.Ìåòîä Øåííîíà . . . . . . . . . . . . . . . . . . 21Ðåãóëÿðíûå ðàçáèåíèÿ åäèíè÷íîãî êóáà èìîäåëèðîâàíèå ôóíêöèé ïåðåìåííûìè.Ñèíòåç ñõåì äëÿ íåêîòîðûõ äåøèôðàòîðîâ èìóëüòèïëåêñîðîâ.

. . . . . . . . . . . . . . . . . 28Äèçúþíêòèâíî-óíèâåðñàëüíûå ìíîæåñòâàôóíêöèé. Àñèìïòîòè÷åñêè íàèëó÷øèéìåòîä Î. Á. Ëóïàíîâà äëÿ ñèíòåçàñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîââ áàçèñå {&, ∨, ¬} . . . . . . . . . . . . . . . . . 35Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçàêîíòàêòíûõ ñõåì . . . . . . . .

. . . . . . . . . . 40Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ôîðìóëâ áàçèñå {&, ∨, ¬}. Ïîâåäåíèå ôóíêöèè Øåííîíàäëÿ ãëóáèíû ÔÀË. . . . . . . . . . . . . . . . . 462ÎãëàâëåíèåŸ83Ñèíòåç ñõåì äëÿ ÔÀË èç ñïåöèàëüíûõ êëàññîâ.Îöåíêè ñëîæíîñòè èíäèâèäóàëüíûõ ÔÀË,ìèíèìàëüíîñòü íåêîòîðûõ ñõåì. . . . . . . . . . 49Ëèòåðàòóðà56ÂâåäåíèåÊóðñ ¾Îñíîâû êèáåðíåòèêè¿ (ðàíåå ¾Ýëåìåíòû êèáåðíåòèêè¿), ñîçäàòåëåì è îñíîâíûì ëåêòîðîì êîòîðîãî áûë÷ë.-êîðð. ÐÀÍ Ñ. Â. ßáëîíñêèé, ÷èòàåòñÿ íà ôàêóëüòåòåÂÌèÊ ÌÃÓ ñ ïåðâûõ ëåò åãî ñóùåñòâîâàíèÿ.  íàñòîÿùååâðåìÿ îí ÷èòàåòñÿ â 68 ñåìåñòðàõ è ÿâëÿåòñÿ îáÿçàòåëüíûìäëÿ âñåõ ñòóäåíòîâ, îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòè 01.02 ïðèêëàäíàÿ ìàòåìàòèêà è èíôîðìàòèêà, à òàêæå áàêàëàâðîâ îäíîèìåííîãî íàïðàâëåíèÿ 510200 è íàïðàâëåíèÿ 010400 èíôîðìàöèîííûå òåõíîëîãèè.

Ïðè ýòîì îáúåì è, â íåêîòîðîé ñòåïåíè, ïðîãðàììà êóðñà ¾Îñíîâû êèáåðíåòèêè¿ âàðüèðóþòñÿ â çàâèñèìîñòè îò ñïåöèàëèçàöèè è íàïðàâëåíèÿ.Êóðñ ¾Îñíîâû êèáåðíåòèêè¿ ïîñâÿùåí èçëîæåíèþ òåîðèè äèñêðåòíûõ óïðàâëÿþùèõ ñèñòåì, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé ÷àñòü äèñêðåòíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîéêèáåðíåòèêè.  íåé ðàçðàáàòûâàþòñÿ è èçó÷àþòñÿ äèñêðåòíûå ìàòåìàòè÷åñêèå ìîäåëè, îïèñûâàþùèå ôóíêöèîíèðîâàíèå è ñòðóêòóðó ñëîæíûõ ñèñòåì ïðåîáðàçîâàíèÿ èíôîðìàöèè (èíòåãðàëüíûõ ñõåì, ïðîãðàìì è ò.

ï.).  îñíîâå ýòèõìîäåëåé ëåæàò ðàçëè÷íûå ñïîñîáû çàäàíèÿ ôóíêöèîíèðîâàíèÿ óïðàâëÿþùèõ ñèñòåì ñ ïîìîùüþ äèñêðåòíûõ ôóíêöèéè èõ ñòðóêòóðíàÿ ðåàëèçàöèÿ â òåõ èëè èíûõ êëàññàõ ãðàôîâ (êëàññàõ ñõåì). Ïðè èññëåäîâàíèè óïðàâëÿþùèõ ñèñòåìñòàâÿòñÿ è ðåøàþòñÿ äâå îñíîâíûå çàäà÷è: çàäà÷à àíàëèçàè çàäà÷à ñèíòåçà.Çàäà÷à àíàëèçà ñîñòîèò â íàõîæäåíèè ôóíêöèîíèðîâàíèÿ äàííîé ñõåìû, à çàäà÷à ñèíòåçà â ïîñòðîåíèè ñõåìû,èìåþùåé (ðåàëèçóþùåé) çàäàííîå ôóíêöèîíèðîâàíèå. Êàæäàÿ èç ýòèõ çàäà÷ ìîæåò ðàññìàòðèâàòüñÿ ëèáî êàê èíäè4Ââåäåíèå5âèäóàëüíàÿ çàäà÷à, è òîãäà åå ðåøåíèåì ÿâëÿåòñÿ êîíêðåòíîå ôóíêöèîíèðîâàíèå (ñõåìà), ëèáî êàê ìàññîâàÿ çàäà÷à,è òîãäà åå ðåøåíèåì äîëæåí áûòü àëãîðèòì íàõîæäåíèÿôóíêöèîíèðîâàíèÿ (ñõåìû). Çàäà÷à ñèíòåçà èìååò, êàê ïðàâèëî, ìíîæåñòâî ðåøåíèé, èç êîòîðûõ âûáèðàþò ðåøåíèå,îïòèìàëüíîå ïî êàêîìó-ëèáî êðèòåðèþ.

×àùå âñåãî â êà÷åñòâå òàêîãî êðèòåðèÿ âûñòóïàåò ñëîæíîñòü ñõåìû, ïîíèìàåìàÿ êàê ñóììà ñëîæíîñòåé ñîñòàâëÿþùèõ åå ýëåìåíòîâèëè çàäåðæêà ñõåìû, ïîíèìàåìàÿ êàê ìàêñèìàëüíàÿ ñóììà çàäåðæåê äëÿ ïîñëåäîâàòåëüíî ñîåäèíåííûõ ýëåìåíòîâñõåìû.Ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ ðàçëè÷íûå êðèòåðèè îïòèìàëüíîñòè îòðàæàþò ðàçëè÷íûå ïàðàìåòðû ìîäåëèðóåìûõ ýëåêòðîííûõ ñõåì èëè ïðîãðàìì. Òàê, íàïðèìåð, ñëîæíîñòü ìîæåò õàðàêòåðèçîâàòü ñòîèìîñòü, ðàçìåðû èëè ïîòðåáëÿåìóþ ìîùíîñòü ÑÁÈÑ, à òàêæå âðåìÿ âûïîëíåíèÿïðîãðàììû íà îäíîì ïðîöåññîðå. Ïðè ýòîì çàäåðæêà ñõåìûõàðàêòåðèçóåò âðåìÿ ñðàáàòûâàíèÿ ÑÁÈÑ èëè âðåìÿ âûïîëíåíèÿ ïðîãðàììû íà ïàðàëëåëüíûõ ïðîöåññîðàõ è ò. ï.Åñëè çàäà÷à ñèíòåçà ðåøåíà â îäíîé ìîäåëè, ìîæíî ïûòàòüñÿ ïåðåíåñòè ýòî ðåøåíèå â äðóãèå ìîäåëè ñ ïîìîùüþñòðóêòóðíîãî ìîäåëèðîâàíèÿ.

Êðîìå òîãî, ïîëó÷åííîå ðåøåíèå ìîæíî ¾óëó÷øèòü¿ ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé. Ñ äðóãîé ñòîðîíû, åñëè çàäà÷à ñèíòåçà ðåøåíàäëÿ îäíèõ ôóíêöèé, ìîæíî ïûòàòüñÿ ¾ðàçáèòü¿ (äåêîìïîçèðîâàòü) íîâóþ ôóíêöèþ íà óæå ðàññìîòðåííûå è ïîñòðîèòüèç ñèíòåçèðîâàííûõ äëÿ íèõ ñõåì ñõåìó äëÿ íîâîé ôóíêöèèñ ïîìîùüþ îïåðàöèè ñóïåðïîçèöèè.Óêàçàííûå âûøå çàäà÷è ðàññìàòðèâàþòñÿ â ëåêöèÿõ äëÿâñåõ îñíîâíûõ êëàññîâ ñõåì (äèçúþíêòèâíûå íîðìàëüíûåôîðìû, ôîðìóëû è ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ,êîíòàêòíûå ñõåìû), à òàêæå äëÿ íåêîòîðûõ ìîäèôèêàöèéýòèõ êëàññîâ.Ïåðâàÿ ãëàâà ïîñâÿùåíà ðàçëè÷íûì âîïðîñàì ïðåäñòàâ-6Ââåäåíèåëåíèÿ ôóíêöèé àëãåáðû ëîãèêè ñ ïîìîùüþ òàáëèö è äèçúþíêòèâíûõ íîðìàëüíûõ ôîðì (ìèíèìèçàöèÿ äèçúþíêòèâíûõíîðìàëüíûõ ôîðì).Âòîðàÿ ãëàâà ñîäåðæèò îïèñàíèå ñòðóêòóðû è ôóíêöèîíèðîâàíèÿ ñõåì èç îñíîâíûõ êëàññîâ óïðàâëÿþùèõ ñèñòåì,à òàêæå èç íåêîòîðûõ êëàññîâ, ïðåäñòàâëÿþùèõ ñîáîé èõîáîáùåíèÿ èëè ìîäèôèêàöèè.

 íåé óñòàíàâëèâàþòñÿ âåðõíèå îöåíêè ÷èñëà ñõåì ðàçëè÷íûõ òèïîâ, ðàññìàòðèâàþòñÿîñîáåííîñòè ïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè â ðàçëè÷íûõ êëàññàõ ñõåì è íåêîòîðûå âîïðîñû èõ ñòðóêòóðíîãî ìîäåëèðîâàíèÿ.Âî âòîðîé ãëàâå èçó÷àþòñÿ òàêæå ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ñõåì íà îñíîâå òîæäåñòâ âî âñåõ îñíîâíûõ êëàññàõ óïðàâëÿþùèõ ñèñòåì. Äëÿ êàæäîãî èç íèõ ïðèâîäèòñÿñèñòåìà ¾îñíîâíûõ¿ òîæäåñòâ, äîêàçûâàåòñÿ ïîëíîòà ýòîéñèñòåìû è èçó÷àþòñÿ âîïðîñû åå èçáûòî÷íîñòè. òðåòüåé ãëàâå ïîäðîáíî ðàññìàòðèâàåòñÿ çàäà÷à ñèíòåçà óïðàâëÿþùèõ ñèñòåì.

 íåé ïðèâîäèòñÿ öåëûé ñïåêòðìåòîäîâ ñèíòåçà ñõåì (îò ïðîñòåéøèõ äî àñèìïòîòè÷åñêè îïòèìàëüíûõ), óñòàíàâëèâàþòñÿ íèæíèå ìîùíîñòíûå îöåíêèôóíêöèé Øåííîíà è îöåíêè ñëîæíîñòè ðÿäà êîíêðåòíûõôóíêöèé, äîêàçûâàåòñÿ ìèíèìàëüíîñòü íåêîòîðûõ ñõåì. ÷åòâåðòîé ãëàâå ïðåäñòàâëåíû íåêîòîðûå âîïðîñû íàäåæíîñòè è êîíòðîëÿ ñõåì (ïîñòðîåíèå òåñòâ äëÿ òàáëèö,ñèíòåç ñàìîêîððåêòèðóþùèõñÿ êîíòàêòíûõ ñõåì).Ãëàâà 3Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõñèñòåìŸ1 Çàäà÷à ñèíòåçà. Ïðîñòåéøèå ìåòîäû ñèíòåçà ñõåì è ñâÿçàííûå ñ íèìè âåðõíèå îöåíêèñëîæíîñòè ôóíêöèé. îáùåì âèäå çàäà÷à ñèíòåçà ñîñòîèò â ïîñòðîåíèè ïî çàäàííîé ñèñòåìå ôóíêöèé ðåàëèçóþùåé åå ñõåìû, êîòîðàÿïðèíàäëåæèò çàäàííîìó êëàññó è íà êîòîðîé äîñòèãàåòñÿìèíèìàëüíîå çíà÷åíèå çàäàííîãî ôóíêöèîíàëà ñëîæíîñòè.×àñòíûì ñëó÷àåì ýòîé çàäà÷è ÿâëÿåòñÿ ðàññìîòðåííàÿ ⠟7ãëàâû 1 çàäà÷à ìèíèìèçàöèè ÄÍÔ.

Äàäèì îñíîâíûå îïðåäåëåíèÿ, ñâÿçàííûå ñ çàäà÷åé ñèíòåçà ñõåì, è ââåäåì íåîáõîäèìûå îáîçíà÷åíèÿ.Ïóñòü U îäèí èç ââåäåííûõ â ãëàâå 2 êëàññîâ ñõåì,êîòîðûé ÿâëÿåòñÿ ïîëíûì â òîì ñìûñëå, ÷òî êàæäóþ ñèñòåìó ÔÀË F ìîæíî ðåàëèçîâàòü íåêîòîðîé åãî ñõåìîé Σ,à Ψ êàêîé-ëèáî ôóíêöèîíàë ñëîæíîñòè ñõåì êëàññà U,òî åñòü îòîáðàæåíèå U âî ìíîæåñòâî íåîòðèöàòåëüíûõ äåéñòâèòåëüíûõ ÷èñåë. Áóäåì ñ÷èòàòü, ÷òî ôóíêöèîíàë ñëîæíîñòè Ψ îáëàäàåò ñâîéñòâîì ìîíîòîííîñòè, òî åñòü Ψ (Σ) >Ψ (Σ0 ), åñëè Σ, Σ0 ∈ U, è Σ0 ïîëó÷àåòñÿ èç Σ â ðåçóëüòàòåóäàëåíèÿ âåðøèí èëè ðåáåð (ñð.ñ Ÿ7 ãë.

1). Âñå ââåäåííûå âãëàâå 2 ôóíêöèîíàëû ñëîæíîñòè ýòèì ñâîéñòâîì îáëàäàþò.Îïðåäåëèì ñëîæíîñòü Ψ (F ) ñèñòåìû ÔÀË F îòíîñèòåëüíî78Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìôóíêöèîíàëà Ψ â êëàññå U êàê ìèíèìàëüíîå çíà÷åíèå âåëè÷èíû Ψ (Σ) íà ìíîæåñòâå òåõ ñõåì Σ èç U, êîòîðûå ðåàëèçóþò F . Ïðè ýòîì ñõåìà Σ, ïðèíàäëåæàùàÿ êëàññó U, êîòîðàÿðåàëèçóåò F è äëÿ êîòîðîé Ψ (Σ) = Ψ (F ), íàçûâàåòñÿ ìèíèìàëüíîé ñõåìîé â êëàññå U îòíîñèòåëüíî ôóíêöèîíàëà Ψ. ñèëó ìîíîòîííîñòè ôóíêöèîíàëà Ψ, ìèíèìàëüíàÿ ñõåìàâñåãäà ìîæåò áûòü íàéäåíà ñðåäè ïðèâåäåííûõ ñõåì.Âåëè÷èíó Ψ (F ), â òîì ñëó÷àå êîãäà ôóíêöèîíàë Ψ ñîâïàäàåò ñ ââåäåííûì â ãëàâå 2 ôóíêöèîíàëîì L (D, R, è ò. ä.),áóäåì íàçûâàòü ñëîæíîñòüþ (ñîîòâåòñòâåííî ãëóáèíîé, ðàíãîì, è ò.

ä.) ñèñòåìû ÔÀË F . Ââåäåì ôóíêöèþΨ (n) = max Ψ (f ) ,f ∈P2 (n)êîòîðàÿ, îáû÷íî, íàçûâàåòñÿ ôóíêöèåé Øåííîíà äëÿ êëàññà U îòíîñèòåëüíî ôóíêöèîíàëà ñëîæíîñòè Ψ.  äàëüíåéøåì ñëîæíîñòü ñèñòåìû ÔÀË F îòíîñèòåëüíî ôóíêöèîíàAëà Ψ äëÿ ëþáîãî èç ââåäåííûõ êëàññîâ âèäà UAÁ (âèäà U )AAáóäåì îáîçíà÷àòü ÷åðåç ΨÁ (F ) (ñîîòâåòñòâåííî Ψ (F )), àôóíêöèþ Øåííîíà äëÿ ýòîãî êëàññà îòíîñèòåëüíî Ψ ÷åAðåç ΨAÁ (n) (ñîîòâåòñòâåííî Ψ (n)).  îáîçíà÷åíèÿõ êëàññîâΦUCÁ , UÁ , à òàêæå ñâÿçàííûõ ñ íèìè ôóíêöèîíàëîâ ñëîæíîñòè è ôóíêöèé Øåííîíà, íèæíèé èíäåêñ Á âèäà Á0 áóäåì,êàê îáû÷íî, îïóñêàòü.Îòìåòèì íåêîòîðûå ïðîñòåéøèå ñîîòíîøåíèÿ ìåæäó ââåäåííûìè ôóíêöèÿìè.

Î÷åâèäíî, ÷òî äëÿ ñëîæíîñòåé Ψ0 (F )è Ψ00 (F ) ñèñòåìû ÔÀË F îòíîñèòåëüíî ôóíêöèîíàëà Ψ âêëàññàõ ñõåì U0 è U00 ñîîòâåòñòâåííî âûïîëíÿåòñÿ íåðàâåíñòâîΨ0 (F ) 6 Ψ00 (F ) ,åñëè U0 ⊇ U00 .  ÷àñòíîñòè,ΦΨCÁ (F ) 6 ΨÁ (F ) ,ΨK (F ) 6 Ψπ (F )Ÿ1. Çàäà÷à ñèíòåçà9è ò. ä. Äîâîëüíî ÷àñòî âûäåëåíèå ïîäêëàññîâ èç îñíîâíûõêëàññîâ ñõåì ïðîèñõîäèò çà ñ÷åò íàëîæåíèÿ ðàçëè÷íûõ äîïîëíèòåëüíûõ ñâîéñòâ íà ðàññìàòðèâàåìûå ñõåìû.  ÷àñòíîñòè, èç êëàññà ÊÑ âûäåëÿþò π -ñõåìû, ÊÑ, îáëàäàþùèåñâîéñòâàìè ðàçäåëèòåëüíîñòè, è. ò. ï.Çàìåòèì, ÷òî äëÿ ñëîæíîñòè L (F ) ñèñòåìû ÔÀË F =(f1 , . .

. , fm ) â ëþáîì èç ðàññìàòðèâàåìûõ êëàññîâ ñõåì âûïîëíÿþòñÿ íåðàâåíñòâàmax L (fi ) 6 L (F ) 616i6mmXL (f )i .i=1Çàäà÷à ñèíòåçà äîïóñêàåò òðèâèàëüíîå ðåøåíèå, ñâÿçàííîå ñ èñïîëüçîâàíèåì ïåðåáîðíîãî àëãîðèòìà, êîòîðûé, îäíàêî, èìååò áîëüøóþ òðóäîåìêîñòü è ïðàêòè÷åñêè íå ïðèìåíèì, åñëè ÷èñëî ÁÏ áîëüøå 5.Äëÿ ðåàëèçàöèè ïðîèçâîëüíûõ ÔÀË è ïîëó÷åíèÿ âåðõíèõ îöåíîê èõ ñëîæíîñòè ìîæíî èñïîëüçîâàòü äðóãîé ïðîñòåéøèé ìåòîä ñèíòåçà ñõåì, îñíîâàííûé íà ìîäåëèðîâàíèèñîâåðøåííîé ÄÍÔ. Íà îñíîâå ýòîãî ìîäåëèðîâàíèÿ, â ÷àñòíîñòè, äîêàçûâàåòñÿ ñëåäóþùåå óòâåðæäåíèå.Ëåììà 1.1. Äëÿ ëþáîé ôóíêöèè àëãåáðû ëîãèêè f (x1 , . .

. , xn ),f 6= 0, ñóùåñòâóþò ôîðìóëà Ff , Ff ∈ UΦ , è π -ñõåìà Σf ,êîòîðûå ðåàëèçóþò f è äëÿ êîòîðûõ ñïðàâåäëèâû íåðàâåíñòâà:L (Ff ) 6 2n · |Nf | − 1,L (Σf ) 6 n |Nf | .(1.1)Ñëåäñòâèå 1.  ñèëó (1.1), ñ ó÷åòîì òîãî, ÷òî ÔÀË 0ìîæíî ðåàëèçîâàòü π -ñõåìîé ñëîæíîñòè 2, à òàêæå ôîðìóëîé èç UΦ , èìåþùåé ñëîæíîñòü 2, âûïîëíÿþòñÿ íåðàâåíñòâàLC (n) 6 LΦ (n) 6 n · 2n+1 − 1,LK (n) 6 Lπ (n) 6 n · 2n .10Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÑëåäñòâèå 2.

 ñèëó ñëåäñòâèÿ 1 è ñ ó÷¼òîì ñëåäñòâèÿ 2èç òåîðåìû 2.1 ãëàâû 2 ñïðàâåäëèâî íåðàâåíñòâîD(n) 6 n + dlog ne + 2.Ñëåäóþùåå óòâåðæäåíèå äîêàçûâàåòñÿ ìîäåëèðîâàíèåìñîâåðøåííîé ÄÍÔ ñ èñïîëüçîâàíèåì êîíòàêòíîãî äåðåâà.Ëåììà 1.2. Äëÿ ëþáîé ÔÀË f, f ∈ P2 (n) è f 6= 0, ñó-ùåñòâóþò π -ñõåìà Σf è ôîðìóëà Ff , Ff ∈ UΦ , êîòîðûåðåàëèçóþò f è äëÿ êîòîðûõ, íàðÿäó ñ (1.1), ñïðàâåäëèâûòàêæå íåðàâåíñòâà:L (Σf ) 6 2n + |Nf | − 2,L (Ff ) 6 2n+1 + |Nf | − 4.Äîêàçàòåëüñòâî.  êà÷åñòâå Σf ìîæíî âçÿòü π -ñõåìó, êîòîðàÿ ïîëó÷àåòñÿ èç (1, 2n )-ÊÄ ïîðÿäêà n îò ÁÏ x1 , . . . , xn(ñì.