В своей жизни человек совершает множество задач различной степени сложности. Простые задачи со временем становятся привычными и выполняются автоматически, порой даже не задумываясь о том, как ей выполнить. Сложные, наоборот, требуют длительных размышлений о том, как найти решение. Практически всегда можно разбить сложные задачи на более простые этапы.
Пример 1: Задача “Найти скорость движения автомобиля” решается в 3 этапа:
- Узнать пройденное расстояние
- Узнать сколько времени заняла поездка
- Поделить расстояние на затраченное время
Пример 2: Этапы решения задачи “Нарисовать ёлку”
Нахождение скорости и рисование ёлки выглядят разными задачами, но их объединяет один принцип:
каждый их этих процессов описывается последовательностью кратких указаний, точное следование которых позволяет получить нужный результат.
Данные последовательности – алгоритмы решения соответствующих задач. Исполнителем этих алгоритмов является человек.
Что такое алгоритм?
Когда идёт работа над задачей, то обычно составляется план действий для её решения. Это может быть описание, в каком порядке производить вычисления, набор правил, инструкций. У нас всегда есть некие начальные условия (исходные данные) и то, что нужно получить (результат). Алгоритм находится как-раз между двумя этими элементами. Из этого можно сделать вывод, что
Алгоритм – это описание последовательности шагов в решении задач, приводящих от исходных данных к требуемому результату.
Исполнитель
Алгоритмы предназначены для определенных исполнителей.
Исполнитель – это некоторый объект (человек, животное, техническое устройство), способный выполнять определенный набор команд.
Есть два вида исполнителей:
- Формальный
- Неформальный
Формальный исполнитель одну и ту же команду всегда выполняет одинаково.
Неформальный исполнитель может по-разному выполнять команду.
Подумай, к какому виду исполнителю относится человек?
Рассмотрим более подробно формальных исполнителей.
Формальных исполнителей действительно очень много, все они разнообразны, так как их создают для определенных задач. Но у них всех можно указать такие характеристики: круг решаемых задач (назначение), среду, систему команд и режим работы.
Разберем каждую характеристику подробнее:
Круг решаемых задач.
Каждый исполнитель создается для решения некоторого круга задач – выполнение вычислений, построение рисунков на плоскости, построение цепочек символов.
Среда исполнителя.
Область или условия, в которых находится исполнитель называют средой данного исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм. Также среду можно рассматривать как полный набор характеристик, которые описывают состояние исполнителя.
Система команд исполнителя.
Делятся на две группы:
- Команды-приказы
Предписание исполнителю о выполнении отдельного законченного действия. - Команды-запросы
Позволяют узнать текущие характеристики среды исполнителя
Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образуют систему команд данного исполнителя (СКИ).
Режим работы исполнителя.
Для большинства исполнителей предусмотрены режимы непосредственного (ручного) управления и программного управления. В первом случае исполнитель ожидает команд от человека и каждую поступившую команду немедленно выполняет. Во втором случае исполнителю сначала задается полная последовательность команд (программа), а затем он выполняет все эти команды в автоматическом режиме.
Примеры исполнителей.
Исполнитель Черепаха
Перемещается на экране компьютера, оставляя след в виде линии. Система команд Черепахи состоит из следующих команд:
- Вперёд n (где n – целое число) – вызывает передвижение Черепахи на n шагов в направлении движения – туда, куда она смотрит.
- Направо m (где m – целое число) – вызывает изменение направления движения Черепахи на m градусов по часовой стрелке.
- Запись Повтори k [<Команда 1><Команда 2> … <Команда n>], означает, что последовательность команд в скобках повторится k раз.
Подумай, какая фигура появится на экране после выполнения Черепахой следующего алгоритма:
Повтори 12 [Направо 45 Вперёд 20 Направо 45]
Исполнитель Вычислитель
Система команд Вычислителя состоит из двух команд, которым присвоены номера:
1 – вычти 1
2 – умножь на 3
Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза.
При записи алгоритмов для краткости указываются лишь номера команд. Например, алгоритм 21212 означает следующую последовательность команд:
умножь на 3
вычти 1
умножь на 3
вычти 1
умножь на 3
С помощью этого алгоритма число 1 будет преобразовано в 15: ((1 * 3 – 1) * 3 – 1) * 3 = 15
Исполнитель Робот
Исполнитель Робот действует на клетчатом поле, между соседними клетками которого могут стоять стены. Робот передвигается по клеткам поля и может выполнять следующие команды, которым присвоены номера:
1 – вверх
2 – вниз
3 – вправо
4 – влево
При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении.
Если же в этом направлении между клетками стоит стена, то Робот разрушается.
Что произойдет с Роботом, если он выполнить последовательность команд 32323 (здесь цифры обозначают номера команд), начал движение из клетки А? Какую последовательность команд следует выполнить Роботу, чтобы переместиться из клетки А в клетку В, не разрушившись от столкновения со стеной?
Свойства алгоритма
Не все инструкции, последовательности, предписания или планы действий могут быть алгоритмами. Каждый алгоритм обязательно обладает следующими свойствами: дискретностью, понятностью, определённостью, результативностью и массовостью.
Разберём эти свойства подробнее:
Свойство Дискретности – Путь решения задачи разделен на отдельные шаги (действия). Каждому действию соответствует команда.
Только выполнив одну команду, исполнитель может приступить к выполнению следующей команды.
Свойство понятности – Алгоритм состоит только из команд, которые исполнитель может понять и по которым может выполнить требуемые действия.
Свойство определённости – В алгоритме нет команд, смысл которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какую команду выполнять следующей.
Благодаря этому результат алгоритма однозначно определяется набором исходных данных: если алгоритм несколько раз применяется к одному и тому же набору исходных данных, то на выходе всегда получается один и тот же результат.
Свойство результативности – Алгоритм должен обеспечивать получение результата после конечного, возможно, очень большого. числа шагов.
При этом результатом считается не только обусловленный постановкой задачи ответ, но и вывод о невозможности продолжения по какой-либо причине решения данной задачи.
Свойство массовости – Алгоритм должен обеспечивать возможность его применения для решения любой задачи из некоторого класса задач. Например, алгоритм нахождения корней квадратного уравнения должен быть применим к любому квадратному уравнению, алгоритм перехода улицы должен быть применим в любом месте улицы, алгоритм приготовления лекарства должен быть применим для приготовления любого его количества.
Источники: Босова Л. Л., Босова А. Ю., Информатика: учебник для 8 класса. М. : БИНОМ. Лаборатория знаний