OK-metodichka-2010-part2 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 13
Описание файла
Файл "OK-metodichka-2010-part2" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2009)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2009)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 13 страницы из PDF
. . , 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..
