MCP рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рдХрдиреЗрдХреНрдЯ рдХрд░реЗрдВ тЖТ

рдЧрдгрдирд╛ рджрд░реНрдЬ рдХрд░реЗрдВ

рд╣рд░ рдкрд░рд┐рдгрд╛рдо рдХреА рдкреНрд░рд╛рдпрд┐рдХрддрд╛ (рдпрд╛ рдХрдЪреНрдЪреА рдЖрд╡реГрддреНрддрд┐/рдЧрд┐рдирддреА) рджрд░реНрдЬ рдХрд░реЗрдВред рдорд╛рди рдЕрдкрдиреЗ рдЖрдк рд╕рд╛рдорд╛рдиреНрдпреАрдХреГрдд рд╣реЛ рдЬрд╛рддреЗ рд╣реИрдВред

рд╕реВрддреНрд░ (рдлреЙрд░реНрдореВрд▓рд╛)

рд╕реВрддреНрд░ (рдлреЙрд░реНрдореВрд▓рд╛): рд╢реИрдирди рдПрдиреНрдЯреНрд░реЙрдкреА рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рд╡рд┐рдЬреНрдЮрд╛рдкрди

рдкрд░рд┐рдгрд╛рдо

рд╢реИрдирди рдПрдиреНрдЯреНрд░реЙрдкреА
1.5
рдмрд┐рдЯреНрд╕
рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ 3
рдЕрдзрд┐рдХрддрдо рдПрдиреНрдЯреНрд░реЙрдкреА (log2 n) 1.585 bits
рджрдХреНрд╖рддрд╛ (H / Hmax) 94.64%

рд╢реИрдирди рдПрдиреНрдЯреНрд░реЙрдкреА рдХреНрдпрд╛ рд╣реИ?

рд╢реИрдирди рдПрдиреНрдЯреНрд░реЙрдкреА рдХрд┐рд╕реА рд░реИрдВрдбрдо рд╡реИрд░рд┐рдПрдмрд▓ рдореЗрдВ рдореМрдЬреВрдж рдЕрдирд┐рд╢реНрдЪрд┐рддрддрд╛, рдЖрд╢реНрдЪрд░реНрдп рдпрд╛ рд╕реВрдЪрдирд╛ рдХреА рдФрд╕рдд рдорд╛рддреНрд░рд╛ рдХреЛ рдорд╛рдкрддреА рд╣реИред рдЗрд╕реЗ 1948 рдореЗрдВ рдХреНрд▓реЙрдб рд╢реИрдирди рдиреЗ рдкреНрд░рд╕реНрддреБрдд рдХрд┐рдпрд╛ рдерд╛ рдФрд░ рдпрд╣реА рд╕реВрдЪрдирд╛ рд╕рд┐рджреНрдзрд╛рдВрдд (рдЗрдиреНрдлреЙрд░реНрдореЗрд╢рди рдереНрдпреЛрд░реА) рдХреА рдиреАрдВрд╡ рд╣реИред рдЬрдм рдмреЗрд╕-2 рд▓рдШреБрдЧрдгрдХ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рддреЛ рдЗрд╕реЗ рдмрд┐рдЯреНрд╕ рдореЗрдВ рдорд╛рдкрд╛ рдЬрд╛рддрд╛ рд╣реИред 1 рдмрд┐рдЯ рдХреА рдПрдиреНрдЯреНрд░реЙрдкреА рдПрдХ рдирд┐рд╖реНрдкрдХреНрд╖ рд╕рд┐рдХреНрдХреЗ рдХреЛ рдЙрдЫрд╛рд▓рдиреЗ рдЬрд┐рддрдиреА рдЕрдирд┐рд╢реНрдЪрд┐рддрддрд╛ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддреА рд╣реИред

рд╡рд┐рднрд┐рдиреНрди рдПрдВрдЯреНрд░реЙрдкреА рд╕реНрддрд░реЛрдВ рд╡рд╛рд▓реЗ рдкреНрд░рд╛рдпрд┐рдХрддрд╛ рд╡рд┐рддрд░рдгреЛрдВ рдХреЗ рддреАрди рдмрд╛рд░ рдЪрд╛рд░реНрдЯ
рдПрдВрдЯреНрд░реЙрдкреА рдПрдХрд╕рдорд╛рди рд╡рд┐рддрд░рдг рдореЗрдВ рд╕рдмрд╕реЗ рдЕрдзрд┐рдХ рдФрд░ рдЬрдм рдПрдХ рдкрд░рд┐рдгрд╛рдо рд╣рд╛рд╡реА рд╣реЛ рддрдм рд╕рдмрд╕реЗ рдХрдо рд╣реЛрддреА рд╣реИред

рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ

