OK-metodichka-2010-part4 (1132795)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåòèìåíè Ì. Â. ËîìîíîñîâàÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. À. ËîæêèíËåêöèè ïî îñíîâàìêèáåðíåòèêè(âàðèàíò 2010 ã., ãëàâà 4)Ìîñêâà 2010ÎãëàâëåíèåÂâåäåíèå34 Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõ ñèñòåì6Ÿ1Ÿ2Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö.Ïîñòðîåíèå âñåõ òóïèêîâûõ òåñòîâ, îöåíêèäëèíû äèàãíîñòè÷åñêîãî òåñòà . . . .

. . . . . . 6Ñàìîêîððåêòèðóþùèåñÿ êîíòàêòíûå ñõåìû èìåòîäû èõ ïîñòîðîåíèÿ. Àñèìïòîòè÷åñêèíàèëó÷øèé ìåòîä ñèíòåçà êîíòàêòíûõ ñõåì,êîððåêòèðóþùèõ îäèí îáðûâ (îäíî çàìûêàíèå) 13Ëèòåðàòóðà182ÂâåäåíèåÊóðñ ¾Îñíîâû êèáåðíåòèêè¿ (ðàíåå ¾Ýëåìåíòû êèáåðíåòèêè¿), ñîçäàòåëåì è îñíîâíûì ëåêòîðîì êîòîðîãî áûë÷ë.-êîðð. ÐÀÍ Ñ. Â. ßáëîíñêèé, ÷èòàåòñÿ íà ôàêóëüòåòåÂÌèÊ ÌÃÓ ñ ïåðâûõ ëåò åãî ñóùåñòâîâàíèÿ.  íàñòîÿùååâðåìÿ îí ÷èòàåòñÿ â 68 ñåìåñòðàõ è ÿâëÿåòñÿ îáÿçàòåëüíûìäëÿ âñåõ ñòóäåíòîâ, îáó÷àþùèõñÿ ïî ñïåöèàëüíîñòè 01.02 ïðèêëàäíàÿ ìàòåìàòèêà è èíôîðìàòèêà, à òàêæå áàêàëàâðîâ îäíîèìåííîãî íàïðàâëåíèÿ 510200 è íàïðàâëåíèÿ 010400 èíôîðìàöèîííûå òåõíîëîãèè.

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

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

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

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

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

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

 íåé ïðèâîäèòñÿ öåëûé ñïåêòðìåòîäîâ ñèíòåçà ñõåì (îò ïðîñòåéøèõ äî àñèìïòîòè÷åñêè îïòèìàëüíûõ), óñòàíàâëèâàþòñÿ íèæíèå ìîùíîñòíûå îöåíêèôóíêöèé Øåííîíà è îöåíêè ñëîæíîñòè ðÿäà êîíêðåòíûõôóíêöèé, äîêàçûâàåòñÿ ìèíèìàëüíîñòü íåêîòîðûõ ñõåì. ÷åòâåðòîé ãëàâå ïðåäñòàâëåíû íåêîòîðûå âîïðîñû íàäåæíîñòè è êîíòðîëÿ ñõåì (ïîñòðîåíèå òåñòâ äëÿ òàáëèö,ñèíòåç ñàìîêîððåêòèðóþùèõñÿ êîíòàêòíûõ ñõåì).Ãëàâà 4Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõñèñòåìŸ1 Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö.Ïîñòðîåíèå âñåõ òóïèêîâûõ òåñòîâ, îöåíêèäëèíû äèàãíîñòè÷åñêîãî òåñòàÄëÿ óïðàâëÿþùåé ñèñòåìû (ñõåìû) áåç ïàìÿòè, ôóíêöèîíèðîâàíèå êîòîðîé îïèñûâàåòñÿ äèñêðåòíîé ôóíêöèåé èëè,â îáùåì ñëó÷àå, âåêòîð-ôóíêöèåé, ìîæåò áûòü ñôîðìóëèðîâàíà ñëåäóþùàÿ ìîäåëü, â ðàìêàõ êîòîðîé îáû÷íî ðàññìàòðèâàþòñÿ âîïðîñû åå íàäåæíîñòè è êîíòðîëÿ (ñì.

[28,26, 29]). Ïðåäïîëàãàåòñÿ, ÷òî èìååòñÿ íåêîòîðûé ¾âíåøíèé¿èñòî÷íèê íåèñïðàâíîñòåé (èñòî÷íèê ïîìåõ) È, ïîä äåéñòâèåì êîòîðîãî ðàññìàòðèâàåìàÿ ñõåìà Σ ìîæåò ïåðåõîäèòü âîäíî èç ñâîèõ ¾íåèñïðàâíûõ ñîñòîÿíèé¿ (ñõåì), îïðåäåëÿåìûõ ýòèì èñòî÷íèêîì. Ïóñòü ñõåìå Σ = Σ1 , ðåàëèçóþùåéôóíêöèþ f = f1 îò âõîäíûõ ïåðåìåííûõ x = (x1 , .

. . , xn ), èèñòî÷íèêó íåèñïðàâíîñòåé È ñîîòâåòñòâóþò ¾íåèñïðàâíûå¿ñîñòîÿíèÿ (ñõåìû) Σ2 , . . . , Σs , ãäå ñõåìà Σi , i = 2, . . . , s, ðåàëèçóåò ôóíêöèþ fi îò ïåðåìåííûõ x. Ïðè ýòîì âñå ñîñòîÿíèÿ (êàê èñïðàâíîå Σ = Σ1 , òàê è íåèñïðàâíûå Σ2 , . . . , Σs )ðàçáèâàþòñÿ íà êëàññû (ôóíêöèîíàëüíî) íåîòëè÷èìûõ ñîñòîÿíèé, òî åñòü êëàññû ýêâèâàëåíòíîñòè ïî îòíîøåíèþ ðàâåíñòâà ðåàëèçóåìûõ ôóíêöèé, è ðàññìàòðèâàþòñÿ äàëåå ñòî÷íîñòüþ äî íåîòëè÷èìîñòè.  äàëüíåéøåì, ãîâîðÿ î íåíà6Ÿ1. Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö7äåæíîé ñõåìå Σ, áóäåì èìåòü â âèäó ïàðó (Σ, È) è (èëè)ñîîòâåòñòâóþùåå åé ìíîæåñòâî ñõåì âìåñòå ñ òåìè ôóíêöèÿìè, êîòîðûå îíè ðåàëèçóþò.

