OK-metodichka-2010-part3 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 7
Описание файла
Файл "OK-metodichka-2010-part3" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2009)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2009)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 7 страницы из PDF
Ëåãêî âèäåòü, ÷òî ñëîæíîñòü ïîñòðîåííîénñõåìû Σf àñèìïòîòè÷åñêè íå áîëüøå, ÷åì 34 2n .52Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÊðàéíèì ñëó÷àåì ñïåöèàëüíîãî êëàññà ÔÀË ÿâëÿåòñÿ¾èíäèâèäóàëüíàÿ¿ ÔÀË (ñèñòåìà ÔÀË), à òàêæå ïîñëåäîâàòåëüíîñòü òàêèõ ÔÀË (ñîîòâåòñòâåííî ñèñòåì ÔÀË) îòn, n = 1, 2, . . . ïåðåìåííûõ.  ýòîì ñëó÷àå äëÿ ïîëó÷åíèÿíèæíèõ îöåíîê ñëîæíîñòè âìåñòî ìîùíîñòíûõ ñîîáðàæåíèé ïðèõîäèòñÿ îïèðàòüñÿ íà òå èëè èíûå îñîáåííîñòè ¾ïîâåäåíèÿ¿ ðåàëèçóåìûõ ôóíêöèé. Ïðîñòåéøèå îöåíêè òàêîãîòèïà áûëè ïîëó÷åíû â 2 (ñì. ëåììû 2.1, 2.2).Óñòàíîâèì, â çàêëþ÷åíèå, ðÿä àíàëîãè÷íûõ îöåíîê è ñèõ ïîìîùüþ äîêàæåì ìèíèìàëüíîñòü èëè àñèìïòîòè÷åñêóþìèíèìàëüíîñòü íåêîòîðûõ ñõåì.Äîêàæåì ñíà÷àëà, ÷òî (1, 2n )-êîíòàêòíîå äåðåâî ìèíèìàëüíûé êîíòàêòíûé äåøèôðàòîð ïîðÿäêà n â êëàññå ðàçäåëèòåëüíûõ (ïî âûõîäàì) ÊÑ.Ëåììà 8.2.
Åñëè ðàçäåëèòåëüíàÿ ïî âûõîäàì (1, m)-ÊÑ Σðåàëèçóåò m ðàçëè÷íûõ ÔÀË, îòëè÷íûõ îò 0, òîL (Σ) > 2m − 2.Äîêàçàòåëüñòâî. Ïóñòü Σ ïðèâåäåííàÿ è, ñëåäîâàòåëüíî, ñâÿçíàÿ ÊÑ îò ÁÏ x1 , . . . , xn . Èç ðàçäåëèòåëüíîñòè Σñëåäóåò, ÷òî ïðè ëþáîì α, α ∈ B n , ñåòü Σ|α ñîñòîèò íå ìåíåå ÷åì èç m ñâÿçíûõ êîìïîíåíò. Çàìåòèì, ÷òî óäàëåíèåâñÿêîãî ðåáðà óâåëè÷èâàåò ÷èñëî ñâÿçíûõ êîìïîíåíò ãðàôàíå áîëåå ÷åì íà åäèíèöó, è ïîýòîìó ÷èñëî |E (Σ|α )| ÷èñëî êîíòàêòîâ, íå ïðîâîäÿùèõ íà íàáîðå α, óäîâëåòâîðÿåòíåðàâåíñòâó(8.8)|E (Σ|α )| > m − 1.Ñóììèðóÿ (8.8) ïî âñåì α, α ∈ B n , è ó÷èòûâàÿ, ÷òî êàæäûéêîíòàêò ÊÑ Σ íå ïðîâîäèò ðîâíî íà ïîëîâèíå âñåõ íàáîðîâêóáà B n , ïîëó÷èì2n−1 L (Σ) > 2n (m − 1) ,Ëåììà äîêàçàíà.L (Σ) > 2m − 2.8. Ñèíòåç ñõåì äëÿ ÔÀË èç ñïåöèàëüíûõ êëàññîâ53Ñëåäñòâèå.
Êîíòàêòíîå äåðåâî ïîðÿäêà n ÿâëÿåòñÿ ìèíè-ìàëüíîé ðàçäåëèòåëüíîé (1, 2n )-ÊÑ, ðåàëèçóþùåé ñèñòåìóÔÀË Qn .Äåéñòâèòåëüíî, â ñîîòâåòñòâèè ñ ëåììîé 8.2, ñëîæíîñòüðàçäåëèòåëüíîé (1, 2n )-ÊÑ íå ìåíüøå ÷åì 2n+1 − 2, òî åñòüíå ìåíüøå ñëîæíîñòè (1, 2n )-êîíòàêòíîãî äåðåâà ïîðÿäêà n.Ëåììà 8.3. Åñëè ñèñòåìà ÔÀË F = (f1 , . . . , fm ) ñîñòîèòèç ïîïàðíî ðàçëè÷íûõ ÔÀË îò ÁÏ X(n), îòëè÷íûõ îò 0 è1, òîmX¯¯K1−n¯Nf ¯ .L (F ) > 2jj=1Äîêàçàòåëüñòâî. Âîçüìåì ïðèâåäåííóþ (1, m)-ÊÑ Σ, ðåàëèçóþùóþ ñèñòåìó ÔÀË F , è çàìåòèì, ÷òî ïðè ëþáîì α, α ∈B n , â ñåòè Σ|α èìååòñÿ ñâÿçíàÿ êîìïîíåíòà, êîòîðàÿ ñîäåðæèò âõîä Σ è òå åå âûõîäû, ãäå ðåàëèçóåìûå ÔÀË îáðàùàþòñÿ â 1 íà íàáîðå α.
Èç íåðàâåíñòâà (1.2) ãëàâû 2 ñëåäóåò,÷òî ïðè ýòîì|E (Σ|α )| > f1 (α) + · · · + fm (α).Ñóììèðóÿ ïîëó÷åííîå íåðàâåíñòâî ïî âñåì íàáîðàì α, α ∈B n , ïðèäåì (ñì. äîêàçàòåëüñòâî ëåììû 8.2) ê íåðàâåíñòâó2n−1 L(Σ) >mX¯¯¯Nf ¯ ,jj=1èç êîòîðîãî âûòåêàåò íåðàâåíñòâî ëåììû.Ëåììà äîêàçàíà.Ñëåäñòâèå.
LK (Jn ) > 2n+1 − 2, òî åñòü ñ ó÷åòîì ëåì-ìû 4.2LK (Jn ) ∼ 2n+1 .54Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìËåììà 8.4. Åñëè äëÿ ÔÀË f , f ∈ P2 (n), è äëÿ ëþáîãî σ ,σ ∈ B , ÔÀË fσ (x1 , . . . , xn−1 , σ) 6≡ 0, 1, òîCCLC&,∨ (f ) > min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.(8.9)Äîêàçàòåëüñòâî. Ïóñòü Σ ìèíèìàëüíàÿ ïî ÷èñëó ÔÝ &è ∨ ÑÔÝ èç êëàññà UC , êîòîðàÿ ðåàëèçóåò ÔÀË f è êîòîðàÿíå ñîäåðæèò öåïî÷åê èç äâóõ ïîñëåäîâàòåëüíî ñîåäèíåííûõÔÝ ¬. Ïóñòü êîíñòàíòà σ , σ ∈ B , ðàâíà 0 òîãäà è òîëüêîòîãäà, êîãäà ÁÏ xn ïîäàåòñÿ â Σ ëèáî íà âõîä ÔÝ &, ëèáîíà âõîä ÔÝ ¬, âûõîä êîòîðîãî ïîñòóïàåò íà âõîä ÔÝ ∨.b , êîòîðàÿ ðåàëèçóåò ÔÀË fσ , fσ 6≡ 0, 1,Ðàññìîòðèì ÑÔÝ Σè ïîëó÷åíà èç ÑÔÝ Σ â ðåçóëüòàòå ïîäñòàíîâêè xn = σ , àòàêæå ïîñëåäóþùåãî ÝÏ íà îñíîâå òîæäåñòâ τ ÏÊ (ñì. 5ãë.
2) âïëîòü äî óñòðàíåíèÿ âñåõ âõîæäåíèé êîíñòàíò. Óáåäèìñÿ â òîì, ÷òî ïðè óêàçàííîì ÝÏ áóäóò óäàëåíû ïî êðàéíåé ìåðå äâà ÔÝ òèïà & èëè ∨.Äåéñòâèòåëüíî, â ñëó÷àå σ = 0 èç ÑÔÝ Σ áóäåò óäàëåíÔÝ E0 , ÿâëÿþùèéñÿ ëèáî ÔÝ òèïà &, íà âõîä êîòîðîãî ïîäàåòñÿ ÁÏ xn , ëèáî ÔÝ òèïà ∨, íà âõîä êîòîðîãî ïîäàåòñÿâûõîä ÔÝ ¬, ïðèñîåäèíåííîãî ê âõîäó xn . Çàìåòèì, ÷òî âûõîä ÔÝ E0 íå ìîæåò áûòü âûõîäîì ñõåìû è íå ìîæåò áûòüâõîäîì ÔÝ ¬, âûõîä êîòîðîãî ÿâëÿåòñÿ âûõîäîì ñõåìû, òàêêàê ïðè ýòîì ÔÀË fσ áûëà áû ðàâíà êîíñòàíòå. Ñëåäîâàòåëüíî, â ÑÔÝ Σ èìååòñÿ ÔÝ E00 òèïà & èëè ∨, íà âõîäêîòîðîãî ïîñòóïàåò ëèáî âûõîä E0 , ëèáî âûõîä ÔÝ ¬, ïðèñîåäèíåííîãî ê âûõîäó E0 .
Ëåãêî âèäåòü, ÷òî ÔÝ E00 òîæåb è, ñëåäîâàòåëüíî, ñïðàáóäåò óäàëåí ïðè ïåðåõîäå îò Σ ê Σâåäëèâû íåðàâåíñòâàb + 2 > L&,∨ (fσ ) + 2,L&,∨ (f ) = L&,∨ (Σ) > L&,∨ (Σ)èç êîòîðûõ âûòåêàåò (8.9).Ëåììà äîêàçàíà.8. Ñèíòåç ñõåì äëÿ ÔÀË èç ñïåöèàëüíûõ êëàññîâ55Ñëåäñòâèå 1.LC (µn ) > 2n+1 + n − 2.(8.10)Äåéñòâèòåëüíî, (8.10) ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèìåíåíèÿ ëåììû 8.4 ïîñëåäîâàòåëüíî êî âñåì èíôîðìàöèîííûìÁÏ y2n −1 , . .
. , y1 è ó÷èòûâàÿ, ÷òî ïîëó÷èâøàÿñÿ â ðåçóëüòàòå ñîîòâåòñòâóþùèõ ïîäñòàíîâîê êîíñòàíò ÔÀË ñóùåñòâåííî çàâèñèò îò ÁÏ x1 , . . . , xn , y0 .Ñëåäñòâèå 2. Èç ñëåäñòâèÿ 1 è ëåììû 4.3 âûòåêàåò àñèìïòîòè÷åñêîå ðàâåíñòâîLC (µn ) ∼ 2n+1 .Ëèòåðàòóðà[1] Àëåêñååâ Â. Á. Ââåäåíèå â òåîðèþ ñëîæíîñòè àëãîðèòìîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.[2] Àëåêñååâ Â. Á., Âîðîíåíêî À. À., Ëîæêèí Ñ. À.,Ðîìàíîâ Ä. Ñ., Ñàïîæåíêî À. À., Ñåëåçíåâà Ñ.
Í.Çàäà÷è ïî êóðñó ¾Îñíîâû êèáåðíåòèêè¿. Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.[3] Àëåêñååâ Â. Á., Ëîæêèí Ñ. À. Ýëåìåíòû òåîðèè ãðàôîâ, ñõåì è àâòîìàòîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òàÂÌèÊ ÌÃÓ, 2000.[4] Áîðîâêîâ À. À. Êóðñ òåîðèè âåðîÿòíîñòåé. Ì.: Íàóêà,1976.[5] Ãàâðèëîâ Ã. Ï., Ñàïîæåíêî À. À. Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîé ìàòåìàòèêå. 3-å èçä., ïåðåðàá.Ì.: ÔÈÇÌÀÒËÈÒ, 2004.[6] Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè, ïîä ðåäàêöèåé Ñ. Â. ßáëîíñêîãî èÎ. Á. Ëóïàíîâà. Ò. 1.
Ì.: Íàóêà, 1974.[7] Åâäîêèìîâ À. À. Î ìàêñèìàëüíîé äëèíå öåïè â åäèíè÷íîì n-ìåðíîì êóáå // Ìàòåì. çàìåòêè. 1969. 6. 3.Ñ. 309319.[8] Åìåëè÷åâ Â. À., Ìåëüíèêîâ Î. È., Ñàðâàíîâ Â. È.,Òûøêåâè÷ Ð. È. Ëåêöèè ïî òåîðèè ãðàôîâ. Ì.: Íàóêà,1977.56Ëèòåðàòóðà57[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.58Ëèòåðàòóðà[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.Ëèòåðàòóðà59[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..