рд╣рд░ рд╕рдВрднрд╛рд╡рд┐рдд рдкрд░рд┐рдгрд╛рдо рдХреА рдкреНрд░рд╛рдпрд┐рдХрддрд╛ рдХреЛ рдЕрд▓реНрдкрд╡рд┐рд░рд╛рдо рдпрд╛ рд╕реНрдкреЗрд╕ рд╕реЗ рдЕрд▓рдЧ рдХрд░рдХреЗ рджрд░реНрдЬ рдХрд░реЗрдВ (рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП 0.5, 0.25, 0.25)ред рдЖрдк рдХрдЪреНрдЪреА рдЖрд╡реГрддреНрддрд┐рдпрд╛рдБ рдпрд╛ рдЧрд┐рдирддреА рднреА рджрд░реНрдЬ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВ (рдЬреИрд╕реЗ 10, 5, 5) тАФ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╣рд░ рдорд╛рди рдХреЛ рдХреБрд▓ рдпреЛрдЧ рд╕реЗ рднрд╛рдЧ рджреЗрдХрд░ рдЙрдиреНрд╣реЗрдВ рдЕрдкрдиреЗ рдЖрдк рдкреНрд░рд╛рдпрд┐рдХрддрд╛рдУрдВ рдореЗрдВ рдмрджрд▓ рджреЗрддрд╛ рд╣реИред рд╢реВрдиреНрдп рдФрд░ рдЛрдгрд╛рддреНрдордХ рдорд╛рдиреЛрдВ рдХреЛ рдирдЬрд╝рд░рдЕрдВрджрд╛рдЬрд╝ рдХрд░ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдпрд╣ рдЯреВрд▓ рдЖрдкрдХреЛ рдмрд┐рдЯреНрд╕ рдореЗрдВ рдПрдиреНрдЯреНрд░реЙрдкреА, рдЕрдзрд┐рдХрддрдо рд╕рдВрднрд╡ рдПрдиреНрдЯреНрд░реЙрдкреА рдФрд░ рд╡рд┐рддрд░рдг рдХреА рджрдХреНрд╖рддрд╛ рдмрддрд╛рддрд╛ рд╣реИред

рдлреЙрд░реНрдореВрд▓рд╛ рд╕рдордЭреЗрдВ

рдПрдиреНрдЯреНрд░реЙрдкреА рдХреА рдЧрдгрдирд╛ $$H = -\sum_{i=1}^{n} p_i \log_2 p_i \qquad p_i = \frac{x_i}{\sum_{j=1}^{n} x_j}$$ рдХреЗ рд░реВрдк рдореЗрдВ рдХреА рдЬрд╛рддреА рд╣реИ, рдЬрд┐рд╕рдореЗрдВ рд╣рд░ рдкрд░рд┐рдгрд╛рдо i рдХрд╛ рдпреЛрдЧ рд▓рд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рд╣рд░ рдкрдж рдХрд┐рд╕реА рдкрд░рд┐рдгрд╛рдо рдХреА рд╕реВрдЪрдирд╛ рдорд╛рддреНрд░рд╛, \(-\log_2 p_i\), рдХреЛ рдЙрд╕рдХреА рдЖрд╡реГрддреНрддрд┐ \(p_i\) рдХреЗ рдЕрдиреБрд╕рд╛рд░ рднрд╛рд░рд┐рдд рдХрд░рддрд╛ рд╣реИред рджреБрд░реНрд▓рдн рдШрдЯрдирд╛рдПрдБ рдЕрдзрд┐рдХ рд╕реВрдЪрдирд╛ рд▓реЗ рдЬрд╛рддреА рд╣реИрдВ; рдирд┐рд╢реНрдЪрд┐рдд рдШрдЯрдирд╛рдПрдБ (\(p_i = 1\)) рдХреЛрдИ рд╕реВрдЪрдирд╛ рдирд╣реАрдВ рджреЗрддреАрдВред \(n\) рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреЗ рд▓рд┐рдП рдЕрдзрд┐рдХрддрдо рдПрдиреНрдЯреНрд░реЙрдкреА \(\log_2(n)\) рд╣реЛрддреА рд╣реИ, рдЬреЛ рддрдм рдкреНрд░рд╛рдкреНрдд рд╣реЛрддреА рд╣реИ рдЬрдм рд╕рднреА рдкрд░рд┐рдгрд╛рдо рд╕рдорд╛рди рд░реВрдк рд╕реЗ рд╕рдВрднрд╛рд╡рд┐рдд рд╣реЛрдВред рджрдХреНрд╖рддрд╛ \(H\) рдХреЛ рдЙрд╕ рдЕрдзрд┐рдХрддрдо рдХреЗ рдкреНрд░рддрд┐рд╢рдд рдХреЗ рд░реВрдк рдореЗрдВ рджрд░реНрд╢рд╛рддреА рд╣реИред

