Lectionc1 (С.А. Ложкин - Лекции по основам кибернетики (2007))

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

. . . . . . . . . . . . . . . . . . . . . 7Ãèïåðêóá è åãî øèðèíà. Ôóíêöèè àëãåáðûëîãèêè, äèçúþíêòèâíûå è êîíúþíêòèâíûåíîðìàëüíûå ôîðìû . . . . . . . . . . . . . . . . 13Ñîêðàùåííàÿ ÄÍÔ è ñïîñîáû åå ïîñòðîåíèÿ.Íåêîòîðûå îöåíêè äëèíû ñîêðàùåííîé ÄÍÔ . 23Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ. ßäðîè ÄÍÔ Êâàéíà. Êðèòåðèé âõîæäåíèÿèìïëèêàíò â òóïèêîâûå ÄÍÔ, åãîëîêàëüíîñòü .

. . . . . . . . . . . . . . . . . . . 30Îñîáåííîñòè ÄÍÔ äëÿ ôóíêöèé èç íåêîòîðûõêëàññîâ. Òåîðåìà Þ. È. Æóðàâëåâà î ÄÍÔñóììà ìèíèìàëüíûõ . . . . . . . . . . . . . . . 37Ôóíêöèÿ ïîêðûòèÿ, òàáëèöà Êâàéíà è ïîñòðîåíèåâñåõ òóïèêîâûõ ÄÍÔ. Ãðàäèåíòíûé àëãîðèòìè îöåíêà äëèíû ãðàäèåíòíîãî ïîêðûòèÿ . . . . 432ÎãëàâëåíèåŸ7Ÿ8Ÿ93Çàäà÷à ìèíèìèçàöèè ÄÍÔ. Ïîâåäåíèå ôóíêöèéØåííîíà è îöåíêè òèïè÷íûõ çíà÷åíèé äëÿ ðàíãàè äëèíû ÄÍÔ . . . . . . . . . . .

. . . . . . . . 51Àëãîðèòìè÷åñêèå òðóäíîñòè ìèíèìèçàöèè ÄÍÔè îöåíêè ìàêñèìàëüíûõ çíà÷åíèé íåêîòîðûõñâÿçàííûõ ñ íåé ïàðàìåòðîâ . . . . . . . . . . . 55Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö.Ïîñòðîåíèå âñåõ òóïèêîâûõ òåñòîâ, îöåíêèäëèíû äèàãíîñòè÷åñêîãî òåñòà . . . . . . . . . . 63Ëèòåðàòóðà71ÂâåäåíèåÊóðñ ¾Îñíîâû êèáåðíåòèêè¿ (ðàíåå ¾Ýëåìåíòû êèáåðíåòèêè¿),ñîçäàòåëåì è îñíîâíûì ëåêòîðîì êîòîðîãî áûë ÷ë.-êîðð.ÐÀÍ Ñ.

