С.А. Ложкин - Лекции по основам кибернетики (2010) (1132804), страница 13
Текст из файла (страница 13)
10.4: BDD äëÿ `3îáðàçîì ïðîãðàììà íà÷èíàåò ñâîþ ðàáîòó ñ êîìàíäû, ñîïîñòàâëåííîé âõîäó Σ, è âû÷èñëÿåò òó æå ñàìóþ ÔÀË, ÷òî èBDD Σ.Ñõåìà Σ, Σ ∈ UCÁ , ñ ìîíîòîííîé íóìåðàöèåé âåðøèí(ñì. 1), íàçûâàåòñÿÁ (ñì., íàïðèìåð, [11]). Ïóñòü Σ = Σ(x1 , . . . , xn ; z1 , . . .
, zm ),è ïóñòü, äëÿ îïðåäåëåííîñòè, vi , i ∈ [1, p], ãäå p = |V (Σ)|, âåðøèíà ñ íîìåðîì i, ïðè÷åì âåðøèíû v1 , . . . , vn èìåþò ïîìåòêè x1 , . . . , xn , à âåðøèíû vj1 , . . . , vjm ïîìåòêè z1 , . . . , zmñîîòâåòñòâåííî. Ñîïîñòàâèì âåðøèíå vi , i ∈ [1, p], ¾âíóòðåííþþ¿ ÁÏ ui è áóäåì ñ÷èòàòü, ÷òî vi âûïîëíÿåò êîìàíäó ñíîìåðîì i, êîòîðàÿ ÿâëÿåòñÿ:çèñîìâû÷èñëÿþùåé ïðîãðàììîé (ÂÏ) íàä áà-a) êîìàíäîé ââîäà ui = xi , åñëè i ∈ [1, n];(i)(i) b) âû÷èñëÿþùåé êîìàíäîé ui = ϕ(i) u1 , . . . , uk(i) , ãäåϕ(i) ÔÑ îò k (i) ÁÏ, ïðèïèñàííûé âåðøèíå vi â Σ,(i)à uj , j = 1, . . . , k (i) , ÁÏ, ñîïîñòàâëåííàÿ íà÷àëüíîé âåðøèíå äóãè ñ íîìåðîì j , âõîäÿùåé â vi , åñëèi ∈ (n, p].Êðîìå òîãî, áóäåì ñ÷èòàòü, ÷òî êàæäîé âåðøèíå vji , i ∈ [1, m],ñîîòâåòñòâóåò êîìàíäà ñ íîìåðîì (p + i), ÿâëÿþùàÿñÿ êîìàíäîé âûâîäà zi = uji .Ïðåäïîëàãàåòñÿ, ÷òî êîìàíäû ÂÏ Σ âûïîëíÿþòñÿ ïîñëåäîâàòåëüíî â ñîîòâåòñòâèè ñ èõ íîìåðàìè â ìîìåíòû âðå-10.Íåêîòîðûå ìîäèôèêàöèè îñíîâíûõ êëàññîâ ñõåì93ìåíè 1, 2, .
. . , p + m è ÷òî çíà÷åíèå ÁÏ ui , âû÷èñëåííîå âìîìåíò âðåìåíè i, i ∈ (n, p], çàíèìàåò îòäåëüíóþ áèòîâóþÿ÷åéêó ïàìÿòè íà îòðåçêå âðåìåíè [i, ai ), ãäå ai ìàêñèìàëüíûé íîìåð êîìàíäû, â êîòîðîé âñòðå÷àåòñÿ ui . Ìàêñèìàëüíîå ÷èñëî îòðåçêîâ âèäà [i, ai ), ãäå i ∈ (n, p], èìåþùèõíåïóñòîå ïåðåñå÷åíèå, íàçûâàåòñÿÂÏ Σ, è îïðåäåëÿåò ìèíèìàëüíîå ÷èñëî ÿ÷ååê ïàìÿòè, íåîáõîäèìûõ äëÿõðàíåíèÿ åå âíóòðåííèõ ÁÏ un+1 , .
. . , up . Çàìåòèì, ÷òî ÷èñëî ÔÝ ÂÏ Σ õàðàêòåðèçóåò âðåìÿ âûïîëíåíèÿ åå âû÷èñëÿþùèõ êîìàíä íà îäíîì ïðîöåññîðå, à ìàêñèìàëüíàÿ ãëóáèíàâåðøèí Σ âðåìÿ âûïîëíåíèÿ åå âû÷èñëÿþùèõ êîìàíä íàïàðàëëåëüíûõ ïðîöåññîðàõ.øèðèíîéx1 1 •x2 • 2 4 •ux3 •) 5∨& 8 •~∨ 7 •u• 3 •) 6&'&%$!"# •~ ∨10•~¬ 9∨x1 1 • 9 •u&x2 • 2∨•) 4 7 •u& 6 •x3 • 3 •) 5∨• 8∨z1∨!"#•{ '&%$10z1a)b)¬Ðèñ.
10.5: ýêâèâàëåíòíûå ÂÏ øèðèíû 3 è 2Òàê, íà ðèñ. 10.5a ïðèâåäåíà ìîíîòîííàÿ íóìåðàöèÿ âåðøèí äëÿ ÑÔÝ, ïîêàçàííîé íà ðèñ. 4.2a, êîòîðàÿ çàäàåò ÂÏøèðèíû 3, à íà ðèñ. 10.5b ýêâèâàëåíòíàÿ åé ÂÏ øèðèíû 2.Äåéñòâèòåëüíî, ïðè âûïîëíåíèè ïåðâîé (âòîðîé) èç ýòèõ ÂÏäëÿ õðàíåíèÿ âñåõ âíóòðåííèõ ÁÏ, ïðèíàäëåæàùèõ êàæäîìó èç ìíîæåñòâ {u4 }, {u5 , u7 , u8 } è {u6 , u9 , u10 } (ñîîòâåò-94Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìñòâåííî {u4 , u7 , u9 } è {u5 , u6 , u8 , u10 }) ìîæíî èñïîëüçîâàòüîäíó è òó æå ÿ÷åéêó ïàìÿòè.
Ëåãêî âèäåòü òàêæå, ÷òî ãëóáèíà îáåèõ ðàññìàòðèâàåìûõ ÑÔÝ ðàâíà 4.Äëÿ ëþáîé ÔÀË ñóùåñòâóåò ðåàëèçóþùàÿåå ÂÏ íàä áàçèñîì Á0 øèðèíû íå áîëüøå, ÷åì 2.Äîêàçàòåëüñòâî. Èíäóêöèåé ïî äëèíå ìîæíî ïîêàçàòü ÷òîËåììà 10.2.ëþáàÿ ÄÍÔ èëè ÊÍÔ ïîñëå åå îïòèìèçàöèè ïî ÷èñëó îòðèöàíèé è âûïîëíåíèÿ íåêîòîðûõ ïðåîáðàçîâàíèé ïîäîáèÿ(ñì.
2), à òàêæå ïðè ïîäõîäÿùåé ìîíîòîííîé íóìåðàöèèâåðøèí ïåðåõîäèò â ÂÏ øèðèíû 2. Äåéñòâèòåëüíî, ïóñòüÂÏ Σ0 íàä áàçèñîì Á0 íà øàãå ñ íîìåðîì t âû÷èñëÿåò çíà÷åíèå ut ÄÍÔ A0 îò ÁÏ X(n), ïîìåùàÿ åãî â ÿ÷åéêó ïàìÿòèñ íîìåðîì (n + 1), è ïóñòü ÄÍÔ A èìååò âèäA = A0 ∨ K = A0 ∨ (xj1 ∨ . . . ∨ xjr ) · xjr+1 · . . . · xjq .Òîãäà ÂÏ Σ, âû÷èñëÿþùàÿ ÄÍÔ A, ïîëó÷àåòñÿ äîáàâëåíèåìê Σ0 êîìàíä1 :ut+1 = uj1 ∨ uj2 , ut+2 = ut+1 ∨ uj3 , . . .
, ut+r−1 = ut+r−2 ∨ ujr ,ut+r = ut+r−1 , ut+r+1 = ut+r · ujr+1 , . . . , ut+q = ut+q−1 · ujq ,ut+q+1 = ut ∨ ut+q ,ãäå âíóòðåííèå ÁÏ ut+1 , . . . , ut+q ïîìåùàþòñÿ â ÿ÷åéêó ïàìÿòè ñ íîìåðîì (n + 2), à ÁÏ ut+q+1 â ÿ÷åéêó ñ íîìåðîì(n + 1).Ëåììà äîêàçàíà.1Ïðèâåäåííûé ñïèñîê êîìàíä åñòåñòâåííûì îáðàçîì âèäîèçìåíÿåòñÿ â ñëó÷àå r 6 1 èëè r = q .Ëèòåðàòóðà[1]Àëåêñååâ Â. Á. Ââåäåíèå â òåîðèþ ñëîæíîñòè àëãîðèò-[2]Àëåêñååâ Â.
Á., Âîðîíåíêî À. À., Ëîæêèí Ñ. À.,Ðîìàíîâ Ä. Ñ., Ñàïîæåíêî À. À., Ñåëåçíåâà Ñ. Í.ìîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.Çàäà÷è ïî êóðñó ¾Îñíîâû êèáåðíåòèêè¿. Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2002.[3]Àëåêñååâ Â. Á., Ëîæêèí Ñ. À. Ýëåìåíòû òåîðèè ãðà-[4]Áîðîâêîâ À. À. Êóðñ òåîðèè âåðîÿòíîñòåé.
Ì.: Íàóêà,[5]ôîâ, ñõåì è àâòîìàòîâ. Ì.: Èçäàòåëüñêèé îòäåë ô-òàÂÌèÊ ÌÃÓ, 2000.1976.Ãàâðèëîâ Ã. Ï., Ñàïîæåíêî À. À.Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîé ìàòåìàòèêå. 3-å èçä., ïåðåðàá.Ì.: ÔÈÇÌÀÒËÈÒ, 2004.[6] Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè, ïîä ðåäàêöèåéè. Ò. 1.
Ì.: Íàóêà, 1974.Ñ. Â. ßáëîíñêîãîÎ. Á. Ëóïàíîâà[7] Åâäîêèìîâ À. À. Î ìàêñèìàëüíîé äëèíå öåïè â åäè-íè÷íîì n-ìåðíîì êóáå // Ìàòåì. çàìåòêè. 1969. 6. 3.Ñ. 309319.[8]Åìåëè÷åâ Â. À., Ìåëüíèêîâ Î. È., Ñàðâàíîâ Â. È.,Òûøêåâè÷ Ð. È. Ëåêöèè ïî òåîðèè ãðàôîâ. Ì.: Íàóêà,1977.9596Ëèòåðàòóðà[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.97Ëèòåðàòóðà[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.98Ëèòåðàòóðà[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}
