Диссертация (1137405), страница 16
Текст из файла (страница 16)
åÓÌÉ ×ÅÓÁ ÉÇÒÏËÏ× É Ë×ÏÔÁ | ÃÅÌÙÅ ÎÅÏÔÒÉÃÁÔÅÌØÎÙÅ ÞÉÓÌÁ,ÍÏÖÎÏ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÔÅÏÒÅÍÙ 1 ÚÁÍÅÎÉÔØ ÉÎÔÅÇÒÁÌ ÎÁ ÓÕÍÍÕ Ó ÔÅÍÉ ÖÅ ×ÅÒÈÎÉÍ É ÎÉÖÎÉÍ ÐÒÅÄÅÌÁÍÉ. òÁÓÓÕÖÄÅÎÉÑ ÐÒÉ ÜÔÏÍ ÎÅ ÉÚÍÅÎÑÔÓÑ ÎÉËÁË. äÏËÁÚÁÔÅÌØÓÔ×Ï ÞÁÓÔÉ ÔÅÏÒÅÍÙ "ÄÌÑ ÓÕÍÍÙ" ÐÒÉ×ÅÄÅÎÏ × [7].óÄÅÌÁÅÍ ×Ù×ÏÄÙ.äÌÑ -ÉÎÄÅËÓÁ ×ÌÉÑÎÉÅ "× ÓÒÅÄÎÅÍ ÐÏ Ë×ÏÔÅ" ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ, ×Ï ÐÅÒ×ÙÈ,ÞÉÓÌÕ ÇÏÌÏÓÏ×, ×Ï ×ÔÏÒÙÈ, ÓÕÍÍÅ f (i; S ) ÐÏ ×ÓÅÍ ×ÏÚÍÏÖÎÙÍ ËÏÁÌÉÃÉÑÍ, ËÏÔÏÒÕÀ ÍÏÖÎÏ ÉÎÔÅÒÐÒÅÔÉÒÏ×ÁÔØ, ËÁË ÍÅÒÕ ÖÅÌÁÎÉÑ ÏÓÔÁÌØÎÙÈ ÉÇÒÏËÏ× ×ÈÏÄÉÔØ× ËÏÁÌÉÃÉÀ Ó i.âÕÄÅÍ ÇÏ×ÏÒÉÔØ, ÞÔÏ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÔÅÏÒÅÍÅ Ï ÓÒÅÄÎÅÍ, ÅÓÌÉÄÌÑ ÎÅÇÏ ×ÙÐÏÌÎÑÅÔÓÑ ÐÕÎËÔ 2) ÔÅÏÒÅÍÙ 1.
-ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÔÅÏÒÅÍÅ ÏÓÒÅÄÎÅÍ, ÅÓÌÉPS 3i f (i; S )ÎÅ ÚÁ×ÉÓÉÔ ÏÔ i.ìÀÂÏÊ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÊ ÁËÓÉÏÍÁÍ NP, T É SymGL ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ É ÔÅÏÒÅÍÅ Ï ÓÒÅÄÎÅÍ, × ÞÁÓÔÎÏÓÔÉ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ ûÅÐÌÉ|ûÕÂÉËÁ,113ðÅÎÒÏÕÚÁ É ÏÂÝÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ.åÓÌÉ ÐÙÔÁÔØÓÑ ÏÂÏÂÝÉÔØ ÔÅÏÒÅÍÕ ÎÁ ÉÎÄÅËÓ âÁÎÃÁÆÁ (ÉÌÉ ÎÁ ÌÀÂÏÊ ÄÒÕÇÏÊÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÉÎÄÅËÓ), ÎÕÖÎÏ ×ÅÒÈÎÉÊ ÐÒÅÄÅÌ ÉÎÔÅÇÒÉÒÏ×ÁÎÉÑ ÚÁÍÅÎÉÔØ ÎÁw(N ), ÐÏÓËÏÌØËÕ ÐÒÉ ÂÏÌØÛÉÈ Ë×ÏÔÁÈ vq = 0 É ÉÎÄÅËÓ âÁÎÃÁÆÁ ÎÅ ÏÐÒÅÄÅÌÅÎ.ëÒÏÍÅ ÔÏÇÏ, ÎÕÖÎÏ ÎÅ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÔÏÞËÕ 0, Ô.Ë.
ÉÎÁÞÅ v = 1. îÏ É × ÜÔÏÍÓÌÕÞÁÅ ÔÅÏÒÅÍÁ ÎÅ×ÅÒÎÁ.ðÒÉÍÅÒ 2. òÁÓÓÍÏÔÒÉÍ ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ (q; 2; 1; 1) É ×ÙÞÉÓÌÉÍ ÄÌÑ ÎÅÇÏÓÒÅÄÎÅÅ ÚÎÁÞÅÎÉÅ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ.1) 0 < q ≤ 1. ÷ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ c ËÌÀÞÅ×ÙÍÉ ÕÞÁÓÔÎÉËÁÍÉ ÂÕÄÕÔA, B É C , ËÁÖÄÙÊ ÉÚ ÕÞÁÓÔÎÉËÏ× ËÌÀÞÅ×ÏÊ × Ó×ÏÅÊ ËÏÁÌÉÃÉÉ. éÎÄÅËÓ âÁÎÃÁÆÁÒÁ×ÅÎ 1/3 ÄÌÑ ×ÓÅÈ ÉÇÒÏËÏ×.2) 1 < q ≤ 2. ÷ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ Ó ËÌÀÞÅ×ÙÍÉ ÕÞÁÓÔÎÉËÁÍÉ ÂÕÄÕÔA, A + B , A + C , B + C , A ÂÕÄÅÔ ËÌÀÞÅ×ÙÍ × ÐÅÒ×ÙÈ ÔÒÅÈ ËÏÁÌÉÃÉÑÈ, B É C |× ÐÏÓÌÅÄÎÅÊ. Bz (A) = 3=5, Bz (B ) = Bz (C ) = 1=5.3) 2 < q ≤ 3. ÷ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ ÂÕÄÕÔ A + B , A + C , A + B + C .
AÂÕÄÅÔ ËÌÀÞÅ×ÙÍ ×Ï ×ÓÅÈ ÔÒÅÈ ËÏÁÌÉÃÉÑÈ, B | × A + B , C | A + C . Bz (A) = 3=5,Bz (B ) = Bz (C ) = 1=5.4) 3 < q ≤ 4. ÷ÙÉÇÒÙ×ÁÀÝÅÊ ÂÕÄÅÔ ÔÏÌØËÏ ËÏÁÌÉÃÉÑ A + B + C , × ËÏÔÏÒÏÊËÌÀÞÅ×ÙÍÉ ÂÕÄÕÔ ×ÓÅ ÔÒÉ ÉÇÒÏËÁ. éÎÄÅËÓ âÁÎÃÁÆÁ ÒÁ×ÅÎ 1/3 ÄÌÑ ×ÓÅÈ ÉÇÒÏËÏ×.éÔÁË, BzA(q) | ÓÔÕÐÅÎÞÁÔÁÑ ÆÕÎËÃÉÑ, ÐÒÉÎÉÍÁÀÝÁÑ ÚÎÁÞÅÎÉÑ 1/3, 3/5, 3/5,1/3 ÎÁ ÏÔÒÅÚËÁÈ ÄÌÉÎÙ 1. ðÏÜÔÏÍÕ ÐÌÏÝÁÄØ ÐÏÄ ÅÅ ÇÒÁÆÉËÏÍ ÒÁ×ÎÁZ 4áÎÁÌÏÇÉÞÎÏ,Z 4001 3 3 1 28BzA(q) dq = + + + = :3 5 5 3 15BzB (q ) dq =Z 401 1 1 1 16Bzó (q) dq = + + + = :3 5 5 3 15114ô.Å. ÓÒÅÄÎÅÅ ÚÎÁÞÅÎÉÅ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÄÌÑ A ÍÅÎØÛÅ ÞÉÓÌÁ ÇÏÌÏÓÏ×, Á ÄÌÑB É C ÂÏÌØÛÅ.ëÁÖÅÔÓÑ, ÞÔÏ ÔÅÏÒÅÍÁ 2 ÇÏ×ÏÒÉÔ, ÞÔÏ "× ÓÒÅÄÎÅÍ" ÓÐÒÁ×ÅÄÌÉ×ÏÓÔØ ×ÓÅ-ÔÁËÉÅÓÔØ É ×ÌÉÑÎÉÅ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ ÞÉÓÌÕ ÇÏÌÏÓÏ×.
îÁ ÐÒÁËÔÉËÅ ÜÔÏ ÎÅ ÔÁË.åÓÌÉ q ≤ mini wi, ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ÂÕÄÕÔ ×ÓÅ ËÏÁÌÉÃÉÉ, ËÒÏÍÅ ∅; ÅÓÌÉ ÖÅ,ÎÁÏÂÏÒÏÔ, w(n) ≥ q > w(n) − mini wi, ×ÙÉÇÒÙ×ÁÀÝÅÊ ÂÕÄÅÔ ÔÏÌØËÏ N . ÷ ÏÂÏÉÈÓÌÕÞÁÑÈ (ÐÏ ÁËÓÉÏÍÅ ÁÎÏÎÉÍÎÏÓÔÉ) ×ÌÉÑÎÉÑ ×ÓÅÈ ÉÇÒÏËÏ× ÂÕÄÕÔ ÒÁ×ÎÙ É "ÓÌÁÂÙÅ" ÕÞÁÓÔÎÉËÉ ÂÕÄÕÔ ÏÂÌÁÄÁÔØ ÏÔÎÏÓÉÔÅÌØÎÏ ÂÏÌØÛÉÍ ×ÌÉÑÎÉÅÍ.
ôÏÔ ÖÅ ÜÆÆÅËÔ ÎÁÂÌÀÄÁÅÔÓÑ, ÅÓÌÉ Ë×ÏÔÁ ÍÁÌÁ (×ÅÌÉËÁ). ôÁËÉÅ ÓÉÔÕÁÃÉÉ ËÒÁÊÎÅ ÒÅÄËÏ,ÎÏ ×ÓÔÒÅÞÁÀÔÓÑ. îÁÐÒÉÍÅÒ, × óÅÊÍÅ òÅÞÉ ðÏÓÐÏÌÉÔÏÊ ÄÏ 1791 Ç. ÄÅÊÓÔ×Ï×ÁÌÏÐÒÁ×Ï "Liberum veto" | ÌÀÂÏÊ ÄÅÐÕÔÁÔ óÅÊÍÁ ÍÏÇ ÐÒÅËÒÁÔÉÔØ ÏÂÓÕÖÄÅÎÉÅ ×ÏÐÒÏÓÁ, Ô.Å. ÒÅÛÅÎÉÅ ÍÏÇÌÏ ÂÙÔØ ÐÒÉÎÑÔÏ ÔÏÌØËÏ ÐÒÉ ÐÏÄÄÅÒÖËÅ ×ÓÅÈ ÄÅÐÕÔÁÔÏ×,ÞÔÏ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÇÏÌÏÓÏ×ÁÎÉÀ Ó Ë×ÏÔÏÊ (n; 1; : : : ; 1).åÓÌÉ ÖÅ Ë×ÏÔÁ ÂÌÉÚËÁ Ë w(N )=2, (Á ÎÁ ÐÒÁËÔÉËÅ × ÂÏÌØÛÉÎÓÔ×Å ÓÌÕÞÁÅ×w(N )=2 < q ≤ (2=3)w(N )), ÔÏ ÐÒÏÉÓÈÏÄÉÔ "ÐÅÒÅËÏÓ" × ÏÂÒÁÔÎÕÀ ÓÔÏÒÏÎÕ.ôÅÐÅÒØ ÕÖÅ "ÓÉÌØÎÙÅ" ÕÞÁÓÔÎÉËÉ ÏÂÌÁÄÁÀÔ ÏÔÎÏÓÉÔÅÌØÎÏ ÂÏÌØÛÉÍ ×ÌÉÑÎÉÅÍ.üÔÏÔ ÜÆÆÅËÔ ÂÙÌ ÏÔÍÅÞÅÎ ×Ï ÍÎÏÇÉÈ ÒÁÂÏÔÁÈ, ÎÁÐÒÉÍÅÒ, [26, 54].2. áÌÇÏÒÉÔÍÙ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑëÁË ÂÕÄÅÔ ÐÏËÁÚÁÎÏ ÎÉÖÅ, ÓÌÏÖÎÏÓÔØ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ËÒÏÍÅÓÁÍÏÇÏ ÉÎÄÅËÓÁ, ÍÏÖÅÔ ÂÙÔØ ÏÃÅÎÅÎÁ ÉÓÈÏÄÑ ÉÚ ÞÉÓÌÁ ÉÇÒÏËÏ× É (ÅÓÌÉ ÒÅÞØÉÄÅÔ Ï ÇÏÌÏÓÏ×ÁÎÉÉ Ó Ë×ÏÔÏÊ) ÓÕÍÍÁÒÎÏÇÏ ÞÉÓÌÁ ÇÏÌÏÓÏ×.
óÌÅÄÕÀÝÉÅ ÐÒÉÍÅÒÙÐÏËÁÚÙ×ÁÀÔ, Ï ËÁËÉÈ ÃÉÆÒÁÈ ÉÄÅÔ ÒÅÞØ.1152.1. "ðÒÑÍÏÅ" ×ÙÞÉÓÌÅÎÉÅ. ïÃÅÎËÁ ÓÌÏÖÎÏÓÔÉóÒÁÚÕ ÏÔÍÅÔÉÍ, ÞÔÏ ÎÏÒÍÉÒÏ×ËÁ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ (Ô.Å ÐÅÒÅÈÏÄ ÏÔ ÎÅÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ Ë ÎÏÒÍÉÒÏ×ÁÎÎÏÍÕ ÉÎÄÅËÓÕ) ÔÒÅÂÕÅÔ O(n) ÏÐÅÒÁÃÉÊ, ÞÔÏ ÍÎÏÇÏ ÍÅÎØÛÅ, ÞÅÍ ÔÒÅÂÕÅÔÓÑ ÎÁ ÏÓÔÁÌØÎÙÅ ×ÙÞÉÓÌÅÎÉÑ. ðÏÜÔÏÍÕ ÄÁÌØÛÅ ÂÕÄÅÔ ÇÏ×ÏÒÉÔØÓÑÔÏÌØËÏ Ï ÎÅÎÏÒÍÉÒÏ×ÁÎÎÙÈ ÉÎÄÅËÓÁÈ.âÅÓÈÉÔÒÏÓÔÎÙÊ (Ô.Å. ÏÓÎÏ×ÁÎÎÙÊ ÎÁ ÏÐÒÅÄÅÌÅÎÉÉ ÉÌÉ ÐÒÅÄÌÏÖÅÎÉÉ 4) ÁÌÇÏÒÉÔÍ ×ÙÞÉÓÌÅÎÉÑ ÌÀÂÏÇÏ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ ÔÒÅÂÕÅÔ ÐÅÒÅÂÏÒÁ ×ÓÅÈ 2n ËÏÁÌÉÃÉÊ,ÐÒÉÞÅÍ ÄÌÑ ËÁÖÄÏÊ ÉÚ ÎÉÈ ÎÕÖÎÏ ÐÒÏ×ÅÒÉÔØ, ËÁËÉÅ ÉÇÒÏËÉ ÂÕÄÕÔ ËÌÀÞÅ×ÙÍÉ,Ô.Å. ÄÁÖÅ ÅÓÌÉ ×ÙÞÉÓÌÅÎÉÅ f (S ) ÔÒÅÂÕÅÔ O(1) ÏÐÅÒÁÃÉÊ1, ÔÏ ×ÙÞÉÓÌÅÎÉÅ ÎÅÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ ÔÒÅÂÕÅÔ O(n · 2n) ([69]) ÏÐÅÒÁÃÉÊ.åÓÌÉ ÞÉÓÌÏ ÉÇÒÏËÏ× ÐÏÒÑÄËÁ 200 (ËÁË × ÐÒÉ×ÅÄÅÎÎÙÈ ×ÙÛÅ ÐÒÉÍÅÒÁÈ), ÞÉÓÌÏÏÐÅÒÁÃÉÊ ÏÃÅÎÉ×ÁÅÔÓÑ, ËÁË 200 · 2200 ∼ 1062, ÞÔÏ ÎÅÐÒÉÅÍÌÅÍÏ ÄÌÑ ÒÅÁÌØÎÙÈ×ÙÞÉÓÌÅÎÉÊ.åÓÌÉ ÐÒÏÓÔÁÑ ÉÇÒÁ ÚÁÄÁÎÁ ÔÁÂÌÉÃÅÊ ÚÎÁÞÅÎÉÊ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÏÊ ÆÕÎËÃÉÉ,ÔÏ ÚÁÄÁÞÁ ÓÏËÒÁÝÅÎÉÑ ×ÒÅÍÅÎÉ ×ÙÞÉÓÌÅÎÉÊ ÎÅ ÁËÔÕÁÌØÎÁ, ÐÏÓËÏÌØËÕ ÓÁÍÁ ÔÁÂÌÉÃÁ ÚÎÁÞÅÎÉÊ ÚÁÎÉÍÁÅÔ O(2n) ÑÞÅÅË ÐÁÍÑÔÉ É O(2n) ÏÐÅÒÁÃÉÊ ÐÏÔÒÅÂÕÅÔÓÑÔÏÌØËÏ ÄÌÑ ÞÔÅÎÉÑ ÔÁÂÌÉÃÙ.
ëÒÏÍÅ ÔÏÇÏ, ÔÁË ÚÁÄÁÀÔÓÑ ÔÏÌØËÏ ÉÇÒÙ Ó ÍÁÌÙÍ(ËÁË ÐÒÁ×ÉÌÏ ÎÅ ÂÏÌÅÅ 10) ÞÉÓÌÏÍ ÉÇÒÏËÏ×, É × ÜÔÏÍ ÓÌÕÞÁÅ ÎÅÔ ÎÕÖÄÙ × ÓÏËÒÁÝÅÎÉÉ ÐÅÒÅÂÏÒÁ.âÏÌØÛÉÎÓÔ×Ï ÐÒÁËÔÉÞÅÓËÉÈ ×ÙÞÉÓÌÅÎÉÊ ÐÒÏÉÚ×ÏÄÉÔÓÑ, ËÏÇÄÁ ÐÒÏÓÔÁÑ ÉÇÒÁÍÏÖÅÔ ÂÙÔØ ÚÁÐÉÓÁÎÁ, ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ. äÁÌÅÅ ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØÔÏÌØËÏ ÜÔÏÔ ÓÌÕÞÁÊ.óÏËÒÁÔÉÔØ ÐÅÒÅÂÏÒ ÍÏÖÎÏ, ÅÓÌÉ ÎÅ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÚÁ×ÅÄÏÍÏ ÎÅ ÐÏÄÈÏÄÑÝÉÅËÏÁÌÉÃÉÉ, Ô.Å.
ËÏÁÌÉÃÉÉ, × ËÏÔÏÒÙÈ ÎÅ ÍÏÖÅÔ ÂÙÔØ ËÌÀÞÅ×ÙÈ ÉÇÒÏËÏ×, Ô.Å. ÐÅÒÅÂÉÒÁÔØ ÔÏÌØËÏ ÔÁËÉÅ ËÏÁÌÉÃÉÉ S , ÞÔÏ q ≤ w(S ) < q + wmax, ÇÄÅ wmax ÞÉÓÌÏ1 þÔÏÎÅ×ÅÒÎÏ ÕÖÅ ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ116ÇÏÌÏÓÏ× "ÓÁÍÏÇÏ ÓÉÌØÎÏÇÏ" ÉÇÒÏËÁ: wmax = max wi. îÏ ×ÏÚÎÉËÁÀÔ Ä×Å ÐÒÏÂÌÅÍÙ.i∈N1) îÅÐÏÎÑÔÎÏ, ËÁË ÜÆÆÅËÔÉ×ÎÏ ×ÙÄÅÌÉÔØ ÔÁËÉÅ ËÏÁÌÉÃÉÉ. ÷ [74] ÐÏËÁÚÁÎÏ,ÞÔÏ ÕÖÅ NP-ÔÒÕÄÎÏÊ ÂÕÄÅÔ ÄÁÖÅ ÐÒÏ×ÅÒËÁ, ÓÕÝÅÓÔ×ÕÅÔ ÌÉ ËÏÁÌÉÃÉÑ Ó ÄÁÎÎÙÍÞÉÓÌÏÍ ÇÏÌÏÓÏ×.2) ÷ ÌÀÂÏÍ ÓÌÕÞÁÅ, ÒÁÄÉËÁÌØÎÏ ÓÏËÒÁÔÉÔØ ÐÅÒÅÂÏÒ ÎÅ ÕÄÁÓÔÓÑ.
äÁÖÅ × ÂÌÉÚËÏÍ Ë "ÉÄÅÁÌØÎÏÍÕ" ÓÌÕÞÁÅ, ËÏÇÄÁ ×ÓÅ ÉÇÒÏËÉ ÉÍÅÀÔ ÐÏ ÏÄÎÏÍÕ ÇÏÌÏÓÕ, Á Ë×ÏÔÁÒÁ×ÎÁ "ÐÏÌÏ×ÉÎÅ ÇÏÌÏÓÏ× ÐÌÀÓ ÏÄÉÎ" (ÐÕÓÔØ ÄÌÑ ÏÐÒÅÄÅÌÅÎÎÏÓÔÉ n ÞÅÔÎÏ), ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ Ó ËÌÀÞÅ×ÙÍÉ ÉÇÒÏËÁÍÉ ÂÕÄÕÔ ×ÓÅ ËÏÁÌÉÃÉÉ ÉÚ n + 1ÉÇÒÏËÏ×, ËÏÔÏÒÙȵ¶n2n√∼n=2 + 1nÛÔÕË.ë ÓÏÖÁÌÅÎÉÀ, ÅÓÌÉ ÓÞÉÔÁÔØ, ÞÔÏ ×ÅÓÁ ÉÇÒÏËÏ× É Ë×ÏÔÁ | ÐÒÏÉÚ×ÏÌØÎÙÅ ÃÅÌÙÅ ÞÉÓÌÁ, ÔÏ ÐÏÌÉÎÏÍÉÁÌØÎÏÇÏ ÁÌÇÏÒÉÔÍÁ, ÐÏÚ×ÏÌÑÀÝÅÇÏ ×ÙÞÉÓÌÑÔØ ÉÎÄÅËÓÙ×ÌÉÑÎÉÑ, ÎÅ ÓÕÝÅÓÔ×ÕÅÔ.
÷ ÅÄÉÎÓÔ×ÅÎÎÏÊ ÉÚ×ÅÓÔÎÏÊ Á×ÔÏÒÕ ÒÁÂÏÔÅ ÎÁ ÜÔÕ ÔÅÍÕ [74] ÐÏËÁÚÁÎÏ, ÞÔÏ ÚÁÄÁÞÉ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁNP-ÐÏÌÎÙÅ ÄÁÖÅ × ÓÌÕÞÁÅ, ÅÓÌÉ Ë×ÏÔÁ ÒÁ×ÎÁ ÐÏÌÏ×ÉÎÅ ÞÉÓÌÁ ÇÏÌÏÓÏ× +1 ÇÏÌÏÓ.åÓÌÉ ÖÅ ×ÅÓÁ ÉÇÒÏËÏ× ÎÅ×ÅÌÉËÉ, ×ÏÚÍÏÖÎÙ ÂÏÌÅÅ ÏÐÔÉÍÉcÔÉÞÎÙÅ ÏÃÅÎËÉ.2.2. íÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊúÁÄÁÞÕ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÍÏÖÎÏ ÒÁÓÓÍÁÔÒÉ×ÁÔØ É ËÁË ËÏÍÂÉÎÁÔÏÒÎÕÀ ÚÁÄÁÞÕ. ðÒÑÍÏÅ ×ÙÞÉÓÌÅÎÉÅ (ËÁË ÐÒÁ×ÉÌÏ ÉÓÐÏÌØÚÕÀÝÅÅ ÂÉÎÏÍÉÎÁÌØÎÙÅËÏÜÆÆÉÃÉÅÎÔÙ) ×ÏÚÍÏÖÎÏ ÔÏÌØËÏ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ É ÔÏÌØËÏ × ÒÅÄËÉÈ ÓÌÕÞÁÑÈ (ÓÍ.
ÐÒÉÍÅÒ 2 ÉÌÉ, ÎÁÐÒÉÍÅÒ, [7]).ìÕÞÛÉÅ ÒÅÚÕÌØÔÁÔÙ ÄÁÅÔ ÉÓÐÏÌØÚÏ×ÁÎÉÅ ÄÒÕÇÏÊ ËÌÁÓÓÉÞÅÓËÏÊ ËÏÍÂÉÎÁÔÏÒÎÏÊ ÔÅÈÎÉËÉ | ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ.117ïÐÒÅÄÅÌÅÎÉÅ 1 ([13]). ðÕÓÔØ (ai) | ÎÅËÏÔÏÒÁÑ (ÎÅ ×ÁÖÎÏ, ËÏÎÅÞÎÁÑ ÉÌÉ ÂÅÓËÏÎÅÞÎÁÑ) ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ. ðÒÏÉÚ×ÏÄÑÝÅÊ ÆÕÎËÃÉÅÊ ÜÔÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉÎÁÚÙ×ÁÅÔÓÑ (ÆÏÒÍÁÌØÎÁÑ) ÓÕÍÍÁ: a0 + a1x + a2x2 + : : : + aixi + : : :ðÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ ÏÐÒÅÄÅÌÅÎÙ É ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ Ó ÎÅÓËÏÌØËÉÍÉ ÉÎÄÅËÓÁÍÉ.
÷ ÜÔÏÍ ÓÌÕÞÁÅ ÐÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ ÚÁ×ÉÓÑÔ ÏÔ ÎÅÓËÏÌØËÉÈÐÅÒÅÍÅÎÎÙÈ. ôÁË, ÐÒÏÉÚ×ÏÄÑÝÅÊ ÆÕÎËÃÉÅÊ ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ (ai;j ) ÂÕÄÅÔPi;jai;j xiyj .ðÒÉÍÅÒ 3. æÕÎËÃÉÑ(x + 1)n=n µ ¶XnxiiÂÕÄÅÔ ÐÒÏÉÚ×ÏÄÑÝÅÊ ÆÕÎËÃÉÅÊ ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÂÉÎÏÍÉÎÁÌØÎÙÈ ËÏÜÆi=0ÆÉÃÉÅÎÔÏ×:µµ ¶ µ ¶µ ¶¶nnn1; n;;;:::;:23n÷ÙÞÉÓÌÑÔØ ÉÎÄÅËÓÙ âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ ÐÏÍÏÇÁÅÔ ÓÌÅÄÕÀÝÁÑ ÌÅÍÍÁ.ðÕÓÔØ (q; w1; : : : ; wn) | ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ, bk (i) | ÞÉÓÌÏ ËÏÁÌÉÃÉÊ c ÓÕÍÍÁÒÎÙÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ× k, ÎÅ ×ËÌÀÞÁÀÝÉÍ ÉÇÒÏËÁ i, Á bk;n(i) | ÞÉÓÌÏ ËÏÁÌÉÃÉÊÉÚ n ÉÇÒÏËÏ× c ÓÕÍÍÁÒÎÙÍ ÞÉÓÌÏÍ ÇÏÌÏÓÏ× k, ÎÅ ×ËÌÀÞÁÀÝÉÍ ÉÇÒÏËÁ i.ìÅÍÍÁ 1.
[68] ðÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ bk (i) ÒÁ×ÎÁGi(x) =Yj 6=i(1 + xwj );Á ÄÌÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ bk;n(i) |Si(x; y ) =Yj 6=i(1 + yxwj ):118ðÏÓËÏÌØËÕ ÉÇÒÏË i ËÌÀÞÅ×ÏÊ × ËÏÁÌÉÃÉÉ S , ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ ËÏÁÌÉÃÉÑ S \{i}ÎÁÂÉÒÁÅÔ ÏÔ q − wi ÄÏ q − 1 ÇÏÌÏÓÏ×, ÔÏ ÞÉÓÌÏ ËÏÁÌÉÃÉÊ, × ËÏÔÏÒÙÈ i ËÌÀÞÅ×ÏÊ,Ô.Å. ÏÂÝÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ ÒÁ×ÅÎq−1Xk=q−wibk (i);ÉÌÉ ÓÕÍÍÅ ËÏÜÆÆÉÃÉÅÎÔÏ× ÐÒÉ ÓÔÅÐÅÎÑÈ x ÏÔ q − wi ÄÏ q − 1 ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÊÐÒÏÉÚ×ÏÄÑÝÅÊ ÆÕÎËÃÉÉ.ðÏÍÅÎÑ× ÐÏÒÑÄÏË ÓÕÍÍÉÒÏ×ÁÎÉÑ, ÉÎÄÅËÓ ûÅÐÌÉ|ûÕÂÉËÁ ÍÏÖÎÏ ÚÁÐÉÓÁÔØËÁËn−1X(s − 1)!(n − s)!(s−1)!(n−s)!=wi;s;SSi =n!n!s=1s=1 S ∈W (v);|S |=sn−1XXiÇÄÅ wi;s | ÞÉÓÌÏ ËÏÁÌÉÃÉÊ ÉÚ s ÉÇÒÏËÏ×, × ËÏÔÏÒÙÈ i ËÌÀÞÅ×ÏÊ.
ó ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ,wi;s =q−1Xk=q−wibk;s(i);Ô.Å. ÒÁ×ÎÏ ÓÕÍÍÅ ËÏÜÆÆÉÃÉÅÎÔÏ× ÐÒÏÉÚ×ÏÄÑÝÅÊ ÆÕÎËÃÉÉ S (x; y) ÐÒÉ s-Ê ÓÔÅÐÅÎÉy É ÓÔÅÐÅÎÑÈ x ÏÔ q − wi ÄÏ q − 1-Ê, ÞÔÏ ÐÏÚ×ÏÌÑÅÔ ×ÙÞÉÓÌÉÔØ ÉÎÄÅËÓ ûÅÐÌÉ|ûÕÂÉËÁ.ðÒÉ ×ÙÞÉÓÌÅÎÉÉ ËÏÜÆÆÉÃÉÅÎÔÏ× ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ Gi ÅÓÔÅÓÔ×ÅÎÎÏ ÐÏÓÌÅ ÒÁÓËÒÙÔÉÑ ÏÞÅÒÅÄÎÙÈ ÓËÏÂÏË ÓÒÁÚÕ ÖÅ ÐÒÉ×ÏÄÉÔØ ÐÏÄÏÂÎÙÅ ÓÌÁÇÁÅÍÙÅ.éÍÅÎÎÏ ÂÌÁÇÏÄÁÒÑ ÜÔÏÍÕ ÏÄÎÏ×ÒÅÍÅÎÎÏ ÏÂÒÁÂÁÔÙ×ÁÀÔÓÑ ÍÎÏÇÉÅ ËÏÁÌÉÃÉÉ ÓÏÄÉÎÁËÏ×ÏÊ ÓÕÍÍÏÊ ÇÏÌÏÓÏ× ÐÒÉ ×ÙÞÉÓÌÅÎÉÉ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ É Ó ÏÄÎÉÍ É ÔÅÍÖÅ ÞÉÓÌÏÍ ÕÞÁÓÔÎÉËÏ× É ÓÕÍÍÏÊ ÇÏÌÏÓÏ× ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ. ïÓÏÂÅÎÎÏ ÔÁËÁÑ ÓÈÅÍÁ ×ÙÞÉÓÌÅÎÉÊ ÜÆÆÅËÔÉ×ÎÁ, ÅÓÌÉ ÍÎÏÇÉÅ ÕÞÁÓÔÎÉËÉ ÇÏÌÏÓÏ×ÁÎÉÑÉÍÅÀÔ ÒÁ×ÎÏÅ ÞÉÓÌÏ ÇÏÌÏÓÏ×.
÷ ÜÔÏÍ ÓÌÕÞÁÅ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÉÍ ÓËÏÂËÉ ÍÏÖÎÏ119ÒÁÓËÒÙ×ÁÔØ Ó ÐÏÍÏÝØÀ ÆÏÒÍÕÌÙ ÂÉÎÏÍÁ îØÀÔÏÎÁ.ðÒÉ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÍ ÐÅÒÅÍÎÏÖÅÎÉÉ ÍÏÖÎÏ ÉÓËÌÀÞÁÔØ ÞÌÅÎÙ, ÓÔÅÐÅÎØ ËÏÔÏÒÙÈ ÐÏ x ÎÅ ÍÅÎØÛÅ Ë×ÏÔÙ, ÐÏÓËÏÌØËÕ × ÄÁÌØÎÅÊÛÅÍ ÜÔÁ ÓÔÅÐÅÎØ ÎÅ ÍÏÖÅÔÕÍÅÎØÛÉÔØÓÑ É ÎÅ ÂÕÄÅÔ ÕÞÔÅÎÁ ÐÒÉ ÐÏÄÓÞÅÔÅ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ.
áÎÁÌÏÇÉÞÎÏ, ÍÏÖÎÏ ÎÅ ÕÞÉÔÙ×ÁÔØ ÞÌÅÎÙ, ÓÔÅÐÅÎØ ËÏÔÏÒÙÈ ÐÒÉ ÄÏÍÎÏÖÅÎÉÉ ÎÅ ÍÏÖÅÔÄÏÓÔÉÇÎÕÔØ q − wi.ðÒÉÍÅÒ 4. ÷ÙÞÉÓÌÉÍ Ó ÐÏÍÏÝØÀ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ ÄÌÑÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ (5;3,2,1,1,1).G1(x) = (1+ x2)(1+ x)3 = (1+ x2)(1+3x +3x2 + x3) = 1+3x +4x2 +4x3 +3x4 + x5:îÁÓ ÉÎÔÅÒÅÓÕÅÔ ÓÕÍÍÁ ËÏÜÆÆÉÃÉÅÎÔÏ× ÐÒÉ ÓÔÅÐÅÎÑÈ ÏÔ 5 − 3 ÄÏ 5 − 1, Ô.Å.T Bz1 = 4 + 4 + 3 = 11. áÎÁÌÏÇÉÞÎÏ,G2(x) = (1 + x3)(1 + x)3 = (1 + x2)(1 + 3x + 3x2 + x3) =1 + 3x + 3x2 + 2x3 + 3x4 + 3x5 + x6:G3(x) = G4(x) = G5(x) = (1 + x3)(1 + x2)(1 + x)2 =(1 + x2 + x3 + : : :)(1 + 2x + x2) = : : : + 3x4 + : : :÷ ÐÏÓÌÅÄÎÅÊ ÆÏÒÍÕÌÅ ÐÏËÁÚÁÎÏ, ÞÔÏ ÐÏÓËÏÌØËÕ ÎÁÓ ÉÎÔÅÒÅÓÕÅÔ ÔÏÌØËÏ ËÏÜÆÆÉÃÉÅÎÔ ÐÒÉ x4, ×ÙÞÉÓÌÅÎÉÑ ÍÏÖÎÏ ÐÒÏ×ÏÄÉÔØ ÎÅ ÐÏÌÎÏÓÔØÀ. éÔÁË.T Bz2 = b3(2) + b4(2) = 5, T Bz3 = T Bz4 = T Bz5 = 3. îÁËÏÎÅÃ, Bz1 = 11=(11 +5 + 3 + 3 + 3) = 11=25 = 0; 44, Bz2 = 5=25 = 0; 2, Bz3 = Bz4 = Bz5 = 3=25 = 0; 12.ëÒÏÍÅ ÔÏÇÏ, ÐÒÏÝÅ ÓÎÁÞÁÌÁ ×ÙÞÉÓÌÉÔØ ÆÕÎËÃÉÉ120G(x) =Yj ∈N(1 + xwj )ÉÌÉ S (x; y) =Yj ∈N(1 + yxwj );(3.4)Á ÐÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ Gi(x) (Si(x; y )) ÐÏÌÕÞÉÔØ ÉÚ Gi(x) (Si(x; y)) Ó ÐÏÍÏÝØÀÄÅÌÅÎÉÑ ÍÎÏÇÏÞÌÅÎÏ×:Gi(x) =Si(x; y ) =G(x)1+xwi ;S (x;y)1+yxwi :(3.5)üÔÏ ÐÏÚ×ÏÌÑÅÔ ÐÅÒÅÍÎÏÖÁÔØ n ÓËÏÂÏË ÎÅ n ÒÁÚ, Á ×ÓÅÇÏ ÏÄÉÎ.äÌÑ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÍÅÔÏÄÏÍ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ ÔÒÅÂÕÅÔÓÑ O(C (v) · n), ÇÄÅ C (v) | ÞÉÓÌÏ ÒÁÚÌÉÞÎÙÈ ÚÎÁÞÅÎÉÊ, ËÏÔÏÒÙÅ ÍÏÖÅÔ ÐÒÉÎÉÍÁÔØ ×ÅÓ ËÏÁÌÉÃÉÉ × ÉÇÒÅ v [34].
ïÃÅÎËÁ ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ ÈÕÖÅ |O(C (v) · n2). ïÔÍÅÔÉÍ, ÞÔÏ C ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ ÓÕÍÍÁÒÎÏÅ ÞÉÓÌÏ ÇÏÌÏÓÏ×. âÏÌÅÅÔÏÇÏ, ÉÓÐÏÌØÚÕÑ ÓÏÏÂÒÁÖÅÎÉÑ ÉÚ ÐÒÅÄÙÄÕÝÅÇÏ ÁÂÚÁÃÁ, ÏÃÅÎËÕ ÍÏÖÎÏ ÕÌÕÞÛÉÔØÄÏ q · n (q · n2).ðÒÉÍÅÒ 5. [95] ðÏÌÉÔÉÞÅÓËÉÅ ÇÒÕÐÐÙ × å×ÒÏÐÅÊÓËÏÍ ÐÁÒÌÁÍÅÎÔÅ É ÎÅÐÒÉÓÏÅÄÉÎÉ×ÛÉÅÓÑ ÄÅÐÕÔÁÔÙ ÏÂÒÁÚÕÀÔ ÉÇÒÕ ÉÚ 36 ÉÇÒÏËÏ×: 7 ÐÁÒÔÉÊ Ó ÇÏÌÏÓÁÍÉ 266,201, 89, 42, 41, 35, 27 É 29 ÎÅÐÒÉÓÏÅÄÉÎÉ×ÛÉÈÓÑ ÄÅÐÕÔÁÔÏ×. éÇÒÁ ÉÍÅÅÔ ×ÉÄ:(367; 266; 201; 89; 42; 41; 35; 27; 1; : : : ; 1). ðÒÏÉÚ×ÏÄÑÝÁÑ ÆÕÎËÃÉÑ ÄÌÑ 1-ÇÏ ÉÇÒÏËÁÓÏÄÅÒÖÉÔ 464 ÎÅÎÕÌÅ×ÙÈ ËÏÜÆÆÉÃÉÅÎÔÁ.
ðÒÉ ÐÏÌÎÏÍ ÐÅÒÅÂÏÒÅ ÐÒÉÄÅÔÓÑ ÒÁÓÓÍÏÔÒÅÔØ 235 ≈ 3; 43 · 1010 ËÏÁÌÉÃÉÊ.îÏ × ÐÌÏÈÏÍ ÓÌÕÞÁÅ (×ÅÓÁ ×ÓÅÈ ËÏÁÌÉÃÉÊ ÒÁÚÌÉÞÎÙ) C (v) = 2n É ÞÉÓÌÏ ÏÐÅÒÁÃÉÊ ÒÏ×ÎÏ ÔÏ ÖÅ, ÞÔÏ É ÐÒÉ "ÐÒÑÍÏÍ" ×ÙÞÉÓÌÅÎÉÉ.ðÒÏÉÚ×ÏÄÑÝÉÅ ÆÕÎËÃÉÉ ÂÙÌÉ ÉÓÐÏÌØÚÏ×ÁÎÙ ÄÌÑ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÊ ÐÒÁËÔÉÞÅÓËÉ ÓÒÁÚÕ ÐÏÓÌÅ ÉÈ (ÉÎÄÅËÓÏ×) ÐÏÑ×ÌÅÎÉÑ. ÷ÐÅÒ×ÙÅ | × [73] ×1962 Ç. ÄÌÑ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ. íÅÔÏÄ ÂÙÌ ÁÄÁÐÔÉÒÏ×ÁÎ ÄÌÑ121×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ × [39] É ÐÒÉÍÅÎÑÌÓÑ, × ÞÁÓÔÎÏÓÔÉ, ÄÌÑ ÏÃÅÎËÉ ×ÌÉÑÎÉÑ × ëÏÌÌÅÇÉÉ ×ÙÂÏÒÝÉËÏ× óûá [64] É ÓÏ×ÅÔÅ ÍÉÎÉÓÔÒÏ× å×ÒÏÓÏÀÚÁ [35, 96].÷ [27, 96] ÍÅÔÏÄ ÐÒÏÉÚ×ÏÄÑÝÉÈ ÆÕÎËÃÉÊ ÂÙÌ ÁÄÁÐÔÉÒÏ×ÁÎ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÕÞÉÔÙ×ÁÀÝÉÈ ÏÇÒÁÎÉÞÅÎÉÑ ÎÁ ÓÏÚÄÁÎÉÅ ËÏÁÌÉÃÉÊ.2.3. ðÒÉÂÌÉÖÅÎÎÙÅ ÍÅÔÏÄÙ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑåÓÌÉ ÞÉÓÌÏ ÉÇÒÏËÏ× (É ÞÉÓÌÏ ÉÈ ÇÏÌÏÓÏ×) ÓÌÉÛËÏÍ ×ÅÌÉËÏ, ÞÔÏÂÙ ÐÒÉÍÅÎÉÔØÐÒÑÍÙÅ ÍÅÔÏÄÙ ×ÙÞÉÓÌÅÎÉÊ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÎÅÏÂÈÏÄÉÍÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÐÒÉÂÌÉÖÅÎÎÙÅ ÍÅÔÏÄÙ.îÁÓËÏÌØËÏ ÉÚ×ÅÓÔÎÏ Á×ÔÏÒÕ, ÐÒÉÂÌÉÖÅÎÎÙÅ ×ÙÞÉÓÌÅÎÉÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑÐÒÏ×ÏÄÉÌÉÓØ ÔÏÌØËÏ ÄÌÑ ÉÎÄÅËÓÏ× âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ, ÉÓÐÏÌØÚÕÑ ÉÈ×ÅÒÏÑÔÎÏÓÔÎÕÀ ÉÎÔÅÒÐÒÅÔÁÃÉÀ.