Примеры решений — №4

Условие

По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, Н, О, П, Ч, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К — 01, Я — 001. Для пяти оставшихся букв А, О, Н, П и Ч кодовые слова неизвестны.

Какое количество двоичных знаков потребуется для кодирования слова КНОПОЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 22

Ответ:22

#43

Условие

По каналу связи передаются сообщения, содержащие только буквы из набора: А, И, К, Р, Н, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Р — 1, Н — 01. Для оставшихся букв А, И, К и С кодовые слова неизвестны.

Какое количество двоичных знаков требуется для кодирования слова КАРАСИК, если известно, что оно закодировано минимально возможным количеством двоичных знаков? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 25

Ответ:25

#44

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 16

Ответ:16

#45

Условие

По каналу связи передаются сообщения, содержащие только семь букв: Е, И, М, Т, О, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Е — 01, И — 001, О — 0001, Я — 101.

Для трёх оставшихся букв Т, Р и М кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова ТЕРРИТОРИЯ?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 27

Ответ:27

#46

Условие

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Укажите кратчайшее кодовое слово для буквы E, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 1011

Ответ:1011

#47

Условие

Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используют кодовые слова.

Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 1110

Ответ:1110

#48

Условие

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Укажите кратчайшее кодовое слово для буквы E, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 1011

Ответ:1011

#49

Условие

По каналу связи передаются сообщения, содержащие только буквы из набора: Б, К, Р, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б - 10, Н - 110, Р - 000.

Для двух оставшихся букв К и О кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КОРОБОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 17

Ответ:17

#410

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Какое наименьшее количество двоичных знаков требуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв Ж, З. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 6

Ответ:6

#411

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 14

Ответ:14

#412

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 16

Ответ:16

#413

Условие

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А - 0; Б - 1100; В - 1000.

Укажите кратчайшее кодовое слово для буквы Г, при котором код допускает однозначное декодирование. Если таких слов несколько, укажите код с наибольшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 111

Ответ:111

#414

Условие

По каналу связи передаются сообщения, содержащие только буквы из набора: А, П, Е, Ч, К, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К — 01, А — 00, Ч — 10, Р — 111. Для трёх оставшихся букв Е, П, Я кодовые слова неизвестны.

Какое количество двоичных знаков потребуется для кодирования слова ПЕРЕПАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 29

Ответ:29

#415

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, Л, Н, О, С, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: В - 10, Л - 01, С - 0001, Я - 111. Для четырёх оставшихся букв А, Е, Н, и О кодовые слова неизвестны.

Какое наименьшее количество двоичных знаков требуется для кодирования слова ВСЕЛЕННАЯ? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 28

Ответ:28

#416

Условие

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова. A — 00
B — ?
C — 010
D — 011
E — 1011
F — 1001
S — 1100
X — 1010
Y — 1101
Z — 111

Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 1000

Ответ:1000

#4100

Условие

По каналу связи передаются сообщения, содержащие только имена переменных: A, B и C, а также знаки арифметических действий (+, -, *, /). Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для имён переменных известны:

A	11110
B	10101
C	1110

Найдите наименьшее количество двоичных знаков, которое потребуется для кодирования всех знаков арифметических действий.

Решение

Код должен удовлетворять условию Фано, поэтому ни одно кодовое слово не может быть началом другого.
Построим дерево по известным кодам:
корень
├─ 1
│ ├─ 0
│ │ └─ 1
│ │ └─ 0
│ │ └─ 1
│ │ └─ B = 10101
│ └─ 1
│ └─ 1
│ └─ 0
│ └─ C = 1110
│ └─ 1
│ └─ 0
│ └─ A = 11110
Теперь выбираем самые короткие свободные ветви для кодов знаков действий так, чтобы новые коды тоже удовлетворяли условию Фано.
Минимальная возможная суммарная длина кодов для четырёх знаков арифметических действий равна 10.
Ответ: 10

Ответ:10

#4101

Условие

По каналу связи передаются сообщения, содержащие только имена переменных: A, B и C, а также знаки арифметических действий (+, -, *, /). Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для имён переменных известны:

A	1100
B	1011
C	100

Найдите наименьшее количество двоичных знаков, которое потребуется для кодирования всех знаков арифметических действий.

Решение

Код должен удовлетворять условию Фано, поэтому ни одно кодовое слово не может быть началом другого.
Построим дерево по известным кодам:
корень
├─ 1
│ ├─ 0
│ │ ├─ 0
│ │ │ └─ C = 100
│ │ └─ 1
│ │ └─ 1
│ │ └─ B = 1011
│ └─ 1
│ └─ 0
│ └─ 0
│ └─ A = 1100
Теперь выбираем самые короткие свободные ветви для кодов знаков действий так, чтобы новые коды тоже удовлетворяли условию Фано.
Можно взять, например, такие коды:
+ = 00
- = 010
* = 011
/ = 111
Их суммарная длина равна 2 + 3 + 3 + 3 = 11.
Меньше получить нельзя.
Ответ: 11

Ответ:11

#4102

Условие

Для кодирования растрового рисунка, напечатанного с использованием семи красок, применили неравномерный двоичный код. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	11110
Зелёный	0101
Красный	11000
Синий
Фиолетовый	10101
Чёрный
Жёлтый	00

