Диссертация (1137405), страница 17
Текст из файла (страница 17)
éÎÁÞÅ ÇÏ×ÏÒÑ, ÒÁÚ ×ÌÉÑÎÉÅ | ×ÅÒÏÑÔÎÏÓÔØ ÎÅËÏÔÏÒÏÇÏ ÓÏÂÙÔÉÑ, ÔÏ ÅÇÏ ÍÏÖÎÏ ÏÃÅÎÉÔØ, ÉÓÐÏÌØÚÕÑ ÍÁÔÅÍÁÔÉÞÅÓËÕÀ ÓÔÁÔÉÓÔÉËÕ.ïÓÎÏ×ÎÏÊ ÎÅÄÏÓÔÁÔÏË ÐÅÒÅÞÉÓÌÅÎÎÙÈ ÎÉÖÅ ÍÅÔÏÄÏ× | ÎÅ×ÏÚÍÏÖÎÏÓÔØ ÈÏÒÏÛÏ ÏÃÅÎÉÔØ ÔÏÞÎÏÓÔØ ×ÙÞÉÓÌÅÎÉÊ. óËÏÒÅÅ ×ÓÅÇÏ ÏÎ ÎÅÕÓÔÒÁÎÉÍ, ÐÏÓËÏÌØËÕÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ "ÎÅ ÎÅÐÒÅÒÙ×ÎÙ" | ÏÞÅÎØ ÍÁÌÅÎØËÉÅ ÉÚÍÅÎÅÎÉÑ ÞÉÓÌÁ ÇÏÌÏÓÏ× ÍÏÇÕÔ ÐÒÉ×ÅÓÔÉ Ë ÓÕÝÅÓÔ×ÅÎÎÏÍÕ ÐÅÒÅÒÁÓÐÒÅÄÅÌÅÎÉÀ ×ÌÉÑÎÉÑ.äÏÓÔÏÉÎÓÔ×Ï, ËÁË É ÐÏÌÁÇÁÅÔÓÑ ÐÒÉÂÌÉÖÅÎÎÙÍ ÍÅÔÏÄÁÍ, | ÍÁÌÏÅ ×ÒÅÍÑ ÒÁÂÏÔÙ, ÔÏÞÎÅÅ ÍÏÖÎÏ ÐÏÔÒÁÔÉÔØ ×ÓÅ ÉÍÅÀÝÅÅÓÑ ÍÁÛÉÎÎÏÅ ×ÒÅÍÑ, ÓËÏÌØËÏ ÂÙ ÅÇÏÎÅ ÂÙÌÏ | ÞÅÍ ÂÏÌØÛÅ "ÉÔÅÒÁÃÉÊ", ÔÅÍ ×ÙÛÅ ÔÏÞÎÏÓÔØ.÷ÐÅÒ×ÙÅ ([72], 1960 Ç.) ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ ÂÙÌÉ ÐÒÉÂÌÉÖÅÎÎÏ ×ÙÞÉÓÌÅÎÙ ÍÅÔÏÄÏÍ íÏÎÔÅ-ëÁÒÌÏ.
óÐÏÓÏ ÚÁ×ÉÓÉÔ ÏÔ ×ÅÒÏÑÔÎÏÓÔÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ. ôÁË,ÄÌÑ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ ÍÏÖÎÏ ×ÙÂÉÒÁÔØ ÓÌÕÞÁÊÎÙÊ ÐÏÒÑÄÏËÉÇÒÏËÏ× É ÓÞÉÔÁÔØ, × ËÁËÏÊ ÄÏÌÅ ÓÌÕÞÁÅ× ÐÒÉ ÄÏÂÁ×ÌÅÎÉÉ ÉÇÒÏËÁ i ÏÂÒÁÚÏ×ÁÌÁÓØ122×ÙÉÇÒÙ×ÁÀÝÁÑ ËÏÁÌÉÃÉÑ. äÌÑ ÉÎÄÅËÓÁ ðÅÎÒÏÕÚÁ (âÁÎÃÁÆÁ) ÎÅÏÂÈÏÄÉÍÏ ×ÙÂÉÒÁÔØ ÓÌÕÞÁÊÎÕÀ ËÏÁÌÉÃÉÀ É ÓÞÉÔÁÔØ ×ÅÒÏÑÔÎÏÓÔØ ÔÏÇÏ, ÞÔÏ ÉÇÒÏË × ÎÅÊ ÂÕÄÅÔËÌÀÞÅ×ÙÍ.÷ [79, 80] ïÕÜÎ ÐÒÅÄÌÏÖÉÌ ÍÅÔÏÄ, ÏÓÎÏ×ÁÎÎÙÊ ÎÁ ÔÏÍ, ÞÔÏ ËÏÜÆÆÉÃÉÅÎÔ ×ÆÏÒÍÕÌÅ ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ÂÅÔÁ-ÆÕÎËÃÉÀ:s!(n − s − 1)!=B(s + 1; n − s) =n!Z1xs(1 − x)n−s−1 dx:0åÓÌÉ ÓÞÉÔÁÔØ, ÞÔÏ ÉÇÒÏËÉ ÐÒÉÎÉÍÁÀÔ ÒÅÛÅÎÉÑ ÎÅÚÁ×ÉÓÉÍÏ É x | ×ÅÒÏÑÔÎÏÓÔØ ÔÏÇÏ, ÞÔÏ ÉÇÒÏË ÇÏÌÏÓÕÅÔ ÚÁ, ÐÏÄÙÎÔÅÇÒÁÌØÎÁÑ ÆÕÎËÃÉÑ ÒÁ×ÎÁ ×ÅÒÏÑÔÎÏÓÔÉ ÔÏÇÏ, ÞÔÏ ËÏÁÌÉÃÉÑ S ÇÏÌÏÓÕÅÔ ÚÁ ÒÅÛÅÎÉÅ, Á N \ (S ∪ {i} | ÐÒÏÔÉ×, Ô.Å.×ÅÒÏÑÔÎÏÓÔÉ ÔÏÇÏ, ÞÔÏ ÇÏÌÏÓ ÉÇÒÏËÁ i ÏËÁÖÅÔÓÑ ÒÅÛÁÀÝÉÍ.
÷ÅÒÏÑÔÎÏÓÔØ ÖÅÔÏÇÏ, ÞÔÏ ÉÇÒÏË i ÂÕÄÅÔ ËÌÀÞÅ×ÙÍ × ÏÂÒÁÚÏ×Á×ÛÅÊÓÑ ËÏÁÌÉÃÉÉ, ÂÕÄÅÔ ÒÁ×ÎÁp(x) =XS ∈Wixs(1 − x)n−s−1:þÔÏÂÙ ÐÏÌÕÞÉÔØ ÉÎÄÅËÓ ûÅÐÌÉ|ûÕÂÉËÁ, ÎÕÖÎÏ ÐÒÏÉÎÔÅÇÒÉÒÏ×ÁÔØ p(x) ÏÔ 0ÄÏ 1, Á ÞÔÏÂÙ ÐÏÌÕÞÉÔØ ÉÎÄÅËÓ âÁÎÃÁÆÁ | ÐÏÄÓÔÁ×ÉÔØ x = 1=2.ðÏÜÔÏÍÕ ÄÌÑ ÐÒÉÂÌÉÖÅÎÎÏÇÏ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁÄÏÓÔÁÔÏÞÎÏ ÏÃÅÎÉÔØ p(x).
äÌÑ ÜÔÏÇÏ ÒÁÓÓÍÁÔÒÉ×ÁÅÔÓÑ ÓÌÕÞÁÊÎÁÑ ×ÅÌÉÞÉÎÁ wi(x),ÒÁ×ÎÁÑ ÓÕÍÍÅ ÇÏÌÏÓÏ× ×ÓÅÈ ÉÇÒÏËÏ×, ×ÈÏÄÑÝÉÈ × ËÏÁÌÉÃÉÀ Ó i. éÇÒÏË i ËÌÀÞÅ×ÏÊ× ÐÏÌÕÞÉ×ÛÅÊÓÑ ËÏÁÌÉÃÉÉ, ÅÓÌÉ q − wi ≤ wi(x) < q, Ô.Å.fi(x) = P (q − wi ≤ wi(x) < q):üÔÁ ×ÅÒÏÑÔÎÏÓÔØ ÐÒÉÂÌÉÖÅÎÎÏ ×ÙÞÉÓÌÑÅÔÓÑ × ÐÒÅÄÐÏÌÏÖÅÎÉÉ, ÞÔÏ wi(x) ÒÁÓÐÒÅÄÅÌÅÎÏ ÎÏÒÍÁÌØÎÏ.ðÒÅÄÐÏÌÏÖÅÎÉÅ Ï ÎÏÒÍÁÌØÎÏÍ ÒÁÓÐÒÅÄÅÌÅÎÉÉ wi(x) ÄÏÐÕÓÔÉÍÏ, ÅÓÌÉ ÉÇÒÏËÏ×ÍÎÏÇÏ É ×ÓÅ ÏÎÉ ÏÂÌÁÄÁÀÔ ÐÒÉÍÅÒÎÏ ÏÄÉÎÁËÏ×ÙÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ×. åÓÌÉ ÜÔÏ ÎÅ123ÔÁË, ÔÏ ÏÛÉÂËÉ ×ÙÞÉÓÌÅÎÉÑ ÍÏÇÕÔ ÂÙÔØ ×ÅÌÉËÉ [69, 94].÷ ÒÁÂÏÔÁÈ ä.
ìÉÞÁ [68, 69] ÐÒÅÄÌÁÇÁÅÔÓÑ ËÏÍÂÉÎÉÒÏ×ÁÎÎÙÊ ÍÅÔÏÄ, ÓÏÞÅÔÁÀÝÉÊ × ÓÅÂÅ "ÐÒÑÍÏÊ" ÁÌÇÏÒÉÔÍ É ÍÅÔÏÄ ïÕÜÎÁ. ôÉÐÉÞÎÁ ÓÉÔÕÁÃÉÑ, × ËÏÔÏÒÏÊÎÅÓËÏÌØËÏ ÉÇÒÏËÏ× ÏÂÌÁÄÁÀÔ ÏÔÎÏÓÉÔÅÌØÎÏ ÂÏÌØÛÉÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ× (ÍÁÖÏÒÉÔÁÒÎÙÅ ÁËÃÉÏÎÅÒÙ × ÁËÃÉÏÎÅÒÎÙÈ ÏÂÝÅÓÔ×ÁÈ), Á ÏÓÔÁÌØÎÙÅ | ÍÁÌÙÍ. ðÕÓÔØM | ÍÎÏÖÅÓÔ×Ï ÉÇÒÏËÏ× Ó ÂÏÌØÛÉÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ×. æÕÎËÃÉÀ fi(x) ÍÏÖÎÏ×ÙÞÉÓÌÉÔØ, ËÁËfi(x) =XS ⊆M \{i}p(S; x)gi(S; x);ÇÄÅ p(S; x) = xs(1 − x)m−s−1 | ×ÅÒÏÑÔÎÏÓÔØ ÔÏÇÏ, ÞÔÏ ×ÓÅ ÉÇÒÏËÉ ËÏÁÌÉÃÉÉ SÐÒÏÇÏÌÏÓÕÀÔ ÚÁ ÒÅÛÅÎÉÅ, Á M \ (S ∪ {i}) | ÐÒÏÔÉ×, Á gi(S; x) | ×ÅÒÏÑÔÎÏÓÔØÔÏÇÏ, ÞÔÏ ÉÇÒÏË i ÂÕÄÅÔ ËÌÀÞÅ×ÙÍ × ÓÌÏÖÉ×ÛÅÊÓÑ ÓÉÔÕÁÃÉÉ.äÌÑ ËÁÖÄÏÇÏ S ÆÕÎËÃÉÑ p(S; x) ×ÙÞÉÓÌÑÅÔÓÑ ÔÏÞÎÏ, Á gi(S; x) ÐÒÉÂÌÉÖÅÎÎÏ,ÔÅÍ ÖÅ ÍÅÔÏÄÏÍ, ÞÔÏ É fi(x) × ÍÅÔÏÄÅ ïÕÜÎÁ.þÉÓÌÏ "ÂÏÌØÛÉÈ" ÉÇÒÏËÏ× ×ÙÂÉÒÁÅÔÓÑ ÌÉÂÏ ÉÓÈÏÄÑ ÉÚ ÓÐÅÃÉÆÉËÉ ÉÇÒÙ, ÌÉÂÏÉÚ ÉÍÅÀÝÅÇÏÓÑ ÍÁÛÉÎÎÏÇÏ ×ÒÅÍÅÎÉ | ÞÅÍ ÂÏÌØÛÅ "ÂÏÌØÛÉÈ" ÉÇÒÏËÏ×, ÔÅÍÂÏÌØÛÅ ×ÒÅÍÅÎÉ ÚÁÊÍÅÔ ×ÙÞÉÓÌÅÎÉÅ, ÎÏ ÔÅÍ ÏÎÏ ÂÕÄÅÔ ÔÏÞÎÅÅ.óËÏÒÅÅ ×ÓÅÇÏ, ÍÅÔÏÄ ìÉÞÁ ÄÁÅÔ ÈÏÒÏÛÉÅ ÒÅÚÕÌØÔÁÔÙ (ÈÏÔÑ Á×ÔÏÒÕ ÎÅ ÉÚ×ÅÓÔÎÏ, ÉÓÐÏÌØÚÏ×ÁÌÓÑ ÌÉ ÏÎ ÇÄÅ-ÎÉÂÕÄØ, ËÒÏÍÅ ÏÒÉÇÉÎÁÌØÎÙÈ ÒÁÂÏÔ), ÎÏ ÐÏÌÕÞÉÔØÏÃÅÎËÕ ÅÇÏ ÔÏÞÎÏÓÔÉ ÚÁÔÒÕÄÎÉÔÅÌØÎÏ.1243.
áÌÇÏÒÉÔÍÙ ÒÁÓÞÅÔÁ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ× Ó ÐÏÍÏÝØÀ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ"ðÒÑÍÏÊ" ÁÌÇÏÒÉÔÍ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÒÁÂÏÔÁÅÔ ÄÌÑ -ÉÎÄÅËÓÁÓÔÏÌØ ÖÅ ÈÏÒÏÛÏ, ËÁË É ÄÌÑ ËÌÁÓÓÉÞÅÓËÉÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ. áÌÇÏÒÉÔÍ ÓÏÓÔÏÉÔ × ÐÅÒÅÂÏÒÅ ËÏÁÌÉÃÉÊ É × ÜÔÏÍ ÓÌÕÞÁÅ ÎÅ ×ÁÖÎÏ, ÞÔÏ ÓÕÍÍÉÒÏ×ÁÔØ ÐÏ ×ÓÅÍÜÌÅÍÅÎÔÁÍ Wi(v) | ËÏÎÓÔÁÎÔÙ, ËÁË × ÉÎÄÅËÓÅ âÁÎÃÁÆÁ, ÉÌÉ ËÁËÉÅ-ÔÏ ÄÒÕÇÉÅÞÉÓÌÁ.îÏ, "ÐÒÑÍÏÊ" ÁÌÇÏÒÉÔÍ ÎÅ ÐÏÚ×ÏÌÑÅÔ ×ÙÞÉÓÌÑÔØ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ ÚÁ ÒÁÚÕÍÎÏÅ ×ÒÅÍÑ ÕÖÅ ÐÒÉ n ∼ 60. ðÏÜÔÏÍÕ ×ÓÔÁÅÔ ×ÏÐÒÏÓ, ËÁË ÐÒÉÍÅÎÉÔØ Ë -ÉÎÄÅËÓÕÍÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ.÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÆÕÎËÃÉÉ f (i; S ) ÚÁ×ÉÓÑÔ ÔÏÌØËÏ ÏÔ ÍÁÔÒÉÃÙ ÐÒÅÄÐÏÞÔÅÎÉÊ P ([28], ÓÍ. ÔÁËÖÅ ÐÒÉÍÅÒ 23, ÇÌÁ×Á 1).
äÌÑ ÔÏÇÏ, ÞÔÏÂÙÐÏÄÞÅÒËÎÕÔØ ÜÔÏÔ ÆÁËÔ, ×ÍÅÓÔÏ f (i; S ) ÂÕÄÅÍ ÐÉÓÁÔØ f (i; S; P ).éÎÄÅËÓÙ ×ÌÉÑÎÉÑ, ÐÏÓÔÒÏÅÎÎÙÅ ÎÁ ÏÓÎÏ×Å ÍÁÔÒÉÃÙ ÐÒÅÄÐÏÞÔÅÎÉÊ P , ×ÙÞÉÓÌÑÀÔÓÑ ÐÏ ÁÎÁÌÏÇÉÞÎÙÍ Ó ÉÎÄÅËÓÁÍÉ âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ ÆÏÒÍÕÌÁÍ,ÏÄÎÁËÏ, Ó ÏÄÎÉÍ ÎÀÁÎÓÏÍ. ïÐÒÅÄÅÌÉÍrk (i) =rk;l (i) =óÏÏÔ×ÅÔÓÔ×ÅÎÎÏ,r(i) =Xw(S )=kf (i; S; P );Xw(S )=k;|S |=l;q−1Xk=q−wirk (i) =125f (i; S; P ):q−1X Xl k=q−wirk;l (i):3.1.
áÎÁÌÏÇ ÉÎÄÅËÓÁ âÁÎÃÁÆÁðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄRi(x) =Yj 6=iPj ∈S fij .(1 + fij xwj ) =òÁÓÓÍÏÔÒÉÍ ÍÎÏÇÏÞÌÅÎX YS ⊆(N \i) j ∈Sfij xw(S ) =XkxkX Yw(S )=k j ∈Sfij :ëÏÜÆÆÉÃÉÅÎÔ ÐÒÉ xk ÐÏÈÏÖ ÎÁ rk (i) Ó ÏÄÎÉÍ ÏÔÌÉÞÉÅÍ | ËÏÜÆÆÉÃÉÅÎÔÙ fijÎÅ ÓËÌÁÄÙ×ÁÀÔÓÑ, Á ÐÅÒÅÍÎÏÖÁÀÔÓÑ. ðÏÜÔÏÍÕ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ rk (i)×ÙÞÉÓÌÑÅÔÓÑ ÔÁË ÖÅ, ËÁË Ri(x), ÎÏ ÏÐÅÒÁÃÉÑ ÕÍÎÏÖÅÎÉÑ ÚÁÍÅÎÑÅÔÓÑ ÎÁ ÏÐÅÒÁÃÉÀÓÌÏÖÅÎÉÑ.óÌÅÄÏ×ÁÔÅÌØÎÏ, i(v) ÍÏÖÅÔ ÂÙÔØ ×ÙÞÉÓÌÅÎÏ ÚÁ ÔÏ ÖÅ ×ÒÅÍÑ, ÞÔÏ É ÉÎÄÅËÓâÁÎÃÁÆÁ, Ô.Å. ÚÁ O(C (v) · n).îÏ, × ÏÔÌÉÞÉÅ ÏÔ ÉÎÄÅËÓÏ× âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ, × Ri(x) ×ÈÏÄÑÔ ÒÁÚÎÙÅ ËÏÎÓÔÁÎÔÙ fij ÄÌÑ ÒÁÚÎÙÈ i, ÐÏÜÔÏÍÕ ÎÅ×ÏÚÍÏÖÎÏ ÐÏÌÕÞÉÔØ ÆÏÒÍÕÌÙ, ÁÎÁÌÏÇÉÞÎÙÅ (3.4)-(3.5).
ëÁÖÄÕÀ ËÏÏÒÄÉÎÁÔÕ i(v) ÐÒÉÈÏÄÉÔÓÑ ×ÙÞÉÓÌÑÔØ ÏÔÄÅÌØÎÏ.ðÏÜÔÏÍÕ ×ÙÞÉÓÌÅÎÉÅ (v) (ÉÌÉ N(v)) ÔÒÅÂÕÅÔ O(C (v) · n2) ÏÐÅÒÁÃÉÊ.3.2. áÎÁÌÏÇ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄPj ∈S f0 (|S |)fij .ôÁËÏ×Ù, × ÞÁÓÔÎÏÓÔÉ, ÒÁÓÓÍÏÔÒÅÎÎÙÅ× ÐÒÉÍÅÒÅ 23 f +(i; S; P ), f −(i; S; P ) É f (i; S; P ).òÁÓÓÍÏÔÒÉÍ ÍÎÏÇÏÞÌÅÎRi(x; y ) =Yj 6=i(1 + fij yxwj ) =X YS ⊆(N \i) j ∈Sfij ysxw(S ) =Xk;sxk y lXYw(S )=k;|S |=l j ∈Sfij :ëÏÜÆÆÉÃÉÅÎÔ ÐÒÉ xk yl ÐÏÈÏÖ ÎÁ rk;l (i) Ó Ä×ÕÍÑ ÏÔÌÉÞÉÑÍÉ | ËÏÜÆÆÉÃÉÅÎÔÙfij ÎÅ ÓËÌÁÄÙ×ÁÀÔÓÑ, Á ÐÅÒÅÍÎÏÖÁÀÔÓÑ, É ËÏÜÆÆÉÃÉÅÎÔÙ ÐÒÉ yl ÄÏÌÖÎÙ ÂÙÔØÕÍÎÏÖÅÎÙ ÎÁ f0(l). ðÏÜÔÏÍÕ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ rk;l (i) ×ÙÞÉÓÌÑÅÔÓÑ ÔÁË126ÖÅ, ËÁË Ri(x; y ), ÎÏ ÏÐÅÒÁÃÉÑ ÕÍÎÏÖÅÎÉÑ ÚÁÍÅÎÑÅÔÓÑ ÎÁ ÏÐÅÒÁÃÉÀ ÓÌÏÖÅÎÉÑ, ÁÕÍÎÏÖÅÎÉÅ ÎÁ f0(l) ÐÒÏÉÚ×ÏÄÉÔÓÑ × ËÏÎÃÅ ×ÙÞÉÓÌÅÎÉÊ.
ðÏÓÌÅÄÎÀÀ ÏÐÅÒÁÃÉÀÍÏÖÎÏ ×ÏÓÐÒÉÎÉÍÁÔØ ËÁË ÓËÁÌÑÒÎÏÅ ÐÒÏÉÚ×ÅÄÅÎÉÅ ×ÅËÔÏÒÁ Ri(x; y ), ÒÁÚÌÏÖÅÎÎÏÇÏ ÐÏ ÓÔÅÐÅÎÑÍ y É ×ÅËÔÏÒÁ (1; f0(1); f0(2); : : : ; f0(n)).óÌÅÄÏ×ÁÔÅÌØÎÏ, i(v) ÍÏÖÅÔ ÂÙÔØ ×ÙÞÉÓÌÅÎÏ ÚÁ ÔÏ ÖÅ ×ÒÅÍÑ, ÞÔÏ É ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ, Ô.Å. ÚÁ O(C (v) · n2). óÏÏÔ×ÅÔÓÔ×ÅÎÎÏ, (v) (ÉÌÉ N(v))×ÙÞÉÓÌÑÅÔÓÑ ÚÁ O(C (v) · n3) ÏÐÅÒÁÃÉÊ. ÷ÙÞÉÓÌÑÔØ i(v) ÏÄÎÏ×ÒÅÍÅÎÎÏ ÎÅ ÐÏÌÕÞÁÅÔÓÑ ÐÏ ÔÏÊ ÖÅ ÐÒÉÞÉÎÅ, ÞÔÏ É ÄÌÑ ÁÎÁÌÏÇÁ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ.3.3.
ïÓÎÏ×ÎÁÑ ÔÅÏÒÅÍÁþÔÏÂÙ ÚÁÐÉÓÁÔØ ÐÏÌÕÞÅÎÎÙÅ ÒÅÚÕÌØÔÁÔÙ ÆÏÒÍÁÌØÎÏ, ××ÅÄÅÍ "ÐÓÅ×ÄÏÞÉÓÌÁ" a,ËÏÔÏÒÙÅ ÓËÌÁÄÙ×ÁÀÔÓÑ É ×ÙÞÉÔÁÀÔÓÑ ÐÏ ÏÂÙÞÎÙÍ ÐÒÁ×ÉÌÁÍ (× ÔÏÍ ÞÉÓÌÅ É ÓÏÂÙÞÎÙÍÉ ÞÉÓÌÁÍÉ), ÐÒÉ ÕÍÎÏÖÅÎÉÉ ÎÁ 1 ÏÎÉ ÎÅ ÍÅÎÑÀÔÓÑ, ÎÏ ÐÒÉ ÐÅÒÅÍÎÏÖÅÎÉÉ ÍÅÖÄÕ ÓÏÂÏÊ ÎÅ ÕÍÎÏÖÁÀÔÓÑ, Á ÓËÌÁÄÙ×ÁÀÔÓÑ. ô.Å.a + b = a + b; a − b = a − b; 1 · b = b; a + b = a + b; a − b = a − b; a · b = a + b:÷Ï ××ÅÄÅÎÎÙÈ ÏÂÏÚÎÁÞÅÎÉÑÈ ÒÁÓÓÕÖÄÅÎÉÑ ÜÔÏÇÏ ÐÁÒÁÇÒÁÆÁ ÄÏËÁÚÙ×ÁÀÔ ÓÌÅÄÕÀÝÅÅ ÕÔ×ÅÒÖÄÅÎÉÅ.ôÅÏÒÅÍÁ 2.
1). ðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄPj ∈S fij ,ÇÄÅ fij ÚÁ×ÉÓÑÔ ÔÏÌØËÏÏÔ i, j É P . ôÏÇÄÁ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ rk (i) ÉÍÅÅÔ ×ÉÄRi(x) =2). ðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄPYj 6=i(1 + fij xwj ):j ∈S f0 (s)fij ,ÇÄÅ fij ÚÁ×ÉÓÑÔ ÔÏÌØËÏ ÏÔ i, jÉ P . ôÏÇÄÁ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ rk;l (i) ÉÍÅÅÔ ×ÉÄ127Ri(x; y ) =*Yj 6=i+(1 + fij yxwj ); (1; f0(1); f0(2); : : : ; f0(n)) :ðÒÉ×ÅÄÅÎÎÙÊ ÁÌÇÏÒÉÔÍ ÐÅÒ×ÏÎÁÞÁÌØÎÏ ÂÙÌ ÎÁÐÉÓÁÎ ÄÌÑ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÄÌÑ íÅÖÄÕÎÁÒÏÄÎÏÇÏ ×ÁÌÀÔÎÏÇÏ ÆÏÎÄÁ (IMF, 184 ÕÞÁÓÔÎÉËÁ, ÓÕÍÍÁ ÇÏÌÏÓÏ× | 2,2 ÍÌÎ), Á ÔÁËÖÅ ÉÓÐÏÌØÚÏ×ÁÌÓÑ ÄÌÑ ÐÏÄÓÞÅÔÁ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ× çä òæ, ÕÞÉÔÙ×ÁÀÝÉÈ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ÄÅÐÕÔÁÔÏ× ÐÏ ÒÅÇÉÏÎÁÍ.-ÉÎÄÅËÓ ×ÙÞÉÓÌÑÌÓÑ ÄÌÑ ÆÕÎËÃÉÊ ÉÎÔÅÎÓÉ×ÎÏÓÔÉ f +(i; S; P ) É f −(i; S; P ), Ô.Å.ÉÓÐÏÌØÚÏ×ÁÌÁÓØ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÏÔ Ä×ÕÈ ÐÅÒÅÍÅÎÎÙÈ. äÌÑ ×ÙÞÉÓÌÅÎÉÊÎÅÏÂÈÏÄÉÍÏ ÈÒÁÎÉÔØ ×ÓÅ ÅÅ ËÏÜÆÆÉÃÉÅÎÔÙ, Ô.Å.
ÐÒÏÇÒÁÍÍÁ ÔÒÅÂÕÅÔ O(qn) ÑÞÅÅË ÐÁÍÑÔÉ (ðÏÓËÏÌØËÕ ÉÇÒÏË ÎÅ ÍÏÖÅÔ ÂÙÔØ ËÌÀÞÅ×ÙÍ × ËÏÁÌÉÃÉÉ, ÇÄÅ ÓÕÍÍÁÇÏÌÏÓÏ× ÏÓÔÁÌØÎÙÈ ÉÇÒÏËÏ× ÂÏÌØÛÅ Ë×ÏÔÙ, ÔÁËÉÅ ËÏÁÌÉÃÉÉ ÍÏÖÎÏ ÎÅ ÏÂÓÞÉÔÙ×ÁÔØ É ÎÅ ×ÙÄÅÌÑÔØ ÐÏÄ ÎÉÈ ÐÁÍÑÔØ.). äÌÑ IMF ÜÔÏ ÏÚÎÁÞÁÌÏ ÏËÏÌÏ 12 ÞÁÓÏ×ÒÁÂÏÔÙ ÐÒÏÇÒÁÍÍÙ É 4 çâ ÐÁÍÑÔÉ, ËÏÔÏÒÙÅ ÐÕÔÅÍ ÏÐÔÉÍÉÚÁÃÉÉ ÁÌÇÏÒÉÔÍÁ ÐÏÄËÏÎËÒÅÔÎÕÀ ÚÁÄÁÞÕ ÕÄÁÌÏÓØ ÓÏËÒÁÔÉÔØ ÄÏ 1.5 çâ.ë ÓÏÖÁÌÅÎÉÀ, ÞÅÍ "ÍÅÎÅÅ ÌÉÎÅÊÎÏ" ÕÓÔÒÏÅÎÙ ÆÏÒÍÕÌÙ ÄÌÑ ÆÕÎËÃÉÉ ÉÎÔÅÎÓÉ×ÎÏÓÔÉ, ÔÅÍ ÓÌÏÖÎÅÅ ÐÒÉÍÅÎÉÔØ ÍÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ.äÌÑ ÆÕÎËÃÉÉ f (S; P ) (ÆÏÒÍÕÌÁ (1.8)) ÜÔÏ ÅÝÅ ×ÏÚÍÏÖÎÏ.
îÏ × ÜÔÏÍ ÓÌÕÞÁÅÄÌÑ ËÁÖÄÏÇÏ ÍÎÏÖÅÓÔ×Á ËÏÁÌÉÃÉÊ ÉÚ s ÉÇÒÏËÏ× Ó ÓÕÍÍÏÊ ÇÏÌÏÓÏ× k ÐÒÉÄÅÔÓÑÈÒÁÎÉÔØ (É ÐÅÒÅÓÞÉÔÙ×ÁÔØ), ÓËÏÌØËÏ ÒÁÚ ËÁÖÄÙÊ ÉÇÒÏË ×ÈÏÄÉÔ × ÜÔÉ ËÏÁÌÉÃÉÉ.÷ ÒÅÚÕÌØÔÁÔÅ ÐÏÔÒÅÂÕÅÔÓÑ × n ÒÁÚ ÂÏÌØÛÅ ÐÁÍÑÔÉ É × n ÒÁÚ ÖÅ ×ÏÚÒÁÓÔÅÔ ×ÒÅÍÑÒÁÂÏÔÙ. äÌÑ IMF ÜÔÏ ÏÚÎÁÞÁÅÔ ∼ 3 · 1015 ÏÐÅÒÁÃÉÊ É 300 çâ ÐÁÍÑÔÉ.åÓÌÉ ÆÕÎËÃÉÉ ÉÎÔÅÎÓÉ×ÎÏÓÔÉ ÕÓÔÒÏÅÎÙ ÓÌÏÖÎÅÅ (ÎÁÐÒÉÍÅÒ, ËÁË × ÆÏÒÍÕÌÁÈ(3.4)|(3.5)), ÐÒÉÍÅÎÉÔØ ÍÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ ÎÅ ÕÄÁÅÔÓÑ É ÐÒÉÈÏÄÉÔÓÑÉÓÐÏÌØÚÏ×ÁÔØ ÐÒÉÂÌÉÖÅÎÎÙÅ ÍÅÔÏÄÙ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ.1284. ðÒÉÍÅÒÙ É ÐÒÉÍÅÎÅÎÉÅ4.1.
ï ÐÒÁ×ÉÌÅ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ × óÏ×ÅÔÅ ÍÉÎÉÓÔÒÏ×å×ÒÏÐÅÊÓËÏÇÏ óÏÀÚÁC 1 ÍÁÑ 2004 Ç. × å×ÒÏÓÏÀÚ ×ÈÏÄÑÔ 27 ÓÔÒÁÎ, ÒÁÓÐÒÅÄÅÌÅÎÉÅ ÇÏÌÏÓÏ× ËÏÔÏÒÙÈ ×óÏ×ÅÔÅ íÉÎÉÓÔÒÏ× åó ÐÒÉ×ÅÄÅÎÏ × ÔÁÂÌÉÃÅ 3.1 (c. 130).äÅËÌÁÒÁÃÉÑ 20 ÕÓÔÁÎÁ×ÌÉ×ÁÅÔ ÔÁËÖÅ ÔÒÅÂÏ×ÁÎÉÑ Ë Ë×ÁÌÉÆÉÃÉÒÏ×ÁÎÎÏÍÕ ÂÏÌØÛÉÎÓÔ×Õ ÐÒÉ ÇÏÌÏÓÏ×ÁÎÉÉ ÚÁ ÚÁËÏÎÏÐÒÏÅËÔÙ, ×ÎÅÓÅÎÎÙÅ ÎÁ ÒÁÓÓÍÏÔÒÅÎÉÅ åó.äÌÑ ÔÏÇÏ ÞÔÏÂÙ ÚÁËÏÎÏÐÒÏÅËÔ ÂÙÌ ÐÒÉÎÑÔ, ÎÅÏÂÈÏÄÉÍÁ Ë×ÏÔÁ × 258 ÇÏÌÏÓÏ×É Ë×ÁÌÉÆÉÃÉÒÏ×ÁÎÎÏÅ ÂÏÌØÛÉÎÓÔ×Ï ÞÌÅÎÏ× óí (14 ÉÚ 27). ëÒÏÍÅ ÔÏÇÏ, ÌÀÂÁÑÓÔÒÁÎÁ ÍÏÖÅÔ ÚÁÔÒÅÂÏ×ÁÔØ ÐÏÄÔ×ÅÒÖÄÅÎÉÑ ÔÏÇÏ, ÞÔÏ ÎÁÓÅÌÅÎÉÅ ÓÔÒÁÎ, ÓÏÓÔÁ×ÌÑÀÝÉÈ Ë×ÁÌÉÆÉÃÉÒÏ×ÁÎÎÏÅ ÂÏÌØÛÉÎÓÔ×Ï, ÐÒÅÄÓÔÁ×ÌÑÅÔ ÐÏ ËÒÁÊÎÅÊ ÍÅÒÅ 62%ÏÂÝÅÇÏ ÎÁÓÅÌÅÎÉÑ å×ÒÏÓÏÀÚÁ.ôÁËÉÍ ÏÂÒÁÚÏÍ, × óí ÐÒÉÍÅÎÑÅÔÓÑ ÔÒÅÈÍÁÖÏÒÉÔÁÒÎÏÅ ÐÒÁ×ÉÌÏ ÐÒÉÎÑÔÉÑÒÅÛÅÎÉÊ, Ô.Å. ÔÒÅÂÕÅÔÓÑ ÏÄÎÏ×ÒÅÍÅÎÎÏ 258 ÇÏÌÏÓÏ× "ÚÁ" ÉÚ 345, 14 ÇÏÌÏÓÏ× "ÚÁ"ÉÚ 27 (ÐÏ ÓÔÒÁÎÁÍ) É ÐÏÄÄÅÒÖËÁ ÓÔÒÁÎ, ÏÂÌÁÄÁÀÝÉÈ × ÓÕÍÍÅ 62% ÎÁÓÅÌÅÎÉÑ åó.òÁÚÕÍÅÅÔÓÑ, ÓÕÝÅÓÔ×ÕÀÔ ÍÎÏÇÏÞÉÓÌÅÎÎÙÅ ÐÒÉÞÉÎÙ, ÂÌÁÇÏÄÁÒÑ ËÏÔÏÒÙÍ ÐÒÁ×ÉÌÏ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÏ ÉÍÅÎÎÏ ÔÁË, ÎÏ Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÍÁÔÅÍÁÔÉËÉ, ÍÎÏÇÏÅ ÍÏÖÎÏ ÕÐÒÏÓÔÉÔØ.1.
úÁÍÅÔÉÍ, ÞÔÏ ÓÁÍÁÑ ÂÏÌØÛÁÑ ÐÏ ÞÉÓÌÕ ÇÏÌÏÓÏ× ËÏÁÌÉÃÉÑ ÉÚ 13 ÉÇÒÏËÏ×ÎÁÂÉÒÁÅÔ 29 · 4+27 · 2+14+13+12 · 5 = 257 (!) ÇÏÌÏÓÏ×, Ô.Å. ÐÒÏÉÇÒÙ×ÁÅÔ. ðÏÜÔÏÍÕÐÅÒ×ÏÅ ÕÓÌÏ×ÉÅ ("ÚÁ" ÄÏÌÖÎÏ ÐÒÏÇÏÌÏÓÏ×ÁÔØ ÂÏÌØÛÉÎÓÔ×Ï ÓÔÒÁÎ) ÉÚÌÉÛÎÅ. äÁÌÅÅÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ×ÔÏÒÏÅ É ÔÒÅÔØÅ ÕÓÌÏ×ÉÅ.2. ïÐÉÛÅÍ ×ÓÅ ÓÉÔÕÁÃÉÉ, × ËÏÔÏÒÙÈ ËÏÁÌÉÃÉÑ, ÎÁÂÒÁ×ÛÁÑ ÎÅ ÍÅÎÅÅ 258 ÇÏÌÏÓÏ×, ÎÅ ÓÏÄÅÒÖÉÔ 62% ÎÁÓÅÌÅÎÉÑ.÷×ÅÄÅÍ ÎÅÓËÏÌØËÏ ÏÂÏÚÎÁÞÅÎÉÊ.
ðÒÏÎÕÍÅÒÕÅÍ ÓÔÒÁÎÙ × ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÔÁ129ôÁÂÌÉÃÁ 3.1. òÁÓÐÒÅÄÅÌÅÎÉÅ ÇÏÌÏÓÏ× × óÏ×ÅÔÅ ÍÉÎÉÓÔÒÏ× ÒÁÓÛÉÒÅÎÎÏÇÏ å×ÒÏÓÏÀÚÁ (ÓÏÇÌÁÓÎÏäÅËÌÁÒÁÃÉÉ 20 ÄÏÇÏ×ÏÒÁ × îÉÃÃÅ)çÏÌÏÓÁóÔÒÁÎÁ× óÏ×ÅÔÅ ÍÉÎÉÓÔÒÏ×ËÁÖÄÏÊ ÓÔÒÁÎÙçÅÒÍÁÎÉÑ29÷ÅÌÉËÏÂÒÉÔÁÎÉÑ29æÒÁÎÃÉÑ29éÔÁÌÉÑ29éÓÐÁÎÉÑ27ðÏÌØÛÁ27òÕÍÙÎÉÑ14îÉÄÅÒÌÁÎÄÙ13çÒÅÃÉÑ12þÅÈÉÑ12âÅÌØÇÉÑ12÷ÅÎÇÒÉÑ12ðÏÒÔÕÇÁÌÉÑ12û×ÅÃÉÑ10âÏÌÇÁÒÉÑ10á×ÓÔÒÉÑ10óÌÏ×ÁËÉÑ7äÁÎÉÑ7æÉÎÌÑÎÄÉÑ7éÒÌÁÎÄÉÑ7ìÉÔ×Á7ìÁÔ×ÉÑ4óÌÏ×ÅÎÉÑ4üÓÔÏÎÉÑ4ëÉÐÒ4ìÀËÓÅÍÂÕÒÇ4íÁÌØÔÁ3éÔÏÇÏ345äÏÌÑÎÁÓÅÌÅÎÉÑ, %17,1512,3212,311,918,277,984,623,32,192,122,122,092,081,831,681,591,121,111,070,790,750,590,40,290,160,090,081001,692,352,352,433,263,383,033,935,475,665,665,745,765,465,956,286,256,306,548,869,336,771013,792544,4437,53,45ÂÌÉÃÅÊ 3.1 É ÏÂÏÚÎÁÞÉÍ ÉÈ a1; : : : ; a27.õÓÌÏ×ÎÏ ÂÕÄÅÍ ÎÁÚÙ×ÁÔØ ÓÔÒÁÎÙ, ÉÍÅÀÝÉÅ ÍÁËÓÉÍÁÌØÎÏÅ ÞÉÓÌÏ ÇÏÌÏÓÏ× (29:çÅÒÍÁÎÉÑ, ÷ÅÌÉËÏÂÒÉÔÁÎÉÑ, æÒÁÎÃÉÑ, éÔÁÌÉÑ), ËÒÕÐÎÙÍÉ.ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ U ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÓÔÒÁÎ, ×ÈÏÄÑÝÉÈ × åó, A = {a1; a2; a3; a4}| ÍÎÏÖÅÓÔ×Ï ËÒÕÐÎÙÈ ÓÔÒÁÎ, B = {a1; : : : ; a6} | ÍÎÏÖÅÓÔ×Ï ÓÔÒÁÎ, ÉÍÅÀÝÉÈ ÎÅ130ÍÅÎÅÅ 27 ÇÏÌÏÓÏ×, ó = {a7; a8} | ÍÎÏÖÅÓÔ×Ï ÓÔÒÁÎ, ÉÍÅÀÝÉÈ 14 ÉÌÉ 13 ÇÏÌÏÓÏ×.ïÂÏÚÎÁÞÉÍ ÔÁËÖÅ ÞÅÒÅÚ V (T ) ÞÉÓÌÏ ÇÏÌÏÓÏ× × ËÏÁÌÉÃÉÉ T , Á P (T ) | ÐÒÏÃÅÎÔÎÁÓÅÌÅÎÉÑ, ÐÒÏÖÉ×ÁÀÝÉÊ × ÓÔÒÁÎÁÈ ÉÚ T .÷ ÞÅÔ×ÅÒÔÏÊ ËÏÌÏÎËÅ ÔÁÂÌÉÃÙ 3.1 ÄÁÎÙ ÏÔÎÏÛÅÎÉÑ ÔÒÅÔØÅÊ ËÏÌÏÎËÉ ËÏ ×ÔÏÒÏÊ, Ô.Å.
ÓËÏÌØËÏ ÇÏÌÏÓÏ× × ËÁÖÄÏÊ ÓÔÒÁÎÅ ÐÒÉÈÏÄÉÔÓÑ ÎÁ 1% ÎÁÓÅÌÅÎÉÑ. ïÂÏÚÎÁÞÉÍ ÜÔÏ ÞÉÓÌÏ ÄÌÑ ÓÔÒÁÎÙ ai ÞÅÒÅÚ (ai). áÎÁÌÏÇÉÞÎÏ, ÏÂÏÚÎÁÞÉÍ (T ) = VP ((TT ))ÄÌÑ ÌÀÂÏÊ ÎÅÐÕÓÔÏÊ ËÏÁÌÉÃÉÉ T .÷ ÏÓÎÏ×Å ÐÅÒÅÂÏÒÁ ÌÅÖÉÔ ÓÌÅÄÕÀÝÅÅ ÐÒÏÓÔÏÅ ÓÏÏÂÒÁÖÅÎÉÅ: ÎÅ ÍÏÖÅÔ ÂÙÔØÔÁË, ÞÔÏ ÄÌÑ ÌÀÂÏÇÏ a ∈ T (a) < , ÎÏ (T ) > , Ô.Å. × ÓÒÅÄÎÅÍ ÐÏ ËÏÁÌÉÃÉÉ ÎÁ1% ÎÁÓÅÌÅÎÉÑ ÐÒÉÈÏÄÉÔÓÑ ÂÏÌØÛÅ ÇÏÌÏÓÏ×, ÞÅÍ ÄÌÑ ÌÀÂÏÇÏ ÕÞÁÓÔÎÉËÁ ËÏÁÌÉÃÉÉ.ëÏÁÌÉÃÉÑ, × ËÏÔÏÒÕÀ ÎÅ ×ÈÏÄÉÔ ÎÅ ÂÏÌÅÅ ÏÄÎÏÊ ÉÚ ËÒÕÐÎÙÈ ÓÔÒÁÎ, ÎÁÂÉÒÁÅÔÎÅ ÂÏÌÅÅ 345 − 29 · 3 = 258 ÇÏÌÏÓÏ×, Ô.Å.