1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 6
Текст из файла (страница 6)
Çíà÷åíèå N0 îïðåäåëÿåòñÿ ýêñïåðèìåíòàëüíî ñ ïîìîùüþ ðåàëèçàöèè âûáîðêè ξ1 , . . . , ξn è ôèêñàöèè çàòðàò s = nt äëÿêàæäîãî èç àëãîðèòìîâ 1.1 è 1.5.1.3.2. Ïðèâåäåíèå âåðîÿòíîñòåé ê îáùåìó çíàìåíàòåëþ. Àëãîðèòì 1.5 ïîçâîëÿåò ïðåäëîæèòü öåëûé ðÿä ìîäèôèêàöèé àëãîðèòìîâ 1.1 è 1.4. Ìû ðàññìîòðèìòðè òàêèõ ìîäèôèêàöèè: äëÿ îòíîñèòåëüíî íåáîëüøîãî N (ïðèâåäåíèå âåðîÿòíîñòåé êîáùåìó çíàìåíàòåëþ), äëÿ óìåðåííî áîëüøîãî N (ìåòîä Óîëêåðà [10] ñì. ïîäðàçä.1.3.3) è äëÿ áîëüøîãî N (êâàíòèëüíûé ìåòîä [8] ñì.
ïîäðàçä. 1.3.4). Êðîìå òîãî, âïîäðàçä. 1.3.5 äëÿ ñëó÷àÿ áîëüøîãî N áóäóò ðàññìîòðåíû ñïåöèàëüíûå àëãîðèòìû ìîäåëèðîâàíèÿ äèñêðåòíîãî ðàñïðåäåëåíèÿ, íå ñâÿçàííûå ñ ïðèìåíåíèåì ôîðìóëû (1.36) áèíàðíûé ïîèñê è ìåòîä "ìàæîðàíòíîé ÷àñòîòû"[11].Ðàññìîòðèì ñëó÷àé îòíîñèòåëüíî íåáîëüøîãî N òàêîãî, ÷òî âåðîÿòíîñòè pi èç ñîîòíîøåíèÿ (1.18) ïðåäñòàâëÿþò ñîáîé îáûêíîâåííûå äðîáè, êîòîðûå ìîæíî ïðèâåñòèê îáùåìó çíàìåíàòåëþ M , ò. å. pi = mi /M , ïðè÷åì m1 + .
. . + mN = M è M ≤ M0 .Çäåñü ÷åðåç M0 îáîçíà÷åí ðàçìåð ìàêñèìàëüíîãî ìàññèâà äëÿ çàäàííîãî êîìïüþòåðà èâûáðàííîãî ÿçûêà ïðîãðàììèðîâàíèÿ.âñåãäàÐàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ 0 , ýêâèâàëåíòíóþñëó÷àéíîé âåëè÷èíåξ ñ ðàñïðåPi−1Pi00äåëåíèåì (1.18) è òàêóþ, ÷òî ξ = xj = xi ïðè j = s=1 ms + 1, . . . , s=1 ms , ïðè÷åìP(ξ 0 = x0j ) = 1/M (ò.
å. ïåðâûå m1 çíà÷åíèé x0j ñëó÷àéíîé âåëè÷èíû ξ 0 ðàâíû x1 , ñëåäóþùèå m2 çíà÷åíèé ðàâíû x2 è ò. ä., ïðè÷åì âñå çíà÷åíèÿ {x0j } ðàâíîâåðîÿòíû). Âûáîðî÷íûå çíà÷åíèÿ ñëó÷àéíîé âåëè÷èíû ξ 0 ðåàëèçóþòñÿ ñîãëàñíî àëãîðèòìó 1.5: ξ 0 = x0m0ïðè m0 = [M α] + 1. Ðàññìîòðåííàÿ ìîäèôèêàöèÿ îçíà÷àåò çàìåíó àëãîðèòìà 1.1 äëÿìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíû ξ íà àëãîðèòì 1.5 äëÿ âåëè÷èíû ξ 0 .1.3.3. Ïåðåðàñïðåäåëåíèå âåðîÿòíîñòåé (ìåòîä Óîëêåðà).
Ðàññìîòðèì òåïåðüñëó÷àé óìåðåííî áîëüøîãî N , äëÿ êîòîðîãî N ≈ M0 /2. Çäåñü âìåñòî àëãîðèòìà 1.1 ìîæíî ïðåäëîæèòü ïðîñòóþ êîíñòðóêöèþ, âêëþ÷àþùóþ èñïîëüçîâàíèå ôîðìóëû (1.36) èîäíîãî ñðàâíåíèÿ. Èäåþ ýòîé êîíñòðóêöèè ïðîùå âñåãî îáúÿñíèòü ãðàôè÷åñêè. Èçîáðàçèì ðàñïðåäåëåíèå (1.18) â âèäå äèàãðàììû, ñîñòîÿùåé èç ñòîëáöîâ åäèíè÷íîé øèðèíûè âûñîòû pi (ñì. ðèñ. 1.1). Ïðîâåäåì íà âûñîòå h = 1/N ëèíèþ, ïàðàëëåëüíóþ îñíîâàíèþ äèàãðàììû.
×àñòü ñòîëáöîâ äèàãðàììû èìåþò âûñîòó, áîëüøóþ h, à ÷àñòü ìåíüøóþ h. Íåñëîæíî ñôîðìóëèðîâàòü àëãîðèòì ïåðåðàñïðåäåëåíèÿ ÷àñòåé ñòîëáöîâ äèàãðàììû òàêèì îáðàçîì, ÷òîáû âñå ñòîëáöû èìåëè âûñîòó h è â êàæäîì èç íèõáûëè íå áîëåå ÷åì äâå äîëè èñõîäíûõ ñòîëáöîâ. Ïðîöåäóðà ïåðåðàñïðåäåëåíèÿ ñîñòîèò â ïîñëåäîâàòåëüíîì âûáîðå ìàêñèìàëüíîãî (íàïðèìåð, l-ãî) è ìèíèìàëüíîãî (m-ãî)ñòîëáöîâ (ïðè ýòîì âûïîëíåíû ñòðîãèå íåðàâåíñòâà pl > 1/N è pm < 1/N ) è â äîïîëíåíèè m-ãî ñòîëáöà ÷àñòüþ l-ãî äîPâûñîòû h (ýòî âîçìîæíî, ò.
ê. íà ëþáîì øàãå ïðîöåññàpmin + pmax ≥ 1/N , âåäü èíà÷å Ni=1 pi < 1). Ïîñëå êàæäîãî øàãà çàâîäèòñÿ äâóìåðíàÿÿ÷åéêà Em , â êîòîðîé õðàíèòñÿ ÷èñëî Fm = N pm (çäåñü pm ìèíèìàëüíàÿ íà äàííîìøàãå âûñîòà ñòîëáöà) è íîìåð ñòîëáöà l, èç êîòîðîãî âçÿòî äîïîëíåíèå m-ãî ñòîëáöà. äàëüíåéøåì m-ÿ ÿ÷åéêà íå ìåíÿåòñÿ (ñîîòâåòñòâóþùèé ñòîëáåö èìååò âûñîòó 1/N , èîí íå ìîæåò áûòü íè ìàêñèìàëüíûì, íè ìèíèìàëüíûì, ò. ê. íå âûïîëíåíû íåðàâåíñòâàpm > 1/N è pm < 1/N ). Åñëè æå èñõîäíûé (m-é) ñòîëáåö èìåë âûñîòó h = 1/N , òîîí çàìåíÿåòñÿ íà äâóìåðíóþ ÿ÷åéêó Em , â êîòîðîé âòîðàÿ êîîðäèíàòà ïóñòà.
Ïðîöåññïåðåðàñïðåäåëåíèÿ çàêàí÷èâàåòñÿ (÷åðåç N øàãîâ), êîãäà íà âñåõ ïîçèöèÿõ âîçíèêàþò äâóìåðíûå ÿ÷åéêè Ej (ò. å. ôàêòè÷åñêè âîçíèêàåò ìàññèâ äëèíû 2N , ÷òî îáúÿñíÿåòñîîòíîøåíèå N ≈ M0 /2 äëÿ ìàêñèìàëüíî âîçìîæíûõ N ). Ïîñëå ïðîâåäåííîé ïîäãîòîâèòåëüíîé ðàáîòû âîçíèêàåòÀëãîðèòì 1.6.m = [α1 N + 1](1.36)Em = (Fm ; l)α2α2 < Fmξ = xmξ = xlÑîãëàñíî ôîðìóëå(ñì. ñîîòíîøåíèå) âûáèðàåì íîìåð ÿ÷åéêè. Ðåàëèçóåì òàêæå âòîðîå âûáîðî÷íîå çíà÷åíèåñòàíäàðòíîé ñëó÷àéíîé âåëè÷èíû.
Åñëè, òî, èíà÷å.Ðèñ. 1.1. Ñõåìà ïåðåðàñïðåäåëåíèÿ âåðîÿòíîñòåé ïðè ïðèìåíåíèè ìåòîäà ÓîëêåðàÎáîñíîâàíèå àëãîðèòìà 1.6 ïðèâåäåíî äàëåå â ïîäðàçä. 1.8.2. Çàìåòèì, ÷òî àëãîðèòì1.6 äîïóñêàåò ñëåäóþùóþ ìîäèôèêàöèþ: âìåñòî α2 ìîæíî âçÿòü âåëè÷èíóα3 =α1 − (m − 1)/N= N α1 − m + 1.1/N(1.37)Îáîñíîâàíèå òàêîé çàìåíû ñëåäóåò èç òîãî, ÷òî ñëó÷àéíàÿ âåëè÷èíà α3 ðàâíîìåðíîðàñïðåäåëåíà íà èíòåðâàëå (0, 1) äëÿ ëþáîãî α1 ∈ ((m − 1)/N, m/N ), ÷òî, â ñâîþ î÷åðåäü, ñëåäóåò èç óòâåðæäåíèÿ 1.2 (ñì.
òàêæå îáîñíîâàíèå ìîäèôèöèðîâàííîãî ìåòîäàñóïåðïîçèöèè èç ïîäðàçä. 1.6.3). Öåëåñîîáðàçíîñòü ïðèìåíåíèÿ ôîðìóëû (1.37) ñâÿçàíàñ òåì, ÷òî ðåàëèçàöèÿ íîâîãî âûáîðî÷íîãî çíà÷åíèÿ α2 ñ ïîìîùüþ îáðàùåíèÿ ê ãåíåðàòîðó òèïà RAN DOM ÿâëÿåòñÿ îòíîñèòåëüíî òðóäîåìêîé îïåðàöèåé (ñì. çàìå÷àíèå1.2).Ðàññìîòðèì ñëó÷àé áîëüøîãî N (ò. å. N > M0 è äàæåN = ∞). Òðóäîåìêîñòè t èç ñîîòíîøåíèé (1.21) è (1.28) â ýòîì ñëó÷àå ìîæíî ñóùåñòâåííî óìåíüøèòü, åñëè ïðèìåíèòü òàê íàçûâàåìûéìîäåëèðîâàíèÿäèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí, êîòîðûé ñîñòîèò â ñëåäóþùåì.Çàäàäèì öåëîå ÷èñëî K è ðàçîáüåì èíòåðâàë (0, 1) íà K ðàâíûõ ÷àñòåé [(j−1)/K, j/K), j =1, . . . , K .
Äàëåå ïîñòðîèì ìàññèâ öåëûõ ÷èñåë {Xj }Kj=1 òàêîé, ÷òî1.3.4. Êâàíòèëüíûé ìåòîä.êâàíòèëüíûé ìåòîäXj = min{k : Rk = p1 + p2 + . . . + pk ≥ (j − 1)/K},ìàññèâîì íèæíèõ êâàíòèëåéêîòîðûé íàçûâàåòñÿ(ñì. ðèñ. 1.2). Ýòîò ìàññèâ çàäàåòíîìåð k ýëåìåíòà ìàññèâà {Ri ; i = 1, 2, . . . , N }, ñ êîòîðîãî ñëåäóåò íà÷èíàòü ïîèñêââåðõ (ò. å. êàê è â àëãîðèòìàõ âèäà 1.1 è 1.4, âû÷èòàòü âåëè÷èíû Rq , q = k, k +1, . . . èç α äî ïîëó÷åíèÿ ïåðâîãî îòðèöàòåëüíîãî çíà÷åíèÿ) ïðè (j − 1)/K ≤ α < j/K .Îêîí÷àòåëüíî ìîäåëèðîâàíèå äèñêðåòíîé ñëó÷àéíîé âåëè÷èíû âûãëÿäèò ñëåäóþùèìîáðàçîì.Àëãîðèòì 1.7.α(0, 1)j[(j − 1)/K, j/K)α(1.36) j = [Kα + 1]RXjÑôîðìóëèðîâàííûé àëãîðèòì íå ïðèâîäèò, êàê â àëãîðòìàõ èç ïîäðàçä. 1.3.2 è 1.3.3,ê ïîëíîé çàìåíå àëãîðèòìîâ 1.1 è 1.4 íà àëãîðèòì 1.5, à ëèøü óáûñòðÿåò ïðîöåññ âû÷èòàíèÿ ñóìì Rm â ñòàíäàðòíûõ àëãîðèòìàõ 1.1 è 1.4 çà ñ÷åò ïðèìåíåíèÿ ôîðìóëû (1.36)è èñïîëüçîâàíèÿ äîïîëíèòåëüíîé îïåðàòèâíîé ïàìÿòè ÝÂÌ äëÿ õðàíåíèÿ ìàññèâîâ íîìåðîâ {Xj } è ñóìì {RXj }.
Òåñòîâûå âû÷èñëåíèÿ ïîêàçàëè, ÷òî ïðè N ≤ 3M0 ñëåäóåòâûáèðàòü ÷èñëî K êâàíòèëåé [(j − 1)/K, j/K) òàê, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèåN/K ≈ 3 (ïðè ýòîì òðóäîåìêîñòü àëãîðèòìà 1.7 ïðàêòè÷åñêè íå ìåíÿåòñÿ ñ ðîñòîìN ). Îñîáî ïîä÷åðêíåì, ÷òî êâàíòèëüíûé ìåòîä ðàáîòàåò è â ñëó÷àå áåñêîíå÷íîãî ÷èñëàçíà÷åíèé ñëó÷àéíîé âåëè÷èíû ξ (ò. å.
äëÿ N = ∞); çäåñü ìîæíî áðàòü K ≈ M0 .1. Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ðàâíîìåðíî ðàñïðåäåëåííîé âèíòåðâàëåñëó÷àéíîé âåëè÷èíû.2. Âû÷èñëÿåì íîìåð ïîëóèíòåðâàëà, â êîòîðûé ïîïàäàåò ïîôîðìóëå òèïà:.3. Ðåàëèçóåì ïîñëåäîâàòåëüíûé ïîèñê ñíèçó ââåðõ íà÷èíàÿ ñ .Ðèñ. 1.2. Ñõåìà ôîðìèðîâàíèÿ ñóììR xjïðè ïðèìåíåíèè êâàíòèëüíîãî ìåòîäà1.3.5. Áèíàðíûé ïîèñê. Ìåòîä "ìàæîðàíòíîé ÷àñòîòû".
Ñëåäóþùàÿ ìîäèôèêàöèÿ ñòàíäàðòíîãî àëãîðèòìà 1.1 ïðèâîäèò ê óìåíüøåíèþ âû÷èñëèòåëüíûõ çàòðàò.Àëãîðèòì 1.8 (áèíàðíûé ïîèñê).α(0, 1)s1 := 1, s2 :=N +1k := [(s1 + s2 )/2]Rk = p 1 + . . . + p k < αs1 := ks2 := ks2 − s1 > 1m = s1 ξ = x mrr+1Ìîæíî ïîêàçàòü, ÷òî ïðè 2 < N ≤ 2äëÿ ïîëó÷åíèÿ âûáîðî÷íîãî çíà÷åíèÿ xmòðåáóåòñÿ (r + 1) ñðàâíåíèé. Òàêèì îáðàçîì, çàòðàòû t̂ àëãîðèòìà 1.8 èìåþò ïîðÿäîêlog2 N , è ïðè áîëüøèõ N âûïîëíåíî t̂ << t, ãäå âåëè÷èíà t îïðåäåëÿåòñÿ ñîîòíîøåíèåì (1.21). Ñëåäóåò, îäíàêî, îòìåòèòü, ÷òî èñïîëüçîâàíèå äîïîëíèòåëüíîé îïåðàòèâíîéïàìÿòè è ôîðìóëû (1.36) (ñì. àëãîðèòì Óîëêåðà èç ïîäðàçä.
1.3.3 è êâàíòèëüíûé àëãîðèòì èç ïîäðàçä. 1.3.4) ïîçâîëÿåò äîáèòüñÿ òîãî, ÷òî òðóäîåìêîñòü ïðàêòè÷åñêè íåóâåëè÷èâàåòñÿ ñ ðîñòîì N .Óïîìÿíåì åùå îäèí àëãîðèòì, êîòîðûé ïðèìåíÿåòñÿ â ñëó÷àå, êîãäà N > M0 è ôîðìóëà ïåðåñ÷åòà âåðîÿòíîñòåé (1.25) ìåíÿåòñÿ ïîñëå ïîëó÷åíèÿ î÷åðåäíîãî âûáîðî÷íîãî1. Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ðàâíîìåðíî ðàñïðåäåëåííîé â èíòåðâàëåñëó÷àéíîé âåëè÷èíû è ïîëàãàåì.2. Âû÷èñëÿåì öåëóþ ÷àñòü.3.
Åñëè, òî ïîëàãàåì, èíà÷å ïðèñâàèâàåì.4. Åñëè, òî èäåì íà ï. 2, èíà÷å ïîëàãàåìè.çíà÷åíèÿ. Òàêèå ñèòóàöèè âîçíèêàþò, â ÷àñòíîñòè, â àëãîðèòìàõ ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ ïðîöåññîâ ãàçîâîé äèíàìèêè [11]. Ñòàíäàðòíûå àëãîðèòìû 1.1 è 1.4 îêàçûâàþòñÿ íåýôôåêòèâíûìè. Ìîäèôèêàöèè òèïà àëãîðèòìà Óîëêåðà è êâàíòèëüíîãî ìåòîäàòàêæå íå ïîìîãàþò, ò.
ê. èõ ïðèìåíåíèå öåëåñîîáðàçíî ïðè ðåàëèçàöèè áîëüøîãî êîëè÷åñòâà âûáîðî÷íûõ çíà÷åíèé ïðè ôèêñèðîâàííîì äèñêðåòíîì ðàñïðåäåëåíèè (1.18).Ñëåäóþùèé àëãîðèòì ïîçâîëÿåò ïîëó÷èòü ïðèåìëåìûå ðåçóëüòàòû äëÿ îïèñàííûõ ñèòóàöèé.Àëãîðèòì 1.9 (ìåòîä "ìàæîðàíòíîé ÷àñòîòû").α(1.36)m00αpm > α pmaxpmax = max{p1 , .
. . , pN }ξ = xmÅñëè âû÷èñëåíèå âåëè÷èíû pmax çàòðóäíåíî, òî ìîæíî ïîëîæèòü pmax = 1. Êðîìåòîãî, àëãîðèòì ïðèìåíèì è â òîì ñëó÷àå, êîãäà ïîëîæèòåëüíûå ÷èñëà {p1 , . . . , pN } íåâ òî÷íîñòè ðàâíû, à òîëüêî ïðîïîðöèîíàëüíû âåðîÿòíîñòÿì (ò. å. èõ ñóììà ìîæåò íåðàâíÿòüñÿ åäèíèöå). Àëãîðèòì 1.9 ëåã÷å âñåãî îáîñíîâàòü ñ ïîìîùüþ ïåðåõîäà îò äèñêðåòíîãî ê íåïðåðûâíîìó ðàñïðåäåëåíèþ ñ êóñî÷íî-ïîñòîÿííîé ïëîòíîñòüþ (ñì. äàëååïîäðàçä. 1.8.2). Ïðè ýòîì ïîëó÷àåòñÿ ÷àñòíûé ñëó÷àé ìàæîðàíòíîãî ìåòîäà èñêëþ÷åíèÿ, ðàññìîòðåííîãî â ðàçä. 1.7.1. Ðåàëèçóÿ âûáîðî÷íîå çíà÷åíèå è èñïîëüçóÿ ôîðìóëóíàõîäèì ðàâíîìåðíî ðàñïðåäåëåííûé íîìåð .2. Ðåàëèçóåì åùå îäíî çíà÷åíèå . Åñëè, òî èäåì íà ïóíêò 1 (çäåñü), èíà÷å.1.3.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
