it-cont (Полный комплект лекций Г.А. Дьячкова)
Описание файла
Файл "it-cont" внутри архива находится в папке "Полный комплект лекций Г.А. Дьячкова". PDF-файл из архива "Полный комплект лекций Г.А. Дьячкова", который расположен в категории "". Всё это находится в предмете "теория информации" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
á.ç. äØÑÞËÏ×óÏÄÅÒÖÁÎÉÅ ÓÐÅÃËÕÒÓÁ "ôÅÏÒÉÑ ÉÎÆÏÒÍÁÃÉÉ"§1.÷×ÅÄÅÎÉÅ1. ôÅÏÒÅÔÉËÏ-ÉÎÆÏÒÍÁÃÉÏÎÎÁÑ ÂÌÏË-ÓÈÅÍÁ, ÓÏÏÂÝÅÎÉÅ ÉÓÔÏÞÎÉËÁ É ËÏÄÏ×ÙÅ ÓÌÏ×Á, ÌÉÎÅÊÎÏÅ ËÏÄÉÒÏ×ÁÎÉÅ, ÓËÏÒÏÓÔØ ËÏÄÁ.2. ëÁÎÁÌ Ó×ÑÚÉ, ÆÏÒÍÕÌÉÒÏ×ËÉ ÐÒÑÍÏÊ É ÏÂÒÁÔÎÏÊ ÔÅÏÒÅÍ ûÅÎÎÏÎÁ, ÍÅÔÏÄ ÓÌÕÞÁÊÎÏÇÏËÏÄÉÒÏ×ÁÎÉÑ.3. íÁÔÅÍÁÔÉÞÅÓËÁÑ ÍÏÄÅÌØ ÚÁÄÁÞÉ ÐÏÉÓËÁ, ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ÍÏÄÅÌÉ ÐÏÉÓËÁ á. òÅÎØÉ.§2.ðÅÒÅÄÁÞÁ ÄÉÓËÒÅÔÎÙÈ ÓÏÏÂÝÅÎÉÊÐÏ Ä×ÏÉÞÎÏÍÕ ËÁÎÁÌÕ Ó×ÑÚÉ1. ëÏÄÉÒÏ×ÁÎÉÅ, ÄÅËÏÄÉÒÏ×ÁÎÉÅ, ×ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ËÏÄÁ. äÅËÏÄÉÒÏ×ÁÎÉÅ ÐÏ ÍÉÎÉÍÕÍÕ ÒÁÓÓÔÏÑÎÉÑ (íò-ÄÅËÏÄÉÒÏ×ÁÎÉÅ) É ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÐÏ ÍÁËÓÉÍÕÍÕ ÐÒÁ×ÄÏÐÏÄÏÂÉÑ(íð-ÄÅËÏÄÉÒÏ×ÁÎÉÅ) ÄÌÑ ÄÁÎÎÏÇÏ ËÏÄÁ.2. ïÐÔÉÍÁÌØÎÏÓÔØ íð-ÄÅËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ ÒÁ×ÎÏ×ÅÒÏÑÔÎÙÈ ÓÏÏÂÝÅÎÉÊ.3. ÷ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ × Ä×ÏÉÞÎÏÍ ÓÉÍÍÅÔÒÉÞÎÏÍ ËÁÎÁÌÅ ÂÅÚ ÐÁÍÑÔÉ (äóë) É × ËÁÎÁÌÅÓ ÒÁ×ÎÏ×ÅÓÎÙÍ ÛÕÍÏÍ (ëòû) ÄÌÑ Ä×ÕÈ ËÏÄÏ×ÙÈ ÓÌÏ×.4.
ìÏÇÁÒÉÆÍÉÞÅÓËÁÑ ÁÓÉÍÐÔÏÔÉËÁlog N ! = N log¡N ¢t, ÏÓÎÏ×ÁÎÎÁÑ ÎÁ ÎÅÒÁ×ÅÎÓÔ×ÁÈ óÔÉÒÌÉÎÇÁ:log eN 1+ log 2N + S (N ); 0 < S (N ) <:e 212N5. ôÅÏÒÅÍÁ Ï ÂÏÌØÛÉÈ ÕËÌÏÎÅÎÉÑÈ ÄÌÑ ÉÓÐÙÔÁÎÉÊ âÅÒÎÕÌÌÉ.6. ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ëòû.§3.ôÅÏÒÅÍÙ ËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ ËÏÍÂÉÎÁÔÏÒÎÏÊ ÍÏÄÅÌÉÄ×ÏÉÞÎÏÇÏ ËÁÎÁÌÁ Ó ÏÛÉÂËÁÍÉ1. îÉÖÎÑÑ ÇÒÁÎÉÃÁ ÉÓÞÅÒÐÙ×ÁÎÉÑ ÄÌÑ M (N; D)- ÏÂߣÍÁ ÍÁËÓÉÍÁÌØÎÏÇÏ ËÏÄÁ ÄÌÉÎÙ NÓ ÒÁÓÓÔÏÑÎÉÅÍ D.2. îÉÖÎÑÑ ÇÒÁÎÉÃÁ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ M (N; D).13. çÒÁÎÉÃÁ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ M (N; D) × ÁÎÓÁÍÂÌÅ ÒÁ×ÎÏ×ÅÓÎÙÈ ËÏÄÏ×.4. îÉÖÎÑÑ ÇÒÁÎÉÃÁ ÷ÁÒÛÁÍÏ×Á-çÉÌØÂÅÒÔÁ (÷ç) ÄÌÑ ÓËÏÒÏÓÔÉ R(d) ÏÐÔÉÍÁÌØÎÏÇÏ ËÏÄÁÓ ÒÁÓÓÔÏÑÎÉÅÍ D ∼ dN .5.
÷ÅÒÈÎÑÑ ÇÒÁÎÉÃÁ èÜÍÍÉÎÇÁ ÄÌÑ R(d).6. ÷ÅÒÈÎÑÑ ÇÒÁÎÉÃÁ ðÌÏÔËÉÎÁ ÄÌÑ R(d).7. ìÉÎÅÊÎÙÊ Ä×ÏÉÞÎÙÊ ËÏÄ É ÅÇÏ ËÏÄÏ×ÏÅ ÒÁÓÓÔÏÑÎÉÅ.8. ëÏÄ èÜÍÍÉÎÇÁ, ÅÇÏ ÏÐÔÉÍÁÌØÎÏÓÔØ.9. ìÉÎÅÊÎÙÊ ËÏÄ Ó ÐÒÏ×ÅÒËÏÊ ÎÁ ÞÅÔÎÏÓÔØ, ÅÇÏ ÏÐÔÉÍÁÌØÎÏÓÔØ.10. çÒÁÎÉÃÁ ÷ç ÄÌÑ ÌÉÎÅÊÎÏÇÏ ËÏÄÁ.§4.ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ Ó×ÑÚÉ1. ó×ÏÊÓÔ×Á ÜÎÔÒÏÐÉÉ É ÉÎÆÏÒÍÁÃÉÉ:(a) H (X | Y ) ≤ H (X ) ≤ ln | X |.(b)J (X ; Y ) = J (Y ; X ) = H (Y ) − H (Y | X ) = H (X ) − H (X | Y ) == H (X ) + H (Y ) − H (X ; Y ) ≥ 0:(c) J (X ; Y |Z ) = H (Y |Z ) − H (Y |X; Z ) ≥ 0.(d) J (X ; Y1 ; Y2 ) = J (X ; Y1 ) + J (X ; Y2 |Y1 ), J (X ; Y1N ) =NPn=1J (X ; Yn |Y1n−1 ).(e) J (X ; f (Y )) ≤ J (X ; Y ).(f) åÓÌÉ p(y|x; z ) = p(y|x), ÔÏ J (Y ; X |Z ) ≤ J (Y ; X ).åÓÌÉ p(x|z ) = p(x), ÔÏ J (Y ; X |Z ) ≥ J (Y ; X ).(g) îÅÒÁ×ÅÎÓÔ×Ï æÁÎÏ: ecÌÉ Pr{X 6= Y } = , ÔÏ H (X |Y ) ≤ ln |X | + h().(h) H (Y1N ) ≤NPn=1H (Yn ).(i) åÓÌÉ p(y1N |xN1 ) =NQn=1p(yn |xn ), ÔÏH (Y1N |X1N ) =NXn=1H (Yn |Xn );J (X1N ; Y1N ) ≤2.
ôÅÏÒÅÍÁ ÐÅÒÅÒÁÂÏÔËÉ ÄÁÎÎÙÈ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ Ó×ÑÚÉ.3. ðÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉ.2NXn=1J (Xn ; Yn ):4. ÷ÙÞÉÓÌÅÎÉÅ ÐÒÏÐÕÓËÎÏÊ ÓÐÏÓÏÂÎÏÓÔÉ ÄÌÑ Ä×ÏÉÞÎÏÇÏ ÓÉÍÍÅÔÒÉÞÎÏÇÏ ËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉ: C = ln 2 − h(p).5. îÉÖÎÑÑ ÇÒÁÎÉÃÁ -ÜÎÔÒÏÐÉÉ ÓÏÏÂÝÅÎÉÑ Ó ÒÁ×ÎÏ×ÅÒÏÑÔÎÙÍÉ ÚÎÁÞÅÎÉÑÍÉ.6. ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ ÂÅÚ ÐÁÍÑÔÉ.7. ïÂÒÁÔÎÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ ËÁÎÁÌÁ Ó ÒÁ×ÎÏ×ÅÓÎÙÍ ÛÕÍÏÍ.8. MÁÔÅÍÁÔÉÞÅÓËÁÑ ÍÏÄÅÌØ ÐÅÒÅÄÁÞÉ ÄÉÓËÒÅÔÎÏÇÏ ÓÏÏÂÝÅÎÉÑ ÐÏ ÄÉÓËÒÅÔÎÏÍÕ ËÁÎÁÌÕÂÅÚ ÐÁÍÑÔÉ Ó ÏÂÒÁÔÎÏÊ Ó×ÑÚØÀ.9. ôÅÏÒÅÍÁ ÐÅÒÅÒÁÂÏÔËÉ ÄÁÎÎÙÈ É ÐÒÏÐÕÓËÎÁÑ ÓÐÏÓÏÂÎÏÓÔØ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏ ËÁÎÁÌÁ ÂÅÚÐÁÍÑÔÉ Ó ÏÂÒÁÔÎÏÊ Ó×ÑÚØÀ.§5.íÏÄÅÌØ ÓÔÁÔÉÞÅÓËÏÇÏ ÐÏÉÓËÁ á.
òÅÎØÉ1. ïÂÒÁÔÎÁÑ É ÐÒÑÍÁÑ ÔÅÏÒÅÍÙ ûÅÎÎÏÎÁ ÄÌÑ (M; k)-ÐÌÁÎÏ×.2. ðÏÓÔÒÏÅÎÉÅ ÏÐÔÉÍÁÌØÎÙÈ (M; k)-ÐÌÁÎÏ×.(a) ëÏÎÓÔÒÕËÃÉÉ, ÏÓÎÏ×ÁÎÎÙÅ ÎÁ q-ÎÙÈ ÏÄÎÏÒÏÄÎÙÈ ÒÁÚÄÅÌÑÀÝÉÈ ÍÁÔÒÉÃÁÈ.(b) ëÏÎÓÔÒÕËÃÉÉ, ÏÓÎÏ×ÁÎÎÙÅ ÎÁ ÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑ ÒÁÚÂÉÅÎÉÑÈ ËÏÎÅÞÎÏÇÏ ÍÎÏÖÅÓÔ×Á.§6.ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ ÄÌÑ äëâð1. ðÏÒÏÇÏ×ÏÅ ÄÅËÏÄÉÒÏ×ÁÎÉÅ ÄÌÑ äëâð, ÄÅËÏÄÉÒÕÀÝÁÑ ÆÕÎËÃÉÑ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁÄÌÑ äóë.2. ÷ÅÒÏÑÔÎÏÓÔØ ÏÛÉÂËÉ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁ ÄÌÑ äëâð.3. çÒÁÎÉÃÁ ÓÌÕÞÁÊÎÏÇÏ ËÏÄÉÒÏ×ÁÎÉÑ ÄÄÑ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÐÏÒÏÇÏ×ÏÇÏ ÄÅËÏÄÅÒÁ.4. ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ Ï ÓÒÅÄÎÅÊ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ äëâð.5. ðÒÑÍÁÑ ÔÅÏÒÅÍÁ ûÅÎÎÏÎÁ Ï ÍÁËÓÉÍÁÌØÎÏÊ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ äëâð.6. ôÅÏÒÅÍÁ Ï ÂÏÌØÛÉÈ ÕËÌÏÎÅÎÉÑÈ ÄÌÑ ÓÕÍÍÙ ÎÅÚÁ×ÉÓÉÍÙÈ ÄÉÓËÒÅÔÎÙÈ ÏÄÉÎÁËÏ×Ï ÒÁÓÐÒÅÄÅÌÅÎÎÙÈ ÓÌÕÞÁÊÎÙÈ ×ÅÌÉÞÉÎ.7. ÷Ù×ÏÄ ÜËÓÐÏÎÅÎÃÉÁÌØÎÏÊ ÇÒÁÎÉÃÙ ×ÅÒÏÑÔÎÏÓÔÉ ÏÛÉÂËÉ ÄÌÑ äëâð Ó ÐÏÍÏÝØÀ ÔÅÏÒÅÍÙ Ï ÂÏÌØÛÉÈ ÕËÌÏÎÅÎÉÑÈ.8.
÷ÙÐÕËÌÏÓÔØ ××ÅÒÈ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊ ÆÕÎËÃÉÉ J(Q; W) ÐÏ ×ÈÏÄÎÏÍÕ ÒÁÓÐÒÅÄÅÌÅÎÉÀ Q.9. ÷ÙÐÕËÌÏÓÔØ ×ÎÉÚ ÉÎÆÏÒÍÁÃÉÏÎÎÏÊ ÆÕÎËÃÉÉ J(Q; W) ÐÏ ÕÓÌÏ×ÎÏÍÕ ÒÁÐÒÅÄÅÌÅÎÉÀ W.3§7.ðÏÓÌÅÄÏ×ÁÔÅÌØÎÙÅ ÐÌÁÎÙ ÐÏÉÓËÁ1. áÓÉÍÐÔÏÔÉËÁ ÄÌÉÎÙ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÇÏ (M; k)-ÐÌÁÎÁ ÄÌÑ ÍÏÄÅÌÉ ÐÏÉÓËÁ á. òÅÎØÉ.2. ðÒÅÆÉËÓÎÙÊ ËÏÄ, ËÏÄÏ×ÏÅ ÄÅÒÅ×Ï, ÎÅÒÁ×ÅÎÓÔ×Ï ëÒÁÆÔÁ.3. ïÂÒÁÔÎÁÑ É ÐÒÑÍÁÑ ÔÅÏÒÅÍÙ ûÅÎÎÏÎÁ ÄÌÑ ÐÒÅÆÉËÓÎÙÈ ËÏÄÏ×.4. ôÅÏÒÅÍÁ ËÏÄÉÒÏ×ÁÎÉÑ ÄÌÑ ÁÌÆÁ×ÉÔÎÏÇÏ ËÏÄÁ.5. çÒÁÎÉÃÙ ÍÉÎÉÍÁÌØÎÏ ×ÏÚÍÏÖÎÏÇÏ ÞÉÓÌÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÈ ÇÒÕÐÐÏ×ÙÈ ÐÒÏ×ÅÒÏË × ÂÕÌÅ×ÏÊ ÍÏÄÅÌÉ ÐÏÉÓËÁ m ÄÅÆÅËÔÏ× ÓÒÅÄÉ M ÏÂßÅËÔÏ×:µlog2¶M≤ NÐÏÓ (m; M ) ≤ m log2 M:m6.
ïÃÅÎËÁ ÓÒÅÄÎÅÇÏ ÞÉÓÌÁ ÇÒÕÐÐÏ×ÙÈ ÐÒÏ×ÅÒÏË ÄÌÑ ÂÉÎÏÍÉÁÌØÎÏÊ ÍÏÄÅÌÉ ÐÏÉÓËÁ ÄÅÆÅËÔÏ×.§8.ìÏÇ-ÏÐÔÉÍÁÌØÎÙÅ ÐÏÒÔÆÅÌÉ ÉÎ×ÅÓÔÉÒÏ×ÁÎÉÑ ÎÁ ÒÙÎËÅ ÃÅÎÎÙÈ ÂÕÍÁÇ1. óËÏÒÏÓÔØ ÕÄ×ÏÅÎÉÑ ËÁÐÉÔÁÌÁ ÎÁ ÒÙÎËÅ ÃÅÎÎÙÈ ÂÕÍÁÇ É ÌÏÇ-ÏÐÔÉÍÁÌØÎÙÊ ÐÏÒÔÆÅÌØÉÎ×ÅÓÔÉÒÏ×ÁÎÉÑ.2. ÷ÙÐÕËÌÏÓÔØ ÓËÏÒÏÓÔÉ ÕÄ×ÏÅÎÉÑ É ÕÓÌÏ×ÉÑ ÌÏÇ-ÏÐÔÉÍÁÌØÎÏÓÔÉ.3. òÙÎÏË ÃÅÎÎÙÈ ÂÕÍÁÇ Ó ÄÏÐÏÌÎÉÔÅÌØÎÏÊ ÉÎÆÏÒÍÁÃÉÅÊ.4. ôÏÔÁÌÉÚÁÔÏÒ ÎÁ ÓËÁÞËÁÈ.4.