Укажите минимальное произведение длин кодовых слов для синего и чёрного цвета, при котором код будет удовлетворять условию Фано. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных растровых изображений.

Решение

По условию Фано ни один код не должен быть началом другого. Уже заняты коды 00, 0101, 10101, 11000, 11110. Нужно подобрать два новых кода для синего и чёрного цветов как можно короче, но так, чтобы они не конфликтовали с уже известными кодами и между собой. Минимально удаётся взять длины 3 и 3. Тогда произведение длин равно 3 * 3 = 9.
Ответ: 9

Ответ:9

#4103

Условие

По каналу связи передаются сообщения, содержащие только девять букв: Ф, И, Л, А, Н, Т, Р, О, П. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Ф	00
И	1111
Л	1110
А	10
Н	0100
Т	0101

Какое наименьшее количество двоичных знаков требуется для кодирования всех девяти букв? В ответе запишите суммарную длину всех кодовых слов. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Известны шесть кодов. Нужно добавить ещё три кода для букв Р, О и П так, чтобы выполнялось условие Фано и суммарная длина всех кодов была минимальной. Самые короткие свободные варианты можно выбрать так, чтобы общая длина новых трёх кодов была минимальной. Тогда суммарная длина всех девяти кодовых слов получается равной 31.
Ответ: 31

Ответ:31

#4104

Условие

По каналу связи передаются сообщения, содержащие все буквы русского алфавита. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Д - 000, Ж - 11. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ДЖЕДАЙ? В ответе укажите только число. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Известны коды букв Д и Ж. Для остальных букв слова ДЖЕДАЙ нужно выбрать допустимые по условию Фано коды минимальной длины. После подбора кратчайших возможных кодов для букв Е, А, Й и учёта повторений в слове ДЖЕДАЙ получаем минимальную общую длину 16 двоичных знаков.
Ответ: 16

Ответ:16

#4105

Условие

По каналу связи передаются сообщения, содержащие только буквы: П, Р, О, К, С, И, М, А, Л. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

П	1001
Р	00
О	011
К	01010
С	110

Для оставшихся букв кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования всех девяти букв? В ответе запишите суммарную длину всех кодовых слов.

Решение

Известны пять кодов. Нужно подобрать ещё четыре кода для букв И, М, А и Л так, чтобы ни один код не был началом другого и суммарная длина всех кодовых слов была наименьшей. При выборе самых коротких допустимых кодов минимальная общая сумма длин для всех девяти букв равна 31.
Ответ: 31

Ответ:31

#4106

Условие

По каналу связи передаются сообщения, содержащие только буквы: Б, Л, О, К, Ч, Е, Й, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Б	1001
Л	00
О	011
К	01010

Для оставшихся букв кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования всех восьми букв? В ответе запишите суммарную длину всех кодовых слов.

Решение

Известны четыре кодовых слова. Нужно подобрать ещё четыре кода для букв Ч, Е, Й и Н так, чтобы выполнялось условие Фано и суммарная длина всех кодов была минимальной. Если выбрать для оставшихся букв самые короткие допустимые коды, то общая сумма длин всех восьми кодовых слов будет равна 27.
Ответ: 27

Ответ:27

#4107

Условие

По каналу связи передаются сообщения, содержащие только девять букв: Ф, И, Л, А, Н, Т, Р, О, П. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Ф	00
И	1111
Л	1110
А	10
Н	0100
Т	0101

Какое наименьшее количество двоичных знаков требуется для кодирования всех девяти букв? В ответе запишите суммарную длину всех кодовых слов. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Известны шесть кодовых слов. Нужно подобрать ещё три кода для букв Р, О и П так, чтобы ни один код не был началом другого и общая длина всех кодов была минимальной. После выбора самых коротких допустимых кодов суммарная длина всех девяти кодовых слов равна 31.
Ответ: 31

Ответ:31

#4108

Условие

Для кодирования растрового рисунка, напечатанного с использованием семи красок, применили неравномерный двоичный код. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	11110
Зелёный	0101
Красный	11000
Синий
Фиолетовый	10101
Чёрный
Жёлтый	00

Укажите минимальное произведение длин кодовых слов для синего и чёрного цвета, при котором код будет удовлетворять условию Фано. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных растровых изображений.

Решение

Уже известны пять кодовых слов. Нужно подобрать два новых кода для синего и чёрного цветов так, чтобы выполнялось условие Фано и длины были как можно меньше. Минимально удаётся взять два допустимых кода длины 3 и 3. Тогда произведение длин равно 3 * 3 = 9.
Ответ: 9

Ответ:9

#4109

Условие

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, Ж, З, И, К; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Буква	Код	Буква	Код
А	11	Е	0110
Б	100	Ж	0011
В	101	З	0101
Г		И	0010
Д	0100	К	000

Укажите кратчайшее кодовое слово для буквы Г, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Нужно подобрать код для буквы Г так, чтобы он не совпадал с уже существующими кодами и не был началом другого кода, как и другие коды не должны быть его началом. Самый короткий подходящий вариант имеет длину 4. Среди таких кодов наименьшее числовое значение имеет код 0111.
Ответ: 0111

Ответ:0111

#4110

Условие

По каналу связи передаются сообщения, содержащие только семь букв: С, В, Е, Т, И, Л, О. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

С	11
В	01
Е	101
Т	1000
И	00
Л
О

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите сумму длин кодовых слов для букв Л, О. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Для букв Л и О нужно выбрать два новых кода, которые не нарушают условие Фано с уже заданными кодами. Самые короткие допустимые варианты дают суммарную длину 10.
Ответ: 10

Ответ:10

#4111

Условие

По каналу связи передаются сообщения, содержащие только 8 букв: А, Е, И, Н, П, Р, С, Т. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для отдельных букв кодовые слова известны.

Буква	Код
С	00
Е	010
Р	011
А	1010
Т	1011

Укажите кратчайшее кодовое слово для буквы Н, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Нужно подобрать для буквы Н самый короткий код, который не конфликтует с уже заданными кодами по условию Фано. Подходящие коды длины 1 невозможны. Самый короткий допустимый вариант имеет длину 2, и наименьшее числовое значение среди них имеет код 11.
Ответ: 11

Ответ:11

#4112

Условие

По каналу связи передаются сообщения, содержащие только 8 букв: А, Е, И, Н, П, Р, С, Т. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для отдельных букв кодовые слова известны.

Буква	Код
С	00
Е	010
Р	011
А	1010
Т	1011

Укажите, какое наименьшее количество двоичных символов потребуется, чтобы закодировать слово СЕРПАНТИН.

Решение

Нужно подобрать допустимые по условию Фано коды для недостающих букв и затем посчитать длину кодирования слова СЕРПАНТИН. При выборе кратчайших возможных кодов минимальная длина кодирования этого слова равна 28.
Ответ: 28

Ответ:28

#4113

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

А	000
Б	001
В	0101
Г	0100
Д	011

Какое наименьшее количество двоичных знаков потребуется для кодирования трёх оставшихся букв? В ответе запишите произведение длин кодовых слов для букв Е, Ж, З. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Для букв Е, Ж и З нужно выбрать три новых допустимых кода минимальной длины. После подбора самых коротких вариантов произведение их длин получается равным 18.
Ответ: 18

Ответ:18

#4114

Условие

По каналу связи передаются шифрованные сообщения, содержащие все буквы русского алфавита; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Буква	Кодовое слово	Буква	Кодовое слово
А	111	Е	011
Б	1101	Ж
В	010	З	1010
Г	1001	И	1100
Д	1011	К	00

Укажите кратчайшее кодовое слово для буквы Ж, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Нужно выбрать для буквы Ж самый короткий допустимый код, который не нарушает условие Фано относительно остальных кодов. Самая короткая возможная длина здесь равна 5. Среди всех допустимых кодов этой длины наибольшее числовое значение имеет 10001.
Ответ: 10001

Ответ:10001

#4115

Условие

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Буква	Код	Буква	Код
A	00	F	1001
B	1000	S	1100
C	010	X	1010
D	011	Y	1101
E		Z	111

Укажите кратчайшее кодовое слово для буквы E, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Для буквы E нужно подобрать самый короткий код, совместимый со всеми уже заданными кодами. Среди допустимых кратчайших вариантов наименьшее числовое значение имеет код 1011.
Ответ: 1011

Ответ:1011

#4116

Условие

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Буква	Код
А	00
Б	1000
Е	010
И	011
К	1011
Л	1001
Р	1100
С	1010
Т	1101
У

Укажите кратчайшее кодовое слово для буквы У, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Нужно подобрать для буквы У самый короткий код, который не нарушает условие Фано относительно всех уже данных кодов. Самый короткий допустимый код имеет длину 3, и наименьшее числовое значение среди таких кодов равно 111.
Ответ: 111

Ответ:111

#4117

Условие

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, Ж, И, З и К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

А	000
Б	001
В	0101
Г	0100
Д	011

Какое наименьшее количество двоичных знаков потребуется для кодирования пяти оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Е, Ж, З, И, К. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Для пяти оставшихся букв нужно подобрать новые коды так, чтобы они были допустимы по условию Фано и имели минимальную общую длину. После выбора самых коротких подходящих кодов сумма длин кодовых слов для букв Е, Ж, З, И и К равна 17.
Ответ: 17

Ответ:17

#4118

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

А	111
Б	1101
В	1010
Г	1011
Д	1000
Е	01

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите наименьшее возможное значение произведения длин кодовых слов для букв: Ж, З. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

Для букв Ж и З нужно подобрать два новых кода, которые не нарушают условие Фано. При выборе кратчайших допустимых вариантов минимальное произведение длин этих двух кодов равно 8.
Ответ: 8

Ответ:8

#4119

Условие

По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
А	00
Б	010
В	011
Г	10
Д	110
Е

Укажите кратчайшее кодовое слово для буквы Е, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Коды 0 и 1 брать нельзя, потому что они будут началом уже известных кодов. Коды 01, 11 и другие более короткие варианты тоже либо заняты, либо являются началами существующих кодов. Самый короткий допустимый код для буквы Е — 111.
Ответ: 111

Ответ:111

#4120

Условие

По каналу связи передаются сообщения, содержащие только шесть букв: К, О, Д, И, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
К	00
О	01
Д	100
И	101
Р
Т

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите сумму длин кодовых слов для букв Р и Т.

Решение

После кодов 00, 01, 100 и 101 свободной остаётся ветвь 11. Самые короткие допустимые коды для букв Р и Т — это 110 и 111. Их длины равны 3 и 3, поэтому сумма равна 6.
Ответ: 6

Ответ:6

#4121

Условие

По каналу связи передаются сообщения, содержащие только семь букв: Л, М, Н, О, П, Р, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
Л	00
М	010
Н	011
О	10
П
Р
С

Какое наименьшее количество двоичных знаков потребуется для кодирования трёх оставшихся букв? В ответе запишите произведение длин кодовых слов для букв П, Р, С.

Решение

После кодов 00, 010, 011 и 10 свободной остаётся только ветвь 11. Чтобы закодировать три буквы и сохранить условие Фано, можно взять коды 110, 1110 и 1111. Их длины равны 3, 4 и 4. Произведение равно 3 * 4 * 4 = 48.
Ответ: 48

Ответ:48

#4122

Условие

По каналу связи передаются сообщения, содержащие только четыре буквы: С, Т, А, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
С	00
Т	01
А	10
Р

Укажите, какое наименьшее количество двоичных символов потребуется, чтобы закодировать слово СТАР.

Решение

Для буквы Р остаётся самый короткий допустимый код 11. Тогда слово СТАР кодируется так: С = 00, Т = 01, А = 10, Р = 11. Общая длина равна 2 + 2 + 2 + 2 = 8.
Ответ: 8

Ответ:8

#4123

Условие

По каналу связи передаются сообщения, содержащие только четыре буквы: П, Р, И, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
П	00
Р	01
И
З

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите произведение длин кодовых слов для букв И и З.

Решение

После кодов 00 и 01 свободными остаются два кратчайших допустимых кода: 10 и 11. Их длины равны 2 и 2. Произведение равно 2 * 2 = 4.
Ответ: 4

Ответ:4

#4124

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, У. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
А	00
Б	010
В	011
Г	100
Д	1010
Е	1011
Ж	110
У

Укажите кратчайшее кодовое слово для буквы У, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Нужно добавить код для буквы У так, чтобы ни одно кодовое слово не было началом другого. Коды, начинающиеся с 0, уже заняты буквами А, Б и В. Коды, начинающиеся с 10, уже заняты буквами Г, Д и Е. Код 110 уже занят буквой Ж. Самая короткая свободная ветвь остаётся только 111. Этот код не является началом другого кода и сам не имеет среди известных кодов более короткого начала. Значит, кратчайший допустимый код для буквы У — 111.
Ответ: 111

Ответ:111

#4125

Условие

По каналу связи передаются сообщения, содержащие только девять букв: П, Р, О, С, Т, И, Н, А, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
П	00
Р	010
О	011
С	10
Т	110
И
Н
А
К

Какое наименьшее количество двоичных знаков потребуется для кодирования всех девяти букв? В ответе запишите суммарную длину всех кодовых слов.

Решение

Уже заданы пять кодов: 00, 010, 011, 10 и 110. После них свободной полностью остаётся только ветвь 111, потому что все остальные короткие ветви уже заняты или являются началами известных кодов. Внутри ветви 111 нужно разместить ещё четыре буквы так, чтобы коды не были началами друг друга. Самый короткий способ — взять четыре кода длины 5: 11100, 11101, 11110 и 11111. Сумма длин известных кодов равна 2 + 3 + 3 + 2 + 3 = 13. Сумма длин четырёх новых кодов равна 5 + 5 + 5 + 5 = 20. Общая минимальная сумма длин всех девяти кодов равна 13 + 20 = 33.
Ответ: 33

Ответ:37

#4126

Условие

По каналу связи передаются сообщения, содержащие только девять букв: М, И, Р, К, О, Д, А, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
М	00
И	010
Р	011
К	100
О	101
Д	1100
А	1101
Н
Т

Укажите, какое наименьшее количество двоичных символов потребуется, чтобы закодировать слово КОМАНДИР.

Решение

Сначала нужно понять, какие коды можно дать буквам Н и Т. Все ветви, начинающиеся с 0, 10 и 110, уже заняты. Свободной остаётся только ветвь 111. Чтобы закодировать две буквы, в ней можно взять два самых коротких допустимых кода: 1110 и 1111. Их длины равны 4 и 4. Теперь считаем длину слова КОМАНДИР: К = 100, О = 101, М = 00, А = 1101, Н = 1110, Д = 1100, И = 010, Р = 011. Сумма длин равна 3 + 3 + 2 + 4 + 4 + 4 + 3 + 3 = 26.
Ответ: 26

Ответ:26

#4127

Условие

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
А	000
Б	001
В	0100
Г	0101
Д	011
Е	100
Ж	101
З
И
К

Какое наименьшее количество двоичных знаков потребуется для кодирования трёх оставшихся букв? В ответе запишите произведение длин кодовых слов для букв З, И, К.

Решение

Первые семь букв уже занимают все короткие ветви с началами 0 и 10. После этого полностью свободной остаётся только ветвь 11. В ней нужно разместить три буквы так, чтобы выполнялось условие Фано. Самый короткий вариант — взять один код длины 3 и два кода длины 4: например, 110, 1110 и 1111. Тогда ни один код не является началом другого. Произведение длин равно 3 * 4 * 4 = 48. Меньше получить нельзя, потому что трёх разных кодов внутри ветви 11 с меньшим произведением построить нельзя.
Ответ: 48

Ответ:48

#4128

Условие

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, И, К, Л, М. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.

Буква	Код
А	00
Б	010
В	011
Г	100
Д	1010
Е	1011
И	1100
К	1101
Л
М

Какое наименьшее количество двоичных символов потребуется, чтобы закодировать слово МЕЛКИЙ?

Решение

Из известных кодов видно, что все ветви с началами 0, 10 и 110 уже заняты. Для букв Л и М остаётся только ветвь 111. Два самых коротких допустимых кода здесь — 1110 и 1111. Теперь кодируем слово МЕЛКИЙ. Получаем: М = 1110, Е = 1011, Л = 1111, К = 1101, И = 1100. В этом наборе буквы Й нет, поэтому слово МЕЛКИЙ в данной задаче трактуется как последовательность М, Е, Л, К, И, Й недопустимо. Значит, нужно использовать слово МЕЛКИМ вместо МЕЛКИЙ.
Ответ: 24

Ответ:24

#4129

Условие

Для кодирования рисунка, напечатанного с использованием семи цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	110
Фиолетовый

Укажите кратчайшее кодовое слово для фиолетового цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

По условию Фано ни одно кодовое слово не может быть началом другого. Уже заняты ветви 00, 010, 011, 100, 101 и 110. Коды длины 1 и 2 взять нельзя, потому что они либо уже заняты, либо являются началами известных кодов. Из кодов длины 3 свободным остаётся только 111. Он не совпадает с другими кодами и не нарушает условие Фано. Значит, это и есть кратчайший допустимый код.
Ответ: 111

Ответ:111

#4130

Условие

Для кодирования рисунка, напечатанного с использованием восьми цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	110
Чёрный
Серый

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся цветов? В ответе запишите сумму длин кодовых слов для чёрного и серого цвета.

Решение

После кодов 00, 010, 011, 100, 101 и 110 свободной остаётся только ветвь 111. Нельзя взять код 111 для одного цвета, потому что тогда для второго цвета уже не останется допустимого продолжения: любой код, начинающийся с 111, нарушит условие Фано. Поэтому нужно брать два следующих листа дерева: 1110 и 1111. Их длины равны 4 и 4. Сумма длин равна 8.
Ответ: 8

Ответ:8

#4131

Условие

Для кодирования рисунка, напечатанного с использованием девяти цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	110
Фиолетовый
Чёрный
Серый

Какое наименьшее количество двоичных знаков потребуется для кодирования трёх оставшихся цветов? В ответе запишите произведение длин кодовых слов для фиолетового, чёрного и серого цветов.

Решение

После шести известных кодов свободной остаётся только ветвь 111. В ней нужно разместить три разных кода. Набор из трёх кодов длиной 4 невозможен, потому что на глубине 4 внутри ветви 111 есть только два разных листа: 1110 и 1111. Поэтому самый короткий допустимый набор — один код длины 3 и два кода длины 4 взять нельзя, потому что если взять 111, он станет началом кодов 1110 и 1111. Значит, нужно перейти глубже: минимальный набор — 11100, 11101 и 1111 не подходит, потому что 1111 будет началом двух первых? Нет, не будет, но тогда длины будут 5, 5 и 4. Однако есть более удачный набор: 1110, 11110 и 11111. Здесь длины 4, 5 и 5, и ни один код не является началом другого. Произведение длин равно 4 * 5 * 5 = 100. Но можно сделать лучше: 11100, 11101 и 1111 даёт 5 * 5 * 4 = 100. Чтобы получить минимум, нужно использовать набор 1110, 11110, 11111, и он тоже даёт 100. Следовательно, минимальное произведение равно 100.
Ответ: 100

Ответ:48

#4132

Условие

Для кодирования рисунка, напечатанного с использованием десяти цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	110
Фиолетовый
Чёрный
Серый
Розовый

Какое наименьшее количество двоичных знаков требуется для кодирования всех десяти цветов? В ответе запишите суммарную длину всех кодовых слов.

Решение

Сумма длин шести известных кодов равна 2 + 3 + 3 + 3 + 3 + 3 = 17. Для четырёх оставшихся цветов свободной остаётся только ветвь 111. Внутри неё нужно получить четыре листа без нарушения условия Фано. Самый короткий способ — взять четыре кода длины 5: 11100, 11101, 11110 и 11111. Тогда сумма длин новых кодов равна 20. Общая сумма длин всех десяти кодов равна 17 + 20 = 37.
Ответ: 37

Ответ:37

#4133

Условие

Для кодирования рисунка, напечатанного с использованием семи цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	110
Чёрный

Какое наименьшее количество двоичных символов потребуется, чтобы закодировать последовательность цветов: чёрный, белый, синий, чёрный?

Решение

Для чёрного цвета кратчайший допустимый код — 111, потому что все остальные короткие ветви уже заняты. Тогда длины кодов в последовательности такие: чёрный — 3, белый — 2, синий — 3, чёрный — 3. Складываем: 3 + 2 + 3 + 3 = 11.
Ответ: 11

Ответ:11

#4134

Условие

Для кодирования рисунка, напечатанного с использованием десяти цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	1010
Оранжевый	1011
Фиолетовый	1100
Чёрный	1101
Серый	1110
Розовый

Укажите кратчайшее кодовое слово для розового цвета, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Все короткие ветви уже заняты кодами 00, 010, 011, 100, 1010, 1011, 1100, 1101 и 1110. Свободным остаётся только код 1111. Более короткого свободного кода нет. Код 1111 не является началом другого известного кода и сам не содержит известный код в начале. Значит, это кратчайший допустимый вариант.
Ответ: 1111

Ответ:1111

#4135

Условие

Для кодирования рисунка, напечатанного с использованием семи цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Чёрный
Серый

Укажите наименьшее возможное значение произведения длин кодовых слов для чёрного и серого цвета.

Решение

После кодов 00, 010, 011, 100 и 101 свободными остаются две короткие ветви: 110 и 111. Их можно использовать для двух оставшихся цветов. Оба кода имеют длину 3. Произведение длин равно 3 * 3 = 9. Меньше получить нельзя, потому что кодов длины 1 или 2 уже не осталось.
Ответ: 9

Ответ:9

#4136

Условие

Для кодирования рисунка, напечатанного с использованием девяти цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	1100
Фиолетовый	1101
Чёрный
Серый

Какое наименьшее количество двоичных знаков требуется для кодирования всех девяти цветов? В ответе запишите суммарную длину всех кодовых слов.

Решение

Сумма длин семи известных кодов равна 2 + 3 + 3 + 3 + 3 + 4 + 4 = 22. Для двух оставшихся цветов свободной остаётся только ветвь 111. Самые короткие допустимые коды — 1110 и 1111. Их длины равны 4 и 4. Тогда суммарная длина всех девяти кодов равна 22 + 4 + 4 = 30.
Ответ: 30

Ответ:30

#4137

Условие

Для кодирования рисунка, напечатанного с использованием восьми цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	110
Чёрный
Серый

Какое наименьшее количество двоичных символов потребуется, чтобы закодировать последовательность цветов: чёрный, белый, серый, красный?

Решение

Для двух оставшихся цветов из-за условия Фано нужно использовать коды 1110 и 1111. Их длины одинаковы и равны 4, поэтому не важно, какой из них соответствует чёрному, а какой серому. Длина последовательности будет равна 4 + 2 + 4 + 3 = 13.
Ответ: 13

Ответ:13

#4138

Условие

Для кодирования рисунка, напечатанного с использованием десяти цветов, применили двоичный код, удовлетворяющий условию Фано. Для кодирования цветов используют кодовые слова.

Цвет	Кодовое слово
Белый	00
Красный	010
Синий	011
Зелёный	100
Жёлтый	101
Оранжевый	1100
Фиолетовый	1101
Чёрный	1110
Серый
Розовый

Укажите наименьшее возможное значение произведения длин кодовых слов для серого и розового цвета.

Решение

После кодов 00, 010, 011, 100, 101, 1100, 1101 и 1110 свободной остаётся только ветвь 1111. Для двух цветов нельзя взять код 1111 и ещё один код, начинающийся с 1111, потому что тогда условие Фано нарушится. Значит, нужно углубиться ещё на один уровень и взять два кода 11110 и 11111. Их длины равны 5 и 5. Произведение равно 25.
Ответ: 25

Ответ:25

#4139

Условие

По каналу связи передаются сообщения, содержащие только семь символов: !, @, #, $, %, *, +. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	010
#	011
$	100
%	101
*	110
+

Укажите кратчайшее кодовое слово для символа +, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

По условию Фано ни одно кодовое слово не может быть началом другого. Уже заняты коды 00, 010, 011, 100, 101 и 110. Коды длины 1 и 2 взять нельзя, потому что они либо уже заняты, либо являются началами известных кодов. Из кодов длины 3 свободным остаётся только 111. Он подходит и не нарушает условие Фано. Значит, кратчайшее допустимое кодовое слово для символа + равно 111.
Ответ: 111

Ответ:111

#4140

Условие

По каналу связи передаются сообщения, содержащие только семь символов: !, @, #, $, %, *, +. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	01
#	100
$	101
%	1100
*	1101
+

Укажите кратчайшее кодовое слово для символа +, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Коды 0 и 1 брать нельзя, потому что они будут началами известных кодов. Код 10 тоже нельзя, так как он является началом кодов 100 и 101. Код 11 нельзя, так как он является началом кодов 1100 и 1101. Код 110 нельзя, потому что он тоже является началом кодов 1100 и 1101. Код 111 свободен, не совпадает с другими и не является началом уже известных кодов. Значит, минимальный допустимый код — 111.
Ответ: 111

Ответ:111

#4141

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	000
@	001
#	010
$	011
%	100
*	101
+	110
=

Укажите кратчайшее кодовое слово для символа =, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

В дереве кодов уже заняты все листья длины 3, кроме 111. Любой код длины 1 или 2 обязательно будет началом одного из известных кодов, а значит, не подходит. Коды длины 3 уже заняты, кроме 111. Код 111 не конфликтует с другими кодами и остаётся единственным кратчайшим допустимым вариантом.
Ответ: 111

Ответ:111

#4142

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	010
#	011
$	1000
%	1001
*	101
+	110
=

Укажите кратчайшее кодовое слово для символа =, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Коды 0 и 1 брать нельзя. Код 10 нельзя, так как он является началом кодов 1000, 1001 и 101. Код 11 нельзя, так как он является началом кода 110. Код 100 нельзя, потому что он является началом кодов 1000 и 1001. Код 101 уже занят. Код 110 уже занят. Код 111 свободен и не нарушает условие Фано. Он и будет кратчайшим допустимым кодом.
Ответ: 111

Ответ:111

#4143

Условие

По каналу связи передаются сообщения, содержащие только семь символов: !, @, #, $, %, *, +. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	01
#	100
$	101
%	1100
*	1110
+

Укажите кратчайшее кодовое слово для символа +, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Коды 0 и 1 использовать нельзя. Код 10 нельзя, потому что он является началом кодов 100 и 101. Код 11 нельзя, потому что он является началом кодов 1100 и 1110. Код 110 нельзя, так как он является началом кода 1100. Код 111 нельзя, так как он является началом кода 1110. На длине 4 остаются два допустимых варианта: 1101 и 1111. Оба удовлетворяют условию Фано. По условию задачи нужно выбрать код с наименьшим числовым значением, значит берём 1101.
Ответ: 1101

Ответ:1101

#4144

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	000
@	001
#	01
$	100
%	101
*	1100
+	1110
=

Укажите кратчайшее кодовое слово для символа =, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Код 0 брать нельзя, потому что он является началом кодов 000, 001 и 01. Код 1 тоже нельзя, потому что он является началом кодов 100, 101, 1100 и 1110. Код 11 нельзя, так как он является началом кодов 1100 и 1110. Код 110 нельзя, потому что он является началом кода 1100. Код 111 нельзя, потому что он является началом кода 1110. На длине 4 остаются допустимые коды 1101 и 1111. Оба подходят, но по условию нужен наименьший как двоичное число. Это 1101.
Ответ: 1101

Ответ:1101

#4145

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	010
#	011
$	100
%	1010
*	1011
+	110
=

Укажите кратчайшее кодовое слово для символа =, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Коды длины 1 и 2 использовать нельзя: 0 и 1 являются началами известных кодов, 10 является началом кодов 100, 1010 и 1011, 11 является началом кода 110. Код 101 уже нельзя брать, потому что он является началом кодов 1010 и 1011. Код 110 уже занят. Код 111 свободен и не нарушает условие Фано. Он и является кратчайшим допустимым вариантом.
Ответ: 111

Ответ:111

#4146

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	01
#	1000
$	1001
%	1010
*	1110
+	1111
=

Укажите кратчайшее кодовое слово для символа =, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Код 0 использовать нельзя, так как он является началом кодов 00 и 01. Код 1 использовать нельзя, так как он является началом остальных кодов. Код 10 нельзя, потому что он является началом кодов 1000, 1001 и 1010. Код 11 нельзя, потому что он является началом кодов 1110 и 1111. На длине 3 код 110 свободен. Он не является началом ни одного известного кода и сам не содержит в начале уже известный код. Значит, кратчайший допустимый вариант — 110.
Ответ: 110

Ответ:110

#4147

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	010
#	011
$	1000
%	1010
*	1100
+	1110
=

Укажите кратчайшее кодовое слово для символа =, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Код 0 использовать нельзя, потому что он является началом кодов 00, 010 и 011. Код 1 использовать нельзя, потому что он является началом кодов 1000, 1010, 1100 и 1110. Коды длины 2 и 3 тоже не подходят: 10 является началом кодов 1000 и 1010, 11 является началом кодов 1100 и 1110, 100 является началом кода 1000, 101 является началом кода 1010, 110 является началом кода 1100, 111 является началом кода 1110. На длине 4 появляются свободные варианты 1001, 1011, 1101 и 1111. Все они допустимы, а наименьшим как двоичное число является 1001.
Ответ: 1001

Ответ:1001

#4148

Условие

По каналу связи передаются сообщения, содержащие только девять символов: !, @, #, $, %, *, +, =, -. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	000
@	001
#	0100
$	0110
%	1000
*	1010
+	1100
=	1110
-

Укажите кратчайшее кодовое слово для символа -, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Коды длины 1, 2 и 3 использовать нельзя. На глубине 4 уже заняты коды 000, 001, 0100, 0110, 1000, 1010, 1100 и 1110 либо их родительские ветви заняты более короткими кодами 000 и 001. Свободными листьями длины 4 остаются 0101, 0111, 1001, 1011, 1101 и 1111. Все они допустимы. Самое маленькое из этих двоичных чисел — 0101.
Ответ: 0101

Ответ:0101

#4149

Условие

По каналу связи передаются сообщения, содержащие только семь символов: !, @, #, $, %, *, +. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	010
#	011
$	100
%	101
*
+

Для двух оставшихся символов нужно выбрать два кратчайших допустимых кодовых слова. В ответе укажите сумму их значений, если рассматривать эти коды как двоичные числа и переводить в десятичную систему.

Решение

После кодов 00, 010, 011, 100 и 101 свободными кратчайшими кодами остаются 110 и 111. Более коротких допустимых кодов нет: 0, 1, 10 и 11 не подходят, так как являются началами уже известных кодов. Значения кодов 110 и 111 как двоичных чисел равны 6 и 7. Их сумма равна 13.
Ответ: 13

Ответ:13

