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

• Дискретность: Последовательность шагов для закрытия двери ключом – каждый шаг должен быть выполнен перед переходом к следующему.
• Детерминированность: Арифметическая операция, например, сложение двух чисел, всегда дает один и тот же результат.
• Понятность: Инструкция по сборке мебели должна быть понятна человеку без необходимости принимать самостоятельные решения.
• Результативность: Алгоритм нахождения простых чисел должен завершиться за конечное время.
• Массовость: Алгоритм деления подходит для деления любых двух чисел, а не только конкретной пары.

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

Для исправления необходимо заменить неопределенный шаг 2 на точное, измеримое предписание. Например:

• Шаг 1: Отложить на прямой \(MN\) отрезки \(AB\) и \(AC\) одинаковой длины, используя циркуль с центром в точке \(A\).
• Шаг 2 (измененный): Установить раствор циркуля равным двум длинам отрезка \(AB\) (или \(AC\)).
• Шаг 3: Провести дуги окружностей с центрами в точках \(B\) и \(C\) заданным раствором, найти две точки пересечения \(D\) и \(E\).
• Шаг 4: Соединить точки \(D\) и \(E\) прямой линией, получить отрезок \(DE\). Этот отрезок пройдет через точку \(A\) и будет искомым перпендикуляром.

Таким образом устраняется двусмысленность «в полтора-два раза больше», и алгоритм становится детерминированным и понятным.

• Шаг 1: Одновременно запускаем часы на 3 минуты и на 8 минут.
• Шаг 2: Когда истекут 3-минутные часы, в 8-минутных остается \(8-3 = 5\) минут. Начинаем варку.
• Шаг 3: Когда истекут 8-минутные часы (т.е. прошло 5 минут варки), их тут же переворачиваем.
• Шаг 4: Через 2 минуты (когда 8-минутные часы закончат отсчет оставшихся в них 2 минут), общее время варки составит \(5 + 2 = 7\) минут.

Система команд исполнителя Колдун:

• Налить: Налить 100 мл воды в котел.
• Добавить(Ингредиент): Добавить указанный ингредиент в котел.
• Нагреть(Т): Нагреть котел до температуры \(T\) градусов.
• Помешать: Перемешать содержимое котла.
• Отмерить(Время): Отмерить указанное время (минуты) с помощью песочных часов.

Алгоритм «Эликсир»:

• Шаг 1: Налить 100 мл воды в котел.
• Шаг 2: Добавить(Корень Мандрагоры).
• Шаг 3: Добавить(Пыльца Папоротника).
• Шаг 4: Помешать.
• Шаг 5: Нагреть(\(90^\circ C\)).
• Шаг 6: Отмерить(7) минут (см. решение задачи 4).
• Шаг 7: Добавить(Слеза Феникса).
• Шаг 8: Выключить нагрев.

• Количество алгоритмов: Поскольку каждый из 5 шагов может быть выполнен одной из двух команд, общее количество различных алгоритмов равно \(2^5 = 32\).
• Одинаковый результат: Для того чтобы результат был одинаковым, общее количество прибавлений (+5) и вычитаний (-2) должно быть одинаковым. Пусть \(k\) — количество прибавлений, \(5-k\) — количество вычитаний. Итоговый результат: \(5k + (-2)(5-k) = 5k - 10 + 2k = 7k - 10\). Для фиксированного результата \(R\) (например, \(R=4\)), \(7k - 10 = R\), то есть \(7k = R+10\). Поскольку \(k\) может принимать значения от 0 до 5, для разных результатов \(R\) будет разное количество алгоритмов. Например, если \(R=4\), то \(k=2\), то есть 2 прибавления и 3 вычитания. Количество таких алгоритмов — количество перестановок: \(C_5^2 = \frac{5!}{2!3!} = 10\).

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

• Словесное описание на естественном языке.
• Запись на языке программирования.
• Графическое представление в виде блок-схем.
• Запись на частично формализованном естественном языке (например, с математическими обозначениями).

• Задача: Алгоритм быстрого возведения в степень \(x^n\). Оптимальный способ записи: Формализованный текст с математическими обозначениями, чтобы показать шаги, основанные на двоичном представлении \(n\).
• Задача: Структура программы, включающая условные операторы и циклы. Оптимальный способ записи: Блок-схема, поскольку она наглядно отображает логическую структуру и ветвления алгоритма.
• Задача: Реализация программы на компьютере. Оптимальный способ записи: Запись на языке программирования (например, Python, C++), так как это готовый к выполнению код.

Система команд исполнителя Автомат:

• \(S1 \leftarrow D1 + D2\): Вычислить сумму первой и второй цифры (\(D1, D2\)).
• \(S2 \leftarrow D2 + D3\): Вычислить сумму второй и третьей цифры (\(D3\)).
• \(S3 \leftarrow D3 + D4\): Вычислить сумму третьей и четвертой цифры (\(D4\)).
• Отбросить(S): Отбросить из множества \(\{S1, S2, S3\}\) ту сумму \(S\), которая не превышает двух других (то есть \(\min\{S1, S2, S3\}\)).
• Записать(S_A, S_B): Записать оставшиеся суммы \(S_A\) и \(S_B\) в порядке неубывания без разделителей.

Возможность получения результатов 1610, 1010, 1019:

• Цифры \(D_i \in [0, 9]\). Максимальная сумма \(D_i + D_j = 9 + 9 = 18\). Минимальная сумма \(D_i + D_j = 0 + 0 = 0\).
• Результат состоит из двух двузначных чисел (сумм) \(S_A\) и \(S_B\).
• 1610: Невозможно. Суммы \(S_i\) не могут быть больше 18. Число 1610 состоит из 16 и 10. \(16 \le 18\) и \(10 \le 18\) — возможно.
• 1010: Невозможно. Суммы \(S_i\) не могут быть больше 18. Число 1010 состоит из 10 и 10. \(10 \le 18\) и \(10 \le 18\) — возможно.
• 1019: Невозможно. Сумма \(S_i\) не может быть 19, так как \(9+9=18\).

Минимальное и максимальное значение результата:

• Минимальный результат: Получается, когда все цифры минимальны, например \(0000\). \(S1=0, S2=0, S3=0\). Отбросить \(\min(0, 0, 0)=0\). Оставшиеся 0, 0. Результат: 00.
• Максимальный результат: Получается, когда все цифры максимальны, например \(9999\). \(S1=18, S2=18, S3=18\). Отбросить \(\min(18, 18, 18)=18\). Оставшиеся 18, 18. Результат: 1818.

Наименьшее и наибольшее \(x\) для результата 1418:

• Результат 1418 означает, что две оставшиеся суммы \(\{S_A, S_B\}\) равны 14 и 18. (Порядок неубывания).
• Отброшенная сумма \(S_{\min}\) должна быть меньше или равна 14. То есть \(\{S1, S2, S3\} = \{14, 18, S_{\min}\}\), где \(S_{\min} \le 14\).
• Наименьшее \(x\) (минимум \(D1D2D3D4\)): Для минимума ищем \(D1, D2\) минимальные, чтобы \(D1+D2=S_{\min}\). \(D4\) должно быть максимальным.
• Случай 1: Отброшен \(S1\). \(S1=14, S2=18, S3=18\). \(D2+D3=18 \implies D2=9, D3=9\). \(D3+D4=18 \implies D4=9\). \(D1+D2=14 \implies D1=14-9=5\). Число: \(5999\).
• Случай 2: Отброшен \(S2\). \(S2=14, S1=18, S3=18\). \(D1+D2=18 \implies D1=9, D2=9\). \(D3+D4=18 \implies D4=9\). \(D2+D3=14 \implies 9+D3=14 \implies D3=5\). Число: \(9959\).
• Случай 3: Отброшен \(S3\). \(S3=14, S1=18, S2=18\). \(D1+D2=18 \implies D1=9, D2=9\). \(D2+D3=18 \implies D3=9\). \(D3+D4=14 \implies 9+D4=14 \implies D4=5\). Число: \(9995\).
• Наименьшее число \(x\): \(5999\).
• Наибольшее \(x\): Для максимума ищем \(D1, D2\) максимальные.
• Случай 2: \(9959\) (максимум среди \(D1, D2\) с \(S2=14\)).
• Случай 3: \(9995\) (максимум среди \(D1, D2\) с \(S3=14\)).
• Наибольшее число \(x\): \(9995\).

