1. Введение (1107640), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

ðÕÓÔØ ÄÁÎÏ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×ÏA = {a1 ; a2 ; : : : ; aM };4ÓÏÓÔÏÑÝÅÅ ÉÚ M ÜÌÅÍÅÎÔÏ× (ÆÁËÔÏÒÏ× ), Ó ÎÅËÏÔÏÒÙÍ ÆÉËÓÉÒÏ×ÁÎÎÙÍ, ÎÏ ÎÅÉÚ×ÅÓÔÎÙÍÐÏÄÍÎÏÖÅÓÔ×ÏÍ S = {ai1 ; ai2 ; : : : ; aim }; 1 ≤ i1 < i2 < : : : < im ≤ M , ËÏÔÏÒÏÅ ÎÁÄÏ ÎÁÊÔÉ .üÌÅÍÅÎÔÙ ÐÏÄÍÎÏÖÅÓÔ×Á S ÎÁÚÙ×ÁÀÔÓÑ ÄÅÆÅËÔÎÙÍÉ ÜÌÅÍÅÎÔÁÍÉ (ÉÌÉ ÚÎÁÞÉÍÙÍÉ ÆÁËÔÏÒÁÍÉ). ïÂÙÞÎÏ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÎÅÉÚ×ÅÓÔÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï ÚÎÁÞÉÍÙÈ ÆÁËÔÏÒÏ×ÐÒÉÎÁÄÌÅÖÉÔ ÎÅËÏÔÏÒÏÍÕ ÉÚ×ÅÓÔÎÏÍÕ ËÌÁÓÓÕ ÄÏÐÕÓÔÉÍÙÈ ÐÏÄÍÎÏÖÅÓÔ×.äÌÑ ÐÏÉÓËÁ S ⊆ A ÒÁÚÒÅÛÁÅÔÓÑ ÐÒÏ×ÅÓÔÉ ÓÅÒÉÀ ÉÚ N ÜËÓÐÅÒÉÍÅÎÔÏ× (ÇÒÕÐÐÏ×ÙÈ ÐÒÏ×ÅÒÏË ), × ËÁÖÄÏÍ ÉÚ ËÏÔÏÒÙÈ ÍÏÖÎÏ ×ÙÂÒÁÔØ ÎÅËÏÔÏÒÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï (ÇÒÕÐÐÕ) T ⊆ A É×ÙÑÓÎÉÔØ: ÓÏÄÅÒÖÉÔ ÉÌÉ ÎÅÔ ÔÅÓÔÉÒÕÅÍÁÑ ÇÒÕÐÐÁ T ÈÏÔÑ ÂÙ ÏÄÉÎ ÄÅÆÅËÔÎÙÊ ÜÌÅÍÅÎÔ.ïÂÏÚÎÁÞÁÑ ÓÉÍ×ÏÌÏÍ ∅ ÐÕÓÔÏÅ ÍÎÏÖÅÓÔ×Ï, ÍÏÖÎÏ ÎÁÐÉÓÁÔØ, ÞÔÏ Ä×ÏÉÞÎÙÊ ÒÅÚÕÌØÔÁÔ ÐÒÏ×ÅÒËÉ y ∈ {0; 1} ×ÙÞÉÓÌÑÅÔÓÑ ÐÏ ÓÌÅÄÕÀÝÅÍÕ ÐÒÁ×ÉÌÕ:½y=T1; ÅÓÌÉ S T T 6= ∅;0; ÅÓÌÉ S T = ∅:äÁÎÎÕÀ ÍÏÄÅÌØ ×ÙÞÉÓÌÅÎÉÑ ÒÅÚÕÌØÔÁÔÁ ÐÒÏ×ÅÒËÉ ÐÒÉ ÇÒÕÐÐÏ×ÏÍ ÔÅÓÔÉÒÏ×ÁÎÉÉ ÅÓÔÅÓÔ×ÅÎÎÏ ÎÁÚ×ÁÔØ ÂÕÌÅ×ÏÊ ÍÏÄÅÌØÀ.

îÁ ×ÙÂÏÒ ÐÏÄÍÎÏÖÅÓÔ×Á Tn ; n = 1; N; ËÏÔÏÒÏÅ ÐÒÏ×ÅÒÑÅÔÓÑ × n-ÏÍ ÜËÓÐÅÒÉÍÅÎÔÅ, ×ÏÚÍÏÖÎÙ ÎÅËÏÔÏÒÙÅ ÏÇÒÁÎÉÞÅÎÉÑ. üÔÏÔ ×ÙÂÏÒ ÍÏÖÅÔ ÚÁ×ÉÓÅÔØ ÔÁËÖÅ ÏÔ ÒÅÚÕÌØÔÁÔÏ× y1 ; y2 ; : : : ; yn−1 ÐÒÅÄÙÄÕÝÉÈ ÇÒÕÐÐÏ×ÙÈ ÐÒÏ×ÅÒÏË. îÁ ÏÓÎÏ×ÁÎÉÉÉÔÏÇÁ ÐÒÏ×ÅÒÏË y = (y1 ; y2 ; : : : ; yN ); ÇÄŽyn ,T1; ÅÓÌÉ S T Tn 6= ∅;0; ÅÓÌÉ S Tn = ∅;ÜËÓÐÅÒÉÍÅÎÔÁÔÏÒ ÄÏÌÖÅÎ ÏÄÎÏÚÎÁÞÎÏ ×ÏÓÓÔÁÎÏ×ÉÔØ (ÎÁÊÔÉ) ÎÅÉÚ×ÅÓÔÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×ÏÚÎÁÞÉÍÙÈ ÆÁËÔÏÒÏ× S .ðÒÉÍÅÒÁÍÉ ÒÅÁÌØÎÙÈ ÐÒÏÃÅÄÕÒ ÐÏÉÓËÁ, Ó×ÏÄÑÝÉÈÓÑ Ë ÏÐÉÓÁÎÎÏÊ ÍÏÄÅÌÉ, Ñ×ÌÑÅÔÓÑ ÐÏÉÓËÄÅÆÅËÔÎÙÈ ÐÒÉÂÏÒÏ×, ÐÏÉÓË ÜÆÆÅËÔÉ×ÎÙÈ ÌÅËÁÒÓÔ× (ÑÄÏ×), ÐÏÉÓË ÏÛÉÂÏË × ÐÒÏÇÒÁÍÍÅ ÄÌÑü÷í, ÐÏÉÓË ÎÕÖÎÙÈ ËÁÒÔÏÞÅË × ËÁÔÁÌÏÇÅ ÂÉÂÌÉÏÔÅËÉ, ÒÁÄÉÏÌÏËÁÃÉÏÎÎÙÊ ÐÏÉÓË É Ô.Ð.÷ÓÅ ÓÔÒÁÔÅÇÉÉ (ÐÌÁÎÙ ) ÐÏÉÓËÁ ÅÓÔÅÓÔ×ÅÎÎÏ ËÌÁÓÓÉÆÉÃÉÒÏ×ÁÔØ ÎÁ ÓÔÁÔÉÞÅÓËÉÅ, Ô.Å.ÔÁËÉÅ ÓÔÒÁÔÅÇÉÉ, ÄÌÑ ËÏÔÏÒÙÈ ×ÙÂÏÒ n-ÏÊ ÐÒÏ×ÅÒËÉ Tn ; n = 1; 2; : : : ; N; ÎÅ ÚÁ×ÉÓÉÔ ÏÔÒÅÚÕÌØÔÁÔÏ× y1 ; y2 ; : : : ; yn−1 ÐÒÅÄÙÄÕÝÉÈ n − 1 ÐÒÏ×ÅÒÏË, É ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÅ, ËÏÇÄÁ ÔÁËÁÑ ÚÁ×ÉÓÉÍÏÓÔØ ÄÏÐÕÓËÁÅÔÓÑ.

÷ÁÖÎÙÊ ÐÒÉÍÅÒ ××ÅÄÅÎÎÙÈ á.òÅÎØÉ ÓÔÁÔÉÞÅÓËÉÈ ÓÔÒÁÔÅÇÉÊÐÏÉÓËÁ ÏÄÎÏÇÏ ÄÅÆÅËÔÎÏÇÏ ÜÌÅÍÅÎÔÁ × ËÏÎÅÞÎÏÍ ÍÎÏÖÅÓÔ×Å ÒÁÓÓÍÁÔÒÉ×ÁÅÔÓÑ × § 5. ïÓÎÏ×ÎÙÅ ÒÅÚÕÌØÔÁÔÙ ÐÏ ÉÓÓÌÅÄÏ×ÁÎÉÀ ÍÏÄÅÌÉ á.òÅÎØÉ ÐÒÉ×ÅÄÅÎÙ × ËÏÎÃÅ ÄÁÎÎÏÇÏ ××ÏÄÎÏÇÏÒÁÚÄÅÌÁ. îÅËÏÔÏÒÙÅ ÚÁÄÁÞÉ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÇÏ ÐÏÉÓËÁ É Ó×ÑÚÁÎÎÙÅ Ó ÎÉÍÉ ÔÅÏÒÅÔÉËÏÉÎÆÏÒÍÁÃÉÏÎÎÙÅ ÐÒÏÂÌÅÍÙ ÉÚÕÞÁÀÔÓÑ × § 7.îÁÂÏÒ N ÓÔÁÔÉÞÅÓËÉÈ ÐÒÏ×ÅÒÏË ÕÄÏÂÎÏ ÏÐÉÓÙ×ÁÔØ Ó ÐÏÍÏÝØÀ Ä×ÏÉÞÎÏÊ (N × M )ÍÁÔÒÉÃÙX = kxn (m)k; xn (m) ∈ {0; 1}; n = 1; 2; : : : ; N; m = 1; 2; : : : ; M;ÎÁÚÙ×ÁÅÍÏÊ ÓÔÁÔÉÞÅÓËÉÍ ÐÌÁÎÏÍ ÐÏÉÓËÁ ÄÌÉÎÙ N × ËÏÎÅÞÎÏÍ ÍÎÏÖÅÓÔ×Å ÏÂߣÍÁ M .

ðÏÏÐÒÅÄÅÌÅÎÉÀ, ÎÏÍÅÒÁ ÅÄÉÎÉÞÎÙÈ ÐÏÚÉÃÉÊ n-ÏÊ ÓÔÒÏËÉ ÐÌÁÎÁ X Ñ×ÌÑÀÔÓÑ ÎÏÍÅÒÁÍÉ ÆÁËÔÏÒÏ×, ×ËÌÀÞÅÎÎÙÈ × n-ÕÀ ÐÒÏ×ÅÒËÕ, Ô.Å. ÜÌÅÍÅÎÔ ÐÌÁÎÁ½xn (m) ,1; ÅÓÌÉ am ∈ Tn ,0; ÅÓÌÉ am ∈= Tn .5ðÕÓÔØxn , (xn (1); xn (2); : : : ; xn (M )) ∈ {0; 1}M ; n = 1; 2; : : : ; N;ÏÂÏÚÎÁÞÁÅÔ n-ÕÀ ÓÔÒÏËÕ ÐÌÁÎÁ, ËÏÔÏÒÁÑ ÉÄÅÎÔÉÆÉÃÉÒÕÅÔ n-ÕÀ ÐÒÏ×ÅÒËÕ, Á ÓÔÏÌÂÅÃx(m) = (x1 (m); x2 (m); : : : ; xN (m)) ∈ {0; 1}N ; m = 1; 2; : : : ; M;ÏÂÏÚÎÁÞÁÅÔ m-ÙÊ ÓÔÏÌÂÅà ÐÌÁÎÁ X .òÁÓÓÍÏÔÒÉÍ ÓÌÕÞÁÊ, ËÏÇÄÁ ÄÅÆÅËÔÎÏÅ ÍÎÏÖÅÓÔ×Ï S ÓÏÓÔÏÉÔ ÉÚ ÏÄÎÏÇÏ ÚÎÁÞÉÍÏÇÏ ÆÁËÔÏÒÁ am . ôÏÇÄÁ, ËÁË ÌÅÇËÏ ÚÁÍÅÔÉÔØ, ÓÏ×ÏËÕÐÎÏÓÔØ N ÒÅÚÕÌØÔÁÔÏ× ÐÒÏ×ÅÒÏË ÐÒÅÄÓÔÁ×ÌÑÅÔÓÏÂÏÊ m-ÙÊ ÓÔÏÌÂÅà ÐÌÁÎÁ X , Ô.Å. y = x(m).

óÌÅÄÏ×ÁÔÅÌØÎÏ, ÓÔÁÔÉÞÅÓËÉÊ ÐÌÁÎ X ÏÂÌÁÄÁÅÔ Ó×ÏÊÓÔ×ÏÍ ÏÄÎÏÚÎÁÞÎÏÇÏ ×ÏÓÓÔÁÎÏ×ÌÅÎÉÑ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ×ÓÅ ÓÔÏÌÂÃÙx(m) ÐÌÁÎÁ X ÏÔÌÉÞÎÙ ÄÒÕÇ ÏÔ ÄÒÕÇÁ. CÔÏÌÂÅà x(m) ÍÏÖÎÏ ÎÁÚ×ÁÔØ ËÏÄÏ×ÙÍ ÓÌÏ×ÏÍ, ×ËÏÔÏÒÏÅ ÐÌÁÎ X ËÏÄÉÒÕÅÔ ÆÁËÔÏÒ am . üÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ××ÅÄÅÎÎÏÅ × ÐÒÅÄÙÄÕÝÅÍ ÒÁÚÄÅÌÅ ÐÏÎÑÔÉÅ Ä×ÏÉÞÎÏÇÏ ËÏÄÁ X ÄÌÑ ËÏÄÉÒÏ×ÁÎÉÑ ÓÏÏÂÝÅÎÉÑ ÉÓÔÏÞÎÉËÁ, ÐÒÉÎÉÍÁÀÝÅÇÏM ÚÎÁÞÅÎÉÊ, ÜË×É×ÁÌÅÎÔÎÏ ÐÏÎÑÔÉÀ ÓÔÁÔÉÞÅÓËÏÇÏ ÐÌÁÎÁ X ÄÌÑ ÐÏÉÓËÁ ÏÄÎÏÇÏ ÚÎÁÞÉÍÏÇÏÆÁËÔÏÒÁ, ËÏÔÏÒÙÊ ÏÔÏÖÄÅÓÔ×ÌÑÅÔÓÑ Ó ÓÏÏÂÝÅÎÉÅÍ ÉÓÔÏÞÎÉËÁ.

ïÞÅ×ÉÄÎÏ ÔÁËÖÅ, ÞÔÏ ÍÏÄÅÌØ ÐÏÉÓËÁ ÏÄÎÏÇÏ ÚÎÁÞÉÍÏÇÏ ÆÁËÔÏÒÁ ÉÚ M -ÍÎÏÖÅÓÔ×Á ÆÁËÔÏÒÏ× Ó ÐÏÍÏÝØÀ ÇÒÕÐÐÏ×ÙÈÐÒÏ×ÅÒÏË ÜË×É×ÁÌÅÎÔÎÁ ÍÏÄÅÌÉ ÐÅÒÅÄÁÞÉ ÓÏÏÂÝÅÎÉÑ ÉÓÔÏÞÎÉËÁ, ÐÒÉÎÉÍÁÀÝÅÇÏ ÚÎÁÞÅÎÉÑ ×M -ÍÎÏÖÅÓÔ×Å, ÐÏ ËÁÎÁÌÕ ÂÅÚ ÛÕÍÁ.1.3 íÏÄÅÌØ ÐÏÉÓËÁ á.òÅÎØÉ÷ ÜÔÏÊ ÍÏÄÅÌÉ ÒÁÓÓÍÁÔÒÉ×ÁÀÔÓÑ ÓÔÁÔÉÞÅÓËÉÅ ÐÌÁÎÙ ÐÏÉÓËÁ ÏÄÎÏÇÏ ÚÎÁÞÉÍÏÇÏ ÆÁËÔÏÒÁÉÚ M -ÍÎÏÖÅÓÔ×Á ÆÁËÔÏÒÏ× ÐÒÉ ÎÁÌÉÞÉÉ ÏÇÒÁÎÉÞÅÎÉÊ ÎÁ ÏÂßÅÍÙ ÔÅÓÔÉÒÕÅÍÙÈ ÇÒÕÐÐ. ÷×ÅÄÅÍ ÐÁÒÁÍÅÔÒ p; 0 < p ≤ 1=2, ËÏÔÏÒÙÊ ÚÁÄÁÅÔ ÏÇÒÁÎÉÞÅÎÉÅ ÎÁ ÞÉÓÌÏ ÅÄÉÎÉà (×ÅÓ) ÓÔÒÏËÐÌÁÎÁ X :MXm=1xn (m) ≤ k = dpM e; n = 1; 2; : : : ; N:äÁÎÎÏÅ ÏÇÒÁÎÉÞÅÎÉÅ ÏÚÎÁÞÁÅÔ, ÞÔÏ × ËÁÖÄÏÊ ÉÚ N ÓÔÁÔÉÞÅÓËÉÈ ÐÒÏ×ÅÒÏË ÍÏÖÅÔ ÔÅÓÔÉÒÏ×ÁÔØÓÑ ÎÅ ÂÏÌÅÅ k = dpM e ÆÁËÔÏÒÏ×.ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ N (M; k) = N (M; dpM e) ÍÉÎÉÍÁÌØÎÏÅ ÚÎÁÞÅÎÉÅ ÐÁÒÁÍÅÔÒÁ N , ÄÌÑ ËÏÔÏÒÏÇÏ ÐÌÁÎ ÐÏÉÓËÁ X ÏÂÌÁÄÁÅÔ Ó×ÏÊÓÔ×ÏÍ ÏÄÎÏÚÎÁÞÎÏÇÏ ×ÏÓÓÔÁÎÏ×ÌÅÎÉÑ, Ô.Å.

ÓÔÏÌÂÃÙ XÏÔÌÉÞÎÙ ÄÒÕÇ ÏÔ ÄÒÕÇÁ. ÷ § 5 ÂÕÄÅÔ ÄÏËÁÚÁÎÁ ÐÒÉ×ÏÄÉÍÁÑ ÎÉÖÅ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ, ÕÓÔÁÎÁ×ÌÉ×ÁÀÝÁÑ ÁÓÉÍÐÔÏÔÉËÕ ÍÉÎÉÍÁÌØÎÏÊ ÄÌÉÎÙ ÓÔÁÔÉÞÅÓËÏÇÏ ÐÌÁÎÁ ÄÌÑ ÍÏÄÅÌÉ ÐÏÉÓËÁá. òÅÎØÉ.ôÅÏÒÅÍÁ ûÅÎÎÏÎÁ. åÓÌÉ M → ∞, ÔÏ ÓÐÒÁ×ÅÄÌÉ×Ï ÁÓÉÍÐÔÏÔÉÞÅÓËÏÅ ÒÁ×ÅÎÓÔ×ÏN (M; dpM e) =log2 M(1 + o(1));h(p)ÇÄÅ ÓÉÍ×ÏÌ h(p) ÏÂÏÚÎÁÞÁÅÔ ××ÅÄÅÎÎÕÀ ×ÙÛÅ Ä×ÏÉÞÎÕÀ ÜÎÔÒÏÐÉÀ.6.

Характеристики

Список файлов лекций