ВИРІШУ ЄДІ» інформатика
− Вчитель Думбадзе зі школи 162 Кіровського району Петербурга.
Наша група ВКонтакте Мобільні програми:
Для 5 літер латинського алфавіту задані їх двійкові коди (для деяких літер – із двох біт, для деяких – із трьох). Ці коди представлені у таблиці:
| a | b | c | d | e |
Який набір букв закодований двійковим рядком 1100000100110?
Ми бачимо, що виконується умова Фано: жодне кодове слово не є початком іншого кодового слова, тому можемо однозначно розкодувати повідомлення з початку.
Розіб'ємо код зліва направо за даними таблиці та переведемо його в літери:
110 000 01 001 10 - b a c d e.
Для 5 літер латинського алфавіту задані їх двійкові коди (для деяких літер – із двох біт, для деяких – із трьох). Ці коди представлені у таблиці:
| a | b | c | d | e |
Який набір букв закодований двійковим рядком 1000110110110? Усі літери у послідовності — різні.
Ми бачимо, що умови Фано та зворотна умова Фано не виконуються, отже код можна розкодувати неоднозначно.
Будемо пробувати різні варіанти, відкидаючи ті, в яких виходять літери, що повторюються:
1) 100 011 01 10 110
Перша буква визначається однозначно, її код 100: a.
Нехай друга літера – с, тоді наступна літера – d, потім – e та b.
Такий варіант задовольнить умову, отже остаточно отримали відповідь:acdeb.
Для 6 букв латинського алфавіту задані їх двійкові коди (для деяких літер із двох біт, для деяких – зтрьох). Ці коди представлені у таблиці:
| A | B | C | D | E | F |
Яка послідовність із 6 букв закодована двійковим рядком 011111000101100?
Ми бачимо, що умови Фано та зворотна умова Фано не виконуються, отже код можна розкодувати неоднозначно.
Спробуватимемо різні варіанти:
1) 011 11 100 0101100
Перша буква визначається однозначно, її код 011: D.
Друга літера також визначиться однозначно – E.
Нехай третя літера B, тоді наступна починається з коду 010, але таких літер у таблиці немає, отже, припущення неправильне.
2) 011 11 10 00 101 100
Третя літера - С, потім - A. Ми хочемо отримати ще дві літери, щоб у сумі їх було 6, тоді наступна - F, і остання - B.
Остаточно отримали відповідь:DECAFB.
Примітка. DECACEA не підходить, оскільки 7 букв.
так само підходить decacea
011 11 10 00 10 11 00
У завданні питається про послідовність зшостілітер.
Для передачі чисел каналом з перешкодами використовується код перевірки парності. Кожна його цифра записується в двійковому поданні, з додаванням провідних нулів до довжини 4, і до послідовності, що вийшла, дописується сума її елементів по модулю 2 (наприклад, якщо передаємо 23, то отримаємо послідовність 0010100110). Визначте, яке число передавалося каналом у вигляді 01100010100100100110.
З прикладу видно, що два знаки кодуються 10 двійковими розрядами (бітами), на кожну цифру відводиться 5 біт. В умові сказано, що кожна цифра записується кодом довжиною 4 знаки, отже п'яту цифру можна відкинути.
Розіб'ємо двійковий запис на групи по 5 знаків: 01100 01010 01001 00110. Відкидаємо послідню цифру в кожній п'ятірці та переводимо до десяткового запису:
0110 0101 0100 0011 - 6 5 4 3.
Для кодування деякої послідовності, що складається з букв А, Б, В, Г і Д, використовується нерівномірний двійковий код, що дозволяє однозначно декодувати отриману послідовність двійкову. Ось цей код: А - 10; Б - 11; В - 000; Р - 001; Д - 010. Потрібно скоротити для однієї з літер довжину кодового слова так, щоб код, як і раніше, можна було декодувати однозначно. Коди інших букв змінюватися не повинні. Яким із зазначених способів це можна зробити?
1) це неможливо
2) для літери А - 0
3) для літери В - 00
4) для літери Д - 01
Для однозначного декодування кодове слово, що вийшло в результаті скорочення, не повинно бути початком жодного іншого. Другий варіант відповіді не підходить, оскільки код букви А є початком коду букви В. Третій варіант не підходить, оскільки код букви є початком коду букви Г. Четвертий варіант відповіді підходить.