8-Lesson №13

Каждый человек в повседневной жизни, в учёбе или на работе решает огромное количество задач самой разной сложности. Сложные задачи требуют длительных размышлений для нахождения решения; простые и привычные задачи человек решает, не задумываясь, автоматически. В большинстве случаев решение каждой задачи можно разбить на простые этапы (шаги). Для многих таких задач (установка программного обеспечения, сборка шкафа, создание сайта, эксплуатация технического устройства, покупка авиабилета через Интернет и т. д.) уже разработаны и предлагаются пошаговые инструкции, при последовательном выполнении которых можно прийти к желаемому результату.

    Решение задачи «Зарегистрировать аккаунт в VK» можно осуществить за шесть шагов:

1. Зайти на сайт vk.com.
2. Нажать на кнопку Зарегистрироваться.
3. Ввести номер телефона.
4. Подтвердить вход (ввести в окно ввода код из СМС).
5. Ввести информацию о себе (имя, фамилия, дата рождения, пол).
6. Подтвердить ввод данных.

    Этапы решения задачи «Нарисовать весёлого ёжика» представлены графически:

    Задача «Найти наибольший общий делитель (НОД) двух целых чисел» может быть решена так:

1. Разложить первое число на простые множители.
2. Разложить второе число на простые множители.
3. Выписать все простые множители, общие для двух чисел.
4. Вычислить НОД путём перемножения общих простых множителей.

    Самое простое решение задачи «Сортировка мусора» может быть таким:

1. Органические отходы (частицы пищи, растения) поместить в бак серого цвета.
2. Неорганические отходы (пластик, бумага, картон, стекло, металл) поместить в бак синего цвета.
3. Ртутные градусники, люминесцентные лампы, батарейки и аккумуляторы сложить отдельно, в небольшую коробку.

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

    Алгоритм может представлять собой описание некоторой последовательности вычислений (пример 3) или шагов нематематического характера (примеры 1, 2, 4). Но в любом случае перед его разработкой должны быть чётко определены начальные условия (исходные данные) и то, что предстоит получить (результат). Можно сказать, что алгоритм — это описание последовательности шагов в решении задачи, приводящих от исходных данных к требуемому результату.

    В общем виде схему работы алгоритма можно представить следующим образом (рис. 3.1).

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

    Следующий алгоритм приводит к тому, что из одного натурального числа получается другое натуральное число:

1. Исходное число переводится в двоичную систему счисления.
2. Подсчитывается число единиц в полученной двоичной записи исходного числа.
3. Если число единиц в двоичной записи нечётное, то к этой записи справа приписывается 1, если чётное — 0.
4. Число, соответствующее дополненной двоичной записи, переводится в десятичную систему счисления.

    Получившееся таким образом число является результатом работы алгоритма.
    Так, если исходным было число 21, то результатом работы алгоритма будет число 43, а если исходным числом было 15, то результатом работы алгоритма будет число 30.

  Каждый алгоритм предназначен для определённого исполнителя.

    Различают формальных и неформальных исполнителей. Формальный исполнитель не вникает в смысл того, что он делает, и не рассуждает, почему он поступает так, а не иначе. Одну и ту же команду формальный исполнитель всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.

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

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

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

    Система команд исполнителя. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует систему команд данного исполнителя (СКИ). Алгоритм составляется с учётом возможностей конкретного исполнителя, иначе говоря, в системе команд исполнителя, который будет его выполнять.

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

Рассмотрим примеры исполнителей.

Исполнитель Черепаха перемещается на экране компьютера, оставляя след в виде линии. Система команд Черепахи состоит из следующих команд:

    Вперёд п (где п — целое число) — вызывает передвижение Черепахи на п шагов в направлении движения — в том направлении, куда развёрнуты её голова и корпус;

    Направо m (где m — целое число) — вызывает изменение направления движения Черепахи на m градусов по часовой стрелке.

    Повтори к [<Команда 1> <Команда 2> … <Команда п>] означает, что последовательность команд в скобках повторится к раз.

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

1. вычти 1
2. умножь на 3

    Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза. При записи алгоритмов для краткости указываются лишь номера команд.
    Например, алгоритм 21212 означает следующую последовательность команд: 

    С помощью этого алгоритма число 1 будет преобразовано в 15: ((1 • 3 — 1) • 3 — 1) • 3 = 15.

    Исполнитель Робот действует на клетчатом поле, между соседними клетками которого могут стоять стены. Робот передвигается по клеткам поля и может выполнять следующие команды, которым присвоены номера:

При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается.

    К пятизначному натуральному числу применяется следующий алгоритм:

1. Вычислить сумму первых трёх цифр.
2. Вычислить сумму последних двух цифр.
3. Записать полученные два числа друг за другом в порядке возрастания (неубывания).

    Пример работы алгоритма для числа 56789:

1. 5 + 6 + 7 = 18.
2. 8 + 9 = 17.
3. Упорядочив, получаем 1718.

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

    В старших разрядах наименьшего пятизначного числа должны быть самые маленькие цифры из возможных; первая цифра должна быть как можно меньше и т. д. В нашем случае это: 17 = 1 + 7 + 9.

    Есть единственный вариант, позволяющий получить вторую сумму из двух цифр: 18 = 9 + 9.
    Составим наименьшее пятизначное число: 17999.
    В старших разрядах наибольшего пятизначного числа должны быть самые большие цифры; первая цифра должна быть как можно больше и т. д. В нашем случае это 18 = 9 + 9 + 0.
    Вторую сумму из двух цифр можно получить только так: 17 = 9 + 8.
    Составим наибольшее пятизначное число: 99098.
    При разработке алгоритма:

1. выделяются фигурирующие в задаче объекты, устанавливаются свойства объектов, отношения между объектами и возможные действия с объектами;
2. определяются исходные данные и требуемый результат;
3. определяется последовательность действий исполнителя, обеспечивающая переход от исходных данных к результату;
4. последовательность действий записывается с помощью команд, входящих в систему команд исполнителя.

    Можно сказать, что алгоритм — план управления исполнителем.

    Не любая инструкция, последовательность предписаний или план действий может считаться алгоритмом. Каждый алгоритм обязательно обладает следующими свойствами: дискретностью, понятностью, определённостью, результативностью и массовостью.

    Свойство дискретности означает, что путь решения задачи разделён на отдельные шаги (действия). Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель может приступить к выполнению следующей команды.

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

    Свойство определённости означает, что в алгоритме нет команд, смысл которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какую команду выполнять следующей. Благодаря этому результат алгоритма однозначно определяется набором исходных данных: если алгоритм несколько раз применяется к одному и тому же набору исходных данных, то на выходе всегда получается один и тот же результат.

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

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

    Рассмотрим один из методов нахождения всех простых чисел, не превышающих некоторое натуральное число п. Этот метод называется «решето Эратосфена» по имени предложившего его древнегреческого учёного Эратосфена (III в. до н. э.).

    Для нахождения всех простых чисел, не больших заданного числа п, следуя методу Эратосфена, нужно выполнить такие шаги:

1. Выписать подряд все натуральные числа от 2 до n (2, 3, 4, …, n).
2. Заключить в рамку 2 — первое простое число.
3. Вычеркнуть из списка все числа, делящиеся на последнее найденное простое число.
4. Найти первое неотмеченное число (отмеченные числа — зачёркнутые числа или числа, заключённые в рамку) и заключить его в рамку — это будет очередное простое число.
5. Повторять шаги 3 и 4 до тех пор, пока не останется неотмеченных чисел.

    Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:

    Рассмотренные свойства алгоритма позволяют дать более точное определение алгоритма.

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

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

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

    Рассмотрим алгоритм, следуя которому первый игрок наверняка обеспечит себе выигрыш.

1. Если число предметов в куче кратно 3, то уступить ход противнику, иначе начать игру, взяв 1 или 2 предмета так, чтобы осталось количество предметов, кратное 3.
2. Своим очередным ходом каждый раз дополнять число предметов, взятых соперником, до 3 (число оставшихся предметов должно быть кратно 3).

    Исполнитель может не вникать в смысл того, что он делает, и не рассуждать, почему он поступает так, а не иначе, т. е. он может действовать формально. Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека. Для этого:

1. процесс решения задачи представляется в виде последовательности простейших операций;
2. создаётся машина (автоматическое устройство), способная выполнять эти операции в последовательности, заданной в алгоритме;
3. человек освобождается от рутинной деятельности, выполнение алгоритма поручается автоматическому устройству.

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

Выполнить домашнюю работу

Выполнить классную работу