Äëÿ ïðîñòîòû ðàññìîòðåíèÿ áóäåì ñ÷èòàòü, ÷òî âñå ïåðåìåííûå è ôóíêöèè ÿâëÿþòñÿáóëåâñêèìè, õîòÿ ìíîãèå èçëàãàåìûå äàëåå ðåçóëüòàòû áåçñóùåñòâåííûõ èçìåíåíèé ïåðåíîñÿòñÿ íà ñëó÷àé ìíîãîçíà÷íûõ ôóíêöèé, ñëó÷àé âåêòîð-ôóíêöèé è äðóãèå áîëåå îáùèåñëó÷àè.Ïóñòü (Σ, È) óêàçàííàÿ âûøå ìîäåëü íåíàäåæíîé ñõåìûΣ ñ âîçìîæíûìè ñîñòîÿíèÿìè Σ = Σ1 , Σ2 , . .

. , Σs , â êîòîðûõðåàëèçóþòñÿ ÔÀË f = f1 , f2 , . . . , fs ñîîòâåòñòâåííî îò ÁÏX (n), îïðåäåëåííûå íà ìíîæåñòâå íàáîðîâ A== {α1 , . . . , αp } ⊆ B n . Ðàññìîòðèì ìàòðèöó M, M ∈ B p,s ,ãäåM hi, ji = fj (αi ) ,ñ÷èòàÿ, ÷òî i-é ñòðîêå (j -ìó ñòîëáöó) ýòîé òàáëèöû ñîîòâåòñòâóåò íàáîð αi (ñîîòâåòñòâåííî ôóíêöèÿ fj è ñîñòîÿíèå Σj ). Ìàòðèöà, ñîñòîÿùàÿ èç ðàçëè÷íûõ ñòîëáöîâ (ñòðîê)íàçûâàåòñÿ îòäåëèìîé ïî ñòîëáöàì (ñîîòâåòñòâåííî ñòðîêàì ) ìàòðèöåé. Çàìåòèì, ÷òî êàæäîìó êëàññó íåîòëè÷èìûõñîñòîÿíèé ìîäåëè (Σ, È) ñîîòâåòñòâóåò ãðóïïà îäèíàêîâûõñòîëáöîâ ìàòðèöû M è ðàññìîòðèì îòäåëèìóþ ïî ñòîëáöàìc, ñîñòîÿùóþ èç âñåõ ðàçëè÷íûõ ñòîëáöîâ ìàòðèìàòðèöó Möû M .

