💻 Інформатика • Математика

Теорія інформації — розв'язані задачі

6 задач: ентропія Шеннона, взаємна інформація, теорема Шеннона-Хартлі, кодування Хаффмена, код Геммінга

📊 Ентропія Шеннона
Задача 1 Ентропія джерела: нечесна монета
«Нечесна» монета: P(орел) = 0,8; P(решка) = 0,2. а) Обчисліть ентропію Шеннона H. б) Порівняйте із чесною монетою. в) При якому p максимальна ентропія?
Формула ентропії Шеннона (для двійкового джерела)
H(X) = −Σ pᵢ · log₂(pᵢ) [біт]
Підставляємо
H = −[0,8·log₂(0,8) + 0,2·log₂(0,2)]
log₂(0,8) = ln(0,8)/ln(2) = −0,2231/0,6931 = −0,3219
log₂(0,2) = ln(0,2)/ln(2) = −1,6094/0,6931 = −2,3219
H = −[0,8·(−0,3219) + 0,2·(−2,3219)]
H = −[−0,2575 − 0,4644] = −(−0,7219) ≈ 0,722 біт
б) Чесна монета (p = 0,5)
H_max = −2·[0,5·log₂(0,5)] = −[−1] = 1 біт

Нечесна монета дає менше інформації: H = 0,722 < 1 біт. в) Максимум H досягається при рівних імовірностях: p = 0,5 → H = 1 біт.

Відповідь
H ≈ 0,722 біт (менше ніж 1 біт для чесної монети); H_max при p = 0,5
Задача 2 Ентропія джерела з 4 символами
Джерело випромінює символи A, B, C, D з імовірностями P(A) = 0,5; P(B) = 0,25; P(C) = 0,125; P(D) = 0,125. Знайдіть ентропію H і середню довжину оптимального коду. (Символи — в степенях 2, тому код Хаффмена збігається з кодом Шеннона-Фано.)
Ентропія H
H = −[0,5·log₂(0,5) + 0,25·log₂(0,25) + 2·0,125·log₂(0,125)]
= −[0,5·(−1) + 0,25·(−2) + 2·0,125·(−3)]
= −[−0,5 − 0,5 − 0,75] = 1,75 біт/символ
Оптимальний код (Хаффмен) та середня довжина
СимволPКодДовжина lp·l
A0,500010,500
B0,2501020,500
C0,12511030,375
D0,12511130,375
L_avg = Σ pᵢ·lᵢ = 0,5+0,5+0,375+0,375 = 1,75 біт/символ

L_avg = H = 1,75 — ефективність 100%! Це можливо, тому що імовірності — ступені 2.

Відповідь
H = 1,75 біт/символ; L_avg = 1,75 біт (код ідеально ефективний)
📡 Ємність каналу
Задача 3 Теорема Шеннона-Хартлі для гаусівського каналу
Телефонний канал: смуга пропускання B = 3400 Гц. Відношення сигнал/шум SNR = 1000 (30 дБ). Знайдіть ємність каналу C за теоремою Шеннона–Хартлі.
Теорема Шеннона–Хартлі
C = B · log₂(1 + SNR) [біт/с]
Підставляємо
C = 3400 · log₂(1 + 1000) = 3400 · log₂(1001)
log₂(1001) = ln(1001)/ln(2) ≈ 6,9088/0,6931 ≈ 9,97
C ≈ 3400 · 9,97 ≈ 33 900 біт/с ≈ 33,9 кбіт/с

Це теоретична межа Шеннона для цього каналу. Сучасні модеми ADSL2+ досягають до ~25 Мбіт/с завдяки ширшій смузі B ~ 2,2 МГц і адаптивній модуляції.

Відповідь
C ≈ 33,9 кбіт/с (теоретична ємність телефонного каналу)
🛡️ Коди з виявленням і виправленням помилок
Задача 4 Код Геммінга (7,4) — кодування і виправлення помилки
Закодуйте 4-бітне слово D = 1011 кодом Геммінга (7,4). Потім перевірте і виправте: прийнято слово R = 1010110 (можлива одна помилка).
Структура коду Геммінга (7,4): позиції паритетних бітів — 1,2,4; даних — 3,5,6,7
Позиції: 1 2 3 4 5 6 7 Типи: p₁ p₂ d₁ p₃ d₂ d₃ d₄ = p₁ p₂ 1 p₃ 0 1 1
Обчислення паритетних бітів (парний паритет)
p₁ = d₁⊕d₂⊕d₄ = 1⊕0⊕1 = 0 (покриває поз.1,3,5,7) p₂ = d₁⊕d₃⊕d₄ = 1⊕1⊕1 = 1 (покриває поз.2,3,6,7) p₃ = d₂⊕d₃⊕d₄ = 0⊕1⊕1 = 0 (покриває поз.4,5,6,7)
Кодоване слово: 0 1 1 0 0 1 1 (позиції 1,2,3,4,5,6,7)
Перевірка прийнятого R = 1 0 1 0 1 1 0
c₁ = p₁⊕r₃⊕r₅⊕r₇ = 1⊕1⊕1⊕0 = 1 ≠ 0 → помилка c₂ = p₂⊕r₃⊕r₆⊕r₇ = 0⊕1⊕1⊕0 = 0 = 0 → ок c₃ = p₃⊕r₅⊕r₆⊕r₇ = 0⊕1⊕1⊕0 = 0 = 0 → ок Синдром: c₃c₂c₁ = 001 = 1 → помилка у позиції 1!
Виправлення: інвертуємо біт 1
R виправлений: 0 0 1 0 1 1 0 = слово 0110110
Відповідь
Кодоване: 0110011; помилка у позиції 1; виправлено: 0010110 → дані = 1011 ✓
Задача 5 Взаємна інформація I(X;Y)
Бінарний симетричний канал (BSC) з імовірністю помилки p = 0,1; вхід X: P(0) = P(1) = 0,5. Знайдіть: а) H(Y|X); б) H(Y); в) взаємну інформацію I(X;Y) — передану інформацію за один біт.
а) Умовна ентропія (ентропія помилки)
H(Y|X) = H(p) = −[p·log₂p + (1−p)·log₂(1−p)] = −[0,1·log₂(0,1) + 0,9·log₂(0,9)] = −[0,1·(−3,322) + 0,9·(−0,152)] = −[−0,332 − 0,137] = 0,469 біт
б) P(Y=1) = P(X=1)·(1−p) + P(X=0)·p = 0,5·0,9+0,5·0,1 = 0,5 → H(Y) = 1 біт
в) Взаємна інформація
I(X;Y) = H(Y) − H(Y|X) = 1 − 0,469 = 0,531 біт

Канал пропускає лише 53,1% від максимально можливої інформації через шум.

Відповідь
H(Y|X) ≈ 0,469 біт; H(Y) = 1 біт; I(X;Y) ≈ 0,531 біт/символ
Задача 6 Стиснення даних: нерівність Крафта
Чи можливо побудувати однозначно декодований префіксний код для 4 символів з довжинами кодових слів l₁=1, l₂=2, l₃=3, l₄=3? Якщо так — побудуйте його. Яка ефективність відносно ентропії H = 1,75 біт/символ (задача 2)?
Нерівність Крафта для префіксного коду
Σ 2^(−lᵢ) ≤ 1 = 2⁻¹ + 2⁻² + 2⁻³ + 2⁻³ = 0,5 + 0,25 + 0,125 + 0,125 = 1,0 ≤ 1 ✓

Нерівність виконується (з рівністю → код є «повним»). Такий код існує.

Побудова (бінарне дерево)
A → 0 (l=1) B → 10 (l=2) C → 110 (l=3) D → 111 (l=3)
Середня довжина L = 1·p(A)+2·p(B)+3·p(C)+3·p(D)
L = 1·0,5+2·0,25+3·0,125+3·0,125 = 0,5+0,5+0,375+0,375 = 1,75 біт
Ефективність = H/L = 1,75/1,75 = 100%!
Відповідь
Код існує, нерівність Крафта виконується; ефективність = 100% (H = L = 1,75 біт)
🎲 Комбінаторика 📊 Ймовірність 🔢 Лінійна алгебра 🔢 Теорія чисел 📚 Усі задачі

Методика розв'язання

Ця сторінка містить докладно розв'язані задачі з покроковими поясненнями. Мета — показати не лише відповідь, а сформувати розуміння методу, яке можна перенести на аналогічні задачі.

Електрика — фундамент сучасних технологій та енергетики.

Як вчитися на прикладах

Перед переглядом розв'язку спробуйте вирішити задачу самостійно. Якщо застрягли — зверніться до першого кроку, потім знову спробуйте самі. Пояснюйте кожен крок уголос — це радикально покращує засвоєння.

Часті запитання (FAQ)

Які методи розв'язання задач з теорія інформації демонструються на цій сторінці?
Сторінка демонструє стандартні та нестандартні методи розв'язання задач з 'Теорія інформації': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.
Якого рівня складності задачі з теорія інформації представлені?
Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.
Як вчитися на розв'язаних задачах з теорія інформації найефективніше?
Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.
Чи є в розв'язках покрокові пояснення всіх перетворень?
Так, кожен розв'язок теорія інформації містить детальні покрокові пояснення: записується перетворення, обґрунтовується його правомірність, вказуються використані теореми та формули. Підхід 'показати думку', а не лише відповідь.
Як ці задачі з теорія інформації допомагають при підготовці до контрольних та іспитів?
Розв'язані задачі з 'Теорія інформації' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.

🔗 Також за темою

🧮 Калькулятор теорії інформації та кодування 🧮 Калькулятор теорії інформації 💪 Теорія Інформації — Ентропія Шеннона, Кодування 📖 Теорія інформації: ентропія Шеннона, взаємна інформація, теорема каналу