OK-metodichka-2010-part2 (1132793)
Текст из файла
Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåòèìåíè Ì. Â. ËîìîíîñîâàÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. À. ËîæêèíËåêöèè ïî îñíîâàìêèáåðíåòèêè(âàðèàíò 2010 ã., ãëàâà 2)Ìîñêâà 2010ÎãëàâëåíèåÂâåäåíèå24Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì. Îöåíêà÷èñëà ñõåì, èõ ñòðóêòóðíûå ïðåäñòàâëåíèÿ.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ óïðàâëÿþùèõñèñòåì1234567Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé,ñõåì.
Ñâîéñòâà ìàòðèö äîñòèæèìîñòè ñåòåé,îöåíêà ÷èñëà ñåòåé . . . . . . . . . . . . . . . . 7Ôîðìóëû, èõ ñòðóêòóðà, ýêâèâàëåíòíîñòü è ñïîñîáûçàäàíèÿ. Îïòèìèçàöèÿ ïîäîáíûõ ôîðìóë ïîãëóáèíå . . . . . . . . . . . . . . . . . . . . . . . 16Çàäà÷à ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ñõåì íàïðèìåðå ôîðìóë. Ïîëíîòà ñèñòåìû îñíîâíûõòîæäåñòâ äëÿ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèéôîðìóë áàçèñà {&, ∨, ¬} .
. . . . . . . . . . . . 25Ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ. Îöåíêà÷èñëà ôîðìóë è ñõåì â áàçèñå {&, ∨, ¬} . . . . 32Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ñõåì èç ôóíêöèîíàëüíûõýëåìåíòîâ è ìîäåëèðîâàíèå ñ èõ ïîìîùüþ ôîðìóëüíûõïðåîáðàçîâàíèé. Ìîäåëèðîâàíèå ýêâèâàëåíòíûõïðåîáðàçîâàíèé ôîðìóë è ñõåì â ðàçëè÷íûõáàçèñàõ, òåîðåìà ïåðåõîäà . .
. . . . . . . . . . 40Êîíòàêòíûå ñõåìû è π -ñõåìû, îöåíêà èõ ÷èñëà.Îñîáåííîñòè ôóíêöèîíèðîâàíèÿ ìíîãîïîëþñíûõñõåì . . . . . . . . . . . . . . . . . . . . . . . . . 492Îãëàâëåíèå37Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõñõåì. Îñíîâíûå òîæäåñòâà, âûâîäâñïîìîãàòåëüíûõ è îáîáùåííûõ òîæäåñòâ .
. . 618 Ïîëíîòà ñèñòåìû îñíîâíûõ òîæäåñòâè îòñóòñòâèå êîíå÷íîé ïîëíîé ñèñòåìûòîæäåñòâ â êëàññå êîíòàêòíûõ ñõåì . . . . . . . 719 Îïåðàöèÿ ñóïåðïîçèöèè è åå êîððåêòíîñòüäëÿ íåêîòîðûõ òèïîâ ñõåì. Ðàçäåëèòåëüíûåêîíòàêòíûå ñõåìû è ëåììà Øåííîíà . . . . . . 7710 Íåêîòîðûå ìîäèôèêàöèè è ÷àñòíûå ñëó÷àè îñíîâíûõêëàññîâ ñõåì (êàñêàäíûå ñõåìû, BDD, âû÷èñëÿþùèåïðîãðàììû) . . . . .
. . . . . . . . . . . . . . . . 87Ëèòåðàòóðà95ÂâåäåíèåÊóðñ ¾Îñíîâû êèáåðíåòèêè¿ (ðàíåå ¾Ýëåìåíòû êèáåðíåòèêè¿), ñîçäàòåëåì è îñíîâíûì ëåêòîðîì êîòîðîãî áûë÷ë.-êîðð. ÐÀÍ Ñ. Â. ßáëîíñêèé, ÷èòàåòñÿ íà ôàêóëüòåòåÂÌèÊ ÌÃÓ ñ ïåðâûõ ëåò åãî ñóùåñòâîâàíèÿ.  íàñòîÿùååâðåìÿ îí ÷èòàåòñÿ â 68 ñåìåñòðàõ è ÿâëÿåòñÿ îáÿçàòåëüíûìäëÿ âñåõ ñòóäåíòîâ, îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòè 01.02 ïðèêëàäíàÿ ìàòåìàòèêà è èíôîðìàòèêà, à òàêæå áàêàëàâðîâ îäíîèìåííîãî íàïðàâëåíèÿ 510200 è íàïðàâëåíèÿ 010400 èíôîðìàöèîííûå òåõíîëîãèè.
Ïðè ýòîì îáúåì è, â íåêîòîðîé ñòåïåíè, ïðîãðàììà êóðñà ¾Îñíîâû êèáåðíåòèêè¿ âàðüèðóþòñÿ â çàâèñèìîñòè îò ñïåöèàëèçàöèè è íàïðàâëåíèÿ.Êóðñ ¾Îñíîâû êèáåðíåòèêè¿ ïîñâÿùåí èçëîæåíèþ òåîðèè äèñêðåòíûõ óïðàâëÿþùèõ ñèñòåì, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé ÷àñòü äèñêðåòíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîéêèáåðíåòèêè.  íåé ðàçðàáàòûâàþòñÿ è èçó÷àþòñÿ äèñêðåòíûå ìàòåìàòè÷åñêèå ìîäåëè, îïèñûâàþùèå ôóíêöèîíèðîâàíèå è ñòðóêòóðó ñëîæíûõ ñèñòåì ïðåîáðàçîâàíèÿ èíôîðìàöèè (èíòåãðàëüíûõ ñõåì, ïðîãðàìì è ò. ï.).  îñíîâå ýòèõìîäåëåé ëåæàò ðàçëè÷íûå ñïîñîáû çàäàíèÿ ôóíêöèîíèðîâàíèÿ óïðàâëÿþùèõ ñèñòåì ñ ïîìîùüþ äèñêðåòíûõ ôóíêöèéè èõ ñòðóêòóðíàÿ ðåàëèçàöèÿ â òåõ èëè èíûõ êëàññàõ ãðàôîâ (êëàññàõ ñõåì).
Ïðè èññëåäîâàíèè óïðàâëÿþùèõ ñèñòåìñòàâÿòñÿ è ðåøàþòñÿ äâå îñíîâíûå çàäà÷è: çàäà÷à àíàëèçàè çàäà÷à ñèíòåçà.Çàäà÷à àíàëèçà ñîñòîèò â íàõîæäåíèè ôóíêöèîíèðîâàíèÿ äàííîé ñõåìû, à çàäà÷à ñèíòåçà â ïîñòðîåíèè ñõåìû,èìåþùåé (ðåàëèçóþùåé) çàäàííîå ôóíêöèîíèðîâàíèå. Êàæäàÿ èç ýòèõ çàäà÷ ìîæåò ðàññìàòðèâàòüñÿ ëèáî êàê èíäè4Ââåäåíèå5âèäóàëüíàÿ çàäà÷à, è òîãäà åå ðåøåíèåì ÿâëÿåòñÿ êîíêðåòíîå ôóíêöèîíèðîâàíèå (ñõåìà), ëèáî êàê ìàññîâàÿ çàäà÷à,è òîãäà åå ðåøåíèåì äîëæåí áûòü àëãîðèòì íàõîæäåíèÿôóíêöèîíèðîâàíèÿ (ñõåìû). Çàäà÷à ñèíòåçà èìååò, êàê ïðàâèëî, ìíîæåñòâî ðåøåíèé, èç êîòîðûõ âûáèðàþò ðåøåíèå,îïòèìàëüíîå ïî êàêîìó-ëèáî êðèòåðèþ. ×àùå âñåãî â êà÷åñòâå òàêîãî êðèòåðèÿ âûñòóïàåò ñëîæíîñòü ñõåìû, ïîíèìàåìàÿ êàê ñóììà ñëîæíîñòåé ñîñòàâëÿþùèõ åå ýëåìåíòîâèëè çàäåðæêà ñõåìû, ïîíèìàåìàÿ êàê ìàêñèìàëüíàÿ ñóììà çàäåðæåê äëÿ ïîñëåäîâàòåëüíî ñîåäèíåííûõ ýëåìåíòîâñõåìû.Ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ ðàçëè÷íûå êðèòåðèè îïòèìàëüíîñòè îòðàæàþò ðàçëè÷íûå ïàðàìåòðû ìîäåëèðóåìûõ ýëåêòðîííûõ ñõåì èëè ïðîãðàìì.
Òàê, íàïðèìåð, ñëîæíîñòü ìîæåò õàðàêòåðèçîâàòü ñòîèìîñòü, ðàçìåðû èëè ïîòðåáëÿåìóþ ìîùíîñòü ÑÁÈÑ, à òàêæå âðåìÿ âûïîëíåíèÿïðîãðàììû íà îäíîì ïðîöåññîðå. Ïðè ýòîì çàäåðæêà ñõåìûõàðàêòåðèçóåò âðåìÿ ñðàáàòûâàíèÿ ÑÁÈÑ èëè âðåìÿ âûïîëíåíèÿ ïðîãðàììû íà ïàðàëëåëüíûõ ïðîöåññîðàõ è ò. ï.Åñëè çàäà÷à ñèíòåçà ðåøåíà â îäíîé ìîäåëè, ìîæíî ïûòàòüñÿ ïåðåíåñòè ýòî ðåøåíèå â äðóãèå ìîäåëè ñ ïîìîùüþñòðóêòóðíîãî ìîäåëèðîâàíèÿ. Êðîìå òîãî, ïîëó÷åííîå ðåøåíèå ìîæíî ¾óëó÷øèòü¿ ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé. Ñ äðóãîé ñòîðîíû, åñëè çàäà÷à ñèíòåçà ðåøåíàäëÿ îäíèõ ôóíêöèé, ìîæíî ïûòàòüñÿ ¾ðàçáèòü¿ (äåêîìïîçèðîâàòü) íîâóþ ôóíêöèþ íà óæå ðàññìîòðåííûå è ïîñòðîèòüèç ñèíòåçèðîâàííûõ äëÿ íèõ ñõåì ñõåìó äëÿ íîâîé ôóíêöèèñ ïîìîùüþ îïåðàöèè ñóïåðïîçèöèè.Óêàçàííûå âûøå çàäà÷è ðàññìàòðèâàþòñÿ â ëåêöèÿõ äëÿâñåõ îñíîâíûõ êëàññîâ ñõåì (äèçúþíêòèâíûå íîðìàëüíûåôîðìû, ôîðìóëû è ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ,êîíòàêòíûå ñõåìû), à òàêæå äëÿ íåêîòîðûõ ìîäèôèêàöèéýòèõ êëàññîâ.Ïåðâàÿ ãëàâà ïîñâÿùåíà ðàçëè÷íûì âîïðîñàì ïðåäñòàâ-6Ââåäåíèåëåíèÿ ôóíêöèé àëãåáðû ëîãèêè ñ ïîìîùüþ òàáëèö è äèçúþíêòèâíûõ íîðìàëüíûõ ôîðì (ìèíèìèçàöèÿ äèçúþíêòèâíûõíîðìàëüíûõ ôîðì).Âòîðàÿ ãëàâà ñîäåðæèò îïèñàíèå ñòðóêòóðû è ôóíêöèîíèðîâàíèÿ ñõåì èç îñíîâíûõ êëàññîâ óïðàâëÿþùèõ ñèñòåì,à òàêæå èç íåêîòîðûõ êëàññîâ, ïðåäñòàâëÿþùèõ ñîáîé èõîáîáùåíèÿ èëè ìîäèôèêàöèè.
 íåé óñòàíàâëèâàþòñÿ âåðõíèå îöåíêè ÷èñëà ñõåì ðàçëè÷íûõ òèïîâ, ðàññìàòðèâàþòñÿîñîáåííîñòè ïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè â ðàçëè÷íûõ êëàññàõ ñõåì è íåêîòîðûå âîïðîñû èõ ñòðóêòóðíîãî ìîäåëèðîâàíèÿ.Âî âòîðîé ãëàâå èçó÷àþòñÿ òàêæå ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ñõåì íà îñíîâå òîæäåñòâ âî âñåõ îñíîâíûõ êëàññàõ óïðàâëÿþùèõ ñèñòåì. Äëÿ êàæäîãî èç íèõ ïðèâîäèòñÿñèñòåìà ¾îñíîâíûõ¿ òîæäåñòâ, äîêàçûâàåòñÿ ïîëíîòà ýòîéñèñòåìû è èçó÷àþòñÿ âîïðîñû åå èçáûòî÷íîñòè. òðåòüåé ãëàâå ïîäðîáíî ðàññìàòðèâàåòñÿ çàäà÷à ñèíòåçà óïðàâëÿþùèõ ñèñòåì.  íåé ïðèâîäèòñÿ öåëûé ñïåêòðìåòîäîâ ñèíòåçà ñõåì (îò ïðîñòåéøèõ äî àñèìïòîòè÷åñêè îïòèìàëüíûõ), óñòàíàâëèâàþòñÿ íèæíèå ìîùíîñòíûå îöåíêèôóíêöèé Øåííîíà è îöåíêè ñëîæíîñòè ðÿäà êîíêðåòíûõôóíêöèé, äîêàçûâàåòñÿ ìèíèìàëüíîñòü íåêîòîðûõ ñõåì. ÷åòâåðòîé ãëàâå ïðåäñòàâëåíû íåêîòîðûå âîïðîñû íàäåæíîñòè è êîíòðîëÿ ñõåì (ïîñòðîåíèå òåñòâ äëÿ òàáëèö,ñèíòåç ñàìîêîððåêòèðóþùèõñÿ êîíòàêòíûõ ñõåì).Ãëàâà 2Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì.Îöåíêà ÷èñëà ñõåì, èõ ñòðóêòóðíûåïðåäñòàâëåíèÿ.