рдкреНрд░рд╛рдпрд┐рдХрддрд╛ рдХреЗ рд╕рд╛рдкреЗрдХреНрд╖ рджреНрд╡рд┐рдЖрдзрд╛рд░реА рдПрдВрдЯреНрд░реЙрдкреА рдХрд╛ рд╡рдХреНрд░, рдЬреЛ рдЖрдзреЗ рдкрд░ рд╢рд┐рдЦрд░ рдкрд░ рд╣реИ
рджреЛ рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреЗ рд▓рд┐рдП, рдПрдВрдЯреНрд░реЙрдкреА p = 0.5 рдкрд░ 1 рдмрд┐рдЯ рдХреЗ рд╢рд┐рдЦрд░ рдкрд░ рдкрд╣реБрдБрдЪрддреА рд╣реИ рдФрд░ рдЪрд░рдо рдкрд░ 0 рд╣реЛ рдЬрд╛рддреА рд╣реИред

рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг

рдорд╛рди рд▓реАрдЬрд┐рдП рд╡рд┐рддрд░рдг {0.5, 0.25, 0.25} рд╣реИред рдПрдиреНрдЯреНрд░реЙрдкреА рд╣реЛрдЧреА: $$-[0.5\cdot\log_2(0.5) + 0.25\cdot\log_2(0.25) + 0.25\cdot\log_2(0.25)] = -[0.5\cdot(-1) + 0.25\cdot(-2) + 0.25\cdot(-2)] = 0.5 + 0.5 + 0.5 = \textbf{1.5 рдмрд┐рдЯреНрд╕}$$уАВ 3 рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреЗ рд▓рд┐рдП рдЕрдзрд┐рдХрддрдо рдПрдиреНрдЯреНрд░реЙрдкреА \(\log_2(3) \approx 1.585\) рдмрд┐рдЯреНрд╕ рд╣реЛрддреА рд╣реИ, рдЬрд┐рд╕рд╕реЗ рджрдХреНрд╖рддрд╛ рд▓рдЧрднрдЧ 94.64% рдмрдирддреА рд╣реИред

рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓

рдмрд┐рдЯреНрд╕ рд╣реА рдХреНрдпреЛрдВ? рдмреЗрд╕ 2 рдХреЗ рд▓рдШреБрдЧрдгрдХ рд╕реЗ рдПрдиреНрдЯреНрд░реЙрдкреА рдмрд┐рдЯреНрд╕ рдореЗрдВ рдорд┐рд▓рддреА рд╣реИ, рдЬреЛ рдбрд┐рдЬрд┐рдЯрд▓ рд╕реВрдЪрдирд╛ рдХреА рд╕реНрд╡рд╛рднрд╛рд╡рд┐рдХ рдЗрдХрд╛рдИ рд╣реИред рдмреЗрд╕ e рд╕реЗ "рдиреИрдЯреНрд╕" (nats) рдФрд░ рдмреЗрд╕ 10 рд╕реЗ "рд╣рд╛рд░реНрдЯрд▓реА" (hartleys) рдорд┐рд▓рддреЗ рд╣реИрдВред

рдХреНрдпрд╛ рдореЗрд░реА рдкреНрд░рд╛рдпрд┐рдХрддрд╛рдУрдВ рдХрд╛ рдпреЛрдЧ 1 рд╣реЛрдирд╛ рдЬрд╝рд░реВрд░реА рд╣реИ? рдирд╣реАрдВ тАФ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд┐рд╕реА рднреА рдзрдирд╛рддреНрдордХ рдорд╛рди рдХреЛ рд╕рд╛рдорд╛рдиреНрдпреАрдХреГрдд рдХрд░ рджреЗрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рдЖрдк рдХрдЪреНрдЪреА рдЧрд┐рдирддреА рд╕реАрдзреЗ рдкреЗрд╕реНрдЯ рдХрд░ рд╕рдХрддреЗ рд╣реИрдВред

рдЕрдзрд┐рдХрддрдо рдПрдиреНрдЯреНрд░реЙрдкреА рдХреНрдпрд╛ рд╣реЛрддреА рд╣реИ? \(n\) рд╕рдорд╛рди рд░реВрдк рд╕реЗ рд╕рдВрднрд╛рд╡рд┐рдд рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреЗ рд▓рд┐рдП рдпрд╣ \(\log_2(n)\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддреА рд╣реИред рдПрдХ рдирд┐рд╖реНрдкрдХреНрд╖ рд╕рд┐рдХреНрдХреЗ (\(n=2\)) рдХреА рдЕрдзрд┐рдХрддрдо рдПрдиреНрдЯреНрд░реЙрдкреА 1 рдмрд┐рдЯ рд╣реИ; рдПрдХ рдирд┐рд╖реНрдкрдХреНрд╖ рдкрд╛рд╕реЗ (\(n=6\)) рдХреА рд▓рдЧрднрдЧ 2.585 рдмрд┐рдЯреНрд╕ред

рдЕрдВрддрд┐рдо рдЕрдкрдбреЗрдЯ: