it5 (Полный комплект лекций Г.А. Дьячкова)

á.ç.äØÑÞËÏ×ôÅÏÒÉÑ ÉÎÆÏÒÍÁÃÉɧ5. íÏÄÅÌØ ÓÔÁÔÉÞÅÓËÏÇÏ ÐÏÉÓËÁ á. òÅÎØÉóÏÄÅÒÖÁÎÉÅ1. ïÂÒÁÔÎÁÑ É ÐÒÑÍÁÑ ÔÅÏÒÅÍÙ ûÅÎÎÏÎÁ ÄÌÑ (M; k){ÐÌÁÎÏ×.2. ðÏÓÔÒÏÅÎÉÅ ÏÐÔÉÍÁÌØÎÙÈ (M; k){ÐÌÁÎÏ×.(a) ëÏÎÓÔÒÕËÃÉÉ, ÏÓÎÏ×ÁÎÎÙÅ ÎÁ q-ÎÙÈ ÏÄÎÏÒÏÄÎÙÈ ÒÁÚÄÅÌÑÀÝÉÈ ÍÁÔÒÉÃÁÈ.(b) ëÏÎÓÔÒÕËÃÉÉ, ÏÓÎÏ×ÁÎÎÙÅ ÎÁ ÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑ ÒÁÚÂÉÅÎÉÑÈ ËÏÎÅÞÎÏÇÏ ÍÎÏÖÅÓÔ×Á.5.1 ïÐÒÅÄÅÌÅÎÉÑ, ÏÂÏÚÎÁÞÅÎÉÑ, ÐÏÓÔÁÎÏ×ËÁ ÚÁÄÁÞɳ´ðÕÓÔØ X = x(1); x(2); : : : ; x(M ) = kxn (m)k, n = 1; N , m = 1; M , | Ä×ÏÉÞÎÙÊ ËÏÄÏÂßÅÍÁ M , ÄÌÉÎÙ N . úÁÆÉËÓÉÒÕÅÍ ÃÅÌÏÅ ÞÉÓÌÏ k, 1 ≤ k ≤ M=2. ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ³´x(m) = x1 (m); : : : ; xN (m) ; m = 1; M;ÓÔÏÌÂÃÙ (ËÏÄÏ×ÙÅ ÓÌÏ×Á), Á ÞÅÒÅÚ³´xn = xn (1); xn (2); : : : ; xn (M ) ; n = 1; N;ÓÔÒÏËÉ ÜÔÏÇÏ ËÏÄÁ. ðÕÓÔØ ÓÉÍ×ÏÌÙ|x(m)| ,NXn=1xn (m); m = 1; M; É |xn | ,MXm=1xn (m); n = 1; NÏÂÏÚÎÁÞÁÀÔ ÞÉÓÌÏ ÅÄÉÎÉà (×ÅÓ) m-ÏÇÏ ËÏÄÏ×ÏÇÏ ÓÌÏ×Á É n-ÏÊ ÓÔÒÏËÉ.ïÐÒÅÄÅÌÅÎÉÅ 1. ëÏÄ X ÎÁÚÙ×ÁÅÔÓÑ (M; k){ÐÌÁÎÏÍ (ÉÌÉ ÒÁÚÄÅÌÑÀÝÉÍ ÐÌÁÎÏÍ ÓÔÁÔÉÞÅÓËÏÇÏ ÐÏÉÓËÁ × ÍÏÄÅÌÉ á.òÅÎØÉ), ÅÓÌÉ ÄÌÑ ÌÀÂÏÇÏ n = 1; N ×ÅÓ ÓÔÒÏËÉ |xn | = k, Á ×ÓÅÓÔÏÌÂÃÙ x(m), m = 1; M ÏÔÌÉÞÎÙ ÄÒÕÇ ÏÔ ÄÒÕÇÁ.ïÐÒÅÄÅÌÅÎÉÅ 2.

åÓÌÉ ÓÔÒÏËÉ X ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÕÓÌÏ×ÉÀ: |xn | ≤ k, n = 1; N , Á ×ÓÅÓÔÏÌÂÃÙ x(m), m = 1; M ÏÔÌÉÞÎÙ ÄÒÕÇ ÏÔ ÄÒÕÇÁ, ÔÏ ËÏÄ X ÎÁÚÙ×ÁÅÔÓÑ (M; ≤ k){ÐÌÁÎÏÍ.ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ N (M; k) ÉÌÉ ÞÅÒÅÚ N (M; ≤ k) ÍÉÎÉÍÁÌØÎÏ ×ÏÚÍÏÖÎÏÅ ÞÉÓÌÏ ÓÔÒÏË ×ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÍ ÒÁÚÄÅÌÑÀÝÅÍ ÐÌÁÎÅ.

îÁÛÁ ÃÅÌØ | ÐÏÓÔÒÏÅÎÉÅ ÇÒÁÎÉÃ É ÉÓÓÌÅÄÏ×ÁÎÉÅÁÓÉÍÐÔÏÔÉËÉ ÜÔÉÈ ÈÁÒÁËÔÅÒÉÓÔÉË. éÍÅÅÔ ÍÅÓÔÏìÅÍÍÁ 1. åÓÌÉ 1 ≤ k ≤ M=2, ÔÏ N (M; k) = N (M; ≤ k).äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ k0 ≤ k Éxn =M −k}|{´z00:::011:::1;;00:::0| {z } | {z }0³k0k −k 01ÐÒÏÉÚ×ÏÌØÎÁÑ ÓÔÒÏËÁ (M; ≤ k){ÐÌÁÎÁ, × ËÏÔÏÒÏÊ k0 ÅÄÉÎÉÃ, k0 < k. äÏÓÔÁÔÏÞÎÏ ÄÏËÁÚÁÔØ,ÞÔÏ × ÓÔÒÏËÅ xn ÎÁÊÄÅÔÓÑ k − k0 ÎÕÌÅ×ÙÈ ÐÏÚÉÃÉÊ, ËÏÔÏÒÙÅ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ ÅÄÉÎÉÞÎÙÅ ÉÐÒÉ ÜÔÏÍ ÓÏÈÒÁÎÉÔÓÑ Ó×ÏÊÓÔ×Ï ÒÁÚÌÉÞÉÑ ÓÔÏÌÂÃÏ×. úÁÍÅÔÉÍ, ÞÔÏ ÐÒÉ ÚÁÍÅÎÅ Ä×ÕÈ ÎÕÌÅ×ÙÈÐÏÚÉÃÉÊ ÓÔÒÏËÉ xn ÎÁ ÅÄÉÎÉÞÎÙÅ ×ÎÏ×Ø ÐÏÌÕÞÉ×ÛÉÅÓÑ Ä×Á ÓÔÏÌÂÃÁ ÎÅ ÓÏ×ÐÁÄÁÀÔ ÍÅÖÄÕÓÏÂÏÊ, Á ÐÏÔÏÍÕ ÎÅ ÍÏÇÕÔ ÓÏ×ÐÁÓÔØ Ó ÏÄÎÉÍ É ÔÅÍ ÖÅ ÉÚ k0 ÓÔÏÌÂÃÏ×, ËÏÔÏÒÙÅ ÉÍÅÀÔ ×xn ÅÄÉÎÉÃÕ. ðÏÜÔÏÍÕ ÞÉÓÌÏ ÎÕÌÅ×ÙÈ ÐÏÚÉÃÉÊ xn , ËÏÔÏÒÙÅ ÎÅÌØÚÑ ÚÁÍÅÎÑÔØ ÎÁ ÅÄÉÎÉÞÎÙÅÂÅÚ ÐÏÔÅÒÉ Ó×ÏÊÓÔ×Á ÒÁÚÌÉÞÉÑ, ÚÁ×ÅÄÏÍÏ ≤ k0 . óÌÅÄÏ×ÁÔÅÌØÎÏ, ÞÉÓÌÏ "ÈÏÒÏÛÉÈ" ÎÕÌÅ×ÙÈÐÏÚÉÃÉÊ, ËÏÔÏÒÙÅ ÍÏÖÎÏ ÚÁÍÅÎÑÔØ ÎÁ ÅÄÉÎÉÞÎÙÅ ÂÅÚ ÐÏÔÅÒÉ Ó×ÏÊÓÔ×Á ÒÁÚÌÉÞÉÑ ÚÁ×ÅÄÏÍÏ≥ M − k 0 − k 0 = M − 2k 0 ≥ k − k 0 , ÇÄÅ ÐÏÓÌÅÄÎÅÅ ÎÅÒÁ×ÅÎÓÔ×Ï ×ÅÒÎÏ, ÅÓÌÉ k + k 0 ≤ M .ðÏÓËÏÌØËÕ ÐÒÉ k0 < k ≤ M=2 ÉÍÅÅÍ k + k0 ≤ M , ÔÏ ÌÅÍÍÁ 1 ÄÏËÁÚÁÎÁ.÷ ÄÁÌØÎÅÊÛÅÍ, ÎÅ ÎÁÒÕÛÁÑ ÏÂÝÎÏÓÔÉ, ÍÙ ÂÕÄÅÍ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÌÉÛØ ×ÅÌÉÞÉÎÕ N (M; k)É ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ËÏÎÓÔÒÕËÃÉÉ ÏÐÔÉÍÁÌØÎÙÈ (M; k)-ÐÌÁÎÏ× ÐÒÉ 1 ≤ k ≤ M=2.úÁÄÁÞÁ 1.

äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ 1 ≤ k ≤ M=2 ×ÅÌÉÞÉÎÁN (M; k) ≥ dlog2 M e;ÇÄÅ ÐÒÉ k = bM=2c ÄÏÓÔÉÇÁÅÔÓÑ ÚÎÁË ÒÁ×ÅÎÓÔ×Á.NõËÁÚÁÎÉÅ. ðÒÉ 2N −1 <ÄÏÓÔÉÖÅÎÉÑ ÇÒÁÎÉÃÙ dlog2 M e =³ M ≤ 2 ÄÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á´NN ÒÁÓÓÍÏÔÒÉÔÅ ËÏÄ X = x(1); x(2); : : : ; x(2 ) ÏÂßÅÍÁ 2N , ÄÌÉÎÙ N , ÇÄÅ ËÏÄÏ×ÏÅ ÓÌÏ×Ïx(m) Ñ×ÌÑÅÔÓÑ Ä×ÏÉÞÎÙÍÒÁÚÌÏÖÅÎÉÅÍ ÞÉÓÌÁ m − 1, m = 1; 2N . äÏËÁÖÉÔÅ, ÞÔÏ ËÏÄ X 0 =³´x(1); x(2); : : : ; x(M ) ÂÕÄÅÔ (M; ≤ bM=2c){ÐÌÁÎÏÍ ÄÌÉÎÙ N = dlog2 M e.5.2 ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁóÉÍ×ÏÌÏÍ h(u) , −u log2 u − (1 − u) log2 (1 − u), 0 ≤ u ≤ 1, ÂÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ Ä×ÏÉÞÎÕÀÜÎÔÒÏÐÉÀ. éÍÅÅÔ ÍÅÓÔÏìÅÍÍÁ 2. ðÕÓÔØ 1 ≤ k ≤ M=2 É ÓÕÝÅÓÔ×ÕÅÔ (M; k){ÐÌÁÎ X ÄÌÉÎÙ N .

ôÏÇÄÁÓÐÒÁ×ÅÄÌÉ×Ï ÎÅÒÁ×ÅÎÓÔ×ϵN ·hkM¶≥ log2 M;Ô.Å. N (M; k) ≥ðÕÓÔØ k , dMpe, ÇÄÅ 0 < p < 1=2. ôÏÇÄÁµkdMpe1k=≤p+; Ô.Å. hMMMM¶log2 M:h(k=M )µ¶1≤h p+;MÉ ÌÅÍÍÁ 2 ÏÚÎÁÞÁÅÔ, ÞÔÏ ÓÐÒÁ×ÅÄÌÉ×ÁôÅÏÒÅÍÁ 1. (ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ). äÌÑ ÌÀÂÏÇÏ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ p, 0 < p < 1=2,É M → ∞, ÞÉÓÌÏlog MN (M; dMpe)) ≥ 2 (1 + o(1));h(p)ÞÔÏ ÒÁ×ÎÏÓÉÌØÎÏ ÁÓÉÍÐÔÏÔÉÞÅÓËÏÍÕ ÎÅÒÁ×ÅÎÓÔ×Õlog2 M≤ h(p)(1 + o(1)):N (M; dMpe))2äÏËÁÚÁÔÅÌØÓÔ×Ï ÌÅÍÍÙ 2.

ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ ÓÌÕÞÁÊÎÕÀ ×ÅÌÉÞÉÎÕ Ó ÒÁ×ÎÏÍÅÒÎÙÍÒÁÓÐÒÅÄÅÌÅÎÉÅÍ ÎÁ ÍÎÏÖÅÓÔ×Å [M ] , {1; 2; : : : ; M }, Ô.Å.Pr{ = m} , M −1 ; m = 1; M:ðÕÓÔØ X = (x(1); : : : ; x(M )) | ÐÒÏÉÚ×ÏÌØÎÙÊ (M; k){ÐÌÁÎ ÄÌÉÎÙ N . äÌÑ ÜÎÔÒÏÐÉ ûÅÎÎÏÎÁ×ÅËÔÏÒÎÏÊ ÓÌÕÞÁÊÎÏÊ ×ÅÌÉÞÉÎÙ x( ) , (x1 ( ); x2 ( ); : : : ; xN ( )) ÉÍÅÅÍH (x( )) , −MXm=1Pr{x( ) = x(m)} log2 Pr{x( ) = x(m)} = log2 M:ó ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ, ÐÏ Ó×ÏÊÓÔ×Õ ÓÕÂÁÄÄÉÔÉ×ÎÏÓÔÉ ÜÎÔÒÏÐÉÉ ûÅÎÎÏÎÁ (ÓÍ.§4)log2 M = H (x( )) ≤NXn=1H (xn ( )) =¶N µX|xn |n=1hM;ÇÄÅ ÕÞÌÉ, ÞÔÏ Ä×ÏÉÞÎÁÑ ÓÌÕÞÁÊÎÁÑ ×ÅÌÉÞÉÎÁ xn ( ) ÐÒÉÎÉÍÁÅÔ ÚÎÁÞÅÎÉÑ 0, 1 Ó ×ÅÒÏÑÔÎÏÓÔÑÍɵxn ( ) =0M −|xn |M¶1|xn |M:ðÏ ÏÐÒÅÄÅÌÅÎÉÀ (M; k)-ÐÌÁÎÁ X ×ÅÓ ÅÇÏ n-ÏÊ ÓÔÒÏËÉ |xn | = k ÄÌÑ ÌÀÂÏÇÏ n = 1; N . ðÏÜÔÏÍÕµ¶klog2 M = H (x( )) ≤ Nh:MìÅÍÍÁ 2 ÄÏËÁÚÁÎÁ.5.3 ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁðÕÓÔØ 1 ≤ w ≤ t − 1 { ÐÒÏÉÚ×ÏÌØÎÙÅ ÃÅÌÙÅ ÞÉÓÌÁ.ìÅÍÍÁ 3.

óÕÝÅÓÔ×ÕÅÔ (M; k)-ÐÌÁÎ X ÄÌÉÎÙ N Ó ÐÁÒÁÍÅÔÒÁÍɵ ¶µ¶tt−1N = t; M =; k=:ww−1äÏËÁÚÁÔÅÌØÓÔ×Ï ÌÅÍÍÙ 3. éÓËÏÍÙÊ ËÏÄ X ÓÔÒÏÉÔÓÑËÁË Ä×ÏÉÞÎÁÑ N × M -ÍÁÔÒÉÃÁ,¡t¢ÉÍÅÀÝÁÑ N = t ÓÔÒÏË xn É ÓÏÓÔÏÑÝÁÑ ÉÚ ×ÓÅÈ M = w ÓÔÏÌÂÃÏ× (ËÏÄÏ×ÙÈ ÓÌÏ×) x(m) ÄÌÉÎÙ¡¢t É ×ÅÓÁ |x(m)| = w. ÷ÓÅ ÓÔÒÏËÉ xn ÜÔÏÊ ÍÁÔÒÉÃÙ ÉÍÅÀÔ ÏÄÉÎ É ÔÏÔ ÖÅ ×ÅÓ |xn | = wt−−11 ,ÒÁ×ÎÙÊ ÞÉÓÌÕ ËÏÄÏ×ÙÈ ÓÌÏ× ËÏÄÁ X , ÓÏÄÅÒÖÁÝÉÈ × ÆÉËÓÉÒÏ×ÁÎÎÏÊ ÐÏÚÉÃÉÉ ÅÄÉÎÉÞÎÙÊÓÉÍ×ÏÌ.ìÅÍÍÁ 3 ÄÏËÁÚÁÎÁ.úÁÄÁÞÁ 2. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ N → ∞ É ÐÒÏÉÚ×ÏÌØÎÏÍ ÆÉËÓÉÒÏ×ÁÎÎÏÍ p, 0 < p < 1=2,ÓÐÒÁ×ÅÄÌÉ×Ù ÁÓÉÍÐÔÏÔÉÞÅÓËÉÅ ÒÁ×ÅÎÓÔ×Á¡¢Nlog2 M log2 dNpe== h(p)(1 + o(1));NNµkN −1=MdNpe − 13¶ Áµ¶N= p(1 + o(1)):dNpeéÚ ÒÅÚÕÌØÔÁÔÁ ÚÁÄÁÞÉ 2 ×ÙÔÅËÁÅÔôÅÏÒÅÍÁ 2.

(ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ). äÌÑ ÌÀÂÏÇÏ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ p, 0 < p < 1=2,É M → ∞, ÏÔÎÏÛÅÎÉÅlog2 M≥ h(p)(1 + o(1));N (M; dMpe))ÞÔÏ ÒÁ×ÎÏÓÉÌØÎÏ ÁÓÉÍÐÔÏÔÉÞÅÓËÏÍÕ ÎÅÒÁ×ÅÎÓÔ×ÕN (M; dMpe)) ≤log2 M(1 + o(1)):h(p)éÚ ÔÅÏÒÅÍ 1 É 2 ÐÏÌÕÞÁÅÍóÌÅÄÓÔ×ÉÅ. äÌÑ ÌÀÂÏÇÏ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ p, 0 < p < 1=2, É MÁÓÉÍÐÔÏÔÉÞÅÓËÏÍÕ ÒÁ×ÅÎÓÔ×ÏN (M; dMpe)) =→ ∞ÓÐÒÁ×ÅÄÌÉ×Ïlog2 M(1 + o(1)):h(p)5.4 ðÏÓÔÒÏÅÎÉÅ (M; k)-ÐÌÁÎÏ×÷ ÄÁÎÎÏÍ ÒÁÚÄÅÌÅ ÂÕÄÕÔ ÏÐÉÓÁÎÙ ÎÅËÏÔÏÒÙÅ ËÏÎÓÔÒÕËÃÉÉ ÏÐÔÉÍÁÌØÎÙÈ (M; k)-ÐÌÁÎÏ×.úÁÄÁÞÁ 3. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ ÆÉËÓÉÒÏ×ÁÎÎÏÍ k = 1; 2; : : : É M → ∞ ÓÐÒÁ×ÅÄÉ×ÏÁÓÉÍÐÔÏÔÉÞÅÓËÏÅ ÒÁ×ÅÎÓÔ×ϵkhM¶=klog2 M(1 + o(1)) :MüÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ × ÄÁÎÎÙÈ ÕÓÌÏ×ÉÑÈ ÎÉÖÎÑÑ ÇÒÁÎÉÃÁ ÌÅÍÍÙ 2 ÄÌÑ N (M; k) ÒÁ×ÎÏÓÉÌØÎÁÁÓÉÍÐÔÏÔÉÞÅÓËÏÍÕ ÎÅÒÁ×ÅÎÓÔ×ÕN (M; k) ≥M(1 + o(1)) :kóÌÅÄÕÀÝÉÊ ÒÅÚÕÌØÔÁÔ ÐÏËÁÚÙ×ÁÅÔ, ÞÔÏ × ÕÓÌÏ×ÉÑÈ kÕÔÏÞÎÉÔØ ÐÒÉÍÅÒÎÏ × Ä×Á ÒÁÚÁ.ôÅÏÒÅÍÁ 3.

äÌÑ ÌÀÂÏÇÏ 1 ≤ k < M ÞÉÓÌÏ»N (M; k) ≥¿M ÇÒÁÎÉÃÕ ÌÅÍÍÙ 2 ÍÏÖÎϼ2(M − 1):k+1(1)äÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 3. òÁÓÓÍÏÔÒÉÍ ÐÒÏÉÚ×ÏÌØÎÙÊ (M; k)-ÐÌÁÎ X ÄÌÉÎÙ N .ðÕÓÔØ n = 0; N , Á Cn ÏÂÏÚÎÁÞÁÅÔ ÞÉÓÌÏ ÓÔÏÌÂÃÏ× X , ËÏÔÏÒÙÅ ÉÍÅÀÔ ×ÅÓ n. ôÏÇÄÁC0 ≤ 1; C1 ≤ N ;NXn=24Cn = M − C0 − C1 :(2)äÁÌÅÅ, × ÓÉÌÕ (2), ÉÍÅÅÍNk =NPn=0nCn = C1 +NPn=2nCn ≥ C1 + 2= 2(M − C0 ) − C1 ≥ 2(M − 1) − N:NPn=2Cn = C1 + 2(M − C0 − C1 ) =óÌÅÄÏ×ÁÔÅÌØÎÏ, N (k + 1) ≥ 2(M − 1).ôÅÏÒÅÍÁ 3 ÄÏËÁÚÁÎÁ.ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ M (N; k) ÍÁËÓÉÍÁÌØÎÏ ×ÏÚÍÏÖÎÏÅ ÞÉÓÌÏ ËÏÄÏ×ÙÈ ÓÌÏ× ËÏÄÁ X ÄÌÉÎÙN , Õ ËÏÔÏÒÏÇÏ ×ÓÅ ÓÔÏÌÂÃÙ ÒÁÚÌÉÞÎÙ, Á ×ÅÓ ËÁÖÄÏÊ ÓÔÒÏËÉ ÒÁ×ÅÎ k. éÚ ×Ù×ÏÄÁ ÔÅÏÒÅÍÙ 3ÓÌÅÄÕÅÔ, ÞÔϹº1M (N; k) ≤ N (k + 1) + 1; M (2n; k) ≤ n(k + 1) + 1;(3)2ÇÄÅ ÏÐÔÉÍÁÌØÎÙÊ (M; k)-ÐÌÁÎ X , ÎÁ ËÏÔÏÒÏÍ × (1) É (3) ÄÏÓÔÉÇÁÅÔÓÑ ÚÎÁË ÒÁ×ÅÎÓÔ×Á, ÄÏÌÖÅÎÉÍÅÔØ ÐÁÒÁÍÅÔÒÙC0 = 1; C1 = N ; Cn = 0; n = 3; N:üÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÓÐÒÁ×ÅÄÌÉ×ÁìÅÍÍÁ 4.

÷ ÏÐÔÉÍÁÌØÎÏÍ, Ô.Å. ÄÏÓÔÉÇÁÀÝÅÍ ÇÒÁÎÉà (1) É (3), (M; k)-ÐÌÁÎÅ X ÄÌÉÎÙN ÄÏÌÖÅÎ ÂÙÔØ ÏÄÉÎ ÎÕÌÅ×ÏÊ ÓÔÏÌÂÅÃ, N ÒÁÚÌÉÞÎÙÈ ÓÔÏÌÂÃÏ×, ÓÏÄÅÒÖÁÝÉÈ ÐÏ ÏÄÎÏÊÅÄÉÎÉÃÅ, ÐÏÐÁÒÎÏ ÒÁÚÌÉÞÎÙÅ ÓÔÏÌÂÃÙ ×ÅÓÁ 2 É ÎÅ ÄÏÌÖÎÏ ÓÏÄÅÒÖÁÔØÓÑ ÓÔÏÌÂÃÏ× ×ÅÓÁ ≥ 3.5.4.1 ëÏÎÓÔÒÕËÃÉÉ ÏÐÔÉÍÁÌØÎÙÈ (M; k)-ÐÌÁÎÏ×, ÏÓÎÏ×ÁÎÎÙÅÎÁ q-ÎÙÈ ÏÄÎÏÒÏÄÎÙÈ ÒÁÚÄÅÌÑÀÝÉÈ ÍÁÔÒÉÃÁÈéÍÅÅÔ ÍÅÓÔÏìÅÍÍÁ 5. úÁÆÉËÓÉÒÕÅÍ ÐÒÏÉÚ×ÏÌØÎÏÅ ÃÅÌÏÅ ÞÉÓÌÏ k = 2; 3; : : :.

äÌÑ ÌÀÂÏÇÏ ÃÅÌÏÇÏÞÉÓÌÁ q ≥ k − 1 ÓÕÝÅÓÔ×ÕÅÔ (M; k)-ÐÌÁÎ X ÄÌÉÎÙ N , ÐÁÒÁÍÅÔÒÙ ËÏÔÏÒÏÇÏ ÚÁÄÁÀÔÓÑÓÏÏÔÎÏÛÅÎÉÑÍÉN = 2q; M = 1 + 2q + q(k − 1) = 1 + q(k + 1); q = k − 1; k; k + 1; : : : :éÚ ÌÅÍÍÙ 5 É ÔÅÏÒÅÍÙ 3 ×ÙÔÅËÁÅÔôÅÏÒÅÍÁ 4. äÌÑ ÌÀÂÏÇÏ ÃÅÌÏÇÏ ÞÉÓÌÁ q ≥ k − 1 ×ÅÌÉÞÉÎÁM (2q; k) = 1 + q(k + 1):äÏËÁÚÁÔÅÌØÓÔ×Ï ÌÅÍÍÙ 5. ÷ ÓÉÌÕ ÌÅÍÍÙ 4, ÄÌÑ ×Ù×ÏÄÁ ÌÅÍÍÙ 5 ÄÏÓÔÁÔÏÞÎÏ ÐÏÓÔÒÏÉÔØ Ä×ÏÉÞÎÕÀ (2q × q(k − 1))-ÍÁÔÒÉÃÕ, ×ÓÅ q(k − 1) ÓÔÏÌÂÃÏ× ËÏÔÏÒÏÊ ÒÁÚÌÉÞÎÙ É ÉÍÅÀÔ×ÅÓ 2, Á ËÁÖÄÁÑ ÉÚ 2q ÓÔÒÏË ÓÏÄÅÒÖÉÔ ÒÏ×ÎÏ k − 1 ÅÄÉÎÉÃÕ.÷×ÅÄÅÍ q-ÎÙÊ ÁÌÆÁ×ÉÔ A , {1; 2; : : : ; q}. âÕÄÅÍ ÇÏ×ÏÒÉÔØ, ÞÔÏ q-ÎÁÑ (2 × q(k − 1))ÍÁÔÒÉÃÁ B = kbj (u)k, bj (u) ∈ A, ÓÏÓÔÏÑÝÁÑ ÉÚ Ä×ÕÈ ÓÔÒÏË É q(k − 1) ÓÔÏÌÂÃÏ×bj , (bj (1); bj (2); : : : ; bj (q(k − 1))); j = 1; 2;b(u) , (b1 (u); b2 (u)); u = 1; 2; : : : ; q(k − 1):5Ñ×ÌÑÅÔÓÑ ÏÄÎÏÒÏÄÎÏÊ, ÅÓÌÉ ËÁÖÄÙÊ q-ÎÙÊ ÓÉÍ×ÏÌ a ∈ A ×ÓÔÒÅÞÁÅÔÓÑ ÒÏ×ÎÏ k − 1 ÒÁÚ ×ËÁÖÄÏÊ ÉÚ ÅÅ Ä×ÕÈ ÓÔÒÏË. íÁÔÒÉÃÕ B ÎÁÚÏ×ÅÍ ÒÁÚÄÅÌÑÀÝÅÊ, ÅÓÌÉ ×ÓÅ ÅÅ q(k − 1) ÓÔÏÌÂÃÏ×ÏÔÌÉÞÎÙ ÄÒÕÇ ÏÔ ÄÒÕÇÁ.ëÁÖÄÙÊ q-ÎÙÊ ÜÌÅÍÅÎÔ a ∈ A ÍÁÔÒÉÃÙ B ÚÁÍÅÎÉÍ ÎÁ Ä×ÏÉÞÎÙÊ ÓÔÏÌÂÅà ÄÌÉÎÙ q,ËÏÔÏÒÙÊ ÓÏÄÅÒÖÉÔ ÅÄÉÎÉÃÕ ÎÁ a-ÏÊ ÐÏÚÉÃÉÉ É ÎÕÌÉ ÎÁ ÏÓÔÁÌØÎÙÈ q − a ÐÏÚÉÃÉÑÈ, Ô.Å.a( 0| ; 0;{z: : : ; 0} ; 1; |0; 0;{z: : : ; 0} ):(a − 1) ÒÁÚ (q − a) ÒÁÚ⇐⇒îÅÔÒÕÄÎÏ ÐÏÎÑÔØ, ÞÔÏ × ÒÅÚÕÌØÔÁÔÅ ÔÁËÏÇÏ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ ÉÚ ÏÄÎÏÒÏÄÎÏÊ ÒÁÚÄÅÌÑÀÝÅÊÍÁÔÒÉÃÙ B ÐÏÌÕÞÁÅÔÓÑ ÉÓËÏÍÁÑ Ä×ÏÉÞÎÁÑ (2q × q(k − 1))-ÍÁÔÒÉÃÁ, ×ÓÅ q(k − 1) ÓÔÏÌÂÃÏ×ËÏÔÏÒÏÊ ÒÁÚÌÉÞÎÙ É ÉÍÅÀÔ ×ÅÓ 2, Á ËÁÖÄÁÑ ÉÚ 2q ÓÔÒÏË ÓÏÄÅÒÖÉÔ ÒÏ×ÎÏ k − 1 ÅÄÉÎÉÃÕ.äÌÑ ÐÏÓÔÒÏÅÎÉÑ ÏÄÎÏÒÏÄÎÏÊ ÒÁÚÄÅÌÑÀÝÅÊ ÍÁÔÒÉÃÙ B ÍÙ ×ÏÓÐÏÌØÚÕÅÍÓÑ Ä×ÏÉÞÎÏÊ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÏÊ (q × q)-ÍÁÔÒÉÃÅÊ C = kci (j )k, i = 1; 2; : : : q, j = 1; 2; : : : q, ËÏÔÏÒÁÑ ×ÚÁÉÍÎÏ- ÏÄÎÏÚÎÁÞÎÏ Ó×ÑÚÁÎÁ Ó q-ÎÏÊ ÒÁÚÄÅÌÑÀÝÅÊ ÍÁÔÒÉÃÅÊ B = (b(1); b(2); : : : ; b(q(k − 1)) ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏͽci (j ) , 1; ÅÓÌÉ × B ÓÕÝÅÓÔ×ÕÅÔ ÓÔÏÌÂÅà b(u) = (i; j ),0; ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ.ïÞÅ×ÉÄÎÏ, ÞÔÏ ÍÁÔÒÉÃÁ B Ñ×ÌÑÅÔÓÑ ÏÄÎÏÒÏÄÎÏÊ É ÒÁÚÄÅÌÑÀÝÅÊ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ,ËÏÇÄÁ × ÅÅ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÏÊ ÍÁÔÒÉÃÅ ×ÅÓ ËÁÖÄÏÊ ÓÔÒÏËÉ ci , (ci (1); ci (2); : : : ; ci (q)) É ×ÅÓËÁÖÄÏÇÏ ÓÔÏÌÂÃÁ c(j ) , (c1 (j ); c2 (j ); : : : ; cq (j )) ÓÏ×ÐÁÄÁÀÔ É ÒÁ×ÎÙ k − 1.

îÅÔÒÕÄÎÏ ÐÏÎÑÔØ,ÞÔÏ ÔÁËÏÍÕ ÕÓÌÏ×ÉÀ ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÃÉÒËÕÌÑÎÔÎÙÅ ÍÁÔÒÉÃÙ, ÏÐÒÅÄÅÌÑÅÍÙÅ ÓÌÅÄÕÀÝÉÍÏÂÒÁÚÏÍ:•ÐÅÒ×ÁÑ ÓÔÒÏËÁ c1 = (c1 (1); c1 (2); : : : ; c1 (q)) ÃÉÒËÕÌÑÎÔÎÏÊ ÍÁÔÒÉÃÙ C Ñ×ÌÑÅÔÓÑ ÐÒÏÉÚ×ÏÌØÎÏÊ Ä×ÏÉÞÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØÀ ÄÌÉÎÙ q É ×ÅÓÁ k − 1 ≤ q,•i-ÁÑ i = 2; 3; : : : ; q ÓÔÒÏËÁ ci , (ci (1); ci (2); : : : ; ci (q)) Ñ×ÌÑÅÔÓÑ ÃÉËÌÉÞÅÓËÉÍ ÓÄ×ÉÇÏÍ(i − 1)-ÏÊ ÓÔÒÏËÉ ci−1 , (ci−1 (1); ci−1 (2); : : : ; ci−1 (q)), Ô.Å.½ci (j ) ,ci−1 (q);ÅÓÌÉ j = 1,ci−1 (j − 1); ÅÓÌÉ j = 2; 3; : : : ; q.ìÅÍÍÁ 5 ÄÏËÁÚÁÎÁ.óÌÅÄÕÀÝÉÊ ÐÒÉÍÅÒ ÉÌÌÀÓÔÒÉÒÕÅÔ ÍÅÔÏÄ ÐÏÓÔÒÏÅÎÉÑ (M; k)-ÐÌÁÎÁ X , ÏÓÎÏ×ÁÎÎÙÊ ÎÁÍÅÔÏÄÅ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÌÅÍÍÙ 5.ðÒÉÍÅÒ. ðÕÓÔØ k , 3, q , 3 ≥ k − 1 = 2. ôÏÇÄÁq(k − 1) = 6; N = 2q = 6; M = 1 + 2q + q(k − 1) = 13:÷ÙÂÅÒÅÍ ÃÉÒËÕÌÑÎÔÎÕÀ (3 × 3)-ÍÁÔÒÉÃÕ C × ×ÉÄÅ1 1 0C , 0 1 1:1 0 16üÔÏÊ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÏÊ Ä×ÏÉÞÎÏÊ ÍÁÔÒÉÃÅ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÔÒÏÉÞÎÁÑ ÏÄÎÏÒÏÄÎÁÑ ÒÁÚÄÅÌÑÀÝÁÑ (2 × 6)-ÍÁÔÒÉÃÁµ¶112233B=1 2 2 3 1 3 ;ËÏÔÏÒÁÑ ÚÁÄÁÅÔ (13; 3)-ÐÌÁÎ X ÄÌÉÎÙ 6:000X=000100000010000001000000100000010000001100100100010010010010001001100001:0015.4.2 ëÏÎÓÔÒÕËÃÉÉ ÏÐÔÉÍÁÌØÎÙÈ (M; k)-ÐÌÁÎÏ×, ÏÓÎÏ×ÁÎÎÙÅ ÎÁÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑ ÒÁÚÂÉÅÎÉÑÈ ËÏÎÅÞÎÏÇÏ ÍÎÏÖÅÓÔ×ÁéÍÅÅÔ ÍÅÓÔÏ ÓÌÅÄÕÀÝÁÑ ËÏÍÂÉÎÁÔÏÒÎÁÑ¡ ¢ìÅÍÍÁ 6.÷ÓÅ 22n = n(2n − 1) ÒÁÚÌÉÞÎÙÈ 2{ÐÏÄÍÎÏÖÅÓÔ× 2n{ÍÎÏÖÅÓÔ×Á ÍÏÖÎÏÒÁÚÂÉÔØ ÎÁ 2n − 1 ÇÒÕÐÐ, ÇÄÅ ËÁÖÄÁÑ ÇÒÕÐÐÁ ÓÏÄÅÒÖÉÔ n ÐÏÐÁÒÎÏ ÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑ2{ÐÏÄÍÎÏÖÅÓÔ×, ÏÂÒÁÚÕÀÝÉÈ ÒÁÚÂÉÅÎÉÅ 2n{ÍÎÏÖÅÓÔ×Á.