Диссертация (1137405), страница 13
Текст из файла (страница 13)
ðÅÒÅÐÉÛÅÍ ÁËÓÉÏÍÙ:áËÓÉÏÍÁ ÂÏÌ×ÁÎÁ/Null Player (NP). ÷ÙÉÇÒÙÛ ÂÏÌ×ÁÎÁ ÎÅ ÚÁ×ÉÓÉÔ ÏÔÉÎÔÅÎÓÉ×ÎÏÓÔÅÊ ÐÒÅÄÐÏÞÔÅÎÉÊ É ×ÓÅÇÄÁ ÒÁ×ÅÎ 0.õÓÉÌÅÎÎÁÑ ÁËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ/Strong Transfer (ST). äÌÑ ÌÀÂÏÇÏ ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ v É ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v), ÔÁËÉÈ, ÞÔÏ v−S | ÔÏÖÅÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ É ÌÀÂÏÇÏ i ∈ Si(v) − i(v−S ) = f (i; S ):ôÅÏÒÅÍÁ 11. -ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ ÏÄÎÏÚÎÁÞÎÏ ÚÁÄÁÅÔÓÑÁËÓÉÏÍÁÍÉ NP É ST, ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÍÉ ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ.90äÏËÁÚÁÔÅÌØÓÔ×Ï. ëÁË É × ÄÏËÁÚÁÔÅÌØÓÔ×Å ÔÅÏÒÅÍÙ 9, ÏÔÍÅÔÉÍ, ÞÔÏ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÅ ÁËÓÉÏÍÙ ÓÌÁÂÅÅ ÉÈ ÁÎÁÌÏÇÏ×.
ðÏÜÔÏÍÕ ÒÁÚ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÎÅ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÍ ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ ÁËÓÉÏÍÁÍ NP, ST,ÔÏ ÏÎ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ É ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÍ ÁËÓÉÏÍÁÍ.ïÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÂÕÄÅÍ ÄÏËÁÚÙ×ÁÔØ ÐÏ ÉÎÄÕËÃÉÉ ÐÏ ÞÉÓÌÕ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ, ÉÓÐÏÌØÚÕÑ ÐÒÉ ÜÔÏÍ ÐÅÒ×ÕÀ ÞÁÓÔØ ÄÏËÁÚÁÔÅÌØÓÔ×Á.ïÓÎÏ×ÁÎÉÅ ÉÎÄÕËÃÉÉ. ðÕÓÔØ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ ÎÅÔ. üÔÁ ÉÇÒÁ ÚÁÐÉÓÙ×ÁÅÔÓÑ, ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ (n + 1; 1; : : : ; 1).
îÉ ÏÄÉÎ ÉÇÒÏË ÎÅ ÂÕÄÅÔËÌÀÞÅ×ÙÍ ÎÉ × ÏÄÎÏÊ ËÏÁÌÉÃÉÉ. óÌÅÄÏ×ÁÔÅÌØÎÏ, ÐÏ ÁËÓÉÏÍÅ NP i(v) = 0 ÄÌÑ×ÓÅÈ i. ðÏÓËÏÌØËÕ (v) ÔÏÖÅ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ NP, i(v) = 0. úÎÁÞÉÔ i(v) = i(v).ûÁÇ ÉÎÄÕËÃÉÉ. ðÕÓÔØ v ∈ W GPn. åÓÌÉ i | ÂÏÌ×ÁÎ × ÉÇÒÅ v, ÔÏ i(v) =i(v) = 0. åÓÌÉ ÜÔÏ ÎÅ ÔÁË, ÔÏ ÐÏ ÌÅÍÍÅ 4 ÓÕÝÅÓÔ×ÕÅÔ S ∈ M (v), Ô.Þ. v−S ∈W GPn. ë ÉÇÒÅ v−S ÐÒÉÍÅÎÉÍÏ ÐÒÅÄÐÏÌÏÖÅÎÉÅ ÉÎÄÕËÃÉÉ, ÐÏÜÔÏÍÕi(v−S ) = (v−S ) =XT ∈Wi (v−S )f (i; S ):ðÏ ÁËÓÉÏÍÅ ST ÄÌÑ (v), ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ É ÁËÓÉÏÍÅ ST ÄÌÑ (v)i(v) = i(v−S ) + f (i; S ) = i(v−S ) + f (i; S );i(v) = i(v−S ) + f (i; S ):ðÏÜÔÏÍÕ i(v) = i(v). ¥úÁÍÅÞÁÎÉÅ 7. ÷ Ó×ÅÔÅ ÄÏËÁÚÁÎÎÏÇÏ, ÚÁÄÁÞÁ ÐÏÓÔÒÏÅÎÉÑ ÓÐÅÃÉÁÌØÎÙÈ ÁËÓÉÏÍÁÔÉË ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ ËÁÖÅÔÓÑ Á×ÔÏÒÕ ÎÅ ÁËÔÕÁÌØÎÏÊ.âÏÌÅÅ ÉÎÔÅÒÅÓÎÙÍ ÂÙÌÏ ÂÙ ÏÂÏÂÝÅÎÉÅ ÌÅÍÍÙ 4, ÐÏ ÓÕÔÉ ÇÏ×ÏÒÑÝÅÊ, ÞÔÏ ÈÏÔÑÐÒÏÓÔÙÅ ÉÇÒÙ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÇÏÌÏÓÏ×ÁÎÉÑÍ Ó Ë×ÏÔÏÊ, ÎÅ ÏÂÒÁÚÕÀÔ ÒÅÛÅÔËÕ,91ÎÏ ÐÏ ÜÔÏÊ "ÎÅ ÒÅÛÅÔËÅ" ÍÏÖÎÏ ÐÒÏÊÔÉ ÏÔ ÍÁËÓÉÍÁÌØÎÏÇÏ ÜÌÅÍÅÎÔÁ Ë ÍÉÎÉÍÁÌØÎÏÍÕ, ÐÏÓÅÔÉ× ÌÀÂÕÀ ÎÁÐÅÒÅÄ ÚÁÄÁÎÎÕÀ ×ÅÒÛÉÎÕ.
÷ÏÚÍÏÖÎÏ, ÜÔÏ ÓÏÏÂÒÁÖÅÎÉÅÐÏÍÏÖÅÔ ÔÏÞÎÅÅ ÏÐÉÓÁÔØ ÍÎÏÖÅÓÔ×Ï W Gn.4. ðÒÏÅËÔÉ×ÎÙÅ ÁËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑïÓÎÏ×ÏÊ ÄÌÑ ÜÔÏÇÏ ÐÁÒÁÇÒÁÆÁ ÓÔÁÌÏ ÎÅÓËÏÌØËÏ ÄÏ×ÏÌØÎÏ ÏÞÅ×ÉÄÎÙÈ ÎÁÂÌÀÄÅÎÉÊ:• ðÒÉ ×ÙÞÉÓÌÅÎÉÉ ÍÎÏÇÉÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ (âÁÎÃÁÆÁ, äÖÏÎÓÔÏÎÁ, äÉÇÅÎÁ|ðÁËÅÌÁ, èÏÌÅÒÁ|ðÁËÅÌÁ) ×ÎÁÞÁÌÅ ÓÞÉÔÁÅÔÓÑ ÔÁË ÎÁÚÙ×ÁÅÍÙÊ "ÏÂÝÉÊ ÉÎÄÅËÓ",Á ÓÁÍ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÐÏÌÕÞÁÅÔÓÑ ÉÚ ÎÅÇÏ ÎÏÒÍÉÒÏ×ÁÎÉÅÍ,Ô.Å. ÄÅÌÅÎÉÅÍ ÎÁ ÔÁËÏÅ ÞÉÓÌÏ, ÞÔÏÂÙ ÓÕÍÍÁ ×ÌÉÑÎÉÊ ×ÓÅÈ ÉÇÒÏËÏ× ÓÔÁÌÁ ÒÁ×ÎÁÅÄÉÎÉÃÅ. éÎÁÞÅ ÇÏ×ÏÒÑ, × ÉÎÄÅËÓÁÈ ×ÌÉÑÎÉÑ ÉÓÐÏÌØÚÕÀÔÓÑ ÏÔÎÏÓÉÔÅÌØÎÙÅ ÚÎÁÞÅÎÉÑ.•åÓÌÉ × ÓÉÔÕÁÃÉÉ ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ ÕÍÎÏÖÉÔØ ÞÉÓÌÏ ÇÏÌÏÓÏ× ×ÓÅÈ ÉÇÒÏ-ËÏ× É Ë×ÏÔÕ ÎÁ ÏÄÎÏ É ÔÏ ÖÅ ÐÏÌÏÖÉÔÅÌØÎÏÅ ÞÉÓÌÏ, ÎÏ×ÏÅ ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊÂÕÄÅÔ ÚÁÄÁ×ÁÔØ ÔÕ ÖÅ ÐÒÏÓÔÕÀ ÉÇÒÕ, ÞÔÏ É ÓÔÁÒÏÅ.•éÎÔÅÎÓÉ×ÎÏÓÔÉ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ× ([1]) ×Ï ÍÎÏÇÉÈ ÓÌÕÞÁÑÈ ÔÁËÖÅÍÏÇÕÔ ÂÙÔØ ÏÐÒÅÄÅÌÅÎÙ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ, ÐÏÓËÏÌØËÕ ÏÔÕÍÎÏÖÅÎÉÑ ×ÓÅÈ ÉÎÔÅÎÓÉ×ÎÏÓÔÅÊ ÎÁ ÏÄÎÏ É ÔÏ ÖÅ ÞÉÓÌÏ ÏÔÎÏÛÅÎÉÑ ×ÌÉÑÎÉÑÉÇÒÏËÏ× ÎÅ ÉÚÍÅÎÑÔÓÑ, ÐÏÜÔÏÍÕ ÉÈ ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ, Ô.Å.
ËÁË ÜÌÅÍÅÎÔÙ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á.éÓÐÏÌØÚÏ×ÁÎÉÅ ÜÔÏÇÏ ÐÏÄÈÏÄÁ ÓÒÁÚÕ ÖÅ ÐÏÚ×ÏÌÑÅÔ ÉÓÐÒÁ×ÉÔØ Ä×Á ÓÕÝÅÓÔ×ÅÎÎÙÈ ÎÅÄÏÓÔÁÔËÁ ÉÚÌÏÖÅÎÎÙÈ ×ÙÛÅ ÁËÓÉÏÍÁÔÉË.1. ÷ ÒÅÁÌØÎÙÈ ×ÙÞÉÓÌÅÎÉÑÈ, ËÁË ÐÒÁ×ÉÌÏ, ÉÓÐÏÌØÚÕÀÔÓÑ ÏÔÎÏÓÉÔÅÌØÎÙÅ ÚÎÁ92ÞÅÎÉÑ ×ÌÉÑÎÉÑ, Ô.Å. ÎÏÒÍÉÒÏ×ÁÎÎÙÅ ÉÎÄÅËÓ âÁÎÃÁÆÁ ÉÌÉ -ÉÎÄÅËÓ, Á ÁËÓÉÏÍÁÔÉËÉ ÓÔÒÏÑÔÓÑ ÄÌÑ ÎÅÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ("ÏÂÝÅÇÏ") ÉÎÄÅËÓÁ.2.
÷ ÁËÓÉÏÍÁÔÉËÅ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ [50, 65] É ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ× [23], ×ÈÏÄÉÔ ÎÅÅÓÔÅÓÔ×ÅÎÎÁÑ ÁËÓÉÏÍÁ "ïÂÝÅÊ ÓÕÍÍÙ" (ÉÌÉ ÅÅ ÁÎÁÌÏÇ), ×ÏÚÎÉËÁÀÝÁÑ ËÁË ÒÁÚ ÉÚ-ÚÁ ÔÏÇÏ, ÞÔÏ ÓÕÍÍÁ ×ÓÅÈ×ÌÉÑÎÉÊ ÎÅ ÒÁ×ÎÁ ÅÄÉÎÉÃÅ.åÓÌÉ ÐÏÄÈÏÄÉÔØ Ë ÉÎÄÅËÓÁÍ ×ÌÉÑÎÉÑ, ËÁË Ë ÜÌÅÍÅÎÔÁÍ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á, Ô.Å. ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÉÈ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ, ÔÏ ÍÏÖÎÏ ÎÅ ÒÁÚÌÉÞÁÔØ ÏÂÝÉÊ É ÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÉÎÄÅËÓÙ É ÔÁËÉÍ ÐÕÔÅÍ ÉÚÂÁ×ÉÔØÓÑÏÔ ÐÅÒ×ÏÇÏ ÎÅÄÏÓÔÁÔËÁ. á ÁËÓÉÏÍÁ ÏÂÝÅÊ ÓÕÍÍÙ ÓÔÁÎÏ×ÉÔÓÑ ÐÒÏÓÔÏ ÎÅ ÎÕÖÎÁ.ãÅÌØ ÐÁÒÁÇÒÁÆÁ | ÏÂÏÓÎÏ×ÁÎÉÅ ÜÔÏÊ ÔÏÞËÉ ÚÒÅÎÉÑ.4.1.
ðÒÏÅËÔÉ×ÎÙÅ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ: ÏÐÒÅÄÅÌÅÎÉÑïÐÒÅÄÅÌÅÎÉÅ 1 ([17]). îÁ ÍÎÏÖÅÓÔ×Å Rn+1={0} ÒÁÓÓÍÏÔÒÉÍ ÏÔÎÏÛÅÎÉÅ ÜË×É×ÁÌÅÎÔÎÏÓÔÉv1 ∼ v2 ⇔ ∃ 6= 0 : v1 = v2É ÎÁÚÏ×ÅÍ n-ÍÅÒÎÙÍ ÐÒÏÅËÔÉ×ÎÙÍ ÐÒÏÓÔÒÁÎÓÔ×ÏÍ (ÏÂÏÚÎÁÞÅÎÉÅ: RPn) ÍÎÏÖÅÓÔ×Ï ËÌÁÓÓÏ× ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÏ ÜÔÏÍÕ ÏÔÎÏÛÅÎÉÀ.ðÏÓËÏÌØËÕ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÙÅ ×ÅËÔÏÒÙ ÜË×É×ÁÌÅÎÔÎÙ, ÍÏÖÎÏ × ËÁÞÅÓÔ×Å ÐÒÅÄÓÔÁ×ÉÔÅÌÅÊ ËÁÖÄÏÇÏ ËÌÁÓÓÁ ×ÙÂÒÁÔØ ×ÅËÔÏÒ ÄÌÉÎÙ 1. ôÁËÉÈ ×ÅËÔÏÒÏ× 2 (v É −v),É ÎÅ ÓÕÝÅÓÔ×ÕÅÔ ÈÏÒÏÛÅÇÏ ÓÐÏÓÏÂÁ ×ÙÂÒÁÔØ ÏÄÉÎ ÉÚ ÎÉÈ ÓÏÇÌÁÓÏ×ÁÎÎÏ, ÐÏÜÔÏÍÕÐÒÏÅËÔÉ×ÎÏÅ ÐÒÏÓÔÒÁÎÓÔ×Ï ÕÓÔÒÏÅÎÏ ÄÏ×ÏÌØÎÏ ÓÌÏÖÎÏ.ðÒÉÍÅÒ 3 ([17]).
ðÒÏÅËÔÉ×ÎÕÀ ÐÌÏÓËÏÓÔØ ÍÏÖÎÏ ×ÏÓÐÒÉÎÉÍÁÔØ, ËÁË ÓÆÅÒÕÓ ÏÔÏÖÄÅÓÔ×ÌÅÎÎÙÍÉ ÐÒÏÔÉ×ÏÐÏÌÏÖÎÙÍÉ ÔÏÞËÁÍÉ ÉÌÉ ËÁË ËÒÕÇ ÓÏ ÏÔÏÖÄÅ93ÓÔ×ÌÅÎÎÙÍÉ ÐÒÏÔÉ×ÏÐÏÌÏÖÎÙÍÉ ÔÏÞËÁÍÉ ÎÁ ÅÇÏ ËÒÁÀ. ðÒÏÅËÔÉ×ÎÁÑ ÐÌÏÓËÏÓÔØÎÅ ×ËÌÁÄÙ×ÁÅÔÓÑ × ÔÒÅÈÍÅÒÎÏÅ ÐÒÏÓÔÒÁÎÓÔ×Ï.âÕÄÅÍ ÎÁÚÙ×ÁÔØ ÐÒÏÅËÔÉ×ÎÙÍ ÉÎÄÅËÓÏÍ ×ÌÉÑÎÉÑ ÏÔÏÂÒÁÖÅÎÉÅ : SGPn →RPn−1 .åÓÔÅÓÔ×ÅÎÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ : Rn \ {0} → RPn−1 ÓÏÐÏÓÔÁ×ÌÑÅÔ ÎÅÎÕÌÅ×ÏÍÕ×ÅËÔÏÒÕ (x1; : : : ; xn) ÔÏÞËÕ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á (x1 : : : : : xn). üÔÏ ÏÔÏÂÒÁÖÅÎÉÅ ÚÁÄÁÅÔ ÓÏÏÔ×ÅÔÓÔ×ÉÅ ÍÅÖÄÕ ÏÂÙÞÎÙÍÉ É ÐÒÏÅËÔÉ×ÎÙÍÉ ÉÎÄÅËÓÁÍÉ×ÌÉÑÎÉÑ.ëÁÖÄÏÍÕ ÏÂÙÞÎÏÍÕ ÉÎÄÅËÓÕ ×ÌÉÑÎÉÑ, ÎÅ ÒÁ×ÎÏÍÕ 0, ËÁË ×ÅËÔÏÒ, ÎÁ ÐÒÏÓÔÏÊÉÇÒÅ c ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ ÓÏÐÏÓÔÁ×ÌÑÅÔÓÑ ÐÒÏÅËÔÉ×ÎÙÊ ÐÏ ÆÏÒÍÕÌÅ∗()(v) = ((v)):îÁÚÏ×ÅÍ ÏÐÅÒÁÃÉÀ ∗ ÐÒÏÅËÔÉ×ÉÚÁÃÉÅÊ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ.ðÒÏÅËÔÉ×ÎÙÊ -ÉÎÄÅËÓ ÄÌÑ ÉÇÒ Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ ÏÐÒÅÄÅÌÑÅÔÓÑ, ËÁË ÏÂÒÁÚ-ÉÎÄÅËÓÁ ÐÒÉ ÏÔÏÂÒÁÖÅÎÉÉ ∗, Ô.Å.
ÉÎÄÅËÓ ÔÏÔ ÖÅ ÓÁÍÙÊ, ÎÏ ÒÁÓÓÍÁÔÒÉ×ÁÅÔÓÑÓ ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ.P (v) = (1(v) : : : : : n(v))(2.8)ïÐÒÅÄÅÌÅÎÉÅ ËÏÒÒÅËÔÎÏ ÐÏ ÔÅÍ ÖÅ ÐÒÉÞÉÎÁÍ, ÞÔÏ É ÏÐÒÅÄÅÌÅÎÉÅ N(v) | ËÏÏÒÄÉÎÁÔÙ ×ÅËÔÏÒÁ (v) ÎÅÏÔÒÉÃÁÔÅÌØÎÙ É ÎÅ ×ÓÅ ÒÁ×ÎÙ 0. úÄÅÓØ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ,ÞÔÏ v 6= 0; 1.áÎÁÌÏÇÉÞÎÏ, ÐÒÏÅËÔÉ×ÎÙÊ ÁÎÁÌÏÇ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ (P Bz (v)) ÏÐÒÅÄÅÌÑÅÔÓÑ,ËÁË ∗(Bz (v)), Ô.Å. ÜÔÏ ÏÂÙÞÎÙÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ, ÎÏ ×ÅËÔÏÒ ÚÎÁÞÅÎÉÊ ÒÁÓÓÍÁÔÒÉ×ÁÅÔÓÑ ÎÅ ËÁË ÜÌÅÍÅÎÔ Rn, Á ËÁË ÜÌÅÍÅÎÔ RPn−1. ïÔÍÅÔÉÍ, ÞÔÏ ÎÏÒÍÉÒÏ×ÁÎÎÙÊ É ÎÅÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ É ÉÎÄÅËÓ ðÅÎÒÏÕÚÁ ÏÔÌÉÞÁÀÔÓÑÔÏÌØËÏ ÕÍÎÏÖÅÎÉÅÍ ÎÁ ËÏÎÓÔÁÎÔÕ, ÐÏÜÔÏÍÕ ∗(T Bz ) = ∗(Bz ) = ∗(P ) = P Bz .944.2.
áËÓÉÏÍÙðÒÉ ÐÏÓÔÒÏÅÎÉÉ ÁËÓÉÏÍÁÔÉËÉ ÂÕÄÅÍ ÏÔÔÁÌËÉ×ÁÔØÓÑ ÏÔ ÁËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ, ÐÒÅÄÌÏÖÅÎÎÏÊ äÕÂÉ É ûÅÐÌÉ [50].áËÓÉÏÍÙ NP É An ÕÖÅ ÉÍÅÀÔ "ÐÒÏÅËÔÉ×ÎÙÊ ÈÁÒÁËÔÅÒ" É ÐÅÒÅÐÉÓÙ×ÁÀÔÓÑÐÏÞÔÉ ÄÏÓÌÏ×ÎÏ.áËÓÉÏÍÁ ÂÏÌ×ÁÎÁ / Null Player (NP). äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPn ÅÓÌÉ i| ÂÏÌ×ÁÎ × ÉÇÒÅ v, ÔÏ ÅÇÏ ×ÌÉÑÎÉÅ ÒÁ×ÎÏ 0, Ô.Å.i(v) = 0:áÎÏÎÉÍÎÏÓÔØ / Anonimity (An). äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPn, ÌÀÂÏÊ ÐÅÒÅÓÔÁÎÏ×ËÉ ÍÎÏÖÅÓÔ×Á N É ÌÀÂÏÇÏ i ∈ N(v ) = ()(v);ÇÄÅ (v )(S ) = v((S )), Á () | ÐÅÒÅÓÔÁÎÏ×ËÁ ËÏÏÒÄÉÎÁÔ ×ÅËÔÏÒÁ .üÔÕ ÁËÓÉÏÍÕ ÎÅ ÕÄÁÅÔÓÑ ÉÓÐÏÌØÚÏ×ÁÔØ ÐÒÉ ÄÏËÁÚÁÔÅÌØÓÔ×ÁÈ, ÐÏÜÔÏÍÕ ÎÅÏÂÈÏÄÉÍÏ ××ÅÓÔÉ ÂÏÌÅÅ ÓÌÁÂÏÅ ÕÓÌÏ×ÉÅ, ÆÁËÔÉÞÅÓËÉ ÏÇÒÁÎÉÞÉ× ÐÒÉÍÅÎÅÎÉÅ ÁËÓÉÏÍÙAn ÔÏÌØËÏ ÎÁ ÏÌÉÇÁÒÈÉÞÅÓËÉÅ ÉÇÒÙ.óÌÁÂÁÑ ÁËÓÉÏÍÁ ÁÎÏÎÉÍÎÏÓÔÉ / Weak Anonimity (WAn).
äÌÑ ÌÀÂÏÊÏÌÉÇÁÒÈÉÞÅÓËÏÊ ÉÇÒÙ uS ∈ SGPn, É ÌÀÂÙÈ ÉÇÒÏËÏ× i; j ∈ S i(uS ) = j (uS ).÷ ÄÁÌØÎÅÊÛÅÍ ÎÁÍ ÐÏÔÒÅÂÕÀÔÓÑ ÓÌÅÄÕÀÝÉÅ Ä×Á ÕÔ×ÅÒÖÄÅÎÉÑ:õÔ×ÅÒÖÄÅÎÉÅ 1. ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÏÐÒÅÄÅÌÅÎ ÎÁ ÐÒÏÓÔÙÈ ÉÇÒÁÈ: :SGn → RPn. ôÏÇÄÁ ÉÚ ÁËÓÉÏÍÙ ÁÎÏÎÉÍÎÏÓÔÉ ÓÌÅÄÕÅÔ ÓÌÁÂÁÑ ÁËÓÉÏÍÁ ÁÎÏÎÉÍ-ÎÏÓÔÉ.äÏËÁÚÁÔÅÌØÓÔ×Ï. òÁÓÓÍÏÔÒÉÍ ÐÒÏÉÚ×ÏÌØÎÙÅ ÏÌÉÇÁÒÈÉÞÅÓËÕÀ ÉÇÒÕ uS É ÉÇÒÏËÏ× i; j ∈ S . ðÕÓÔØ | ÐÅÒÅÓÔÁÎÏ×ËÁ i É j . ôÏÇÄÁ (uS ) = uS É, ÅÓÌÉ ÕÄÏ×ÌÅ95Ô×ÏÒÑÅÔ ÁËÓÉÏÍÅ An, ÔÏ i(uS ) = j (uS ), ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ. ¥õÔ×ÅÒÖÄÅÎÉÅ 2.
ïÇÒÁÎÉÞÉÍ -ÉÎÄÅËÓ ÎÁ ÍÎÏÖÅÓÔ×Ï ÐÒÏÓÔÙÈ ÉÇÒ Ó ÓÉÍÍÅÔÒÉÞÎÙÍÉ ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ. ôÏÇÄÁ ÏÎ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÓÌÁÂÏÊ ÁËÓÉÏÍÅ ÁÎÏÎÉÍÎÏÓÔÉ.äÏËÁÚÁÔÅÌØÓÔ×Ï. òÁÓÓÍÏÔÒÉÍ ÏÌÉÇÁÒÈÉÞÅÓËÕÀ ÉÇÒÕ uS É Ä×ÕÈ ÉÇÒÏËÏ× i; j ∈S . ðÏÓËÏÌØËÕ ÐÒÅÄÐÏÞÔÅÎÉÑ ÓÉÍÍÅÔÒÉÞÎÙ, ÔÏi(uS ) =ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ. ¥XT ⊇Sf (i; S ) =XT ⊇Sf (j; S ) = j (uS );áËÓÉÏÍÁ BzTP × ÐÒÏÅËÔÉ×ÎÏÍ ÓÌÕÞÁÅ ÎÅ ÉÍÅÅÔ ÓÍÙÓÌÁ, ÐÏÓËÏÌØËÕ É, ÓÌÅÄÏ×ÁÔÅÌØÎÏ, ÓÕÍÍÁ ÅÇÏ ËÏÏÒÄÉÎÁÔ ÏÐÒÅÄÅÌÅÎÁ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ.ðÅÒÅÄ ÔÅÍ, ËÁË ××ÏÄÉÔØ ÐÏÓÌÅÄÎÀÀ ÁËÓÉÏÍÕ, ÐÏÚ×ÏÌÉÍ ÓÅÂÅ ÎÅÂÏÌØÛÏÅ ÎÅÆÏÒÍÁÌØÎÏÅ ÏÂÓÕÖÄÅÎÉÅ.ðÒÁËÔÉÞÅÓËÉ ×Ï ×ÓÅÈ ÁËÓÉÏÍÁÔÉËÁÈ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÉÓÐÏÌØÚÕÅÔÓÑ ÁËÓÉÏÍÁ ÁÄÄÉÔÉ×ÎÏÓÔÉ ÉÌÉ ÅÅ ÁÎÁÌÏÇ (ÁËÓÉÏÍÙ Ad, T, T∗ É ST). îÏ RPn−1 | ÎÅÌÉÎÅÊÎÏÅ ÐÒÏÓÔÒÁÎÓÔ×Ï, ÐÏÜÔÏÍÕ ×ÓÅ "ÌÉÎÅÊÎÙÅ" ÁËÓÉÏÍÙ ÔÅÒÑÀÔ ÓÍÙÓÌ ÐÒÉÐÏÐÙÔËÅ ÒÁÓÓÍÏÔÒÅÔØ ×ÓÅ ×ÈÏÄÑÝÉÅ × ÎÉÈ ÐÅÒÅÍÅÎÎÙÅ ËÁË ÜÌÅÍÅÎÔÙ RPn−1.
ðÏÜÔÏÍÕ ÞÔÏÂÙ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÉÈ ÁÎÁÌÏÇ, ÐÒÉÈÏÄÉÔÓÑ ÐÏÓÔÕÐÉÔØ ÎÅÍÎÏÇÏ ÔÏÎØÛÅ.óÏÇÌÁÓÎÏ ÌÅÍÍÅ 1 (ÇÌÁ×Á 1) ÐÒÉ ×ÙÞÅÒËÉ×ÁÎÉÉ ÍÉÎÉÍÁÌØÎÏÊ ËÏÁÌÉÃÉÉ SÉÇÒÏËÉ, ×ÈÏÄÑÝÉÅ × S , ÔÅÒÑÀÔ ×Ï ×ÌÉÑÎÉÉ ÔÏ, ÞÔÏ ÉÍ ÄÁÅÔ ÜÔÁ ËÏÁÌÉÃÉÑ, Á ÉÇÒÏËi ∈= S ÐÏÌÕÞÁÅÔ ÄÏÐÏÌÎÉÔÅÌØÎÏÅ ×ÌÉÑÎÉÅ ÚÁ ÓÞÅÔ ËÏÁÌÉÃÉÉ S ∪ {i}. ÷ ×ÅËÔÏÒÎÏÊÆÏÒÍÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÌÅÍÍÙ 1 ÚÁÐÉÓÙ×ÁÅÔÓÑ ÔÁË: ÄÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPn ÉÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v)96(v) − (v−S ) = wS ;ÇÄÅ w | ×ÅËÔÏÒ ÄÏÈÏÄÏ× É ÐÏÔÅÒØ, ËÏÏÒÄÉÎÁÔÙ ËÏÔÏÒÏÇÏ ÒÁ×ÎÙwiS =f (i; S ); ÅÓÌÉ i ∈ S ; −f (i; S ∪ {i});ÅÓÌÉ i ∈= S:åÓÌÉ ÒÁÓÓÍÁÔÒÉ×ÁÔØ (v), ËÁË ÔÏÞËÕ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á, ÒÁÚÎÏÓÔØ×ÅËÔÏÒÏ× ÏÐÒÅÄÅÌÅÎÁ ÎÅÏÄÎÏÚÎÁÞÎÏ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