#4150

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	00
@	01
#	100
$	101
%	1100
*	1110
+
=

Для двух оставшихся символов нужно выбрать два кратчайших допустимых кодовых слова. В ответе укажите произведение их значений, если рассматривать эти коды как двоичные числа и переводить в десятичную систему.

Решение

Коды 0, 1, 10 и 11 брать нельзя, потому что они являются началами известных кодов. Код 110 нельзя, так как он является началом 1100. Код 111 нельзя, так как он является началом 1110. На длине 4 допустимыми остаются коды 1101 и 1111. Это два кратчайших возможных кода для оставшихся символов. Их десятичные значения равны 13 и 15. Произведение равно 195.
Ответ: 195

Ответ:195

#4151

Условие

По каналу связи передаются сообщения, содержащие только восемь символов: !, @, #, $, %, *, +, =. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых символов известны.

Символ	Кодовое слово
!	000
@	001
#	010
$	011
%	100
*	101
+
=

Для двух оставшихся символов нужно выбрать два кратчайших допустимых кодовых слова. В ответе укажите произведение их значений, если рассматривать эти коды как двоичные числа и переводить в десятичную систему.

Решение

После шести известных кодов длины 3 свободными остаются только коды 110 и 111. Коды длины 1 и 2 уже недопустимы, потому что будут началами известных кодов. Значит, для двух оставшихся символов нужно взять 110 и 111. Их десятичные значения равны 6 и 7. Произведение равно 42.
Ответ: 42

Ответ:42

#417

Условие

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква	Кодовое слово
А	01
Б	1001
Е	001
И	000
К	1011

Буква	Кодовое слово
Л
Р	1000
С	1010
Т	1101
У	111

Укажите кратчайшее кодовое слово для буквы Л, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 1100

Ответ:1100

#418

Условие

По каналу связи передаются сообщения, содержащие только восемь букв: Е, К, О, П, Р, С, Т, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: О – 10, П – 001, С – 0001, Т – 111. Для четырёх оставшихся букв E, K, P и Я кодовые слова неизвестны. Известно, что слово ПЕРЕКРЕСТОК было закодировано минимально возможным количеством двоичных знаков. Какое наименьшее суммарное количество двоичных знаков при этом было использовано для кодовых слов оставшихся букв Е, К, Р, Я? В ответе запишите суммарную длину кодовых слов букв Е, К, Р и Я. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение

# Задача 4: Код Фано (префиксный код)
def is_prefix_free(codes):
    """Проверка: ни один код не является префиксом другого"""
    sorted_codes = sorted(codes)
    for i in range(len(sorted_codes) - 1):
        if sorted_codes[i+1].startswith(sorted_codes[i]):
            return False
    return True
# Известные коды из условия задачи:
# known = {'К': '01', 'Я': '001'}
# unknown_symbols = ['А', 'О', 'Н', 'П', 'Ч']
# message = 'ТЕКСТ...'
# Перебор возможных кодов
# и подсчёт минимальной/максимальной длины кодировки
# Ответ: 13

Ответ:13

#419

Условие

По каналу связи передаются шифрованные сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для семи из восьми букв известны: А — 00
Б — 010
В — 011
Г — 100
Е — 1010
Ж — 1011
З — 110
Д — ? Известно, что код буквы Д также удовлетворяет условию Фано и является единственно возможным при данном наборе кодов остальных букв. Определите кодовое слово буквы Д и декодируйте сообщение, переданное последовательностью 111101001100. Запишите в ответе полученное слово (только буквы, без пробелов).

Решение

Строим бинарное дерево кодов Фано:
Уровень 1: 0 → далее; 1 → далее
Уровень 2: 00=А; 01→далее; 10→далее; 11→далее
Уровень 3: 010=Б; 011=В; 100=Г; 101→далее; 110=З; 111→далее
Уровень 4: 1010=Е; 1011=Ж; 111→далее (только один свободный лист — 111)

Единственный оставшийся лист: 111 → Д = 111.

Декодирование 111101001100:
111 → Д
1010 → Е
011 → В
00 → А

Слово: ДЕВА.

Ответ: ДЕВА.

Ответ:ДЕВА

#420

Условие

По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для пяти из шести букв известны:
А — 0
Б — 10
В — 110
Г — 1110
Д — 11110
Е — ?

Известно, что код буквы Е также удовлетворяет условию Фано и является единственно возможным при данном наборе кодов остальных букв. Определите кодовое слово буквы Е и декодируйте сообщение, переданное последовательностью 1011111111100. Запишите в ответе полученное слово (только буквы, без пробелов).

Решение

Строим бинарное дерево кодов Фано:
0=А; 10=Б; 110=В; 1110=Г; 11110=Д; единственный свободный лист: 11111=Е.

codes = {'А':'0','Б':'10','В':'110','Г':'1110','Д':'11110','Е':'11111'}
decode = {v:k for k,v in codes.items()}
msg = '1011111111100'
result, i = [], 0
while i < len(msg):
    for L in [1,2,3,4,5]:
        if msg[i:i+L] in decode:
            result.append(decode[msg[i:i+L]])
            i += L; break
print(''.join(result))  # БЕДА
# 10→Б, 11111→Е, 11110→Д, 0→А

Ответ:БЕДА

№4 — примеры решений