Видеоурок: Алгоритмы и исполнители.

 

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

Алгоритм решения некоторой задачи - это алгоритм, приводящий к решению этой задачи за конечное число действий

Свойства алгоритма и его исполнители

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

2. Результативность. Получение из исходных данных результата за конечное число шагов.

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

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

5.  Детерминированность. Выполнение команд алгоритма в строго определенной последовательности.

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

7. Конечность. Завершение работы алгоритма за конечное число шагов. Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.

Способы описания алгоритма

1. Словесный способ Алгоритм представляет собой описание на естественном языке последовательных этапов обработки данных.

2. Графический способ Изображение алгоритма в виде последовательности связанных между собой функциональных блоков.

3. Программный способ (алгоритмический) Алгоритм, предназначенный для записи на компьютере, должен быть записан на понятном ему языке. Такой язык называется языком программирования, а запись алгоритма на этом языке – программа.

Исполнитель алгоритма.

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

Класс исполнителей необычайно разнообразен. Прежде всего, в нем выделяют два типа исполнителей: формальных и неформальных. Формальный исполнитель одну и ту же команду выполняет всегда одинаково, неформальный – может выполнять команду по – разному.

Формальными исполнителями являются преимущественно технические устройства. Человек в роли неформального исполнителя всегда сам отвечает за свои действия. За действия неформального исполнителя отвечает управляющий им объект.

Рассмотрим исполнителя – человека. Жизненный опыт человека растет с увеличением числа освоенных им алгоритмов. Например, чтобы ребенок научился покупать в магазине хлеб, ему нужно сначала рассказать, как это делать (а лучше показать). Поэтому для человека можно сформулировать множество алгоритмов. К ним можно отнести и множество различных инструкций.

Управление - это процесс целенаправленного воздействия одних объектов на другие.

Исполнители являются объектами управления. Управлять ими можно, составив для них алгоритм.

Примеры задач на исполнителя:

Пример 1:

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный мо­мент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n — целое число), вызывающая передвижение Черепашки на n шагов в направлении движения; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 КомандаЗ] означает, что последовательность команд в скобках повторится k раз.

Черепашке был дан для исполнения следующий алгоритм: Повтори 9 [Вперёд 50 Направо 60]. Какая фигура появится на экране?

1) правильный шестиугольник

2) правильный треугольник

3) незамкнутая ло­ма­ная линия

4) правильный девятиугольник

Решение:

Выполняя алгоритм, Черепашка оставляет след в виде одинаковых отрезков, расположенных под углом 180° − 60° = 120° друг к другу. Такой угол составляют между собой стороны правильного шестиугольника. Поэтому за первые шесть шагов алгоритма Черепашка нарисует правильный шестиугольник, а за следующие три шага пройдет по трём его сторонам ещё раз. Следовательно, оставленный Черепашкой след представляет собой правильный шестиугольник.

Примечание:

Сумма внутренних углов выпуклого n-угольника равна 180°(n − 2), поэтому угол между его сторонами может быть най­ден по формуле 180°(1 − 2/n).

Правильный ответ указан под номером 1.

Пример 2:

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может вы­полнять команду Сместиться на (a, b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, у) в точку с координатами (x + а, у + b). Если числа a, b положительные, значение соответствующей координаты увеличивается; если отрицательные, уменьшается.

Например, если Чертёжник находится в точке с координатами (4, 2), то команда Сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Запись

Повтори k раз

Команда1 Команда2 КомандаЗ

Конец

означает, что последовательность команд Команда1 Команда2 КомандаЗ повторится k раз.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 4 paз

Команда1 Сместиться на (1, 3) Сместиться на (1, −2) Конец

Сместиться на (−4, −12)

После выполнения этого алгоритма Чертёжник вернулся в исходную точку. Какую команду надо поставить вместо ко­манды Команда1?

1) Сместиться на (1,−2)

2) Сместиться на (12, 4)

3) Сместиться на (2, 11)

4) Сместиться на (−1, 2)

Решение:

Команда Повтори 4 раз означает, что команды Сместиться на (1, 3) и Сместиться на (1, −2) выполнятся четыре раза. В результате Чертёжник переместится на 4·(1 + 1, 3 − 2) = (8, 4). Выполнив последнюю команду Сместиться на (−4, −12), чертёжник окажется в точке (4, −8).

Чтобы Чертёжник вернулся в исходную точку, необходимо переместить его на (−4, 8). Учитывая, наличие команды Повтори 4, приходим к выводу, что Команда 1 это команда Сместиться на (−1, 2).

Правильный ответ указан под номером 4.

Пример 3:

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

Вверх N,

Вниз N,

Вправо N,

Влево N

(где N — целое число от 1 до 7), перемещающие исполнителя на N клеток вверх, вниз, вправо или влево соответственно.

Запись

Повтори k раз

Команда1 Команда2 Ко­ман­даЗ

Конец

означает, что последовательность команд Команда1 Команда2 КомандаЗ повторится k раз. Если на пути Мурвья встре­чается кубик, то он перемещает его по ходу движения. Пусть, например, кубик находится в клетке Е4. Если Муравей выпол­нит команды вправо 2 вниз 2, то сам окажется в клетке ЕЗ, а кубик в клетке Е2.

 

 

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

Повтори 2 раз

Вправо 2 вниз 1 влево 2

Конец

В какой клетке окажется кубик после выполнения этого алгоритма?

1) Д2

2) Е2

3) Е1

4) ГЗ

Решение:

Заметим, что после исполнения команд вправо 2 влево 2, Муравей окажется в той же клетке, из которой он стартовал. Изначально кубик находится в клетке Е4. Выполнив два раза команду вниз 1, Муравей передвинет кубик в клетку Е2.

Возможность автоматизации деятельности человека

Автоматизация – это процессы в различных сферах деятельности человека , упрощающие его труд за счет выполнения алгоритмов работы различными IT- средствами и техническими устройствами. В современном мире автоматизированы уже почти все сферы деятельности человека: от процессов огромных производств до деятельности в малых организациях. Но этот процесс носит постоянных характер, в силу развития самого общества.

Автоматизация процессов управления представляет собой обязательную часть процесса по усовершенствованию деятельности всех предприятий. В последнее время стал намечаться новый этап, характерный стремлением к преобразованию объединенных автоматизированных систем, которые объединяют в себе все управленческие задачи.