Диссертация (Индексы влияния, зависящие от предпочтений участников - аксиоматическое построение и методы вычисления), страница 3
Описание файла
Файл "Диссертация" внутри архива находится в папке "Индексы влияния, зависящие от предпочтений участников - аксиоматическое построение и методы вычисления". PDF-файл из архива "Индексы влияния, зависящие от предпочтений участников - аксиоматическое построение и методы вычисления", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве НИУ ВШЭ. Не смотря на прямую связь этого архива с НИУ ВШЭ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
ïÓÎÏ×ÎÁÑ ÔÅÏÒÅÍÁ (ÐÁÒÁÇÒÁÆ 3.3.3) ÐÏÚ×ÏÌÑÅÔ ÚÁÐÉÓÁÔØ ÆÏÒÍÕÌÙ, ÎÁ ËÏÔÏÒÙÈ ÏÓÎÏ×ÁÎÙ ÜÔÉ ÁÌÇÏÒÉÔÍÙ, Ó ÐÏÍÏÝØÀ ××ÅÄÅÎÎÙÈ × ÔÏÍ ÖÅ ÐÁÒÁÇÒÁÆÅ14ÐÓÅ×ÄÏÞÉÓÅÌ.ðÁÒÁÇÒÁÆ 3.4.1 ÐÏÓ×ÑÝÅÎ ÏÓÏÂÅÎÎÏÓÔÑÍ ÓÏ×ÒÅÍÅÎÎÏÇÏ ÐÒÁ×ÉÌÁ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ × óÏ×ÅÔÅ íÉÎÉÓÔÒÏ× å×ÒÏÐÅÊÓËÏÇÏ óÏÀÚÁ. ðÏËÁÚÁÎÏ, ÞÔÏ ÏÄÎÏ ÉÚ ÔÒÅÈÎÅÏÂÈÏÄÉÍÙÈ ÕÓÌÏ×ÉÊ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÓÌÅÄÕÅÔ ÉÚ ÏÓÔÁÌØÎÙÈ Ä×ÕÈ, Á ×ÔÏÒÏÅ ÎÅÓÌÅÄÕÅÔ ÉÚ ÐÅÒ×ÏÇÏ ÔÏÌØËÏ × ÎÅÓËÏÌØËÉÈ ÓÌÕÞÁÑÈ.
äÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÜÔÏ ÐÒÁ×ÉÌÏ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ, ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ, Ô.Å. ÎÅ ÔÏÌØËÏÏÔËÁÚÁÔØÓÑ ÏÔ ÔÒÅÔØÅÇÏ ÕÓÌÏ×ÉÑ, ÎÏ É ÏÔËÁÚÁÔØÓÑ ÏÔ ×ÔÏÒÏÇÏ ÐÕÔÅÍ ÎÅÂÏÌØÛÏÊÍÏÄÉÆÉËÁÃÉÉ ÐÅÒ×ÏÇÏ.÷ ÐÁÒÁÇÒÁÆÅ 3.4.2 ÏÐÉÓÙ×ÁÅÔÓÑ ÓÔÒÕËÔÕÒÁ ËÏÍÐÌÅËÓÁ ÐÒÏÇÒÁÍÍ, ×ÙÞÉÓÌÑÀÝÅÇÏ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÅ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ× ÄÌÑ ÂÏÌØÛÏÇÏÞÉÓÌÁ ÉÇÒÏËÏ×.÷ úÁËÌÀÞÅÎÉÉ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÙ ÒÅÚÕÌØÔÁÔÙ ÒÁÂÏÔÙ.ðÒÉÌÏÖÅÎÉÅ ÓÏÄÅÒÖÉÔ ÔÅËÓÔÙ ÐÒÏÇÒÁÍÍ.15çÌÁ×Á 1.éÎÄÅËÓÙ ×ÌÉÑÎÉÑ: ÏÓÎÏ×ÎÙÅ ÐÏÎÑÔÉÑÉ ÏÂÚÏÒ ÌÉÔÅÒÁÔÕÒÙ1. ðÒÏÓÔÙÅ ÉÇÒÙ É ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ1.1.
ðÒÏÓÔÙÅ ÉÇÒÙãÅÌØ ÄÁÎÎÏÇÏ ÒÁÚÄÅÌÁ | ÆÏÒÍÁÌÉÚÁÃÉÑ ×ÓÔÒÅÞÁÀÝÉÈÓÑ ÎÁ ÐÒÁËÔÉËÅ ÐÒÁ×ÉÌÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ × ×ÙÂÏÒÎÙÈ ÏÒÇÁÎÁÈ (ÐÁÒÌÁÍÅÎÔÁÈ, ÓÏÂÒÁÎÉÑÈ ÁËÃÉÏÎÅÒÏ×,ÓÏ×ÅÔÁÈ ÄÉÒÅËÔÏÒÏ× ËÏÍÐÁÎÉÊ É Ô.Ä.). ðÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÎÁ ÇÏÌÏÓÏ×ÁÎÉÅ ÓÔÁ×ÑÔÓÑ ÔÏÌØËÏ Ä×Å ÁÌØÔÅÒÎÁÔÉ×Ù É ×ÙÂÉÒÁÅÔÓÑ ÒÏ×ÎÏ ÏÄÎÁ ÉÚ ÎÉÈ (ÞÁÝÅ ×ÓÅÇÏ |ÐÒÉÎÉÍÁÅÔÓÑ ÌÉ ÐÒÅÄÌÏÖÅÎÉÅ ÉÌÉ ÎÅÔ). ðÒÉ×ÅÄÅÍ ÎÅÓËÏÌØËÏ ÐÒÉÍÅÒÏ×.ðÒÉÍÅÒ 1. ÷ çÏÓÕÄÁÒÓÔ×ÅÎÎÏÊ äÕÍÅ òÏÓÓÉÊÓËÏÊ æÅÄÅÒÁÃÉÉ 450 ÄÅÐÕÔÁÔÏ×.äÌÑ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÔÒÅÂÕÅÔÓÑ ÂÏÌÅÅ ÐÏÌÏ×ÉÎÙ ×ÓÅÈ ÇÏÌÏÓÏ×, Ô.Å.
ÎÅ ÍÅÎÅÅ226.îÁ ÍÏÍÅÎÔ ÎÁÐÉÓÁÎÉÑ ÔÅËÓÔÁ (ÑÎ×ÁÒØ 2013) ÄÅÐÕÔÁÔÙ ÒÁÚÄÅÌÅÎÙ ÎÁ 4 ÆÒÁËÃÉÉ: "åÄÉÎÁÑ òÏÓÓÉÑ" (237 ÄÅÐÕÔÁÔÏ×), ëðòæ (92), "óÐÒÁ×ÅÄÌÉ×ÁÑ òÏÓÓÉÑ"(64) É ìäðò (55). ðÒÅÄÐÏÌÁÇÁÑ ×ÙÓÏËÕÀ ÄÉÓÃÉÐÌÉÎÕ ÇÏÌÏÓÏ×ÁÎÉÑ ×Ï ÆÒÁËÃÉÑÈ,ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÕÞÁÓÔÎÉËÏ× ÇÏÌÏÓÏ×ÁÎÉÑ ÔÏÌØËÏ 4 É ÏÎÉ ÏÂÌÁÄÁÀÔ 237, 92,1664 É 55 ÇÏÌÏÓÁÍÉ, ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ.ðÒÉÍÅÒ 2 ([18]). ÷ Á×ÓÔÒÁÌÉÊÓËÏÍ ÐÒÁ×ÉÔÅÌØÓÔ×Å ÐÒÉ ÇÏÌÏÓÏ×ÁÎÉÉ ÐÏ ÎÅËÏÔÏÒÙÍ ×ÏÐÒÏÓÁÍ ËÁÖÄÙÊ ÉÚ ÛÅÓÔÉ ÛÔÁÔÏ× ÐÏÌÕÞÁÅÔ ÏÄÉÎ ÇÏÌÏÓ, Á ÆÅÄÅÒÁÌØÎÏÅ ÐÒÁ×ÉÔÅÌØÓÔ×Ï | Ä×Á ÇÏÌÏÓÁ. äÌÑ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÎÅÏÂÈÏÄÉÍÏ ÓÏÂÒÁÔØ5 ÇÏÌÏÓÏ×. åÓÌÉ ÇÏÌÏÓÁ "ÚÁ" É "ÐÒÏÔÉ×" ÄÅÌÑÔÓÑ ÐÏÒÏ×ÎÕ, ÒÅÛÅÎÉÅ ÐÒÉÎÉÍÁÅÔÆÅÄÅÒÁÌØÎÏÅ ÐÒÁ×ÉÔÅÌØÓÔ×Ï.ðÒÉÍÅÒ 3.
÷ Ä×ÕÈÐÁÌÁÔÎÏÍ ÐÁÒÌÁÍÅÎÔÅ ÎÏ×ÙÊ ÚÁËÏÎ ÐÒÉÎÉÍÁÅÔÓÑ, ÅÓÌÉ ÅÇÏÐÏÄÄÅÒÖÉ×ÁÀÔ ÂÏÌÅÅ ÐÏÌÏ×ÉÎÙ (ÉÌÉ 2/3 ÉÌÉ 3/4 × ÚÁ×ÉÓÉÍÏÓÔÉ ÏÔ ÐÒÏÃÅÄÕÒÙ)ÄÅÐÕÔÁÔÏ× ÓÎÁÞÁÌÁ ÎÉÖÎÅÊ, Á ÚÁÔÅÍ ×ÅÒÈÎÅÊ ÐÁÌÁÔÙ.ä×ÕÈÐÁÌÁÔÎÙÅ ÐÁÒÌÁÍÅÎÔÙ ÐÒÅÄÕÓÍÏÔÒÅÎÙ ÚÁËÏÎÏÄÁÔÅÌØÎÙÍÉ ÓÉÓÔÅÍÁÍÉ ÷ÅÌÉËÏÂÒÉÔÁÎÉÉ (É ÂÏÌØÛÉÎÓÔ×Á ÂÙ×ÛÉÈ ÂÒÉÔÁÎÓËÉÈ ËÏÌÏÎÉÊ), òÏÓÓÉÉ, çÅÒÍÁÎÉÉ,æÒÁÎÃÉÉ, íÅËÓÉËÉ, âÒÁÚÉÌÉÉ, áÒÇÅÎÔÉÎÙ, óûá É ÒÑÄÁ ÄÒÕÇÉÈ ÓÔÒÁÎ.æÏÒÍÁÌÉÚÁÃÉÑ ÜÔÉÈ ÐÒÁ×ÉÌ ÐÒÅÄÐÏÌÁÇÁÅÔ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï ÕÞÁÓÔÎÉËÏ× (ÄÁÌÅÅ, ÉÇÒÏËÏ×), ËÏÔÏÒÙÅ ÍÏÇÕÔ ÏÂßÅÄÉÎÑÔØÓÑ × ËÏÁÌÉÃÉÉ(ÐÏÄÍÎÏÖÅÓÔ×Á), É ËÁÖÄÁÑ ËÏÁÌÉÃÉÑ ÍÏÖÅÔ ÓÁÍÏÓÔÏÑÔÅÌØÎÏ ÄÏÂÉÔØÓÑ ÎÅËÏÔÏÒÏÇÏ ×ÙÉÇÒÙÛÁ ÄÌÑ Ó×ÏÉÈ ÉÇÒÏËÏ× É ÜÔÏÔ ×ÙÉÇÒÙÛ ÍÏÖÅÔ ÂÙÔØ ÐÒÏÉÚ×ÏÌØÎÙÍÏÂÒÁÚÏÍ ÐÏÄÅÌÅÎ ÍÅÖÄÕ ÞÌÅÎÁÍÉ ËÏÁÌÉÃÉÉ.þÔÏÂÙ ÓÉÓÔÅÍÁ ÐÏÎÑÔÉÊ ÂÙÌÁ ÂÏÌÅÅ ÌÏÇÉÞÎÏÊ, ÎÁÞÎÅÍ Ó ÂÏÌÅÅ ÏÂÝÅÊ ËÏÎÓÔÒÕËÃÉÉ.éÔÁË, ÐÕÓÔØ N | ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï, ÜÌÅÍÅÎÔÙ ËÏÔÏÒÏÇÏ ÚÁÎÕÍÅÒÏ×ÁÎÙÓ 1 ÄÏ n, Ô.Å.
N = {1; : : : ; n}. üÌÅÍÅÎÔÙ ÍÎÏÖÅÓÔ×Á N ÎÁÚÙ×ÁÀÔÓÑ ÉÇÒÏËÁÍÉ,ÐÏÄÍÎÏÖÅÓÔ×Á N | ËÏÁÌÉÃÉÑÍÉ. ëÏÁÌÉÃÉÀ N ÉÎÏÇÄÁ ÎÁÚÙ×ÁÀÔ ÔÏÔÁÌØÎÏÊ.ïÐÒÅÄÅÌÅÎÉÅ 1. ëÏÏÐÅÒÁÔÉ×ÎÏÊ ÉÇÒÏÊ (Ó ÐÏÂÏÞÎÙÍÉ ÐÌÁÔÅÖÁÍÉ) ÎÁÚÙ×ÁÅÔÓÑÐÁÒÁ (N; v ), ÇÄÅ N | ÍÎÏÖÅÓÔ×Ï, Á v : 2N → R+ | ÆÕÎËÃÉÑ, ÓÏÐÏÓÔÁ×ÌÑÀÝÁÑËÁÖÄÏÍÕ ÐÏÄÍÎÏÖÅÓÔ×Õ S ⊂ N ÎÅÏÔÒÉÃÁÔÅÌØÎÏÅ ÞÉÓÌÏ v(S ), ÐÒÉÞÅÍ v(∅) = 0.17ïÂÏÚÎÁÞÉÍ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ËÏÏÐÅÒÁÔÉ×ÎÙÈ ÉÇÒ Ó n ÉÇÒÏËÁÍÉ ÞÅÒÅÚ CGn.ðÅÒ×ÏÅ ÓÉÓÔÅÍÁÔÉÞÅÓËÏÅ ÉÚÌÏÖÅÎÉÅ ÔÅÏÒÉÉ ÉÇÒ (É, × ÞÁÓÔÎÏÓÔÉ, ËÏÏÐÅÒÁÔÉ×ÎÙÈ ÉÇÒ) ÂÙÌÏ ÄÁÎÏ ä. ÆÏÎ îÅÊÍÁÎÏÍ É ï. íÏÒÇÅÎÛÔÅÒÎÏÍ [14].ïÂÙÞÎÏ ÍÎÏÖÅÓÔ×Ï ÉÇÒÏËÏ× ÆÉËÓÉÒÏ×ÁÎÏ, ÐÏÜÔÏÍÕ ÉÇÒÁ (N; v) ÏÂÏÚÎÁÞÁÅÔÓÑÐÒÏÓÔÏ v.÷ÅÌÉÞÉÎÁ v(S ) ÎÁÚÙ×ÁÅÔÓÑ ×ÙÉÇÒÙÛÅÍ ËÏÁÌÉÃÉÉ S É ÉÎÔÅÒÐÒÅÔÉÒÕÅÔÓÑ, ËÁË×ÙÉÇÒÙÛ, ËÏÔÏÒÙÊ ÍÏÇÕÔ ÐÏÌÕÞÉÔØ ÞÌÅÎÙ S , ÄÅÊÓÔ×ÕÑ ÓÏÇÌÁÓÏ×ÁÎÏ.éÇÒÕ v ÎÁÚÙ×ÁÀÔ ÓÕÐÅÒÁÄÄÉÔÉ×ÎÏÊ, ÅÓÌÉ ÄÌÑ ÌÀÂÙÈ Ä×ÕÈ ÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑËÏÁÌÉÃÉÊ S É T ÉÍÅÅÔ ÍÅÓÔÏ v(S ∪ T ) ≥ v(S ) + v(T ), ÔÏ ÅÓÔØ ÌÀÂÁÑ ËÏÁÌÉÃÉÑÍÏÖÅÔ ÄÏÂÉÔØÓÑ ÎÅ ÍÅÎØÛÅÇÏ, ÞÅÍ ÌÀÂÙÅ ÅÅ Ä×Å ÞÁÓÔÉ.éÇÒÏË i ÎÁÚÙ×ÁÅÔÓÑ ÂÏÌ×ÁÎÏÍ × ÉÇÒÅ v, ÅÓÌÉ v(S ∪ {i}) = v(S ) ÄÌÑ ÌÀÂÏÊËÏÁÌÉÃÉÉ S , Ô.Å.
ÐÒÉÓÏÅÄÉÎÅÎÉÅ ÉÇÒÏËÁ i ÎÉÞÅÇÏ ÎÅ ÄÁÅÔ ÎÉ ÏÄÎÏÊ ËÏÁÌÉÃÉÉ.ðÒÉÍÅÒ 4 (éÇÒÁ ÐÒÏÉÚ×ÏÄÓÔ×Á.). ðÕÓÔØ ËÁÖÄÙÊ ÉÚ ÉÇÒÏËÏ× (i) ÏÂÌÁÄÁÅÔ xiÅÄÉÎÉÃÁÍÉ ÎÅËÏÔoÒÏÇÏ ÒÅÓÕÒÓÁ. ëÏÁÌÉÃÉÑ S ÍÏÖÅÔ ×ÌÏÖÉÔØ ×ÅÓØ ÓÕÍÍÁÒÎÙÊÒÅÓÕÒÓ × ÐÒÏÉÚ×ÏÄÓÔ×Ï É ÐÏÌÕÞÉÔØ ÐÒÉÂÙÌØ, ÚÁ×ÉÓÑÝÕÀ ÔÏÌØËÏ ÏÔ ËÏÌÉÞÅÓÔ×ÁÒÅÓÕÒÓÁ: v(S ) = p¡P¢i∈S xi , ÇÄÅ p(·) | ÎÅËÏÔÏÒÁÑ ÆÕÎËÃÉÑ, ÐÒÉÞÅÍ p(0) = 0.åÓÌÉ ÆÕÎËÃÉÑ p ×ÙÐÕËÌÁ, ÔÏ ÏÐÒÅÄÅÌÅÎÎÁÑ ÔÁËÉÍ ÓÐÏÓÏÂÏÍ ÉÇÒÁ ÂÕÄÅÔ ÓÕÐÅÒÁÄÄÉÔÉ×ÎÏÊ.ðÒÉÎÑÔÉÅ ÒÅÛÅÎÉÊ × ×ÙÂÏÒÎÙÈ ÏÒÇÁÎÁÈ ÔÁËÖÅ ÍÏÖÎÏ ÒÁÓÓÍÁÔÒÉ×ÁÔØ, ËÁËËÏÏÐÅÒÁÔÉ×ÎÕÀ ÉÇÒÕ.
ëÏÁÌÉÃÉÑ ÌÉÂÏ ÎÁÂÉÒÁÅÔ ÎÅÏÂÈÏÄÉÍÏÅ ÄÌÑ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ ÞÉÓÌÏ ÇÏÌÏÓÏ× (ÔÏÇÄÁ ÅÓÔÅÓÔ×ÅÎÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÅÅ ×ÙÉÇÒÙÛ ÒÁ×ÅÎ 1)ÉÌÉ ÎÅ ÎÁÂÉÒÁÅÔ (ÔÏÇÄÁ ÅÅ ×ÙÉÇÒÙÛ ÒÁ×ÅÎ 0). éÇÒÙ ÔÁËÏÇÏ ÔÉÐÁ ÎÁÚÙ×ÁÀÔÓÑÐÒÏÓÔÙÍÉ. æÏÒÍÁÌØÎÏ:ïÐÒÅÄÅÌÅÎÉÅ 2. âÕÄÅÍ ÎÁÚÙ×ÁÔØ ÐÒÏÓÔÏÊ ÉÇÒÏÊ ÐÁÒÕ (N; v), ÇÄÅ N | ÍÎÏÖÅÓÔ×Ï, Á v : 2N → {0; 1} | ÆÕÎËÃÉÑ, ÓÏÐÏÓÔÁ×ÌÑÀÝÁÑ ËÁÖÄÏÍÕ ÐÏÄÍÎÏÖÅÓÔ×Õ18N ÌÉÂÏ 0, ÌÉÂÏ 1, ÐÒÉÞÅÍ ×ÙÐÏÌÎÑÅÔÓÑ Ó×ÏÊÓÔ×Ï ÍÏÎÏÔÏÎÎÏÓÔÉ: ÅÓÌÉ S É T |ÐÏÄÍÎÏÖÅÓÔ×Á N É S ⊂ T , ÔÏ v(S ) ≤ v(T ).÷ÐÅÒ×ÙÅ ÐÏÎÑÔÉÅ ÐÒÏÓÔÏÊ ÉÇÒÙ ÐÏÑ×ÌÑÅÔÓÑ ÔÁËÖÅ × [14], ÈÏÔÑ Á×ÔÏÒÙ ÉÍÅÌÉ× ×ÉÄÕ ÎÅ ÓÏ×ÓÅÍ ÔÏ, ÞÔÏ ÐÏÎÉÍÁÅÔÓÑ ÐÏÄ ÐÒÏÓÔÙÍÉ ÉÇÒÁÍÉ × ÎÁÓÔÏÑÝÅÅ ×ÒÅÍÑ.õÓÌÏ×ÉÅ ÍÏÎÏÔÏÎÎÏÓÔÉ | ÜÔÏ ÐÒÏÓÔÏ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁ ÕÓÌÏ×ÉÑ ÓÕÐÅÒÁÄÄÉÔÉ×ÎÏÓÔÉ ÄÌÑ ÓÌÕÞÁÑ ÐÒÏÓÔÙÈ ÉÇÒ.
îÏ, ÅÓÌÉ ÄÌÑ ËÏÏÐÅÒÁÔÉ×ÎÙÈ ÉÇÒ ÕÓÌÏ×ÉÅÓÕÐÅÒÁÄÄÉÔÉ×ÎÏÓÔÉ | ÔÏÌØËÏ Ó×ÏÊÓÔ×Ï, ÔÏ ÄÌÑ ÐÒÏÓÔÙÈ ÉÇÒ ÕÓÌÏ×ÉÅ ÍÏÎÏÔÏÎÎÏÓÔÉ | ÞÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ.þÉÓÌÏ ÉÇÒÏËÏ× × ËÏÁÌÉÃÉÉ S ÏÂÏÚÎÁÞÁÅÔÓÑ ÞÅÒÅÚ s, Á ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÐÒÏÓÔÙÈÉÇÒ n ÉÇÒÏËÏ× | ÞÅÒÅÚ SGn.ïÐÒÅÄÅÌÅÎÉÑ ÄÁÎÙ × ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó [92]. âÏÌÅÅ ÔÒÁÄÉÃÉÏÎÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅÐÒÏÓÔÏÊ ÉÇÒÙ ÐÒÅÄÐÏÌÁÇÁÅÔ ÔÁËÖÅ, ÞÔÏ v(∅) = 0, v(N ) = 1. üÔÏ ÕÓÌÏ×ÉÅ ÉÓËÌÀÞÁÅÔ ÔÏÌØËÏ Ä×Å ÔÒÉ×ÉÁÌØÎÙÅ ÉÇÒÙ.õÔ×ÅÒÖÄÅÎÉÅ 1. ðÕÓÔØ v | ÐÒÏÓÔÁÑ ÉÇÒÁ.
ôÏÇÄÁ1) ÅÓÌÉ v(∅) 6= 0, ÔÏ v(S ) = 1 ÄÌÑ ×ÓÅÈ S ⊆ N ;2) ÅÓÌÉ v(N ) 6= 1, ÔÏ v(S ) = 0 ÄÌÑ ×ÓÅÈ S ⊆ N .äÏËÁÚÁÔÅÌØÓÔ×Ï. 1) åÓÌÉ v(∅) 6= 0, ÔÏ v(∅) = 1 É, ÐÏ Ó×ÏÊÓÔ×Õ ÍÏÎÏÔÏÎÎÏÓÔÉ, ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S v (S ) ≥ v(∅) = 1. á ÐÏÓËÏÌØËÕ v(S ) ÒÁ×ÎÏ ÌÉÂÏ 0ÌÉÂÏ 1, ÔÏ v(S ) = 1.÷ÔÏÒÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÏËÁÚÙ×ÁÅÔÓÑ ÁÎÁÌÏÇÉÞÎÏ. ¥âÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ ÜÔÉ ÉÇÒÙ 0 É 1 ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ1. éÎÏÇÄÁ ÕÄÏÂÎÏ ÎÅ ×ËÌÀÞÁÔØ0 É 1 ×Ï ÍÎÏÖÅÓÔ×Ï ÐÒÏÓÔÙÈ ÉÇÒ, Ï ÞÅÍ ËÁÖÄÙÊ ÒÁÚ ÕÐÏÍÉÎÁÅÔÓÑ ÏÔÄÅÌØÎÏ.ëÏÁÌÉÃÉÑ S ÎÁÚÙ×ÁÅÔÓÑ ×ÙÉÇÒÙ×ÁÀÝÅÊ, ÅÓÌÉ v(S ) = 1, É ÐÒÏÉÇÒÙ×ÁÀÝÅÊ,ÅÓÌÉ v(S ) = 0.1 üÔÏËÏÒÒÅËÔÎÏ, ÐÏÓËÏÌØËÕ × ÄÁÎÎÏÍ ÓÌÕÞÁÅ v = 0(1), ËÁË ÆÕÎËÃÉÑ.19þÁÓÔÏ × ÏÐÒÅÄÅÌÅÎÉÅ ÐÒÏÓÔÏÊ ÉÇÒÙ ÄÏÂÁ×ÌÑÅÔÓÑ ÔÒÅÂÏ×ÁÎÉÅ, ÉÚ×ÅÓÔÎÏÅ, ËÁËÕÓÌÏ×ÉÅ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÉÓÈÏÄÁ ÇÏÌÏÓÏ×ÁÎÉÑ.ëÁÖÄÁÑ ÐÒÏÓÔÁÑ ÉÇÒÁ ÚÁÄÁÅÔ ÓÈÅÍÕ ÇÏÌÏÓÏ×ÁÎÉÑ | ÉÇÒÏËÉ ÇÏÌÏÓÕÀÔ ÚÁ ÏÄÎÕÉÚ Ä×ÕÈ ÁÌØÔÅÒÎÁÔÉ× É ×ÙÂÉÒÁÅÔÓÑ ÔÁ, ÚÁ ËÏÔÏÒÕÀ ÐÒÏÇÏÌÏÓÕÅÔ ×ÙÉÇÒÙ×ÁÀÝÁÑËÏÁÌÉÃÉÑ.
åÓÌÉ ÎÉ ÏÄÎÁ ÉÚ ÁÌØÔÅÒÎÁÔÉ× ÎÅ ÓÏÂÅÒÅÔ ×ÙÉÇÒÙ×ÁÀÝÕÀ ËÏÁÌÉÃÉÀ,ÒÅÛÅÎÉÅ ÎÅ ÐÒÉÎÉÍÁÅÔÓÑ. îÏ ×ÙÂÒÁÎÁ ÍÏÖÅÔ ÂÙÔØ ÔÏÌØËÏ ÏÄÎÁ ÉÚ ÁÌØÔÅÒÎÁÔÉ×,ÐÏÜÔÏÍÕ ËÏÁÌÉÃÉÑ É ÄÏÐÏÌÎÅÎÉÅ Ë ÎÅÊ ÎÅ ÍÏÇÕÔ ÂÙÔØ ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ÏÄÎÏ×ÒÅÍÅÎÎÏ. úÁÐÉÛÅÍ ÜÔÏ ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏ.ïÐÒÅÄÅÌÅÎÉÅ 3. ðÒÏÓÔÁÑ ÉÇÒÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÕÓÌÏ×ÉÀ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ, ÅÓÌÉ ÄÌÑ ÌÀÂÏÊ ×ÙÉÇÒÙ×ÁÀÝÅÊ ËÏÁÌÉÃÉÉ S ËÏÁÌÉÃÉÑ N \ S ÐÒÏÉÇÒÙ×ÁÀÝÁÑ.÷ ÄÉÓÓÅÒÔÁÃÉÉ (ËÒÏÍÅ ÏÄÎÏÇÏ ÏÔÄÅÌØÎÏ ÏÇÏ×ÏÒÅÎÎÏÇÏ ÍÅÓÔÁ) ÎÅ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÐÒÏÓÔÙÅ ÉÇÒÙ ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÕÓÌÏ×ÉÀ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ.úÁÍÅÞÁÎÉÅ 1.
åÓÌÉ ÉÇÒÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÕÓÌÏ×ÉÀ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ,ÔÏ ÌÀÂÙÅ Ä×Å ×ÙÉÇÒÙ×ÁÀÝÉÅ ËÏÁÌÉÃÉÉ ÐÅÒÅÓÅËÁÀÔÓÑ. äÅÊÓÔ×ÉÔÅÌØÎÏ, ÐÕÓÔØÜÔÏ ÎÅ ÔÁË É ×ÙÉÇÒÙ×ÁÀÝÉÅ ËÏÁÌÉÃÉÉ S É T ÔÁËÏ×Ù, ÞÔÏ S ∩ T = ∅. ôÏÇÄÁ T ⊆N \ S É, ÐÏ ÍÏÎÏÔÏÎÎÏÓÔÉ ËÏÁÌÉÃÉÑ N \ S ÔÁËÖÅ ×ÙÉÇÒÙ×ÁÀÝÁÑ. ðÒÏÔÉ×ÏÒÅÞÉÅ.îÁÚÏ×ÅÍ ÏÂßÅÄÉÎÅÎÉÅÍ (ÐÅÒÅÓÅÞÅÎÉÅÍ) ÐÒÏÓÔÙÈ ÉÇÒ v É w ÉÇÒÕ v ∨ w (v ∧ w),ÍÎÏÖÅÓÔ×ÏÍ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ × ËÏÔÏÒÏÊ ÂÕÄÅÔ ÏÂßÅÄÉÎÅÎÉÅ (ÐÅÒÅÓÅÞÅÎÉÅ) ÍÎÏÖÅÓÔ× ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ ÄÌÑ v É w, Ô.Å. ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉS(v ∨ w)(S ) = max(v (S ); w(S ));(v ∧ w)(S ) = min(v (S ); w(S )):áÎÁÌÏÇÉÞÎÏ ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ ÏÂßÅÄÉÎÅÎÉÅ É ÐÅÒÅÓÅÞÅÎÉÅ ËÏÏÐÅÒÁÔÉ×ÎÙÈÉÇÒ, ÎÏ ÄÌÑ ÎÉÈ ÜÔÏ ÎÅ ÂÕÄÅÔ ÉÍÅÔØ ÏÓÏÂÏÇÏ ÓÍÙÓÌÁ.20éÇÒÏË i ÎÁÚÙ×ÁÅÔÓÑ ËÌÀÞÅ×ÙÍ × ËÏÁÌÉÃÉÉ S , ÅÓÌÉ S ×ÙÉÇÒÙ×ÁÀÝÁÑ, Á S \ {i}| ÐÒÏÉÇÒÙ×ÁÀÝÁÑ (ÄÌÑ ÜÔÏÇÏ, ÏÞÅ×ÉÄÎÏ, ÎÅÏÂÈÏÄÉÍÏ, ÞÔÏÂÙ i ∈ S ).éÇÒÏË i ÎÁÚÙ×ÁÅÔÓÑ ÂÏÌ×ÁÎÏÍ, ÅÓÌÉ ÏÎ ÎÅ ËÌÀÞÅ×ÏÊ ÎÉ × ÏÄÎÏÊ ËÏÁÌÉÃÉÉ,Ô.Å.
ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S v(S \ {i}) = v(S ). îÁÚ×ÁÎÉÅ ÄÁÎÏ × [88] ÐÏ ÁÎÁÌÏÇÉÉ ÓÂÒÉÄÖÅÍ | É ÔÁÍ É ÚÄÅÓØ ÂÏÌ×ÁÎ | ÉÇÒÏË, ÎÅ ÉÍÅÀÝÉÊ ×ÏÚÍÏÖÎÏÓÔÉ ×ÌÉÑÔØ ÎÁÓÏÂÙÔÉÑ. íÎÏÖÅÓÔ×Ï ×ÓÅÈ ËÏÁÌÉÃÉÊ, × ËÏÔÏÒÙÈ ÉÇÒÏË i ËÌÀÞÅ×ÏÊ, ÏÂÏÚÎÁÞÁÅÔÓÑWi(v).ðÕÓÔØ i | ÂÏÌ×ÁÎ × ÉÇÒÅ v. ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ v−i ÉÇÒÕ ÓÏ ÍÎÏÖÅÓÔ×ÏÍ ÉÇÒÏËÏ×N \ {i}, ÔÁËÕÀ, ÞÔÏ v−i(S ) = v(S ) (= v(S ∪ {i}).