Ïðè ýòîì áóäåì ñ÷èòàòü, ÷òî êàæäûé ñòîëáåö ìàòðèc ñâÿçàí ñ ñîîòâåòñòâóþùèì êëàññîì íåîòëè÷èìîñòè ñîöû Mc òàáëèöåé êîíñòîÿíèé ìîäåëè (Σ, È), è áóäåì íàçûâàòü Mòðîëÿ äàííîé ìîäåëè. Äëÿ ïðîñòîòû áóäåì, êàê ïðàâèëî,ïðåäïîëàãàòü, ÷òî âñå ñîñòîÿíèÿ ìîäåëè (Σ, È) ïîïàðíî îòc. Ýòî ïðåäïîëîæåíèå, î÷åâèäíî, íåëè÷èìû, òî åñòü, M = Mîãðàíè÷èâàåò îáùíîñòè ðàññóæäåíèé.Ïóñòü, äàëåå, ïîìèìî òàáëèöû êîíòðîëÿ M äëÿ ìîäåëè (Σ, È) çàäàíà öåëü êîíòðîëÿ, òî åñòü óêàçàíî ìíîæåñòâîN, ñîñòîÿùåå èç òåõ íåóïîðÿäî÷åííûõ ïàð ðàçëè÷íûõ ÷èñåëîòðåçêà [1, s], äëÿ êîòîðûõ ïàðû ñîñòîÿíèé (ñòîëáöîâ ìàòðè-8Ãëàâà 4. Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõ ñèñòåìöû M ) ñ ñîîòâåòñòâóþùèìè íîìåðàìè íåîáõîäèìî îòëè÷àòüäðóã îò äðóãà, ñðàâíèâàÿ çíà÷åíèÿ, ðàñïîëîæåííûå â òåõèëè èíûõ ñòðîêàõ äàííîé ïàðû ñòîëáöîâ.  ÷àñòíîñòè, åñëèN ñîñòîèò èç âñåõ ïàð óêàçàííîãî âèäà, òî öåëüþ êîíòðîëÿÿâëÿåòñÿ äèàãíîñòèêà ñõåìû, à åñëè N = {(1, 2) , .

. . , (1, t)},òî ïðîâåðêà èñïðàâíîñòè ñõåìû. Ìíîæåñòâî ñòðîê ìàòðèöû M ñ íîìåðàìè èç T, T ⊆ [1, p], íàçûâàåòñÿ òåñòîìäëÿ ìàòðèöû M îòíîñèòåëüíî ìíîæåñòâà N, èëè, èíà÷å,òåñòîì äëÿ (M, N), åñëè äëÿ ëþáîé ïàðû (i, j) èç N ñóùåñòâóåò t, t ∈ T , òàêîå, ÷òî M ht, ii 6= M ht, ji. Ìîùíîñòüòåñòà íàçûâàåòñÿ òàêæå åãî äëèíîé.Çàìåòèì, ÷òî ìíîæåñòâî, ñîñòîÿùåå èç âñåõ ñòðîê òàáëèöû êîíòðîëÿ, âñåãäà îáðàçóåò òåñò. Òåñò, êîòîðûé ïåðåñòàåòáûòü òåñòîì ïðè óäàëåíèè ëþáîé ñâîåé ñòðîêè, íàçûâàåòñÿ òóïèêîâûì, à òåñò, êîòîðûé èìååò ìèíèìàëüíóþìîùíîñòü, ìèíèìàëüíûì.  òîì ñëó÷àå, êîãäà öåëüþ êîíòðîëÿ ÿâëÿåòñÿ äèàãíîñòèêà ñõåìû (ïðîâåðêà èñïðàâíîñòèñõåìû), òåñò íàçûâàåòñÿ äèàãíîñòè÷åñêèì (ñîîòâåòñòâåííîïðîâåðÿþùèì ).Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî íàáîðîâ τ, τ ⊆ A, îáðàçóåò òåñò äëÿ ìîäåëè (Σ, È) îòíîñèòåëüíî öåëè êîíòðîëÿ N, èëè, èíà÷å, òåñò äëÿ (Σ, È, N), åñëè ñîîòâåòñòâóþùèå íàáîðàì èç τ ñòðîêè ìàòðèöû M îáðàçóþò òåñò äëÿ(M, N).

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций