Частина ІІ. Нерівноймовірні події
Частина І. Рівноймовірні події
1.У змаганні беруть участь 4 команди. Скільки інформації в повідомленні, що виграла 3-я команда?
2. Кулька знаходиться в одному з 64 ящичків. Скільки одиниць інформації буде містити повідомлення про те, де знаходиться кулька?
3. При вгадуванні цілого числа в певному діапазоні було отримано 8 біт інформації. Скільки чисел містив цей діапазон?
5. Скільки біт інформації несе повідомлення про те, що з колоди з 32 карти дістали даму пік?
6. Кулька знаходиться в одній з трьох урн: А, В або С. Визначити, скільки біт інформації містить повідомлення про те, що він знаходиться в урні.
7. Ви кидаєте два кубики з нанесеними на гранях цифрами від 1 до 6. Визначте, скільки біт інформації несе повідомлення, що на одному кубику випала трійка, а на іншому - п'ятірка.
8. Проводяться дві лотереї: "4 з 32" і "5 з 64". Повідомлення про результати який з лотерей несе більше інформації?
9. "Ви виходите на наступній зупинці?" - запитали людини в автобусі. "Немає", - відповів він. Скільки інформації містить відповідь?
10. Задано число з проміжку від 1 до 64. Яку кількість інформації необхідно для вгадування числа з цього проміжку?
11. Яку кількість інформації отримає другий гравець в грі "Вгадай число" при правильній стратегії, якщо гравець загадав число з інтервалу від 1 до 128?
12. Яку кількість інформації отримає перший гравець після першого ходу другого гравця в грі в "хрестики-нулі" на полі 3 на 3?
13. Як було кількість можливих подій, якщо після реалізації одного з них ми отримали кількість інформації рівне 3 біти? 7 біт?
14. Який обсяг інформації містить повідомлення, що зменшує невизначеність знань у 8 разів?
15. Ви підійшли до світлофора, коли горів жовте світло. Після цього загорівся зелений. Яку кількість інформації ви при цьому отримали?
16. Скільки біт інформації несе повідомлення про те, що на світлофорі горить зелене світло?
17. На залізничному вокзалі 8 шляхів відправлення поїздів. Вам повідомили, що ваш поїзд прибуває на четвертий шлях. Скільки інформації ви отримали?
18. Була отримана телеграма: "Зустрічайте, вагон 7". Відомо, що у складі поїзда 16 вагонів. Яку кількість інформації було отримано?
19. При вгадуванні цілого числа в діапазоні від 1 до N було отримано 9 біт інформації. Чому одно N?
20. При вгадуванні цілого числа в певному діапазоні було отримано 8 біт інформації. Скільки чисел містить цей діапазон?
21. Повідомлення про те, що ваш друг живе на 10 поверсі, несе 4 біти інформації. Скільки поверхів у будинку?
22. Скільки інформації несе повідомлення про те, що з колоди карт дістали
- карту чорної масті?
- карту бубнової масті?
- одну карту?
23. В шкільній бібліотеці 16 стелажів з книгами. На кожному стелажі 8 полиць. Яку кількість інформації міститься в повідомленнях
- "книга лежить на 2 полиці"?
- "книга знаходиться на 5-ом стелажі на 3 полиці"?
24. Загадане слово з 10 букв. Ви просите відкрити п'яту літеру. Вам її відкрили. Скільки інформації ви отримали?
25. Яку кількість інформації несе повідомлення: "Зустріч призначена на травень"?
26. Проводяться дві лотереї: "5 з 30" і "3 з 42". Повідомлення про результати який з лотерей несе більше інформації?
27. Проводиться лотерея "6 з 42".
А) Скільки біт інформації ми отримуємо при випаданні 1-го кулі з 42?
Б) Скільки біт інформації ми отримуємо при випаданні 3-го кулі з 41)?
В) Яке кількість інформації несе повідомлення про результати лотереї?
Частина ІІ. Нерівноймовірні події
1. У коробці 5 синіх і 15 червоних кульок. Яку кількість інформації несе повідомлення, що з коробки дістали синій м'яч?
2. В коробці знаходяться кубики трьох кольорів: червоного, жовтого і зеленого. Причому жовтих в два рази більше червоних, зелених на 6 більше, ніж жовтих. Повідомлення про те, що з коробки випадково витягли жовтий кубик, містило 2 біти інформації. Скільки було зелених кубиків?
3. Студенты групи вивчають один з трьох мов: англійська, німецька або французька. Причому 12 студентів не вчать англійську. Повідомлення, що випадково обраний студент Петров вивчає англійську, несе log23 біт інформації, а що Іванов вивчає французьку - 1 біт. Скільки студентів вивчають німецьку мову?
4. У колоді міститься 32 карти. З неї навмання взяли 2 карти. Яку кількість інформації несе повідомлення про те, що обрані туз і король однієї масті?
5. На складі 16 вагонів, серед яких - купейні, П - плацкартні і СВ - спальні. Повідомлення про те, що ваш друг прибуває у СВ, несе 3 біти інформації. Визначте, скільки в поїзді вагонів СВ.
6. Ученики класу, що складається з 21 людини, вивчають німецька або французька мови. Повідомлення про те, що учень A вивчає німецьку мову, несе log23 біт інформації. Скільки людей вивчають французьку мову?
7. Визначити, яка кількість інформації несе літеру "О", використовуючи таблиці 2 частот появи букв в російському тексті.
Табл. 2
| Буква | Частота | Буква | Частота | Буква | Частота | Буква | Частота | |
| пробел | 0,175 | o | 0,090 | е, ë | 0,072 | а | 0,062 | |
| и | 0,062 | т | 0,053 | н | 0,053 | с | 0,045 | |
| р | 0,040 | в | 0,038 | л | 0,035 | к | 0,028 | |
| м | 0,026 | д | 0,025 | п | 0,023 | у | 0,021 | |
| я | 0,018 | ы | 0,016 | з | 0,016 | ъ, ь | 0,014 | |
| б | 0,014 | г | 0,013 | ч | 0,012 | й | 0,010 | |
| х | 0,009 | ж | 0,007 | ю | 0,006 | ш | 0,006 | |
| ц | 0,004 | щ | 0,003 | э | 0,003 | ф | 0,002 | |
8. В кошику лежать 8 чорних куль і 24 білих. Скільки інформації несе повідомлення про те, що дістали чорний шар?
9. У коробці лежать 64 кольорові олівці. Повідомлення про те, що дістали білий олівець, несе 4 біти інформації. Скільки білих олівців було в коробці?
10. У класі 30 осіб. За контрольну роботу з математики отримано 6 п'ятірок, 15 четвірок, 8 трійок і 1 двійка. Яку кількість інформації в повідомленні про те, що Іванов отримав четвірку?
11. За чверть учень отримав 100 оцінок. Повідомлення про те, що він отримав четвірку, несе 2 біти інформації. Скільки четвірок учень отримав за чверть?
12. У ящику лежать рукавички (білі та чорні). Серед них - 2 пари чорних. Повідомлення про те, що з ящика дістали пару чорних рукавичок, несе 4 біти інформації. Скільки всього пар рукавичок було в ящику?
13. Для ремонту школи використовували білу, синю і коричневу фарби. Витратили однакову кількість банок білою та синьою фарби. Повідомлення про те, що закінчилася банку білої фарби, несе 2 біти інформації. Синя фарба витратили 8 банок. Скільки банок коричневої фарби витратили на ремонт школи?
14. В кошику лежать білі і чорні кулі. Серед них 18 чорних куль. Повідомлення про те, що з кошика дістали білий шар, несе 2 біти інформації. Скільки всього в кошику куль?
15. На зупинці зупиняються тролейбуси з різними номерами. Повідомлення про те, що до зупинки підійшов тролейбус з номером N1 несе 4 біти інформації. Ймовірність появи на зупинки тролейбуса з номером N2 у два рази менше, ніж імовірність появи тролейбуса з номером N1. Скільки інформації несе повідомлення про появу на зупинки тролейбуса з номером N2?
ТЕМА: «КІЛЬКІСТЬ ІНФОРМАЦІЇ. АЛФАВІТНИЙ ПІДХІД»
Розробити програму, що дозволяє реалізувати завдання згідно з номером варіанта.
Варіанти обирать по формулі N mod 21, де N – номер по списку.
1. Скільки різних символів, закодованих байтами, міститься в повідомленні:
1101001100011100110100110001110001010111?
2. Для запису листа був використаний алфавіт потужністю 16 символів. Лист складалося з 25 рядків. У кожному рядку разом з пробілами було 64 символи. Скільки байт інформації містив лист?
3. Лист складалося з 30 рядків. У кожному рядку разом з пробілами за 48 символів. Лист містив 900 байт інформації. Яка потужність алфавіту (кількість символів), яким було написано лист?
4. Дані два тексту, що містять однакову кількість символів. Перший текст складається з алфавіту потужністю 16 символів, а другий текст - з 256 символів. У скільки разів інформації в другому тексті більше, ніж у першому?
5. У будинку 160 квартир. Скільки біт повинно містити двійкове слово, щоб закодувати у це будинку двійковим кодом всі квартири?
6. Звичайний дорожній світлофор без додаткових секцій подає шість видів сигналів (безперервні червоний, жовтий і зелений миготливий жовтий, миготливий зелений миготливий червоний і жовтий одночасно). Електронний пристрій управління світлофором послідовно відтворює записані сигнали. Поспіль записано 100 сигналів світлофора. Визначити, скільки становить в байтах даний інформаційний обсяг:
1) 37; 2) 38; 3) 50; 4) 100.
7. Яка мінімальна потужність алфавіту, за допомогою якого можна передавати інформацію?
8. Яке максимально можливе число символів може містити алфавіт, у якого розрядність двійкового коду дорівнює 6?
9. При складанні повідомлення використовували 128-символьний алфавіт. Яким буде інформаційний обсяг такого повідомлення, якщо воно містить 2048 символів?
10. Скільки символів містить повідомлення, записане за допомогою 256-символьного алфавіту, якщо його обсяг склав 1/32 Мбайта?
11. Інформаційне повідомлення об'ємом 2,5 Кб містить 2560 символів. Чому дорівнює потужність алфавіту, за допомогою якого було записано це повідомлення?
12. Для запису повідомлення використовувався 128-символьний алфавіт. Кожна сторінка містить 25 рядків. Всі повідомлення містить 8750 байт і займає 5 сторінок. Скільки символів у рядку?
13. Два тексту містять однакову кількість символів. Перший текст складений в алфавіті потужністю 4 символи, другий - 16 символів. У скільки разів відрізняється кількість інформації в цих текстах?
14. Букви латинського алфавіту закодовані наступним чином:
A B C D E
000 01 100 10 011
Визначте, який набір букв закодований двійковій рядком 0110100011000.
1) ЕВСЕА; 2) BDDEA; 3) BDCEA; 4) EBAEA.
15. В кодуванні Unicode кожен символ кодується 16 бітами. Який інформаційний обсяг наступного повідомлення?
2+2=4, а 5+5=10.
1) 16 біт; 2) 256 біт; 3) 12 байтів; г) 16 байт.
16. Автоматичний пристрій здійснило перекодування інформаційного повідомлення російською мовою, спочатку записаного в 16-бітовому коді Unicode, 8-бітове кодування КОІ-8. При цьому інформаційне повідомлення зменшилася на 480 біт. Яка довжина повідомлення в символах?
1) 30; 2) 60; 3) 120; 4) 480.
17. Азбуки Морзе дозволяє кодувати символи для радіозв'язку, задаючи комбінацію з точок і тире. Скільки різних символів (цифр, символів, знаків пунктуації і т.д.) можна закодувати, використовуючи код Морзе довжиною не менше п'яти і не більше шести сигналів (точок і тире)?
1) 80; 2) 120; 3) 112; 4) 58.
18. Табло світлове складається з лампочок, кожна з яких може перебувати у двох станах ("увімкнено" або "вимкнено"). Яку найменшу кількість лампочок повинно знаходитися на табло, щоб з його допомогою можна було передати 120 різних сигналів?
1) 5; 2) 6; 3) 7; 4) 8.
19. Табло світлове складається з лампочок. Кожна лампочка може перебувати в одному з трьох станів ("увімкнено", "вимкнено" або "блимає"). Яку найменшу кількість лампочок повинно знаходитися на табло, щоб з його допомогою можна було передавати 18 різних сигналів?
1) 6; 2) 5; 3) 3; 4) 4.
20. У велокроссе беруть участь 119 спортсменів. Спеціальний пристрій реєструє проходження кожним з учасників проміжного фінішу, записуючи його номер з використанням мінімального можливої кількості біт, однакового для кожного спортсмена. Який інформаційний обсяг повідомлення, записаного пристроєм, після того, як проміжний фініш пройшли 70 велосипедистів?
1) 70 біт; 2) 70 байт; 3) 490 біт; 4) 119 байт.
21. Даний текст розміром 600 символів. Відомо, що символи беруться з таблиці розміром 16х32. Визначити інформаційний обсяг тексту в бітах.
1) 1000; 2) 2400; 3) 3600; 4) 5400
ТЕМА: «ЕНТРОПІЯ»
Розробити програму, що дозволяє реалізувати завдання згідно з номером варіанта.
1. Визначити ентропію системи, що складається з двох підсистем. Перша підсистема складається з трьох елементів, кожен з яких може перебувати у двох станах з вірогідністю 0.15 і 0.75. Друга підсистема складається з двох елементів, кожен з яких може перебувати в трьох станах з вірогідністю 0.2, 0.4, 0.4.
2. Визначити ентропію ієрархічної системи, заданої графом, якщо кожен елемент системи з однаковою ймовірністю може знаходитися в чотирьох станах.
3. Визначити ентропію джерела повідомлень, якщо він виробляє символи "а", "б", "т", "щ", "п" російського алфавіту. Розподіл ймовірностей букв у російських текстах наведено в таблиці 2.
4. Визначити ентропію системи, що складається з двох підсистем. Перша підсистема складається з двох елементів, кожен з яких може перебувати у двох станах з вірогідністю 0.45 і 0.55. Друга підсистема складається з трьох елементів, кожен з яких може перебувати у двох станах з вірогідністю 0.2, 0.8.
5. Визначити ентропію ієрархічної системи, заданої графом, якщо кожен елемент системи з однаковою ймовірністю може перебувати в трьох станах.
6. Визначити ентропію джерела повідомлень, якщо він виробляє символи "е", "о", "р", "п", "у" російського алфавіту. Розподіл ймовірностей букв у російських текстах наведено в таблиці 2.
7. Визначити ентропію системи, що складається з двох підсистем. Перша підсистема складається з двох елементів, кожен з яких може перебувати у двох станах равновероятно. Друга підсистема складається з трьох елементів, кожен з яких може перебувати в трьох станах з вірогідністю 0.2, 0.75, 0.05.
8. Визначити ентропію ієрархічної системи, заданої графом, якщо кожен елемент системи з однаковою ймовірністю може перебувати у двох станах.
9. Визначити ентропію джерела повідомлень, якщо він виробляє символи "и", "м", "с", "й", "ф" російського алфавіту. Розподіл ймовірностей букв у російських текстах наведено в таблиці 2.
10. Визначити ентропію системи, що складається з трьох підсистем. Перша підсистема складається з двох елементів, кожен з яких може перебувати в трьох станах равновероятно. Друга підсистема складається з трьох елементів, кожен з яких може перебувати у двох станах равновероятно. Третя підсистема складається з двох елементів, кожен з яких може перебувати у двох станах з вірогідністю 0.7, 0.3.
11. Визначити ентропію ієрархічної системи, заданої графом, якщо кожен елемент нульового і першого рівнів системи можуть з однаковою ймовірністю перебувати у двох станах, а елементи інших рівнів - в трьох.
12. Визначити ентропію джерела повідомлень, якщо він виробляє символи "е", "в", "г", "д", "р" російського алфавіту. Розподіл ймовірностей букв у російських текстах наведено в таблиці 2.
13. Визначити ентропію системи, що складається з трьох підсистем. Перша підсистема складається з чотирьох елементів, кожен з яких може перебувати у двох станах равновероятно. Друга підсистема складається з двох елементів, кожен з яких може перебувати у двох станах равновероятно. Третя підсистема складається з трьох елементів, кожен з яких може перебувати у двох станах з вірогідністю 0.35, 0.65.
14. Визначити ентропію ієрархічної системи, заданої графом, якщо кожен елемент нульового і першого рівнів системи можуть з однаковою ймовірністю перебувати в трьох станах, а елементи інших рівнів - у двох.
15. Визначити ентропію джерела повідомлень, якщо він виробляє символи "ь", "о", "н", "у", "з" російського алфавіту. Розподіл ймовірностей букв у російських текстах наведено в таблиці 2.
16. Визначити ентропію системи, що складається з трьох підсистем. Перша підсистема складається з трьох елементів, кожен з яких може перебувати в п'яти станах равновероятно. Друга підсистема складається з трьох елементів, кожен з яких може перебувати в трьох станах равновероятно. Третя підсистема складається з чотирьох елементів, кожен з яких може перебувати у двох станах з вірогідністю 0.81, 0.19.
17. Визначити ентропію ієрархічної системи, заданої графом, якщо кожен елемент нульового, першого і другого рівнів системи можуть з однаковою ймовірністю перебувати у двох станах, а елементи інших рівнів - в трьох.
18. Визначити ентропію джерела повідомлень, якщо він виробляє символи "н", "а", "г", "с", "ч" російського алфавіту. Розподіл ймовірностей букв у російських текстах наведено в таблиці 2.
ТЕМА: «УМОВНА ЕНТРОПІЯ»
Розробити програму, що дозволяє реалізувати завдання згідно з номером варіанта.
1. Скласти довільну канальну матрицю розміром 3*3 з боку джерела повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку при рівноймовірній появі символів в повідомленні.
2. Скласти довільну канальну матрицю розміром 3*3 з боку джерела повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку при ймовірностях p(a1)=0.3, p(a2)=0.5, p(a3)=0.2.
3. При передачі повідомлень по каналу зв'язку з шумами була отримана наступна статистика: літера "а "з 100 разів була прийнята (95-i) раз, де i - номер варіанта, літеру "б" з 100 разів була прийнята (94-i) раз, буква "в" з 100 разів була прийнята (96-i) раз, буква "г" з 100 разів була прийнята (96-i) разів. Довизначте самостійно відсутні ймовірності та побудуйте канальну матрицю з боку джерела повідомлень. Визначте ентропію отриманих повідомлень.
4. Скласти довільну канальну матрицю розміром 4*4 з боку джерела повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку при рівноймовірній появі символів в повідомленні.
5. Скласти довільну канальну матрицю розміром 4*4 з боку джерела повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку при ймовірностях p(a1)=0.15, p(a2)=0.4, p(a3)=0.25, p(a4)=0.2.
6. При передачі повідомлень по каналу зв'язку з шумами була отримана наступна статистика: цифра "1" з 100 разів була прийнята (94-i) раз, де i - номер варіанта, цифра "2" з 100 разів була прийнята (93-i) раз, цифра "3" з 100 разів була прийнята (97-i) раз, цифра "4" з 100 разів була прийнята (95-i) разів. Довизначте самостійно відсутні ймовірності та побудуйте канальну матрицю з боку джерела повідомлень. Визначте ентропію отриманих повідомлень.
7. Скласти довільну канальну матрицю розміром 3*3 з боку приймача повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку, якщо символи алфавіту, з якого складено повідомлення, - рівноймовірні.
8. Скласти довільну канальну матрицю розміром 3*3 з боку приймача повідомлень. Обчислити ентропію приймача повідомлень, якщо символи алфавіту, з якого складено повідомлення, - рівноймовірні.
9. Скласти довільну канальну матрицю розміром 3*3 з боку приймача повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку при ймовірностях p(b1)=0.1, p(b2)=0.4, p(b3)=0.5.
10. При передачі повідомлень по каналу зв'язку з шумами була отримана наступна статистика: символ "*" з 100 разів був прийнятий (98-i) раз, де i - номер варіанта, символ "/" з 100 разів був прийнятий (94-i) раз, символ "+" з 100 разів був прийнятий (95-i) раз, символ "-" з 100 разів був прийнятий (96-i) разів. Довизначте самостійно відсутні ймовірності та побудуйте канальну матрицю з боку джерела повідомлень. Визначте ентропію отриманих повідомлень.
11. Скласти довільну канальну матрицю розміром 4*4 з боку приймача повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку, якщо символи алфавіту, з якого складено повідомлення, - рівноймовірні.
12. Скласти довільну канальну матрицю розміром 3*3 з боку приймача повідомлень. Обчислити ентропію приймача повідомлень, якщо символи алфавіту, з якого складено повідомлення, мають ймовірності p(a1)=0.4, p(a2)=0.25, p(a3)=0.35.
13. Скласти довільну канальну матрицю розміром 4*4 з боку приймача повідомлень. Обчислити повну умовну ентропію повідомлень, переданих по даному каналу зв'язку при ймовірностях p(b1)=0.25, p(b2)=0.2, p(b3)=0.05, p(b4)=0.5.
14. Скласти довільну канальну матрицю розміром 4*4 з боку приймача повідомлень. Обчислити ентропію приймача повідомлень, якщо символи алфавіту, з якого складено повідомлення, - рівноймовірні.
15. При передачі повідомлень по каналу зв'язку з шумами була отримана наступна статистика: буква "x" з 100 разів була прийнята (100-i) раз, де i - номер варіанта, буква "y" з 100 разів була прийнята (99-i) раз, буква "z" з 100 разів була прийнята (98-i) разів. Довизначте самостійно відсутні ймовірності та побудуйте канальну матрицю з боку джерела повідомлень. Визначте ентропію отриманих повідомлень.
16. Скласти довільну канальну матрицю розміром 5*5 з боку приймача повідомлень. Обчислити ентропію приймача повідомлень, якщо символи алфавіту, з якого складено повідомлення, - рівноймовірні.
17. Скласти довільну канальну матрицю розміром 4*4 з боку приймача повідомлень. Обчислити ентропію приймача повідомлень, якщо символи алфавіту, з якого складено повідомлення, мають ймовірності p(a1)=0.3, p(a2)=0.25, p(a3)=0.35, p(a4)=0.1.
18. Скласти довільну канальну матрицю розміром 5*5 з боку приймача повідомлень. Обчислити ентропію приймача повідомлень, якщо символи алфавіту, з якого складено повідомлення, мають ймовірності p(a1)=0.1, p(a2)=0.2, p(a3)=0.2, p(a4)=0.25, p(a5)=0.25.
ТЕМА: «КВАНТУВАННЯ ІНФОРМАЦІЇ. РІВНОМІРНА ДИСКРЕТИЗАЦІЯ»
Розробити програму, що дозволяє реалізувати завдання згідно з номером варіанта.
Необхідно вибрати функцію y=f(x) згідно з варіантом завдання, наведеним у таблиці 3. Значення x змінюються від xmin до xmax. Проконтролювати правильність введення xmin, xmax, кроку дискретизації і коректність обчислюваного вирази.
Побудувати 4 графіка обраної функції так, щоб на них були представлені:
1) аналоговий сигнал - безперервна функція безперервного аргументу (вибирається найменше з можливих прибутків Dx);
2) безперервна функція дискретного аргументу (Dx вибирається істотним);
3) дискретна безперервного аргументу;
4) цифровий сигнал - дискретна дискретного аргументу.
При побудові дискретних функцій для всіх варіантів завдань значення функції необхідно ототожнювати з найближчим рівнем квантування.
Подання графіків можна організувати одним з наступних способів:
1) відображає графіки послідовно один за іншим, перемикання між графіками здійснювати по натисканню клавіші;
2) розбити екран на 4 області, в кожній з яких відображати свій графік.
Примітки.
1) Осі і відліки графіків повинні бути підписані.
2) Перед побудовою графіка необхідно перевірити існування функції у всіх точках, тобто коректно обробляти розриви функції.
Табл. 3
1.  | 2.  |
3.  | 4.  |
5.  | 6.  |
7.  | 8.  |
9.  | 10.  |
11.  | 12.  |
13.  | 14.  |
15.  | 16.  |
17.  | 18.  |
19.  | 20.  |
21.  | 22.  |
23.  | 24.  |
25.  | 26.  |
27.  | 28.  |
29.  | 30.  |
ТЕМА: «КОДУВАННЯ ІНФОРМАЦІЇ. ТАБЛИЧНЕ ПОДАННЯ»
Розробити програму, що дозволяє реалізувати завдання згідно з номером варіанта.
Побудувати код і представити його у вигляді таблиці перекодування.
В первинний алфавіт включити символи, з яких складаються власне прізвище, ім'я та по батькові студента + спеціальні символи (пробіл, точка, кома і т.д.). Символи в таблиці перекодування сортувати за алфавітом.
Програма повинна налаштовуватися на роботу в десятковій системі числення і в тій, що наведена в таблиці 5 згідно з номером у списку.
Програма в діалоговому режимі повинна запитувати у користувача слова/фрази російською мовою (ті, які можна скласти із символів первинного алфавіту - інакше видати повідомлення про помилку!) і виводити їх у закодованому вигляді, користуючись таблицею перекодування.
Виконати завдання для двох систем числення!
Визначити, чи є отриманий код рівномірним/нерівномірним, повним/неповним.
Табл. 5
| № по списку | Основа системи числення |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| |
Приклад.
ПІБ студента - Петренко Николай Степанович, за списком № 2.
1) Основа системи числення - 3.
Таблиця перекодування:
а 0
в 1
е 2
и 10
й 11
…
або (за вибором студента)
а 00
в 01
е 02
и 10
й 11
…
Перекодування:
Введено: ива
Получимо: 10 1 0
або 10 01 00
2) Основа системи числення – 10.
Таблиця перекодування:
а 0
в 1
е 2
и 3
й 4
…
Перекодування:
Введено: ива
Получимо: 3 1 0
ТЕМА: «КОДУВАННЯ ІНФОРМАЦІЇ.
ПРЕФІКСНІ КОДИ»
Розробити програму, що дозволяє реалізувати завдання згідно з номером варіанта.
В первинний алфавіт включити символи, з яких складаються власне прізвище, ім'я та по батькові студента + пробіл. Символи в таблиці перекодування сортування за алфавітом.
Програма повинна налаштовуватися на роботу в системі числення, наведеною в таблиці 6 згідно з номером у списку.
Програма повинна вивести ПІБ студента у вигляді префиксных кодів (тільки в текстовому вигляді, без побудови дерев!). Для кожної префиксной комбінації визначити префікси/суфікси.
Табл. 6
| № по списку | Основа системи счислення |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| |
ТЕМА: «ПОБУДОВА ОПТИМАЛЬНИХ НЕРІВНОМІРНИХ КОДІВ.
МЕТОД ШЕННОНА-ФАНО»
Розробити програму, що дозволяє в наочному вигляді провести формування оптимальних нерівномірних кодів за методом Шеннона-Фано для символів первинного алфавіту з вірогідністю, наведеними в таблиці 7.
Примітка: "ОС" означає "обчислити самостійно" (сума ймовірностей символів повинна дорівнювати 1).
Обчислити довжини для отриманих кодових комбінацій і середню довжину lср.
Табл. 7
| № по списку | А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 |
| | 0.11 | 0.21 | 0.031 | 0.041 | 0.051 | 0.061 | 0.071 | ОС |
| | 0.12 | 0.22 | 0.032 | 0.042 | 0.052 | 0.062 | ОС | 0.082 |
| | 0.13 | 0.23 | 0.033 | 0.043 | 0.053 | ОС | 0.073 | 0.083 |
| | 0.14 | 0.24 | 0.034 | 0.044 | ОС | 0.064 | 0.074 | 0.084 |
| | 0.15 | 0.25 | 0.035 | ОС | 0.055 | 0.065 | 0.075 | 0.085 |
| | 0.16 | 0.26 | ОС | 0.046 | 0.056 | 0.066 | 0.076 | 0.086 |
| | 0.17 | ОС | 0.037 | 0.047 | 0.057 | 0.067 | 0.077 | 0.087 |
| | ОС | 0.28 | 0.038 | 0.048 | 0.058 | 0.068 | 0.078 | 0.088 |
| | 0.11 | 0.021 | 0.31 | 0.041 | 0.051 | 0.061 | 0.071 | ОС |
| | 0.12 | 0.022 | 0.32 | 0.042 | 0.052 | 0.062 | ОС | 0.082 |
| | 0.13 | 0.023 | 0.33 | 0.043 | 0.053 | ОС | 0.073 | 0.083 |
| | 0.14 | 0.024 | 0.34 | 0.044 | ОС | 0.064 | 0.074 | 0.084 |
| | 0.15 | 0.025 | 0.35 | ОС | 0.055 | 0.065 | 0.075 | 0.085 |
| | 0.16 | 0.026 | ОС | 0.046 | 0.056 | 0.066 | 0.076 | 0.086 |
| | 0.17 | ОС | 0.37 | 0.047 | 0.057 | 0.067 | 0.077 | 0.087 |
| | ОС | 0.028 | 0.38 | 0.048 | 0.058 | 0.068 | 0.078 | 0.088 |
| | 0.011 | 0.21 | 0.031 | 0.041 | 0.0051 | 0.061 | 0.071 | ОС |
| | 0.012 | 0.22 | 0.032 | 0.042 | 0.0052 | 0.062 | ОС | 0.082 |
| | 0.013 | 0.23 | 0.033 | 0.043 | 0.0053 | ОС | 0.073 | 0.083 |
| | 0.014 | 0.24 | 0.034 | 0.044 | ОС | 0.064 | 0.074 | 0.084 |
| | 0.015 | 0.25 | 0.035 | ОС | 0.0055 | 0.065 | 0.075 | 0.085 |
| | 0.016 | 0.26 | ОС | 0.046 | 0.0056 | 0.066 | 0.076 | 0.086 |
| | 0.017 | ОС | 0.037 | 0.047 | 0.0057 | 0.067 | 0.077 | 0.087 |
| | ОС | 0.28 | 0.038 | 0.048 | 0.0058 | 0.068 | 0.078 | 0.088 |
| | 0.011 | 0.22 | 0.033 | 0.044 | 0.0055 | 0.066 | 0.077 | ОС |
ТЕМА: «ПОБУДОВА ОПТИМАЛЬНИХ НЕРІВНОМІРНИХ КОДІВ.
МЕТОД ХАФФМЕНА»
Розробити програму, що дозволяє в наочному вигляді провести формування оптимальних нерівномірних кодів за методом Хаффмена для символів первинного алфавіту з вірогідністю, наведеними в таблиці 8.
Примітка: "ОС" означає "обчислити самостійно" (сума ймовірностей символів повинна дорівнювати 1).
Обчислити довжини для отриманих кодових комбінацій і середню довжину lср.
Табл. 8
| № по списку | А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 |
| | 0.011 | 0.22 | 0.033 | 0.044 | 0.0055 | 0.066 | 0.077 | ОС |
| | ОС | 0.28 | 0.038 | 0.048 | 0.0058 | 0.068 | 0.078 | 0.088 |
| | 0.017 | ОС | 0.037 | 0.047 | 0.0057 | 0.067 | 0.077 | 0.087 |
| | 0.016 | 0.26 | ОС | 0.046 | 0.0056 | 0.066 | 0.076 | 0.086 |
| | 0.015 | 0.25 | 0.035 | ОС | 0.0055 | 0.065 | 0.075 | 0.085 |
| | 0.014 | 0.24 | 0.034 | 0.044 | ОС | 0.064 | 0.074 | 0.084 |
| | 0.013 | 0.23 | 0.033 | 0.043 | 0.0053 | ОС | 0.073 | 0.083 |
| | 0.012 | 0.22 | 0.032 | 0.042 | 0.0052 | 0.062 | ОС | 0.082 |
| | 0.011 | 0.21 | 0.031 | 0.041 | 0.0051 | 0.061 | 0.071 | ОС |
| | ОС | 0.028 | 0.38 | 0.048 | 0.058 | 0.068 | 0.078 | 0.088 |
| | 0.17 | ОС | 0.37 | 0.047 | 0.057 | 0.067 | 0.077 | 0.087 |
| | 0.16 | 0.026 | ОС | 0.046 | 0.056 | 0.066 | 0.076 | 0.086 |
| | 0.151 | 0.125 | 0.135 | ОС | 0.155 | 0.165 | 0.075 | 0.085 |
| | 0.14 | 0.024 | 0.34 | 0.044 | ОС | 0.064 | 0.074 | 0.084 |
| | 0.13 | 0.023 | 0.33 | 0.043 | 0.053 | ОС | 0.073 | 0.083 |
| | 0.12 | 0.022 | 0.32 | 0.042 | 0.052 | 0.062 | ОС | 0.082 |
| | 0.11 | 0.021 | 0.31 | 0.041 | 0.051 | 0.061 | 0.071 | ОС |
| | ОС | 0.28 | 0.038 | 0.048 | 0.058 | 0.068 | 0.078 | 0.088 |
| | 0.17 | ОС | 0.037 | 0.047 | 0.057 | 0.067 | 0.077 | 0.087 |
| | 0.16 | 0.26 | ОС | 0.046 | 0.056 | 0.066 | 0.076 | 0.086 |
| | 0.15 | 0.25 | 0.035 | ОС | 0.055 | 0.065 | 0.075 | 0.085 |
| | 0.14 | 0.24 | 0.034 | 0.044 | ОС | 0.064 | 0.074 | 0.084 |
| | 0.13 | 0.23 | 0.033 | 0.043 | 0.053 | ОС | 0.073 | 0.083 |
| | 0.12 | 0.22 | 0.032 | 0.042 | 0.052 | 0.062 | ОС | 0.082 |
| | 0.11 | 0.21 | 0.031 | 0.041 | 0.051 | 0.061 | 0.071 | ОС |
ТЕМА: «ПОБУДОВА ЛІНІЙНИХ ГРУПОВИХ КОДІВ.
КОД ХЕММІНГА»
Розробити програму, що дозволяє в наочному вигляді продемонструвати побудову коду Хеммінга для інформаційної послідовності, заданої згідно з номером варіанта (таблиця 9).
Послідовність виконання програми:
1) визначити кількість інформаційних розрядів;
2) обчислити кількість контрольних розрядів;
3) обчислити загальну кількість розрядів;
4) визначити номера контрольних та інформаційних розрядів;
5) побудувати модель коду;
6) виконати серію перевірок, визначити значення контрольних розрядів;
7) сформувати результуючий код.
Табл. 9
| № по списку | Інформаційна послідовність | № по списку | Інформаційна послідовність |
ТЕМА: «ВИКОРИСТАННЯ МАТРИЦЬ ПРИ РОБОТІ З ГРУПОВИМИ КОДАМИ»
Розробити програму, що дозволяє побудувати груповий код, здатний виправляти як мінімум одиночні помилки при передачі зазначеного числа (згідно з номером варіанта у таблиці 10) символів первинного алфавіту.
Побудувати породжує матрицю групового коду. Виділити інформаційну та перевірочну частини матриці.
Примітка. Код повинен володіти потенційною можливістю корекції якомога більшої кількості помилок.
Табл. 9
| № по списку | Кількість символів первинного алфавіту | № по списку | Кількість символів первинного алфавіту |
ТЕМА: «ПОБУДОВА ЦИКЛІЧНИХ КОДІВ.
ВИЯВЛЕННЯ ТА ВИПРАВЛЕННЯ ОДИНОЧНИХ ПОМИЛОК»
Розробити програму, що дозволяє побудувати циклічний код, здатний виправляти одну помилку.
Для всіх варіантів визначити наступні параметри коду: nі=4, nк=3.
Непарні номери варіантів будують код методом 1, парні - методом 2.
На вимогу викладача вибрати допустиму кодову комбінацію з множини кодових комбінацій побудованого циклічного коду, внести програмним чином спотворення в зазначений розряд (згідно номера варіанта у таблиці 10) комбінації, і програмним чином його виправити.
Примітка: розряди кодових комбінацій нумеруються в напрямку справа наліво, починаючи з 0.
Табл. 10
| № по списку | Номер розряду кодової комбінації | № по списку | Номер розряду кодової комбінації |
Список літератури
1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. – М.: Изд-во МГУ, 2002 . – 381 с.
2. Габидулин, Э. М., Пилипчук, Н. И. Лекции по теории информации. — М.: МФТИ, 2007. - 214 с.
3. Кузьмин И.В. Основы теории информации и кодирования . – М. Высшая школа, 1977. – 280 с.
4. Волькенштейн М. В. Энтропия и информация. — М.: Наука, 2006. - 185 с.
5. Яглом А.М., Яглом И.М. Вероятность и информация. – М.: Наука, 1973. – 512 с.
6. Игнатов В.А. Теория информации и передачи сигналов. – М.: Высшая школа, 1979. – 280 с.
7. Цымбал В.П. Теория информации и кодирование – М.: Высшая школа, 1992. – 263 с.
8. Цымбал В.П. Задачник по теории информации и кодированию – М.Высшая школа, 1992. – 276 с.
9. Душин В.К. Теоретические основы информационных процессов и систем . – М.: Дашков и Ко, 2003. – 348 с.
10. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. – М.: «Наука», 1980. – 976 с.
11. Гольденберг Л.М. и др. Цифровая обработка сигналов: Справочник/ Л.М. Гольденберг, Б.Д. Матюшкин, М.Н. Поляк. – М.: Радио и связь, 1985. – 312 с.
12. Гоноровский И.С. Радиотехнические цепи и сигналы. Учебник для вузов. – М.: «Советское радио», 1971. – 672 с.