OK-metodichka-2010-part1 (1132792), страница 9
Текст из файла (страница 9)
[6, 22, 10]).P2 (n)f 0 f 00KΣM0Sn−3 (NK , f ) = Sn−3 (NK , f 00 )Òåîðåìà 8.1öèþ f ÷åòíîé äëèíû t = 2k > 2n − 2 > 4. Äåéñòâèòåëüíî,åñëè óêàçàííàÿ ÔÀË f íàéäåíà, à åå ìíîæåñòâî Nf ñîîòâåò-58Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûñòâóåò ðèñ. 8.1a, òî, ïîëàãàÿNf 0 = Nf \ {α1 }è Nf 00 = Nf \ {αt+1 } ,ïîëó÷èì öåïíûå ÔÀË f 0 è f 00 íå÷åòíîé äëèíû 2k − 1 òàêèå,÷òî êàæäîå ðåáðî Ni , ãäå i = 2, .
. . , t−1, âõîäèò â ÄÍÔ ΣMîäíîé èç íèõ, íî íå âõîäèò â ÄÍÔ ΣM äðóãîé. Ïðè ýòîì,î÷åâèäíî, Sk−2 (Nk , f 0 ) = Sk−2 (Nk , f 00 ) è, ñëåäîâàòåëüíî, èñêîìàÿ ÝÊ K ñîîòâåòñòâóåò ðåáðó Nk .Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà âîçüìåì â êà÷åñòâå föåïíóþ ÔÀË äëèíû (2n − 2), ó êîòîðîé ìíîæåñòâî Nf ñîñòîèò èç âñåõ íàáîðîâ αi = (1, . . . , 1, 0, . . . , 0), ãäå i ∈ [1, n],| {z } | {z }in−iè íàáîðîâ αn+i = αi , i ∈ [1, n), à ðåáðî ñ íîìåðîì j, j ∈[1, 2n − 2], èìååò âèä Nj = {αj , αj+1 } (ñì. ðèñ. 8.2) è ïðèìåíèì ê íåé îïèñàííûå âûøå ïîñòðîåíèÿ.Òåîðåìà äîêàçàíà.Çàìå÷àíèå 1.Èç òåîðåìû ñëåäóåò, ÷òî êðèòåðèé âõîæäåíèÿ ÝÊ â ÄÍÔ ΣM íå èìååò òàêîãî ëîêàëüíîãî õàðàêòåðà,êàê êðèòåðèé âõîæäåíèÿ ÝÊ â ÄÍÔ ΣT (ñðàâíèòå ñ òåîðåìîé 4.1).Çàìå÷àíèå 2.
Èçâåñòíî [7], ÷òî ïðè n > 14 â P2 (n) èìååòñÿöåïíàÿ ÔÀË ÷åòíîé äëèíû t, t > 2n−11 − 4, íà îñíîâå êîòîðîé ñïðàâåäëèâîñòü òåîðåìûìîæíî óñòàíîâèòü äëÿ îêðåñòtíîñòè ïîðÿäêà 2 − 2 (ñì. äîêàçàòåëüñòâî).Ëèòåðàòóðà[1]Àëåêñååâ Â. Á. Ââåäåíèå â òåîðèþ ñëîæíîñòè àëãîðèò-[2]Àëåêñååâ Â. Á., Âîðîíåíêî À. À., Ëîæêèí Ñ. À.,Ðîìàíîâ Ä. Ñ., Ñàïîæåíêî À. À., Ñåëåçíåâà Ñ. Í.ìîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.Çàäà÷è ïî êóðñó ¾Îñíîâû êèáåðíåòèêè¿. Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.[3]Àëåêñååâ Â. Á., Ëîæêèí Ñ. À.
Ýëåìåíòû òåîðèè ãðà-[4]Áîðîâêîâ À. À. Êóðñ òåîðèè âåðîÿòíîñòåé. Ì.: Íàóêà,[5]ôîâ, ñõåì è àâòîìàòîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òàÂÌèÊ ÌÃÓ, 2000.1976.Ãàâðèëîâ Ã. Ï., Ñàïîæåíêî À. À.Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîé ìàòåìàòèêå. 3-å èçä., ïåðåðàá.Ì.: ÔÈÇÌÀÒËÈÒ, 2004.[6] Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè, ïîä ðåäàêöèåéè.
Ò. 1. Ì.: Íàóêà, 1974.Ñ. Â. ßáëîíñêîãîÎ. Á. Ëóïàíîâà[7] Åâäîêèìîâ À. À. Î ìàêñèìàëüíîé äëèíå öåïè â åäè-íè÷íîì n-ìåðíîì êóáå // Ìàòåì. çàìåòêè. 1969. 6. 3.Ñ. 309319.[8]Åìåëè÷åâ Â. À., Ìåëüíèêîâ Î. È., Ñàðâàíîâ Â. È.,Òûøêåâè÷ Ð. È. Ëåêöèè ïî òåîðèè ãðàôîâ. Ì.: Íàóêà,1977.5960Ëèòåðàòóðà[9]Æóðàâëåâ Þ. È. Ëîêàëüíûå àëãîðèòìû âû÷èñëåíèÿèíôîðìàöèè // Êèáåðíåòèêà. 1.
1965. Ñ. 1219.[10]Æóðàâëåâ Þ. È. Òåîðåòèêî-ìíîæåñòâåííûå ìåòîäû â[11]Êóçüìèí Â. À. Îöåíêè ñëîæíîñòè ðåàëèçàöèè ôóíê-[12]Ëîæêèí Ñ. À. Îöåíêè âûñîêîé ñòåïåíè òî÷íîñòè äëÿ[13]Ëîæêèí Ñ. À. Ñòðóêòóðíîå ìîäåëèðîâàíèå è äåêîì-[14]Ëóïàíîâ Î. Á.[15]Ëóïàíîâ Î. Á.[16]Ëóïàíîâ Î. Á. Î ñëîæíîñòè ðåàëèçàöèè ôóíêöèé àë-[17]Ìóðîãà Ñ.àëãåáðå ëîãèêè // Ïðîáëåìû êèáåðíåòèêè. Âûï. 8.Ì.: Ôèçìàòãèç, 1962. Ñ. 5-44.öèé àëãåáðû ëîãèêè ïðîñòåéøèìè âèäàìè áèíàðíûõïðîãðàìì // Ñá. ¾Ìåòîäû äèñêðåòíîãî àíàëèçà âòåîðèè êîäîâ è ñõåì¿.
Íîâîñèáèðñê, 1976. Âûï. 29.Ñ. 1139ñëîæíîñòè óïðàâëÿþùèõ ñèñòåì èç íåêîòîðûõ êëàññîâ // Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè. Âûï. 6.Ì.: Íàóêà, 1996. Ñ. 189214.ïîçèöèÿ äëÿ íåêîòîðûõ êëàññîâ ñõåì. Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2001.Àñèìïòîòè÷åñêèå îöåíêè ñëîæíîñòèóïðàâëÿþùèõ ñèñòåì. Ì.: Èçä-âî ÌÃÓ, 1984.Î ñëîæíîñòè ðåàëèçàöèè ôóíêöèéàëãåáðû ëîãèêè ðåëåéíî-êîíòàêòíûìè ñõåìàìè //Ïðîáëåìû êèáåðíåòèêè. Âûï. 11.
Ì.: Íàóêà, 1964.Ñ. 2548.ãåáðû ëîãèêè ôîðìóëàìè // Ïðîáëåìû êèáåðíåòèêè.Âûï. 3. Ì.: Ôèçìàòãèç, 1960. Ñ. 6180.Ñèñòåìû ïðîåêòèðîâàíèÿ ñâåðõáîëüøèõèíòåãðàëüíûõ ñõåì. Ì.: Ìèð, 1985.61Ëèòåðàòóðà[18]Íå÷èïîðóê Ý. È. Î òîïîëîãè÷åñêèõ ïðèíöèïàõ ñàìî-[19]Íèãìàòóëëèí Ð. Ã.[20]Ïîâàðîâ Ã. Í. Ìåòîä ñèíòåçà âû÷èñëèòåëüíûõ è óï-[21]Ñàïîæåíêî À.
À. Äèçúþíêòèâíûå íîðìàëüíûå ôîð-[22]Ñàïîæåíêî À. À. Íåêîòîðûå âîïðîñû ñëîæíîñòè àë-[23]Ñàïîæåíêî À. À., Ëîæêèí Ñ. À. Ìåòîäû ëîãè÷åñêî-[24]Ôèõòåíãîëüö Ã. Ì. Îñíîâû ìàòåìàòè÷åñêîãî àíàëèçà,[25]Ôèõòåíãîëüö Ã. Ì. Îñíîâû ìàòåìàòè÷åñêîãî àíàëèçà,[26]×åãèñ È. À., ßáëîíñêèé Ñ. Â.êîððåêòèðîâàíèÿ // Ïðîáëåìû êèáåðíåòèêè. Âûï. 21.Ì.: Íàóêà, 1969. Ñ. 5102.Ì.: Íàóêà, 1991.Ñëîæíîñòü áóëåâûõ ôóíêöèé.ðàâëÿþùèõ êîíòàêòíûõ ñõåì // Àâòîìàòèêà è òåëåìåõàíèêà. 1957.
Ò. 18. 2. Ñ. 145162.ìû. Ì.: Èçä-âî ÌÃÓ, 1975.ãîðèòìîâ. Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2001.ãî ïðîåêòèðîâàíèÿ è îöåíêè ñëîæíîñòè ñõåì íà äîïîëíÿþùèõ ÌÎÏ-òðàíçèñòîðàõ // Ìèêðîýëåêòðîíèêà. 1983. Ò. 12. 1. Ñ. 4247.òîì 1. Ì.: Íàóêà, 1968.òîì 2. Ì.: Íàóêà, 1964.Ëîãè÷åñêèå ñïîñîáûêîíòðîëÿ ðàáîòû ýëåêòðè÷åñêèõ ñõåì // Òðóäû ÌÈÀÍ ÑÑÑÐ. Ò. 51.
Ì.: Èçä-âî ÀÍ ÑÑÑÐ, 1958. Ñ. 270360.[27]ßáëîíñêèé Ñ. Â. Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó.[28]ßáëîíñêèé Ñ. Â. Íàäåæíîñòü óïðàâëÿþùèõ ñèñòåì.2-å èçä., ïåðåðàá. è äîï. Ì.: Íàóêà, 1986.Ì.: Èçä-âî ÌÃÓ, 1991.62Ëèòåðàòóðà[29]ßáëîíñêèé Ñ. Â.[30]ßáëîíñêèé Ñ. Â. Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ óï-[31]Cardot C. Quelques resultats sur l'application de l'algebre[32]Íåêîòîðûå âîïðîñû íàäåæíîñòè èêîíòðîëÿ óïðàâëÿþùèõ ñèñòåì // Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè. Âûï. 1. Ì.: Íàóêà, 1988.
Ñ. 525.ðàâëÿþùèõ ñèñòåì. Ì.: Èçä-âî ÌÃÓ, 1986.de Boole a la synthese des circuits a relais //Ann. Telecommunications. 1952. V.7. 2. P. 7584.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}
