OK-metodichka-2010-part4 (1132795), страница 3
Текст из файла (страница 3)
Äëÿ ëþáîé ÊÑ Σ ñóùåñòâóþò ýêâèâàëåíòíûååé (1, 0)- è (0, 1)-ñàìîêîððåêòèðóþùèåñÿ ÊÑ Σ0 è Σ00 ñîîòâåòñòâåííî òàêèå, ÷òîL(Σ0 ) 6 L(Σ) + ζ(Σ), L(Σ00 ) 6 L(Σ) + ζ(Σ).(2.1)Ýòîò ñïîñîá ïîçâîëÿåò óñòàíîâèòü àñèìïòîòèêó ôóíêöèèKØåííîíà äëÿ ñëîæíîñòè ÊÑ èç UK(0,1) è U(1,0) .Äëÿ ÔÀË f è p > 0, q > 0 îïðåäåëèì åå (p, q)-ñàìîêîððåêòèðóþùóþñÿ êîíòàêòíóþ ñëîæíîñòü LK(p,q) (f ) êàê ìèíèKìàëüíóþ ñëîæíîñòü ÊÑ Σ, Σ ∈ U(p,q) , ðåàëèçóþùåé f , àçàòåì ââåäåì ñîîòâåòñòâóþùóþ ôóíêöèþ ØåííîíàKLK(p,q) (n) = max L(p,q) (f ).f ∈P2 (n)Î÷åâèäíî, ÷òîKKLK (f ) 6 LK(p,q) (f ) L (n) 6 L(p,q) (n)Kòàê êàê UK(p,q) ⊆ U .(2.2)16 Ãëàâà 4. Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõ ñèñòåìÒåîðåìà 2.1.
Äëÿ n = 1, 2, ... èìååò ìåñòî ñëåäóþùèåàñèìïòîòè÷åñêèå ðàâåíñòâàKLK(1,0) (n) ∼ L(0,1) (n) ∼2n.nÄîêàçàòåëüñòâî. Òðåáóåìûå íèæíèå îöåíêè äëÿ ôóíêöèéKØåííîíà LK(1,0) (n) è L(0,1) (n) âûòåêàþò èç (2.2) è ìîùíîñòíûõ íèæíèõ îöåíîê ôóíêöèè Øåííîíà LK (n) èç òåîðåìû2.1 ãëàâû 3.Äëÿ ïîëó÷åíèÿ ñîîòâåòñòâóþùèõ âåðõíèõ îöåíîê âîçüìåì ïðîèçâîëüíóþ ÔÀË f , f ∈ P2 (n), è ïîñòðîèì äëÿ íååÊÑ Σf ïî òåîðåìå 6.1 ãëàâû 3.
Èç çàìå÷àíèÿ ê ýòîé òåîðåìåâûòåêàåò, ÷òî ïðè óêàçàííûõ òàì çíà÷åíèÿõ ïàðàìåòðîâ2nζ(Σf ) = o( √ )n nè ïîýòîìó, â ñîîòâåòñòâèè ñ ëåììîé 2.2 è (2.1), ñóùåñòâóþò00KÊÑ Σ0f ∈ UK(1,0) è ÊÑ Σf ∈ U(0,1) , êîòîðûå ðåàëèçóþò ÔÀËf ñî ñëîæíîñòüþ, àñèìïòîòè÷åñêè íå ïðåâîñõîäÿùåéÒåîðåìà äîêàçàíà.2nn .Äëÿ ïîñòðîåíèÿ íåòðèâèàëüíûõ ÊÑ, êîððåêòèðóþùèõáîëåå îäíîãî îáðûâà èëè çàìûêàíèÿ, ìîæíî èñïîëüçîâàòüñëåäóþùóþ êîíñòðóêöèþ. Ïóñòü ÊÑ Σi , i = 1, . .
. , r, ðåàëèçóåò ÔÀË f è êîððåêòèðóåò ti îáðûâîâ (çàìûêàíèé), òîãäàÊÑ Σ, êîòîðàÿ ïîëó÷àåòñÿ â ðåçóëüòàòå ïàðàëëåëüíîãî (ïîñëåäîâàòåëüíîãî) ñîåäèíåíèÿ Σ1 , . . . , Σr , ðåàëèçóåò ÔÀË fñ êîððåêöèåé t1 + . . . + tr + r − 1 îáðûâîâ (çàìûêàíèé).Èíòåðåñíûé ïðèìåð íåòðèâèàëüíîé ñàìîêîððåêöèè ÊÑäà¼ò êîíòàêòíàÿ ñõåìà, ðåàëèçóþùàÿ ÔÀË `n è êîððåêòèðóþùàÿ îäèí îáðûâ, êîòîðàÿ ïîëó÷àåòñÿ èç ñõåìû Êàðäî äîáàâëåíèåì 4 äîïîëíèòåëüíûõ êîíòàêòîâ, ïðîâåäåííûõ ñëåäóþùèì îáðàçîì: äëÿ êàæäîãî σ , σ ∈ B , èç âõîäà (âûõîäà)ýòîé ñõåìû, ïðîâåäåì êîíòàêò âèäà xσn (ñîîòâåòñòâåííî xσ1 )2. Ñàìîêîððåêòèðóþùèåñÿ ÊÑ17â âåðøèíó, ñîåäèíåííóþ êîíòàêòîì âèäà xσ̄n (ñîîòâåòñòâåííîxσ̄1 ) ñ åå âûõîäîì (ñîîòâåòñòâåííî âõîäîì).
Óêàçàííàÿ ñõåìàÿâëÿåòñÿ ìèíèìàëüíîé â ñèëó ëåììû 1.4 ãëàâû 3 è, ñëåäîâàòåëüíî, ñïðàâåäëèâî óòâåðæäåíèå.Ëåììà 2.3. Äëÿ n = 1, 2, . . . èìåþò ìåñòî ðàâåíñòâà¡ ¢KLK(0,1) (`n ) = L(0,1) `n = 4n.Ëèòåðàòóðà[1] Àëåêñååâ Â. Á. Ââåäåíèå â òåîðèþ ñëîæíîñòè àëãîðèòìîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.[2] Àëåêñååâ Â. Á., Âîðîíåíêî À. À., Ëîæêèí Ñ. À.,Ðîìàíîâ Ä. Ñ., Ñàïîæåíêî À. À., Ñåëåçíåâà Ñ. Í.Çàäà÷è ïî êóðñó ¾Îñíîâû êèáåðíåòèêè¿. Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.[3] Àëåêñååâ Â. Á., Ëîæêèí Ñ. À. Ýëåìåíòû òåîðèè ãðàôîâ, ñõåì è àâòîìàòîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òàÂÌèÊ ÌÃÓ, 2000.[4] Áîðîâêîâ À. À. Êóðñ òåîðèè âåðîÿòíîñòåé.
Ì.: Íàóêà,1976.[5] Ãàâðèëîâ Ã. Ï., Ñàïîæåíêî À. À. Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîé ìàòåìàòèêå. 3-å èçä., ïåðåðàá.Ì.: ÔÈÇÌÀÒËÈÒ, 2004.[6] Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè, ïîä ðåäàêöèåé Ñ. Â. ßáëîíñêîãî èÎ. Á. Ëóïàíîâà. Ò. 1. Ì.: Íàóêà, 1974.[7] Åâäîêèìîâ À. À. Î ìàêñèìàëüíîé äëèíå öåïè â åäèíè÷íîì n-ìåðíîì êóáå // Ìàòåì.
çàìåòêè. 1969. 6. 3.Ñ. 309319.[8] Åìåëè÷åâ Â. À., Ìåëüíèêîâ Î. È., Ñàðâàíîâ Â. È.,Òûøêåâè÷ Ð. È. Ëåêöèè ïî òåîðèè ãðàôîâ. Ì.: Íàóêà,1977.18Ëèòåðàòóðà19[9] Æóðàâëåâ Þ. È. Ëîêàëüíûå àëãîðèòìû âû÷èñëåíèÿèíôîðìàöèè // Êèáåðíåòèêà. 1. 1965. Ñ. 1219.[10] Æóðàâëåâ Þ. È. Òåîðåòèêî-ìíîæåñòâåííûå ìåòîäû âàëãåáðå ëîãèêè // Ïðîáëåìû êèáåðíåòèêè. Âûï. 8.Ì.: Ôèçìàòãèç, 1962. Ñ. 5-44.[11] Êóçüìèí Â. À. Îöåíêè ñëîæíîñòè ðåàëèçàöèè ôóíêöèé àëãåáðû ëîãèêè ïðîñòåéøèìè âèäàìè áèíàðíûõïðîãðàìì // Ñá.
¾Ìåòîäû äèñêðåòíîãî àíàëèçà âòåîðèè êîäîâ è ñõåì¿. Íîâîñèáèðñê, 1976. Âûï. 29.Ñ. 1139[12] Ëîæêèí Ñ. À. Îöåíêè âûñîêîé ñòåïåíè òî÷íîñòè äëÿñëîæíîñòè óïðàâëÿþùèõ ñèñòåì èç íåêîòîðûõ êëàññîâ // Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè. Âûï. 6.Ì.: Íàóêà, 1996. Ñ. 189214.[13] Ëîæêèí Ñ. À. Ñòðóêòóðíîå ìîäåëèðîâàíèå è äåêîìïîçèöèÿ äëÿ íåêîòîðûõ êëàññîâ ñõåì. Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2001.[14] Ëóïàíîâ Î. Á. Àñèìïòîòè÷åñêèå îöåíêè ñëîæíîñòèóïðàâëÿþùèõ ñèñòåì.
Ì.: Èçä-âî ÌÃÓ, 1984.[15] Ëóïàíîâ Î. Á. Î ñëîæíîñòè ðåàëèçàöèè ôóíêöèéàëãåáðû ëîãèêè ðåëåéíî-êîíòàêòíûìè ñõåìàìè //Ïðîáëåìû êèáåðíåòèêè. Âûï. 11. Ì.: Íàóêà, 1964.Ñ. 2548.[16] Ëóïàíîâ Î. Á. Î ñëîæíîñòè ðåàëèçàöèè ôóíêöèé àëãåáðû ëîãèêè ôîðìóëàìè // Ïðîáëåìû êèáåðíåòèêè.Âûï. 3. Ì.: Ôèçìàòãèç, 1960.
Ñ. 6180.[17] Ìóðîãà Ñ. Ñèñòåìû ïðîåêòèðîâàíèÿ ñâåðõáîëüøèõèíòåãðàëüíûõ ñõåì. Ì.: Ìèð, 1985.20Ëèòåðàòóðà[18] Íå÷èïîðóê Ý. È. Î òîïîëîãè÷åñêèõ ïðèíöèïàõ ñàìîêîððåêòèðîâàíèÿ // Ïðîáëåìû êèáåðíåòèêè. Âûï. 21.Ì.: Íàóêà, 1969. Ñ. 5102.[19] Íèãìàòóëëèí Ð. Ã. Ñëîæíîñòü áóëåâûõ ôóíêöèé.Ì.: Íàóêà, 1991.[20] Ïîâàðîâ Ã. Í.
Ìåòîä ñèíòåçà âû÷èñëèòåëüíûõ è óïðàâëÿþùèõ êîíòàêòíûõ ñõåì // Àâòîìàòèêà è òåëåìåõàíèêà. 1957. Ò. 18. 2. Ñ. 145162.[21] Ñàïîæåíêî À. À. Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû. Ì.: Èçä-âî ÌÃÓ, 1975.[22] Ñàïîæåíêî À. À. Íåêîòîðûå âîïðîñû ñëîæíîñòè àëãîðèòìîâ. Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2001.[23] Ñàïîæåíêî À. À., Ëîæêèí Ñ. À. Ìåòîäû ëîãè÷åñêîãî ïðîåêòèðîâàíèÿ è îöåíêè ñëîæíîñòè ñõåì íà äîïîëíÿþùèõ ÌÎÏ-òðàíçèñòîðàõ // Ìèêðîýëåêòðîíèêà. 1983. Ò. 12. 1. Ñ. 4247.[24] Ôèõòåíãîëüö Ã. Ì.
Îñíîâû ìàòåìàòè÷åñêîãî àíàëèçà,òîì 1. Ì.: Íàóêà, 1968.[25] Ôèõòåíãîëüö Ã. Ì. Îñíîâû ìàòåìàòè÷åñêîãî àíàëèçà,òîì 2. Ì.: Íàóêà, 1964.[26] ×åãèñ È. À., ßáëîíñêèé Ñ. Â. Ëîãè÷åñêèå ñïîñîáûêîíòðîëÿ ðàáîòû ýëåêòðè÷åñêèõ ñõåì // Òðóäû ÌÈÀÍ ÑÑÑÐ. Ò. 51. Ì.: Èçä-âî ÀÍ ÑÑÑÐ, 1958. Ñ.
270360.[27] ßáëîíñêèé Ñ. Â. Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó.2-å èçä., ïåðåðàá. è äîï. Ì.: Íàóêà, 1986.[28] ßáëîíñêèé Ñ. Â. Íàäåæíîñòü óïðàâëÿþùèõ ñèñòåì.Ì.: Èçä-âî ÌÃÓ, 1991.Ëèòåðàòóðà21[29] ßáëîíñêèé Ñ. Â. Íåêîòîðûå âîïðîñû íàäåæíîñòè èêîíòðîëÿ óïðàâëÿþùèõ ñèñòåì // Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè. Âûï. 1.
Ì.: Íàóêà, 1988. Ñ. 525.[30] ßáëîíñêèé Ñ. Â. Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ óïðàâëÿþùèõ ñèñòåì. Ì.: Èçä-âî ÌÃÓ, 1986.[31] Cardot C. Quelques resultats sur l'application de l'algebrede Boole a la synthese des circuits a relais //Ann. Telecommunications. 1952. V.7. 2. P. 7584.[32] Shannon C.
E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn. J. 1949. V. 28. 1.P. 5998 (Ðóññêèé ïåðåâîä: Øåííîí Ê. Ðàáîòû ïîòåîðèè èíôîðìàöèè è êèáåðíåòèêå. Ì.: ÈË, 1963.Ñ. 59101).[33] Wegener I. Branching programs and binary decisiondiagrams. SIAM Publishers, 2000..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
