Автореферат (1137404), страница 3
Текст из файла (страница 3)
÷ ÒÅÁÌØÎÙÈ ×ÙÞÉÓÌÅÎÉÑÈ, ËÁË ÐÒÁ×ÉÌÏ, ÉÓÐÏÌØÚÕÀÔÓÑ ÏÔÎÏÓÉÔÅÌØÎÙÅ ÚÎÁÞÅÎÉÑ ×ÌÉÑÎÉÑ, Ô.Å. ÎÏÒÍÉÒÏ×ÁÎÎÙÅ ÉÎÄÅËÓ âÁÎÃÁÆÁ ÉÌÉ -ÉÎÄÅËÓ, Á ÁËÓÉÏÍÁÔÉËÉ ÓÔÒÏÑÔÓÑ ÄÌÑ ÎÅÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ("ÏÂÝÅÇÏ") ÉÎÄÅËÓÁ.162. ÷ ÁËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ É ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×, ×ÈÏÄÉÔ ÎÅÅÓÔÅÓÔ×ÅÎÎÁÑ ÁËÓÉÏÍÁ "ïÂÝÅÊ ÓÕÍÍÙ"(ÉÌÉ ÅÅ ÁÎÁÌÏÇ), ×ÏÚÎÉËÁÀÝÁÑ ËÁË ÒÁÚ ÉÚ-ÚÁ ÔÏÇÏ, ÞÔÏ ÓÕÍÍÁ ×ÓÅÈ ×ÌÉÑÎÉÊ ÎÅÒÁ×ÎÁ ÅÄÉÎÉÃÅ.åÓÌÉ ÐÏÄÈÏÄÉÔØ Ë ÉÎÄÅËÓÁÍ ×ÌÉÑÎÉÑ, ËÁË Ë ÜÌÅÍÅÎÔÁÍ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á, Ô.Å. ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÉÈ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ, ÔÏ ÍÏÖÎÏ ÎÅ ÒÁÚÌÉÞÁÔØ ÏÂÝÉÊ É ÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÉÎÄÅËÓÙ É ÔÁËÉÍ ÐÕÔÅÍ ÉÚÂÁ×ÉÔØÓÑÏÔ ÐÅÒ×ÏÇÏ ÎÅÄÏÓÔÁÔËÁ, Á ÁËÓÉÏÍÁ ÏÂÝÅÊ ÓÕÍÍÙ ÓÔÁÎÏ×ÉÔÓÑ ÐÒÏÓÔÏ ÎÅ ÎÕÖÎÁ.ðÒÏÅËÔÉ×ÎÙÅ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ: ÏÐÒÅÄÅÌÅÎÉÑâÕÄÅÍ ÎÁÚÙ×ÁÔØ ÐÒÏÅËÔÉ×ÎÙÍ ÉÎÄÅËÓÏÍ ×ÌÉÑÎÉÑ ÏÔÏÂÒÁÖÅÎÉÅ : SGPn →RPn−1 .åÓÔÅÓÔ×ÅÎÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ : Rn \ {0} → RPn−1 ÓÏÐÏÓÔÁ×ÌÑÅÔ ÎÅÎÕÌÅ×ÏÍÕ×ÅËÔÏÒÕ (x1; : : : ; xn) ÔÏÞËÕ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á (x1 : : : : : xn).
üÔÏ ÏÔÏÂÒÁÖÅÎÉÅ ÚÁÄÁÅÔ ÓÏÏÔ×ÅÔÓÔ×ÉÅ ÍÅÖÄÕ ÏÂÙÞÎÙÍÉ É ÐÒÏÅËÔÉ×ÎÙÍÉ ÉÎÄÅËÓÁÍÉ×ÌÉÑÎÉÑ.ëÁÖÄÏÍÕ ÏÂÙÞÎÏÍÕ ÉÎÄÅËÓÕ ×ÌÉÑÎÉÑ, ÎÅ ÒÁ×ÎÏÍÕ 0, ËÁË ×ÅËÔÏÒ, ÎÁ ÐÒÏÓÔÏÊÉÇÒÅ c ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ ÓÏÐÏÓÔÁ×ÌÑÅÔÓÑ ÐÒÏÅËÔÉ×ÎÙÊ ÐÏ ÆÏÒÍÕÌÅ∗()(v) = ((v)):îÁÚÏ×ÅÍ ÏÐÅÒÁÃÉÀ ∗ ÐÒÏÅËÔÉ×ÉÚÁÃÉÅÊ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ.ðÒÏÅËÔÉ×ÎÙÊ -ÉÎÄÅËÓ ÄÌÑ ÉÇÒ Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ ÏÐÒÅÄÅÌÑÅÔÓÑ, ËÁË ÏÂÒÁÚ-ÉÎÄÅËÓÁ ÐÒÉ ÏÔÏÂÒÁÖÅÎÉÉ ∗P (v) = (1(v) : : : : : n(v))(11)áÎÁÌÏÇÉÞÎÏ, ÐÒÏÅËÔÉ×ÎÙÊ ÁÎÁÌÏÇ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ (P Bz (v)) ÏÐÒÅÄÅÌÑÅÔÓÑ,ËÁË ∗(Bz (v)), Ô.Å. ÜÔÏ ÏÂÙÞÎÙÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ, ÎÏ ×ÅËÔÏÒ ÚÎÁÞÅÎÉÊ ÒÁÓÓÍÁÔÒÉ×ÁÅÔÓÑ ÎÅ ËÁË ÜÌÅÍÅÎÔ Rn, Á ËÁË ÜÌÅÍÅÎÔ RPn−1.
ïÔÍÅÔÉÍ, ÞÔÏ ÎÏÒÍÉÒÏ17×ÁÎÎÙÊ É ÎÅÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ É ÉÎÄÅËÓ ðÅÎÒÏÕÚÁ ÏÔÌÉÞÁÀÔÓÑÔÏÌØËÏ ÕÍÎÏÖÅÎÉÅÍ ÎÁ ËÏÎÓÔÁÎÔÕ, ÐÏÜÔÏÍÕ ∗(T Bz ) = ∗(Bz ) = ∗(P ) = P Bz .÷ÅÄÅÍ ÓÌÅÄÕÀÝÉÅ ÁËÓÉÏÍÙ ÄÌÑ ÐÒÏÅËÔÉ×ÎÙÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ.óÌÁÂÁÑ ÁËÓÉÏÍÁ ÁÎÏÎÉÍÎÏÓÔÉ / Weak Anonimity (WAn). äÌÑ ÌÀÂÏÊÏÌÉÇÁÒÈÉÞÅÓËÏÊ ÉÇÒÙ uS ∈ SGPn, É ∀ i; j ∈ S i(uS ) = j (uS ).ðÒÏÅËÔÉ×ÎÁÑ ÁËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ / ProjeÓtive Transfer Axiom (PT).∀ v ∈ SGPn , ∀ S ∈ M (v )ÔÏÞËÉ (v), (v−S ) É wS ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ.ôÅÏÒÅÍÁ 4. ðÕÓÔØ | ÐÒÏÅËÔÉ×ÎÙÊ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ, ÏÐÒÅÄÅÌÅÎÎÙÊ ÎÁ ÍÎÏÖÅÓÔ×Å ÉÇÒ Ó ÓÉÍÍÅÔÒÉÞÎÙÍÉ ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ÕÓÌÏ×ÉÀÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ. ôÏÇÄÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, WAn ÉPT, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ (v) = (v) .÷ ÒÁÂÏÔÅ ÐÏËÁÚÁÎÏ, ÞÔÏ ÓÏÏÔ×ÅÔÓ×ÕÀÝÉÅ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÉ ÁËÓÉÏÍ (× ÐÅÒ×ÕÀ ÏÞÅÒÅÄØ, PT), ÄÁÀÔ ÎÏ×ÙÅ ÏÐÉÓÁÎÉÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ -ÉÎÄÅËÓÁ É ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ.çÌÁ×Á 3.
ïÃÅÎËÉ É ÁÌÇÏÒÉÔÍÙ ÄÌÑ ÒÁÓÞÅÔÁ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑôÅÏÒÅÍÁ Ï ÓÒÅÄÎÅÍ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑëÁË ÕÖÅ ÏÂÓÕÖÄÁÌÏÓØ, ×ÌÉÑÎÉÅ ÉÇÒÏËÁ × ÇÏÌÏÓÏ×ÁÎÉÉ Ó Ë×ÏÔÏÊ (ÎÅÚÁ×ÉÓÉÍÏ ÏÔ ÔÏÇÏ, ÐÏ ËÁËÏÍÕ ÉÚ ÉÎÄÅËÓÏ× ÏÎÏ ÓÞÉÔÁÌÏÓØ) ÎÅ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ ÞÉÓÌÕÇÏÌÏÓÏ×, ÐÒÉÞÅÍ ×ÌÉÑÎÉÅ ÍÏÖÅÔ ÂÙÔØ ËÁË ÂÏÌØÛÅ, ÔÁË É ÍÅÎØÛÅ ÄÏÌÉ ÞÉÓÌÁÇÏÌÏÓÏ×.äÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÓÔÒÏÇÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÐÒÏÂÌÅÍÁÔÉÞÎÏ. îÏ ÄÌÑ ÎÅ ÎÏÒÍÉÒÏ×ÁÎÎÙÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÓÌÅÄÕÀÝÕÀÔÅÏÒÅÍÕ.ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ vq ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ (q; w1; : : : ; wn), Ô.Å.
ÞÉÓÌÏ ÇÏÌÏÓÏ×ÕÞÁÓÔÎÉËÏ× ÆÉËÓÉÒÏ×ÁÎÏ, q | ÐÁÒÁÍÅÔÒ.ôÅÏÒÅÍÁ 5. 1) äÌÑ |ÉÎÄÅËÓÁ:18Z∞0i(vq ) dq = wi ·XS 3if (i; S ):2) ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, T É SymGL.RôÏÇÄÁ 0∞ i(vq ) dq ÐÒÏÐÏÒÃÉÏÎÁÌÅÎ wi.3) äÌÑ ÉÎÄÅËÓÏ× ðÅÎÒÏÕÚÁ É ûÅÐÌÉ|ûÕÂÉËÁ:Z∞0Pi(vq ) dq =Z∞0SSi(vq ) dq = wi:åÓÌÉ ×ÅÓÁ ÉÇÒÏËÏ× É Ë×ÏÔÁ | ÃÅÌÙÅ ÎÅÏÔÒÉÃÁÔÅÌØÎÙÅ ÞÉÓÌÁ, ÍÏÖÎÏ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÔÅÏÒÅÍÙ 5 ÚÁÍÅÎÉÔØ ÉÎÔÅÇÒÁÌ ÎÁ ÓÕÍÍÕ Ó ÔÅÍÉ ÖÅ ×ÅÒÈÎÉÍ É ÎÉÖÎÉÍÐÒÅÄÅÌÁÍÉ.óÄÅÌÁÅÍ ×Ù×ÏÄÙ.äÌÑ -ÉÎÄÅËÓÁ ×ÌÉÑÎÉÅ "× ÓÒÅÄÎÅÍ ÐÏ Ë×ÏÔÅ" ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ, ×Ï ÐÅÒ×ÙÈ,ÞÉÓÌÕ ÇÏÌÏÓÏ×, ×Ï ×ÔÏÒÙÈ, ÓÕÍÍÅ f (i; S ) ÐÏ ×ÓÅÍ ×ÏÚÍÏÖÎÙÍ ËÏÁÌÉÃÉÑÍ, ËÏÔÏÒÕÀ ÍÏÖÎÏ ÉÎÔÅÒÐÒÅÔÉÒÏ×ÁÔØ, ËÁË ÍÅÒÕ ÖÅÌÁÎÉÑ ÏÓÔÁÌØÎÙÈ ÉÇÒÏËÏ× ×ÈÏÄÉÔØ× ËÏÁÌÉÃÉÀ Ó i.âÕÄÅÍ ÇÏ×ÏÒÉÔØ, ÞÔÏ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÔÅÏÒÅÍÅ Ï ÓÒÅÄÎÅÍ, ÅÓÌÉÄÌÑ ÎÅÇÏ ×ÙÐÏÌÎÑÅÔÓÑ ÐÕÎËÔ 2) ÔÅÏÒÅÍÙ 5.
-ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÔÅÏÒÅÍÅ ÏPÓÒÅÄÎÅÍ, ÅÓÌÉ S 3i f (i; S ) ÎÅ ÚÁ×ÉÓÉÔ ÏÔ i.ìÀÂÏÊ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÊ ÁËÓÉÏÍÁÍ NP, T É SymGL ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ É ÔÅÏÒÅÍÅ Ï ÓÒÅÄÎÅÍ, × ÞÁÓÔÎÏÓÔÉ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ ûÅÐÌÉ|ûÕÂÉËÁ,ðÅÎÒÏÕÚÁ É ÏÂÝÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ.ëÁÖÅÔÓÑ, ÞÔÏ "× ÓÒÅÄÎÅÍ" ÓÐÒÁ×ÅÄÌÉ×ÏÓÔØ ×ÓÅ-ÔÁËÉ ÅÓÔØ É ×ÌÉÑÎÉÅ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ ÞÉÓÌÕ ÇÏÌÏÓÏ×. îÁ ÐÒÁËÔÉËÅ ÜÔÏ ÎÅ ÔÁË. üÔÏ ÏÂÓÔÏÑÔÅÌØÓÔ×Ï ÄÅÔÁÌØÎÏÏÂÓÕÖÄÁÅÔÓÑ × ÒÁÚÄÅÌÅ 3.1.íÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊðÒÏÉÚ×ÏÄÑÝÅÊ ÆÕÎËÃÉÅÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ (ai) ÎÁÚÙ×ÁÅÔÓÑ ÓÕÍÍÁ a0 +19a1x + a2x2 + : : : + aixi + : : : ðÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ ÏÐÒÅÄÅÌÅÎÙ É ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ Ó ÎÅÓËÏÌØËÉÍÉ ÉÎÄÅËÓÁÍÉ.ðÕÓÔØ (q; w1; : : : ; wn) | ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ, bk (i) | ÞÉÓÌÏ ËÏÁÌÉÃÉÊ c ÓÕÍÍÁÒÎÙÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ× k, ÎÅ ×ËÌÀÞÁÀÝÉÍ ÉÇÒÏËÁ i, Á bk;n(i) | ÞÉÓÌÏ ËÏÁÌÉÃÉÊÉÚ n ÉÇÒÏËÏ× c ÓÕÍÍÁÒÎÙÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ× k, ÎÅ ×ËÌÀÞÁÀÝÉÍ ÉÇÒÏËÁ i. ðÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ bk (i) ÒÁ×ÎÁGi(x) =Yj 6=i(1 + xwj );Á ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ bk;n(i)Si(x; y ) =Yj 6=i(1 + yxwj ):ïÂÝÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ ÒÁ×ÅÎ ÓÕÍÍÅ ËÏÜÆÆÉÃÉÅÎÔÏ× Gi(x) ÐÒÉ ÓÔÅÐÅÎÑÈ xÏÔ q − wi ÄÏ q − 1.
éÎÄÅËÓ ûÅÐÌÉ|ûÕÂÉËÁ ÒÁ×ÅÎ ÓÕÍÍÅ ËÏÜÆÆÉÃÉÅÎÔÏ× S (x; y)ÐÒÉ s-Ê ÓÔÅÐÅÎÉ y É ÓÔÅÐÅÎÑÈ x ÏÔ q − wi ÄÏ q − 1-Ê.äÌÑ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÍÅÔÏÄÏÍ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ ÔÒÅÂÕÅÔÓÑ O(q · n), ïÃÅÎËÁ ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ | O(q · n2).áÌÇÏÒÉÔÍÙ ÒÁÓÞÅÔÁ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ× Ó ÐÏÍÏÝØÀ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ"ðÒÑÍÏÊ" ÁÌÇÏÒÉÔÍ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÒÁÂÏÔÁÅÔ ÄÌÑ -ÉÎÄÅËÓÁÓÔÏÌØ ÖÅ ÈÏÒÏÛÏ, ËÁË É ÄÌÑ ËÌÁÓÓÉÞÅÓËÉÈ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ.îÏ "ÐÒÑÍÏÊ" ÁÌÇÏÒÉÔÍ ÎÅ ÐÏÚ×ÏÌÑÅÔ ×ÙÞÉÓÌÑÔØ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ ÚÁ ÒÁÚÕÍÎÏÅ×ÒÅÍÑ ÕÖÅ ÐÒÉ n ∼ 60. ðÏÜÔÏÍÕ ×ÓÔÁÅÔ ×ÏÐÒÏÓ, ËÁË ÐÒÉÍÅÎÉÔØ Ë -ÉÎÄÅËÓÕÍÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ.ðÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÆÕÎËÃÉÉ f (i; S ) ÚÁ×ÉÓÑÔ ÔÏÌØËÏ ÏÔ ÍÁÔÒÉÃÙ ÐÒÅÄÐÏÞÔÅÎÉÊ P .
äÌÑ ÔÏÇÏ, ÞÔÏÂÙ ÐÏÄÞÅÒËÎÕÔØ ÜÔÏÔ ÆÁËÔ, ×ÍÅÓÔÏ f (i; S ) ÂÕÄÅÍ ÐÉÓÁÔØf (i; S; P ).20éÎÄÅËÓÙ ×ÌÉÑÎÉÑ, ÐÏÓÔÒÏÅÎÎÙÅ ÎÁ ÏÓÎÏ×Å ÍÁÔÒÉÃÙ ÐÒÅÄÐÏÞÔÅÎÉÊ P , ×ÙÞÉÓÌÑÀÔÓÑ ÐÏ ÁÎÁÌÏÇÉÞÎÙÍ Ó ÉÎÄÅËÓÁÍÉ âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ ÆÏÒÍÕÌÁÍ.ïÐÒÅÄÅÌÉÍXrk (i) =f (i; S; P );w(S )=krk;l (i) =óÏÏÔ×ÅÔÓÔ×ÅÎÎÏ,r(i) =Xw(S )=k;|S |=l;q −1Xk=q−wirk (i) =áÎÁÌÏÇ ÉÎÄÅËÓÁ âÁÎÃÁÆÁðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄRi(x) =Yj 6=iP(1 + fij xwj ) =j ∈S fij .Xf (i; S; P ):q−1X Xl k=q−wirk;l (i):òÁÓÓÍÏÔÒÉÍ ÍÎÏÇÏÞÌÅÎ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).÷ÙÞÉÓÌÅÎÉÅ (v) (ÉÌÉ N(v)) ÔÒÅÂÕÅÔ O(C (v) · n2) ÏÐÅÒÁÃÉÊ.áÎÁÌÏÇÉÞÎÙÅ ÒÁÓÓÕÖÄÅÎÉÑ ÍÏÖÎÏ ÐÒÏ×ÅÓÔÉ, ÅÓÌÉ f (i; S; P ) ÉÍÅÅÔ ×ÉÄP+j ∈S f0 (|S |)fij . ôÁËÏ×Ù, × ÞÁÓÔÎÏÓÔÉ, ÒÁÓÓÍÏÔÒÅÎÎÙÅ × ÐÒÉÍÅÒÅ 1 f (i; S; P ),f −(i; S; P ) É f (i; S; P ).
óÏÏÔ×ÅÔÓÔ×ÕÀÝÁÑ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÂÕÄÅÔ ÚÁ×ÉÓÅÔØ ÕÖÅ ÏÔ Ä×ÕÈ ÐÅÒÅÍÅÎÎÙÈ, É ÏÂßÅÍ ×ÙÞÉÓÌÅÎÉÊ ÁÎÁÌÏÇÉÞÅÎ ×ÙÞÉÓÌÅÎÉÀÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ. ÷ ÜÔÏÍ ÓÌÕÞÁÅ ×ÙÞÉÓÌÅÎÉÅ (v) (ÉÌÉ N(v)) ÔÒÅÂÕÅÔO(C (v) · n3) ÏÐÅÒÁÃÉÊ.21ïÓÎÏ×ÎÁÑ ÔÅÏÒÅÍÁþÔÏÂÙ ÚÁÐÉÓÁÔØ ÐÏÌÕÞÅÎÎÙÅ ÒÅÚÕÌØÔÁÔÙ ÆÏÒÍÁÌØÎÏ, ××ÅÄÅÍ "ÐÓÅ×ÄÏÞÉÓÌÁ"a, ÔÁË, ÞÔÏa + b = a + b; a − b = a − b; 1 · b = b; a + b = a + b; a − b = a − b; a · b = a + b:÷Ï ××ÅÄÅÎÎÙÈ ÏÂÏÚÎÁÞÅÎÉÑÈ ÒÁÓÓÕÖÄÅÎÉÑ ÜÔÏÇÏ ÐÁÒÁÇÒÁÆÁ ÄÏËÁÚÙ×ÁÀÔ ÓÌÅÄÕÀÝÅÅ ÕÔ×ÅÒÖÄÅÎÉÅ.ôÅÏÒÅÍÁ 6. 1).
ðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄPÇÄÅ fij ÚÁ×ÉÓÑÔ ÔÏÌØËÏÏÔ i, j É P . ôÏÇÄÁ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ rk (i) ÉÍÅÅÔ ×ÉÄRi(x) =PYj 6=ij ∈S fij ,(1 + fij xwj ):2). ðÕÓÔØ f (i; S; P ) ÉÍÅÅÔ ×ÉÄ j ∈S f0(s)fij , ÇÄÅ fij ÚÁ×ÉÓÑÔ ÔÏÌØËÏ ÏÔ i, jÉ P . ôÏÇÄÁ ÐÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ rk;l (i) ÉÍÅÅÔ ×ÉÄRi(x; y ) =*Yj 6=i+(1 + fij yxwj ); (1; f0(1); f0(2); : : : ; f0(n)) :òÁÚÒÁÂÏÔÁÎÎÙÅ ÍÏÄÅÌÉ ÌÅÇÌÉ × ÏÓÎÏ×Õ ËÏÍÐÌÅËÓÁ ÐÒÏÇÒÁÍÍ (ÏÐÉÓÁÎÎÏÇÏ ×ÐÁÒÁÇÒÁÆÅ 3.4.2), ËÏÔÏÒÙÊ ÉÓÐÏÌØÚÏ×ÁÌÓÑ ÄÌÑ ÒÁÓÞÅÔÁ ×ÌÉÑÎÉÑ| × íÅÖÄÕÎÁÒÏÄÎÏÍ ÷ÁÌÀÔÎÏÍ æÏÎÄÅ.| ÒÅÇÉÏÎÏ× × çÏÓÕÄÁÒÓÔ×ÅÎÎÏÊ äÕÍÅ òæ.ðÒÏÇÒÁÍÍÙ ÎÁÐÉÓÁÎÁ ÎÁ ÑÚÙËÅ ó (ÓÕÍÍÁÒÎÏ 300 ÓÔÒÏË).
ïÓÎÏ×ÎÁÑ ÐÒÏÇÒÁÍÍÁ(index.c, ÐÒÉÌÏÖÅÎÉÅ 1) ×ÙÞÉÓÌÑÅÔ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÅ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×, ÐÒÅÄÐÏÌÁÇÁÑ, ÞÔÏ ÉÎÔÅÎÓÉ×ÎÏÓÔÉ ËÏÁÌÉÃÉÊ ×ÙÞÉÓÌÑÀÔÓÑ ÉÓÈÏÄÑ ÉÚ ÍÁÔÒÉÃÙ ÐÒÅÄÐÏÞÔÅÎÉÊ P ÄÌÑ ÆÕÎËÃÉÊ f +(i; S; P ) f −(i; S; P ). ×ÌÉÑÎÉÑÉÇÒÏËÏ× (× ÔÏÍ ÖÅ ÐÏÒÑÄËÅ, ËÁË ÏÎÉ ÕËÁÚÁÎÙ × ÉÓÈÏÄÎÙÈ ÄÁÎÎÙÈ).ðÒÏÇÒÁÍÍÁ (banzhaf.c, ÐÒÉÌÏÖÅÎÉÅ 2) ÎÁÐÉÓÁÎÁ ÎÁ ÑÚÙËÅ ó (70 ÓÔÒÏË) ×ÙÞÉÓÌÑÅÔ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ âÁÎÃÁÆÁ, ÉÓÐÏÌØÚÕÑ ÍÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ.22ðÒÏÇÒÁÍÍÁ memsize.c (ÐÒÉÌÏÖÅÎÉÅ 3) ×ÙÞÉÓÌÑÅÔ ÎÅÏÂÈÏÄÉÍÙÊ ÄÌÑ ÒÁÂÏÔÙÐÒÏÇÒÁÍÍÙ index.c ÏÂßÅÍ ÏÐÅÒÁÔÉ×ÎÏÊ ÐÁÍÑÔÉ.3.
ïÓÎÏ×ÎÙÅ ÒÅÚÕÌØÔÁÔÙ ÄÉÓÓÅÒÔÁÃÉÏÎÎÏÊ ÒÁÂÏÔÙ1) ÷ ÒÁÂÏÔÅ ÐÏÓÔÒÏÅÎÙ ÁËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×| × ÓÌÕÞÁÅ ÐÒÏÓÔÙÈ ÉÇÒ.| × ÓÌÕÞÁÅ ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ.2) ðÒÅÄÌÏÖÅÎ ÐÏÄÈÏÄ Ë ÉÎÄÅËÓÁÍ ×ÌÉÑÎÉÑ, ËÁË Ë ÜÌÅÍÅÎÔÁÍ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á. äÌÑ ÉÇÒ Ó ÓÉÍÍÅÔÒÉÞÎÙÍÉ ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ ÐÒÉ ÕÓÌÏ×ÉÉ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ ÐÏÓÔÒÏÅÎÁ ÁËÓÉÏÍÁÔÉËÁ ÔÁËÉÈ ÉÎÄÅËÓÏ×.3) ðÏÓÔÒÏÅÎ ÁÌÇÏÒÉÔÍ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×, ÉÓÐÏÌØÚÕÀÝÉÊ ÐÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ. óÏÚÄÁÎ ÐÒÏÇÒÁÍÍÎÙÊ ËÏÍÐÌÅËÓ, ÐÏÚ×ÏÌÑÀÝÉÊ ×ÙÞÉÓÌÑÔØ ×ÙÛÅÏÐÉÓÁÎÎÙÅ ÉÎÄÅËÓÙ ÄÌÑ×ÓÅÈ ÂÏÌØÛÉÎÓÔ×Á ÓÕÝÅÓÔ×ÕÀÝÉÈ ÎÁ ÄÁÎÎÙÊ ÍÏÍÅÎÔ ÏÒÇÁÎÏ× ËÏÌÌÅËÔÉ×ÎÏÇÏ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÊ.4) äÌÑ ÉÎÄÅËÓÏ×, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ÁËÓÉÏÍÁÍ ÔÒÁÎÓÆÅÒÁ, ÂÏÌ×ÁÎÁ, ÁÎÏÎÉÍÎÏÓÔÉ É ÐÅÒ×ÏÊ ÞÁÓÔÉ ÁËÓÉÏÍÙ SymGl (Ô.Å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