Андрей Николаевич Колмогоров (1903–1987) был выдающимся советским математиком, внесшим значительный вклад в теорию алгоритмов. В частности, он совместно с А.А. Марковым и другими математиками работал над уточнением и формализацией понятия алгоритма в 1930-х годах. Идеи Колмогорова о сложности алгоритмов (позже – колмогоровская сложность) стали фундаментальными для современной теории информации, связывая понятие сложности с минимальной длиной программы, необходимой для генерации объекта.

• Команда алгоритма: Это отдельная инструкция, которая записана в описании алгоритма.
• Шаг алгоритма: Это отдельное действие, которое исполнитель выполняет по команде.

Пример: В программе на языке высокого уровня команда может быть строкой: \(C = A + B / 2\). Однако, шагами алгоритма (элементарными действиями) будут несколько машинных операций: 1) разделить \(B\) на 2; 2) сложить \(A\) с результатом деления; 3) присвоить результат переменной \(C\).

Сложность алгоритма – это число элементарных шагов (действий), которые необходимо выполнить для реализации алгоритма. Она зависит в наибольшей степени от объема входных данных \(n\). Чем больше данных, тем, как правило, больше шагов требуется. Сложность выражается как функция \(O(f(n))\), например, линейная \(O(n)\) или квадратичная \(O(n^2)\).

При перемножении двух чисел «столбиком» (\(n\) цифр на \(m\) цифр) выполняются следующие операции:

• Происходит \(m\) умножений первого числа на каждую цифру второго числа. Каждое такое умножение включает \(n\) элементарных умножений цифр. Общее число элементарных умножений: \(n \cdot m\).
• Далее происходит сложение \(m\) промежуточных результатов. Каждое сложение может включать до \(n+m\) цифр. Общее число элементарных сложений пропорционально \(m \cdot (n+m) \approx nm + m^2\).

Таким образом, общая сложность алгоритма перемножения «столбиком» составляет порядка \(O(n \cdot m)\). Если \(n \approx m\), сложность будет \(O(n^2)\), то есть квадратичная.

Эффективным считается алгоритм, который имеет наименьшую сложность, то есть требует наименьшего количества элементарных операций для решения задачи. Эффективность также оценивается объемом оперативной памяти, требуемой для его выполнения. Например, алгоритм с линейной сложностью \(O(n)\) будет эффективнее алгоритма с квадратичной сложностью \(O(n^2)\) для больших значений \(n\).

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

• Шаг 1: Переведем \(n=152\) в двоичную систему: \(152_{10} = 10011000_2\).
• Шаг 2: Запишем \(n\) в виде последовательности бит: \(b_7=1, b_6=0, b_5=0, b_4=1, b_3=1, b_2=0, b_1=0, b_0=0\).
• Шаг 3: Последовательно выполняем возведение в квадрат (К) и, если бит \(b_i=1\), умножение на \(x\) (X).

Последовательность операций для \(x^{152}\):

• Начало: \(R=1\).
• \(b_7=1\): \(R \leftarrow R \cdot x \to R=x\) (X); \(R \leftarrow R^2 \to R=x^2\) (К)
• \(b_6=0\): \(R \leftarrow R^2 \to R=x^4\) (К)
• \(b_5=0\): \(R \leftarrow R^2 \to R=x^8\) (К)
• \(b_4=1\): \(R \leftarrow R \cdot x \to R=x^9\) (X); \(R \leftarrow R^2 \to R=x^{18}\) (К)
• \(b_3=1\): \(R \leftarrow R \cdot x \to R=x^{19}\) (X); \(R \leftarrow R^2 \to R=x^{38}\) (К)
• \(b_2=0\): \(R \leftarrow R^2 \to R=x^{76}\) (К)
• \(b_1=0\): \(R \leftarrow R^2 \to R=x^{152}\) (К)
• \(b_0=0\): \(R \leftarrow R^2 \to R=x^{304}\) (К) (Этот шаг не нужен, так как степень уже достигнута).

Итоговое количество операций: 7 возведений в квадрат и 3 умножения, всего 10 операций. Прямое умножение требовало бы 151 операции.