Ýêâèâàëåíòíûåïðåîáðàçîâàíèÿ óïðàâëÿþùèõ ñèñòåì1Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé,ñõåì. Ñâîéñòâà ìàòðèö äîñòèæèìîñòè ñåòåé,îöåíêà ÷èñëà ñåòåéÏîíÿòèå ãðàôà, êîòîðîå îáîáùàåò ïîíÿòèå áèíàðíîãî îòíîøåíèÿ (ñì. 1 ãëàâû 1), ÷àñòî èñïîëüçóåòñÿ äëÿ îïèñàíèÿñòðóêòóðíûõ ìîäåëåé, ñâÿçàííûõ ñ âû÷èñëåíèÿìè, ïðåäñòàâëåíèÿìè èëè ðåàëèçàöèÿìè äèñêðåòíûõ ôóíêöèé. Íàïîìíèì îñíîâíûå ïîíÿòèÿ è îáîçíà÷åíèÿ èç òåîðèè ãðàôîâ, ñåòåé è ñõåì, à òàêæå ñôîðìóëèðóåì íåêîòîðûå èçâåñòíûå ðåçóëüòàòû (ñì., íàïðèìåð, [3, 27, 8]).Ïàðó (V, E), ãäå E ñî÷åòàíèå (ñ âîçìîæíûìè ïîâòîðåíèÿìè) íàä ìíîæåñòâîì óïîðÿäî÷åííûõ è íåóïîðÿäî÷åííûõïàð èç V , áóäåì, êàê îáû÷íî, íàçûâàòüV = V (G)E = E (G).Ïðè ýòîì äëèíà ñî÷åòàíèÿ E ñ÷èòàåòñÿ ÷èñëîì ðåáåð ãðàôàG è îáîçíà÷àåòñÿ ÷åðåç |E|.
Óïîðÿäî÷åííûå (íåóïîðÿäî÷åííûå) ïàðû âåðøèí íàçûâàþòñÿèëè, èíà÷å,(ñîîòâåòñòâåííî), îäèíàêîâûå ïàðû (), äóãè, îòëè÷àþùèåñÿ ïîðÿäêîì âåðøèí, ãðàôîì ñ ìíîæåè ìíîæåñòâîì ðåáåðñòâîì âåðøèíìèìè ðåáðàìèäóãàìèîðèåíòèðîâàííûìè ðåáðàíåîðèåíòèðîâàííûïàðàëëåëüíûìè ðåáðàìèïðîòè-äóãàìè78Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìâîïîëîæíûìè äóãàìè, à ïàðû èç ñîâïàäàþùèõ âåðøèí ïåòëÿìè. Ãðàô èç îðèåíòèðîâàííûõ (íåîðèåíòèðîâàííûõ)ðåáåð ñ÷èòàåòñÿ îðèåíòèðîâàííûì (ñîîòâåòñòâåííî íåîðèåíòèðîâàííûì ).
Çàìåòèì, ÷òî áèíàðíîå îòíîøåíèå ïðåä-ñòàâëÿåò ñîáîé îðèåíòèðîâàííûé ãðàô áåç ïàðàëëåëüíûõäóã. Ïðè ýòîì ñèììåòðè÷íîå àíòèðåôëåêñèâíîå îòíîøåíèåìîæíî ðàññìàòðèâàòü êàê íåîðèåíòèðîâàííûé ãðàô áåç ïàðàëëåëüíûõ ðåáåð è ïåòåëü.Áóäåì ãîâîðèòü, ÷òî îðèåíòèðîâàííîå (íåîðèåíòèðîâàííîå) ðåáðîñîñòàâëÿþùèì åãî âåðøèíàì, à äóãà(u, v)èëè, èíà÷å,èç âåðøèíû u èèëè, èíà÷å,â âåðøèíó v . ×èñëî ðåáåð, èíöèäåíòíûõâåðøèíå v (âõîäÿùèõ â v , âûõîäÿùèõ èç v ) â ãðàôå G, íàçûâàåòñÿ(ñîîòâåòñòâåííî,) âåðøèíû v â ãðàôå G è îáîçíà÷àåòñÿ−÷åðåç dG (v) (ñîîòâåòñòâåííî d+G (v), dG (v)).
Çàìåòèì, ÷òîèíöèäåíòíîèñõîäèòâûõîäèòçàõîäèòâõîäèòñòåïåíüþïîëóñòåïåíüþ çàõîäàïîëóñòåïåíüþ èñõîäàXdG (v) = 2 |E (G)| ,(1.1)v∈V (G)−+−è ÷òî dG (v) = d+G (v)+dG (v) (dG (v) = dG (v) = dG (v)) â ñëó÷àå îðèåíòèðîâàííîãî (ñîîòâåòñòâåííî íåîðèåíòèðîâàííîãî)ãðàôà G.Âåðøèíà v íàçûâàåòñÿ(,) ãðàôà G, åñëè dG (v) = 0 (ñîîòâåòñòâåííî+(v)=0,dd−G (v) = 0). Îðèåíòèðîâàííûé ãðàô G íàçûGâàåòñÿ r-è÷íûì (ñòðîãî r-è÷íûì) ãðàôîì, åñëè d+G (v) 6 r(ñîîòâåòñòâåííî d+(v)=r)äëÿëþáîéîòëè÷íîéîòèñòîêàGâåðøèíû v, v ∈ V (G).Ãðàô G0 = (V 0 , E 0 ) íàçûâàåòñÿãðàôà G == (V, E), åñëè V 0 ⊆ V è E 0 ⊆ E .
Ïðè ýòîì G0 ñ÷èòàåòñÿGV 0 , åñëè E 0 âêëþ÷àåò â ñåáÿ âñå âõîäÿùèå â E ïàðû âåðøèí èç V 0 . Ïîäãðàô, ñîäåðæàùèé âñå âåðøèíû èñõîäíîãîêîì èñòîêîìèçîëèðîâàííîé âåðøèíîé ñòî-ïîäãðàôîìïîäãðàôîì ãðàôà , íàòÿíóòûì íà ìíîæåñòâî âåðøèí1.Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé, ñõåì.9îñòîâíûì ïîäãðàôîìãðàôà, íàçûâàåòñÿ åãî. Ëåãêî âèäåòü,÷òî ïîäãðàô âñåãäà ìîæíî ïîëó÷èòü èç èñõîäíîãî ãðàôà âðåçóëüòàòå (ìíîãîêðàòíîãî) ïðèìåíåíèÿ îïåðàöèéèëè. Ïðè ýòîì óäàëåíèå âåðøèíû,êàê îáû÷íî, ïîäðàçóìåâàåò óäàëåíèå âñåõ èíöèäåíòíûõ åéðåáåð.Ïðè îïðåäåëåíèè ïîíÿòèé, ñâÿçàííûõ ñ ¾äâèæåíèÿìè¿ïî ãðàôó, îãðàíè÷èìñÿ ñëó÷àåì îðèåíòèðîâàííûõ ãðàôîâ,ñ÷èòàÿ, êàê îáû÷íî, ÷òî íåîðèåíòèðîâàííîå ðåáðî ýêâèâàëåíòíî äâóì ïðîòèâîïîëîæíûì äóãàì, ñâÿçàííûì ñ òîé æåïàðîé âåðøèí.
Ïîñëåäîâàòåëüíîñòü C , ñîñòîÿùàÿ èç ðåáåðe1 , e2 , . . . , en , ãäå ei = (vi , vi+1 ) ∈ E (G) ïðè âñåõ i, i ∈ [1, n],íàçûâàåòñÿ (v1 − vn+1 )ãðàôà G. Ïðè ýòîì âåðøèíà v1 (vn+1 ) ñ÷èòàåòñÿ(ñîîòâåòñòâåííî)âåðøèíîé ýòîãî ïóòè, âåðøèíû v2 , . . . , vn åãîâåðøèíàìè, à ÷èñëî n åãî. Åñëè âñå ðåáðà ïóòè ðàçëè÷íû (êàê ýëåìåíòû ñîîòâåòñòâóþùåãî ñî÷åòàíèÿ),òî îí íàçûâàåòñÿ, à åñëè, êðîìå òîãî, ðàçëè÷íû âñååãî âåðøèíû, òî . Åñëè íà÷àëüíàÿ è êîíå÷íàÿ âåðøèíû ïóòè (öåïè) C ñîâïàäàþò, òî C ñ÷èòàåòñÿ(ñîîòâåòñòâåííî). Öèêë, â êîòîðîì âñå âåðøèíû, êðîìå íà÷àëüíîé è êîíå÷íîé, ðàçëè÷íû,íàçûâàåòñÿ.Áóäåì ãîâîðèòü, ÷òîuvG, ãäå u, v ∈ V (G), åñëè u = v èëè â G ñóùåñòâóåò (v − u)-öåïü.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.