OK-metodichka-2010-part2 (С.А. Ложкин - Лекции по основам кибернетики (2009))

Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåòèìåíè Ì. Â. ËîìîíîñîâàÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. À. ËîæêèíËåêöèè ïî îñíîâàìêèáåðíåòèêè(âàðèàíò 2010 ã., ãëàâà 2)Ìîñêâà 2010ÎãëàâëåíèåÂâåäåíèå24Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì. Îöåíêà÷èñëà ñõåì, èõ ñòðóêòóðíûå ïðåäñòàâëåíèÿ.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ óïðàâëÿþùèõñèñòåìŸ1Ÿ2Ÿ3Ÿ4Ÿ5Ÿ67Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé,ñõåì.

Ñâîéñòâà ìàòðèö äîñòèæèìîñòè ñåòåé,îöåíêà ÷èñëà ñåòåé . . . . . . . . . . . . . . . . 7Ôîðìóëû, èõ ñòðóêòóðà, ýêâèâàëåíòíîñòü è ñïîñîáûçàäàíèÿ. Îïòèìèçàöèÿ ïîäîáíûõ ôîðìóë ïîãëóáèíå . . . . . . . . . . . . . . . . . . . . . . . 16Çàäà÷à ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ñõåì íàïðèìåðå ôîðìóë. Ïîëíîòà ñèñòåìû îñíîâíûõòîæäåñòâ äëÿ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèéôîðìóë áàçèñà {&, ∨, ¬} .

. . . . . . . . . . . . 25Ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ. Îöåíêà÷èñëà ôîðìóë è ñõåì â áàçèñå {&, ∨, ¬} . . . . 32Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ñõåì èç ôóíêöèîíàëüíûõýëåìåíòîâ è ìîäåëèðîâàíèå ñ èõ ïîìîùüþ ôîðìóëüíûõïðåîáðàçîâàíèé. Ìîäåëèðîâàíèå ýêâèâàëåíòíûõïðåîáðàçîâàíèé ôîðìóë è ñõåì â ðàçëè÷íûõáàçèñàõ, òåîðåìà ïåðåõîäà . .

. . . . . . . . . . 40Êîíòàêòíûå ñõåìû è π -ñõåìû, îöåíêà èõ ÷èñëà.Îñîáåííîñòè ôóíêöèîíèðîâàíèÿ ìíîãîïîëþñíûõñõåì . . . . . . . . . . . . . . . . . . . . . . . . . 492Îãëàâëåíèå3Ÿ7Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõñõåì. Îñíîâíûå òîæäåñòâà, âûâîäâñïîìîãàòåëüíûõ è îáîáùåííûõ òîæäåñòâ .

. . 61Ÿ8 Ïîëíîòà ñèñòåìû îñíîâíûõ òîæäåñòâè îòñóòñòâèå êîíå÷íîé ïîëíîé ñèñòåìûòîæäåñòâ â êëàññå êîíòàêòíûõ ñõåì . . . . . . . 71Ÿ9 Îïåðàöèÿ ñóïåðïîçèöèè è åå êîððåêòíîñòüäëÿ íåêîòîðûõ òèïîâ ñõåì. Ðàçäåëèòåëüíûåêîíòàêòíûå ñõåìû è ëåììà Øåííîíà . . . . . . 77Ÿ10 Íåêîòîðûå ìîäèôèêàöèè è ÷àñòíûå ñëó÷àè îñíîâíûõêëàññîâ ñõåì (êàñêàäíûå ñõåìû, 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)-öåïü.