ГДЗ по информатике 11 класс учебник Босова параграф 5









1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.

  • детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
  • результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
  • массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
  • дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений;
  • конечность. Каждое из действий и весь алгоритм в целом обязательно завершаются.

 

2. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?

Приготовление не обладает массовостью, так как порядок приготовления торта, не подойдет к приготовлению салата.

3. Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.

1 Проведём окружность с центром в точке А таким радиусом, чтобы она пересекла прямую а в двух точках. Назовём их В и С.

2 С центром в точке В проведем окружность радиусом больше половины длины отрезка ВС.                

3 C центром в точке С этим же радиусом проведём окружность. Получим точку D.                    

4 Через точки А и D проведём прямую. Она будет являться перпендикуляром к прямой а.

4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?

Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.

Одновременно опрокидываем песочные часы на 3 и на 8 минут. 3-минутные часы будем запускать 5 раз, т. е. отсчитаем ими 15 минут. Варить эликсир начнем сразу же после остановки 8-минутных часов (15 - 8 = 7).

5. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.

Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа х?

Алгоритмы с разными выходными данными:

1) x + 5 * 5 + 2 * 0 = x + 25

2) x + 5 * 4 - 2 * 1 = x + 18

3) x + 5 * 3 - 2 * 2 = x + 11

4) x + 5 * 2 - 2 * 3 = x + 4

5) x + 5 * 1 - 2 * 4 = x - 3

6) x + 5 * 0 - 2 * 5 = x - 10

Всего разных алгоритмов : 2^5 = 32

Всего алгоритмов с разными выходными данными: 6

Значит, к одинаковым результатам будут приводить: 32 - 6 = 26 алгоритмов

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

Например, исполнитель умеющий только проводить арифметические операции не сможет найти синус числа.

7. Перечислите известные вам способы записи алгоритмов.

словесный (запись на естественном языке);

графический (запись с использованием графических символов);

программный (тексты на языках программирования).

8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.

Алгоритм по разогреванию супа.

Алгоритм по игре в крестики-нолики

Алгоритм вычисления математической формулы

9. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:

1) вычисляется сумма первой и второй цифр числа;
2) вычисляется сумма второй и третьей цифр числа;
3) вычисляется сумма третьей и четвёртой цифр числа;
4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;
5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.

Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.

Опишите систему команд этого исполнителя.

Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?

Укажите минимальное и максимальное значения результата работы этого исполнителя.

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

Система команд данного исполнителя подразумевает в себе 5 основных действий с 4-значным числом:

1) Сложить 1 и 2 цифру

2) Сложить 2 и 3 цифру

3) Сложить 3 и 4 цифру

4) Найти минимум из этих полученных сумм

5) Отсортировать оставшийся (исходя из 4 пункта) 2 суммы в порядке возрастания.

 

Могут ли результатом работы этого исполнителя быть чиста 1610, 1010, 1019?

 

Ответ:

1610 - нет (потому что 2 числа должны идти в порядке возрастания, а 610 в сумме двух чисел мы получить не сможем)

1010 - возможно. Если число будет 5555.

1019 - нет (потому что мы не можем получить в сумме 2 чисел 19 (максимум 18))

Минимальное число, которое можно получить после обработки данным алгоритмом: 1818 (9999 число до алгоритма)

Минимальное: 01 (1000 число до алгоритма)

Число после алгоритма 1418:

Минимальное число: 1599 (1->6,2->14,3->18,4->6,5->1418)

Максимальное число: 9959 (1->18,2->14,3->14,4->14,5->1418)

 

10. Подготовьте краткое сообщение об одном из учёных (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёсших вклад в развитие теории алгоритмов.

В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

Что собой представляет машина Тьюринга?

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

  • Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
  • Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
  • Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

  • Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
  • Передвигаться на одну ячейку влево или вправо.
  • Менять свое внутреннее состояние.

Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).

 

11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.

В чём отличие шага алгоритма от команды алгоритма

12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?

Сложность алгоритма – это объем работы, который выполнится некоторым алгоритмом. Зависит от входных значений.

13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.

14. Какой алгоритм считается эффективным?

Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня.

15. Постройте эффективный алгоритм возведения числа х в степень n = 152.

 

program step;

var x,n,s,i : integer;

begin

s:= 1;

writeln('Введите число, которое нужно возвести в степень: ');

read(x);

writeln('Введите число n');

readln(n);

n := n - 152;

for i := 1 to n do

 s := s*x;

writeln(s);

end.

Смотрите также: