ГДЗ: Параграф § 4 / Информатика 10 класс

• Пример 1: Решение уравнения по математике. Исходные данные: текст уравнения. Алгоритм: правила преобразования уравнений, правила переноса слагаемых. Результат: значение неизвестной переменной. Тип обработки: Обработка, связанная с получением нового содержания (нового знания).

• Пример 2: Составление списка дел (ToDo-list) на день. Исходные данные: список всех задач (письменные заметки, устные поручения). Алгоритм: правила структурирования (приоритет по срочности, группировка по месту). Результат: упорядоченный список. Тип обработки: Обработка, связанная с изменением формы представления (структурирование).

• Пример 3: Поиск телефона друга в записной книжке. Исходные данные: список контактов, отсортированный по имени. Алгоритм: метод половинного деления (открытие середины и переход к нужной половине). Результат: номер телефона. Тип обработки: Обработка, связанная с изменением формы представления (поиск информации).

Задача о числе размещений с повторениями. Поскольку порядок элементов важен, и для каждого из \( n=8 \) элементов есть \( m=4 \) независимых варианта цвета, общее количество сигналов равно: \( m^n \).
\( 4^8 = 4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 65536 \).

Решение:

Пусть \( n \) – количество цифр, \( m \) – количество букв. Общее количество номеров равно: (Количество комбинаций цифр) \(\times\) (Количество комбинаций букв).
Количество цифр: \( 10^3 = 1000 \).
Количество букв: \( 5^x \), где \( x \) – количество букв в номере.
Требуется, чтобы \( 1000 \cdot 5^x \ge 100000 \).
\( 5^x \ge \frac{100000}{1000} \)
\( 5^x \ge 100 \).
Проверяем степени 5:
\( 5^1 = 5 \)
\( 5^2 = 25 \)
\( 5^3 = 125 \).
Минимальное количество букв, при котором \( 5^x \ge 100 \) – это \( x=3 \).
Наименьшее количество букв, которое должно быть в номере, — 3.

Решение:

Сначала проверяем условие Фано для заданных кодов:

• А (\( 000 \)) является началом Е (\( 001 \)).

• С (\( 10 \)) является началом D (\( 11 \)).

Условие Фано нарушено, поэтому коды нельзя декодировать однозначно слева направо. Для однозначного декодирования необходимо проверить обратное условие Фано (код не является окончанием другого):

• В (\( 01 \)) является окончанием С (\( 10 \)), D (\( 11 \)), Е (\( 001 \)) и А (\( 000 \)).

Обратное условие Фано также нарушено, поэтому декодирование невозможно ни слева направо, ни справа налево. Однако, поскольку только одно сообщение пришло без ошибок, мы должны найти то, которое можно разбить на целые кодовые слова.

Проверим сообщения, разбивая их на кодовые слова:

• 1) \( \mathbf{11} \mid \mathbf{01} \mid \mathbf{000} \mid \mathbf{001} \mid \mathbf{001} \mid \mathbf{10} \mid \mathbf{011} \). Невозможно. \( \mathbf{011} \) – нет такого кода.

• 2) \( \mathbf{11} \mid \mathbf{10} \mid \mathbf{10} \mid \mathbf{000} \mid \mathbf{01} \mid \mathbf{001} \mid \mathbf{001} \mid \mathbf{10} \). Невозможно. \( \mathbf{1110} \) - нет кода. Попробуем с начала: \( \mathbf{11} \mid \mathbf{10} \mid ... \) - не подходит.

• 3) \( \mathbf{11} \mid \mathbf{01} \mid \mathbf{000} \mid \mathbf{001} \mid \mathbf{001} \mid \mathbf{111} \). Невозможно. \( \mathbf{111} \) – нет такого кода.

• 4) \( \mathbf{11} \mid \mathbf{01} \mid \mathbf{10} \mid \mathbf{000} \mid \mathbf{001} \mid \mathbf{001} \mid \mathbf{10} \mid \mathbf{10} \). Возможно: \( \mathbf{11} (\text{D}) \mid \mathbf{01} (\text{B}) \mid \mathbf{10} (\text{C}) \mid \mathbf{000} (\text{A}) \mid \mathbf{001} (\text{E}) \mid \mathbf{001} (\text{E}) \mid \mathbf{10} (\text{C}) \mid \mathbf{10} (\text{C}) \). Сообщение: DBCAEECC.

Сообщение под номером 4 пришло без ошибок, так как его можно полностью разбить на целые кодовые слова из таблицы.

Решение:

Для однозначного декодирования должен использоваться префиксный код, то есть должен выполняться критерий Фано. Построим кодовое дерево, используя имеющиеся коды А (\( 0 \)), Б (\( 10 \)), В (\( 110 \)):

• Ветка \( 0 \) занята кодом А.

• Ветка \( 10 \) занята кодом Б.

• Ветка \( 110 \) занята кодом В.

Остается свободная ветвь, начинающаяся с \( 111 \). Ближайшее свободное место – это кодовое слово \( 111 \). Если мы присвоим Д код \( 111 \), то это будет кратчайший код длиной 3, и он не будет нарушать условие Фано, так как он не является префиксом имеющихся кодов.

Кратчайший код для Д: \( 111 \).

Далее можно искать коды длиной 4: \( 1110 \) и \( 1111 \). Варианты \( 1110 \) и \( 1111 \) также удовлетворяют условию Фано.

Решение:

Проверим условие Фано для существующего кода: А (\( 0 \)), Б (\( 11 \)), В (\( 20 \)), Г (\( 21 \)), Д (\( 22 \)). Условие Фано выполняется, так как ни один код не является префиксом другого.

Попробуем сократить длину одного из кодов, не нарушив условие Фано. Единственный код длиной 1 – это А (\( 0 \)).

• Можно ли сократить Б (\( 11 \)) до \( 1 \)? Если Б = \( 1 \), то Б будет префиксом (\( 1 \)) кода Б (\( 11 \)) (префикс самого себя) и префиксом остальных кодов. Нельзя.

• Можно ли сократить В (\( 20 \)) до \( 2 \)? Если В = \( 2 \), то В будет префиксом (\( 2 \)) кодов В (\( 20 \)), Г (\( 21 \)) и Д (\( 22 \)). Нельзя.

Поскольку сокращение любого кода длиной 2 до кода длиной 1 (кроме \( 0 \), который уже занят) приведет к тому, что этот новый код станет префиксом других кодов, начинающихся с этой же цифры, то нельзя сократить длину ни одного кодового слова, чтобы сохранить однозначное декодирование при условии, что коды остальных букв остаются неизменными.

Решение:

Данное задание не может быть решено, так как не указана длина кодовых слов, и не указан алфавит, используемый для построения кодов (указаны только буквы, которые нужно кодировать). Если предположить, что кодовые слова имеют длину \( N \) и построены из двоичного алфавита \( \{0, 1\} \), то задача о количестве кодовых слов, где нет трех одинаковых символов подряд, решается методом динамического программирования, но это выходит за рамки материала, приведенного в параграфе. Поскольку в условии не определена ни длина, ни алфавит кодовых слов, ответ дать невозможно.

Решение:

Последовательность состоит из \( N=18 \) чисел. Элементы упорядочены по возрастанию.

Просмотр 1: Центральный элемент имеет индекс \( \lfloor 18/2 \rfloor + 1 = 10 \). Центральный элемент: \( 389 \). Искомое \( 180 < 389 \). Отбрасываем правую часть. Последовательность: \( 061 \ 087 \ 154 \ 180 \ 208 \ 230 \ 290 \ 345 \ 367 \).

Просмотр 2: В оставшейся части (\( N=9 \)) центральный элемент имеет индекс \( \lfloor 9/2 \rfloor + 1 = 5 \). Центральный элемент: \( 208 \). Искомое \( 180 < 208 \). Отбрасываем правую часть. Последовательность: \( 061 \ 087 \ 154 \ 180 \).

Просмотр 3: В оставшейся части (\( N=4 \)) центральный элемент имеет индекс \( \lfloor 4/2 \rfloor + 1 = 3 \). Центральный элемент: \( 154 \). Искомое \( 180 > 154 \). Отбрасываем левую часть. Последовательность: \( 180 \).

Просмотр 4: Оставшийся элемент \( 180 \) совпадает с искомым. Поиск завершен.

Решение:

Описанный алгоритм поиска первого незаполненного склада в упорядоченном наборе данных (номера складов) является методом половинного деления (бинарным поиском).

Нам известно, что склады с 1 по 15 заполнены, а склады с 16 по 31 – пусты. Искомый 'склад' – это первый пустой склад, то есть склад №16.

• Шаг 1: Открывается центральный склад \( \frac{31+1}{2} = 16 \). Склад №16 пуст.

• Шаг 2: Ищется первый незаполненный склад в диапазоне 1–15. Открывается средний склад: \( \frac{1+15}{2} = 8 \). Склад №8 заполнен. Ищем в диапазоне 9–15.

• Шаг 3: Открывается средний склад: \( \frac{9+15}{2} = 12 \). Склад №12 заполнен. Ищем в диапазоне 13–15.

• Шаг 4: Открывается средний склад: \( \frac{13+15}{2} = 14 \). Склад №14 заполнен. Ищем в диапазоне 15–15.

• Шаг 5: Открывается склад: 15. Склад №15 заполнен. Ищем в диапазоне 16–15. (Диапазон пуст).

Плотник ищет первый незаполненный склад, начиная с 16. Его цель — найти первый пустой склад. Первый пустой склад — №16.

После того, как плотник обнаружил, что склады 1–15 заполнены, он должен был сделать следующее, чтобы найти первый незаполненный (склад №16):

• 1. Открыл 16. Склад №16 пуст. Цель: искать первый незаполненный в 1–15.

• 2. Открыл 8. Склад №8 заполнен. Искать незаполненный в 9–15.

• 3. Открыл 12. Склад №12 заполнен. Искать незаполненный в 13–15.

• 4. Открыл 14. Склад №14 заполнен. Искать незаполненный в 15–15.

• 5. Открыл 15. Склад №15 заполнен. Искать незаполненный в 16-15. (Диапазон 16–15 пуст).

Плотник должен был вернуться к границе раздела заполненных и пустых складов, которой является склад №16. В итоге ему пришлось открыть 5 дверей (16, 8, 12, 14, 15).