Â. ßáëîíñêèé, ÷èòàåòñÿ íà ôàêóëüòåòå ÂÌèÊ ÌÃÓ ñïåðâûõ ëåò åãî ñóùåñòâîâàíèÿ.  íàñòîÿùåå âðåìÿ îí ÷èòàåòñÿâ 68 ñåìåñòðàõ è ÿâëÿåòñÿ îáÿçàòåëüíûì äëÿ âñåõ ñòóäåíòîâ,îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòè 01.02 ïðèêëàäíàÿ ìàòåìàòèêàè èíôîðìàòèêà, à òàêæå áàêàëàâðîâ îäíîèìåííîãî íàïðàâëåíèÿ510200 è íàïðàâëåíèÿ 010400 èíôîðìàöèîííûå òåõíîëîãèè.Ïðè ýòîì îáúåì è, â íåêîòîðîé ñòåïåíè, ïðîãðàììà êóðñà¾Îñíîâû êèáåðíåòèêè¿ âàðüèðóþòñÿ â çàâèñèìîñòè îò ñïåöèàëèçàöèèè íàïðàâëåíèÿ.Êóðñ ¾Îñíîâû êèáåðíåòèêè¿ ïîñâÿùåí èçëîæåíèþ òåîðèèäèñêðåòíûõ óïðàâëÿþùèõ ñèñòåì, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé÷àñòü äèñêðåòíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé êèáåðíåòèêè. íåé ðàçðàáàòûâàþòñÿ è èçó÷àþòñÿ äèñêðåòíûå ìàòåìàòè÷åñêèåìîäåëè, îïèñûâàþùèå ôóíêöèîíèðîâàíèå è ñòðóêòóðó ñëîæíûõñèñòåì ïðåîáðàçîâàíèÿ èíôîðìàöèè (èíòåãðàëüíûõ ñõåì, ïðîãðàììè ò.

ï.).  îñíîâå ýòèõ ìîäåëåé ëåæàò ðàçëè÷íûå ñïîñîáûçàäàíèÿ ôóíêöèîíèðîâàíèÿ óïðàâëÿþùèõ ñèñòåì ñ ïîìîùüþäèñêðåòíûõ ôóíêöèé è èõ ñòðóêòóðíàÿ ðåàëèçàöèÿ â òåõèëè èíûõ êëàññàõ ãðàôîâ (êëàññàõ ñõåì). Ïðè èññëåäîâàíèèóïðàâëÿþùèõ ñèñòåì ñòàâÿòñÿ è ðåøàþòñÿ äâå îñíîâíûå çàäà÷è:çàäà÷à àíàëèçà è çàäà÷à ñèíòåçà.Çàäà÷à àíàëèçà ñîñòîèò â íàõîæäåíèè ôóíêöèîíèðîâàíèÿäàííîé ñõåìû, à çàäà÷à ñèíòåçà â ïîñòðîåíèè ñõåìû, èìåþùåé(ðåàëèçóþùåé) çàäàííîå ôóíêöèîíèðîâàíèå. Êàæäàÿ èç ýòèõçàäà÷ ìîæåò ðàññìàòðèâàòüñÿ ëèáî êàê èíäèâèäóàëüíàÿ çàäà÷à,è òîãäà åå ðåøåíèåì ÿâëÿåòñÿ êîíêðåòíîå ôóíêöèîíèðîâàíèå4Ââåäåíèå5(ñõåìà), ëèáî êàê ìàññîâàÿ çàäà÷à, è òîãäà åå ðåøåíèåì äîëæåíáûòü àëãîðèòì íàõîæäåíèÿ ôóíêöèîíèðîâàíèÿ (ñõåìû).

Çàäà÷àñèíòåçà èìååò, êàê ïðàâèëî, ìíîæåñòâî ðåøåíèé, èç êîòîðûõâûáèðàþò ðåøåíèå, îïòèìàëüíîå ïî êàêîìó-ëèáî êðèòåðèþ.×àùå âñåãî â êà÷åñòâå òàêîãî êðèòåðèÿ âûñòóïàåò ñëîæíîñòüñõåìû, ïîíèìàåìàÿ êàê ñóììà ñëîæíîñòåé ñîñòàâëÿþùèõåå ýëåìåíòîâ èëè çàäåðæêà ñõåìû, ïîíèìàåìàÿ êàê ìàêñèìàëüíàÿñóììà çàäåðæåê äëÿ ïîñëåäîâàòåëüíî ñîåäèíåííûõ ýëåìåíòîâñõåìû.Ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ ðàçëè÷íûå êðèòåðèè îïòèìàëüíîñòèîòðàæàþò ðàçëè÷íûå ïàðàìåòðû ìîäåëèðóåìûõ ýëåêòðîííûõñõåì èëè ïðîãðàìì. Òàê, íàïðèìåð, ñëîæíîñòü ìîæåò õàðàêòåðèçîâàòüñòîèìîñòü, ðàçìåðû èëè ïîòðåáëÿåìóþ ìîùíîñòü ÑÁÈÑ, àòàêæå âðåìÿ âûïîëíåíèÿ ïðîãðàììû íà îäíîì ïðîöåññîðå.Ïðè ýòîì çàäåðæêà ñõåìû õàðàêòåðèçóåò âðåìÿ ñðàáàòûâàíèÿÑÁÈÑ èëè âðåìÿ âûïîëíåíèÿ ïðîãðàììû íà ïàðàëëåëüíûõïðîöåññîðàõ è ò.

