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

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

2 Каждый алгоритм должен обладать следующими основными свойствами: 1 Результативность. Это свойство состоит в том, что при выполнении алгоритма будет обязательно получен результат. Результат может быть положительным, нулевым, отрицательным. 2 Однозначность. Это свойство состоит в том, что каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола. 3 Конечность. Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов. 4 Массовость. Это свойство состоит в том, что алгоритм решения задачи разрабатывается не для одной конкретной задачи, а целого класса однотипных задач, различающихся лишь исходными данными.

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

4 Установите соответствие между свойствами и их объяснениями. (Запишите так: I-a, II-b ) Свойство Объяснение I. массовость a) можно разбить алгоритм на отдельные действия II.результативност ь b) можно получить результат при решении всех задач данного вида III.конечность c) при одних и тех же данных получается один результат IV.однозначность d) при выполнении алгоритма будет получен результат Задание 1 (в тетради).

5 Задание 2 (в тетради). Какое свойство алгоритма нарушено, если в результате его выполнения происходит следующее: a) смена дня и ночи. b) сумма двух любых чисел равна 4. c) сделать хотел козу, а получил грозу. d) ни ответа, ни привета.

6 Однажды бог Дионис предложил царю Мидасу воспользоваться алгоритмом «Исполнение желаний». Мидас пожелал, чтобы все, к чему он прикасался, превращалось в золото. Уже через несколько минут он стал самым богатым человеком на свете. Вскоре, однако, возникло неожиданное затруднение: еда и питье царя Мидаса также превращались в золото. Царю грозила голодная смерть! Хорошо, что Дионис сжалился над ним и прервал выполнение своего алгоритма. Какое свойство алгоритма было нарушено Мидасом?

7 CПОСОБЫ ОПИСАНИЯ АЛГОРИТМА. Запись алгоритма на естественном языке Запись алгоритма на естественном языке не требует детальных разъяснений и полной формализации. Она обычно используется для алгоритмов, ориентированных на исполнителя - человека. Форма записи команд не формализуется. В командах помимо слов могут использоваться символы и формулы. Важно лишь то, чтобы каждая команда была понятна исполнителю, точно определяла его действия и могла бы быть им выполнена.

8 Примеры алгоритмов можно найти повсюду: рецепт в кулинарной книге, инструкция по использованию плеера, правила деления «столбиком» и т.д. Обычно, мы использует различные алгоритмы не задумываясь. Например, открывая дверь ключом, никто не размышляет над тем, в какой последовательности выполнять действия. Однако чтобы кого-нибудь (скажем, младшего брата) научить открывать дверь, придется четко указать и сами действия, и порядок их выполнения. Например, так: Достать ключ. Вставить ключ в замочную скважину. Повернуть ключ 2 раза против часовой стрелки. Вынуть ключ. Давайте переставим в первом алгоритме второе и третье действия: Достать ключ. Повернуть ключ 2 раза против часовой стрелки. Вставить ключ в замочную скважину. Вынуть ключ. Конечно, можно выполнить и этот алгоритм. Но дверь вряд ли откроется. А что произойдет, если поменять местами четвертое и пятое действия во втором алгоритме? Он станет невыполнимым! Для алгоритма важен не только набор действий, но и то, в каком порядке они выполняются.

9 Пусть дан отрезок АВ. Определите, для решения какой задачи предназначен следующий алгоритм: Поставить ножку циркуля в точку А. Установить раствор циркуля равным длине отрезка АВ. Провести окружность. Поставить ножку циркуля в точку В. Провести окружность. Провести прямую через точки пересечения окружностей. Запишите пример в тетрадь!

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

11 Пример. Составить блок-схему алгоритма вычисления площади треугольника по трем его строкам а, Ь, с согласно формуле

12 Запись алгоритма на формальном ( алгоритмическом) языке. В этом случае используются определенные знаки, слова, правила для записи алгоритм. Общий вид алгоритма на формальном языке выглядит так: алг имя алгоритма начало | тело алгоритма (последовательность команд) Конец Слова алг, начало, конец являются служебными и служат для оформления алгоритма. Имя алгоритма подбирается по результату его выполнения.

13 Задача «Волк, коза и капуста». На берегу реки стоит крестьянин с лодкой, а рядом с ним волк, коза и капуста. Крестьянин должен переправиться сам и перевезти волка, козу и капусту на другой берег. Однако в лодку, кроме крестьянина, помещается либо только волк, либо только коза, либо только капуста. Оставлять же волка с козой или козу с капустой без присмотра нельзя волк может съесть козу, а коза капусту. Как должен вести себя крестьянин?

14 Пример 1: Оформим двумя способами алгоритм решения задачи Волк, коза и капуста. БытовойФормальный перевези козу на другой берег вернись перевези волка вернись вместе с козой вези капусту переправься возьми козу и переправься алг Перевоз начало перевези козу переправься перевези волка перевези козу перевези капусту переправься перевези козу конец

15 алг площадь треугольника (вещ А, В, X) Арг А, В рез Х нач ввод А,В,С р = (А + В + С) / 2 S = р(р – А)(р – В)(р – С) вывод S кон Пример 2. Найдите площадь треугольника по трём сторонам (формула Герона).

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

17 В старинной задаче под названием Волк, коза и капуста Крестьянин был Исполнителем, а его СКИ состояла из четырех операций (перевези козу, перевези волка, перевези капусту, переправься). У каждого исполнителя свой набор команд, именно этим они и отличаются друг от друга. Не всякую команду можно исполнить в любой ситуации. Например, если Крестьянину, находящемуся на пустом берегу дать команду «перевези козу», выполнение алгоритма остановится. Это и понятно: козы нет и перевозить нечего. Эту невозможность выполнить команду мы назовем «ОТКАЗ».

18 О любом исполнителе нужно знать: среда, в которой он работает СКИ (команды и способ их выполнения) когда возникают отказы

19 УПРАЖНЕНИЯ 1.Назвать исполнителей следующих видов работы: уборка в классе, перевозка пассажиров, обучение детей в школе. Попробуйте сформулировать СКИ для каждого из этих исполнителей. 2.Придумать своего исполнителя и описать его по схеме: среда, СКИ, отказы.