ï.Åñëè çàäà÷à ñèíòåçà ðåøåíà â îäíîé ìîäåëè, ìîæíî ïûòàòüñÿïåðåíåñòè ýòî ðåøåíèå â äðóãèå ìîäåëè ñ ïîìîùüþ ñòðóêòóðíîãîìîäåëèðîâàíèÿ. Êðîìå òîãî, ïîëó÷åííîå ðåøåíèå ìîæíî ¾óëó÷øèòü¿ñ ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé. Ñ äðóãîé ñòîðîíû,åñëè çàäà÷à ñèíòåçà ðåøåíà äëÿ îäíèõ ôóíêöèé, ìîæíî ïûòàòüñÿ¾ðàçáèòü¿ (äåêîìïîçèðîâàòü) íîâóþ ôóíêöèþ íà óæå ðàññìîòðåííûåè ïîñòðîèòü èç ñèíòåçèðîâàííûõ äëÿ íèõ ñõåì ñõåìó äëÿíîâîé ôóíêöèè ñ ïîìîùüþ îïåðàöèè ñóïåðïîçèöèè.Óêàçàííûå âûøå çàäà÷è ðàññìàòðèâàþòñÿ â ëåêöèÿõ äëÿâñåõ îñíîâíûõ êëàññîâ ñõåì (äèçúþíêòèâíûå íîðìàëüíûåôîðìû, ôîðìóëû è ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ,êîíòàêòíûå ñõåìû), à òàêæå äëÿ íåêîòîðûõ ìîäèôèêàöèéýòèõ êëàññîâ.Ïåðâàÿ ãëàâà ïîñâÿùåíà ðàçëè÷íûì âîïðîñàì ïðåäñòàâëåíèÿôóíêöèé àëãåáðû ëîãèêè ñ ïîìîùüþ òàáëèö è äèçúþíêòèâíûõíîðìàëüíûõ ôîðì (ìèíèìèçàöèÿ äèçúþíêòèâíûõ íîðìàëüíûõôîðì, ïîñòðîåíèå òåñòîâ äëÿ òàáëèö è ò.

ï.).6ÂâåäåíèåÂòîðàÿ ãëàâà ñîäåðæèò îïèñàíèå ñòðóêòóðû è ôóíêöèîíèðîâàíèÿñõåì èç îñíîâíûõ êëàññîâ óïðàâëÿþùèõ ñèñòåì, à òàêæå èçíåêîòîðûõ êëàññîâ, ïðåäñòàâëÿþùèõ ñîáîé èõ îáîáùåíèÿèëè ìîäèôèêàöèè.  íåé óñòàíàâëèâàþòñÿ âåðõíèå îöåíêè÷èñëà ñõåì ðàçëè÷íûõ òèïîâ, ðàññìàòðèâàþòñÿ îñîáåííîñòèïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè â ðàçëè÷íûõ êëàññàõñõåì è íåêîòîðûå âîïðîñû èõ ñòðóêòóðíîãî ìîäåëèðîâàíèÿ.Âî âòîðîé ãëàâå èçó÷àþòñÿ òàêæå ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿñõåì íà îñíîâå òîæäåñòâ âî âñåõ îñíîâíûõ êëàññàõ óïðàâëÿþùèõñèñòåì.

Äëÿ êàæäîãî èç íèõ ïðèâîäèòñÿ ñèñòåìà ¾îñíîâíûõ¿òîæäåñòâ, äîêàçûâàåòñÿ ïîëíîòà ýòîé ñèñòåìû è èçó÷àþòñÿâîïðîñû åå èçáûòî÷íîñòè. òðåòüåé ãëàâå ïîäðîáíî ðàññìàòðèâàåòñÿ çàäà÷à ñèíòåçàóïðàâëÿþùèõ ñèñòåì.  íåé ïðèâîäèòñÿ öåëûé ñïåêòð ìåòîäîâñèíòåçà ñõåì (îò ïðîñòåéøèõ äî àñèìïòîòè÷åñêè îïòèìàëüíûõ),óñòàíàâëèâàþòñÿ íèæíèå ìîùíîñòíûå îöåíêè ôóíêöèé Øåííîíàè îöåíêè ñëîæíîñòè ðÿäà êîíêðåòíûõ ôóíêöèé, äîêàçûâàåòñÿìèíèìàëüíîñòü íåêîòîðûõ ñõåì.Ãëàâà 1Ïðåäñòàâëåíèå ôóíêöèéäèçúþíêòèâíûìè íîðìàëüíûìèôîðìàìè è ñâÿçàííûå ñ íèì çàäà÷èŸ1Îñíîâíûå ïîíÿòèÿ, îòíîñÿùèåñÿ êìíîæåñòâàì, ìàòðèöàì, ôóíêöèÿì,ôîðìóëàìÁóäåì ñ÷èòàòü èçâåñòíûìè îñíîâíûå ïîíÿòèÿ è îáîçíà÷åíèÿèç òåîðèè ìíîæåñòâ, ìàòåìàòè÷åñêîãî àíàëèçà, äèñêðåòíîéìàòåìàòèêè, òåîðèè âåðîÿòíîñòåé (ñì., íàïðèìåð, [24, 25, 27,4]).

 äàëüíåéøåì ÷åðåç N (÷åðåç N0 ) îáîçíà÷àåòñÿ ìíîæåñòâîâñåõ íàòóðàëüíûõ (ñîîòâåòñòâåííî öåëûõ íåîòðèöàòåëüíûõ)÷èñåë. Ìíîæåñòâî âñåõ öåëûõ ÷èñåë j , äëÿ êîòîðûõ a 6 j 6b, ãäå a; b öåëûå, íàçûâàåòñÿè îáîçíà÷àåòñÿ÷åðåçîòðåçêîì[a; b] = (a 1; b] = [a; b + 1) = (a 1; b + 1) :Ïðè ýòîì îòðåçêè âèäà[a1 ; a2 ) ; [a2 ; a3 ) ; : : : ;ãäå a1 < a2 < a3 < : : :, íàçûâàþòñÿ ïîñëåäîâàòåëüíûìè.Íàïîìíèì íåêîòîðûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ, ñâÿçàííûåñ äåêàðòîâûìè ïðîèçâåäåíèÿìè ìíîæåñòâ. Äëÿ ìíîæåñòâà Aè n 2 N ïîëîæèì( A )n = A n = A A A ;|7{zn ðàç}8Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû n-ÿ äåêàðòîâà ñòåïåíü A, òî åñòü ìíîæåñòâî íàáîðîâ (ñòðîê,ñëîâ, âûáîðîê) äëèíû n ñ ýëåìåíòàìè (áóêâàìè) èç A èëè,èíà÷å, ìíîæåñòâî óïîðÿäî÷åííûõ n-îê ýëåìåíòîâ ìíîæåñòâàA.Äëÿ ìíîæåñòâà A è s; n 2 N ÷åðåç (A)s;n = As;n îáîçíà÷àåòñÿìíîæåñòâî ìàòðèö ñ s ñòðîêàìè, n ñòîëáöàìè è ýëåìåíòàìèèç A.

Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî An = A1;n , è ÷òî As;n n-ÿ äåêàðòîâà ñòåïåíü ìíîæåñòâà As;1 , ýëåìåíòû êîòîðîãîíàçûâàþòñÿ ñòîëáöàìè. ×èñëî ñòîëáöîâ (ñòðîê) ìàòðèöû Míàçûâàåòñÿ åå(ñîîòâåòñòâåííî). Äëÿ ìàòðèöûM 2 As;n è I 0 [1; s] ; I 00 [1; n] ÷åðåç M hI 0 ; I 00 i (ïðè s = 1è I 0 = f1g ÷åðåç M hI 00 i) îáîçíà÷àåòñÿ åå ïîäìàòðèöà,ðàñïîëîæåííàÿ â ñòðîêàõ ñ íîìåðàìè èç I 0 è ñòîëáöàõ ñíîìåðàìè èç I 00 . Íàáîð = (1 ; : : : ; p ), ñîñòîÿùèé èç íåïóñòûõìíîæåñòâ, áóäåì íàçûâàòüìíîæåñòâà = 1 [: : :[p . Ïðè ýòîì ìíîæåñòâà 1 ; : : : ; p ñ÷èòàþòñÿïîêðûòèÿ , à ÷èñëî p åãîèëè. Ïîêðûòèå,ñîñòîÿùåå èç íåïåðåñåêàþùèõñÿ ìíîæåñòâ, íàçûâàåòñÿ.Ïîêðûòèå, â êîòîðîì íè îäíà èç êîìïîíåíò íå ñîäåðæèòñÿâ äðóãîé êîìïîíåíòå (â îáúåäèíåíèè îñòàëüíûõ êîìïîíåíò),ñ÷èòàåòñÿ(ñîîòâåòñòâåííî) ïîêðûòèåì.Åñëè A êîíå÷íîå ìíîæåñòâî, òî åãî ìîùíîñòü, òî åñòü÷èñëî ýëåìåíòîâ, îáîçíà÷àåòñÿ îáû÷íî ÷åðåç jAj. Çàìåòèì,÷òî ïðè ýòîìjAnj = jAjn è jAs;nj = jAjsn ;äëèíîéâûñîòîéïîêðûòèåìêîìïîíåíòàìèäëèíîé ðàíãîìðàçáèåíèåìíåïðèâîäèìûìòóïèêîâûìãäå s; n 2 N, à åñëè jAj = a > n, òî ÷èñëî âûáîðîê (ñëîâ)äëèíû n èç A, â êîòîðûõ âñå ýëåìåíòû ðàçëè÷íû, òàêíàçûâàåìûõ âûáîðîê áåç ïîâòîðåíèé, ðàâíîa (a 1) (a n + 1) :Êàæäîå ñëîâî (íàáîð) = 1 : : : n = (1 ; : : : ; n ) èç Anïðè âñåâîçìîæíûõ ïåðåñòàíîâêàõ áóêâ ïîðîæäàåò ìíîæåñòâîñëîâ, íàçûâàåìîåäëèíû n èç A èëè, èíà÷å,ñî÷åòàíèåìŸ1.9Îñíîâíûå ïîíÿòèÿíåóïîðÿäî÷åííîé n-êîé èç A, è îáîçíà÷àåìîå ÷åðåç f1; : : : ; ng. ÷àñòíîñòè, ñî÷åòàíèå, ñâÿçàííîå ñ (óïîðÿäî÷åííîé) ïàðîé(u; v), ñ÷èòàåòñÿ íåóïîðÿäî÷åííîé ïàðîé fu; vg, ñî÷åòàíèå,ñâÿçàííîå ñ (óïîðÿäî÷åííûì) ðàçáèåíèåì (1 ; : : : ; p ), íåóïîðÿäî÷åííûìðàçáèåíèåì f1 ; : : : ; p g, è òàê äàëåå.

Çàìåòèì, ÷òî ñî÷åòàíèåïîðîæäàåòñÿ ïåðåñòàíîâêàìè áóêâ èç ëþáîãî ñâîåãî ñëîâà.Ïðè ýòîì ñî÷åòàíèå èç A áåç ïîâòîðåíèé, òî åñòü ñî÷åòàíèå,ïîðîæäåííîå ñëîâîì èç An , âñå áóêâû êîòîðîãî ðàçëè÷íû, ññîäåðæàòåëüíîé òî÷êè çðåíèÿ ïðåäñòàâëÿåò ñîáîé ¾îáû÷íîå¿ïîäìíîæåñòâî, à ñî÷åòàíèå ñ ïîâòîðåíèÿìè ¾êðàòíîå¿ ïîäìíîæåñòâîìíîæåñòâà A, òî åñòü ïîäìíîæåñòâî, â êîòîðîå åãî ýëåìåíòûâõîäÿò ñ îïðåäåëåííîé êðàòíîñòüþ (â ñîîòâåòñòâóþùåì ÷èñëå¾ýêçåìïëÿðîâ¿).×èñëî ðàçëè÷íûõ ñî÷åòàíèé áåç ïîâòîðåíèéäëèíû n èçaìíîæåñòâà A; jAj = a, îáîçíà÷àåòñÿ ÷åðåç n .