Практическая работа № 28.

Тема: Алгоритмизация.

Наименование: Алгоритм и его свойства. Разработка алгоритмов.

Цель работы: Ознакомить с понятием алгоритма и его свойствами, с понятием «исполнитель алгоритма» и система команд. Научить описывать простейшие алгоритмы.

1. Краткие теоретические сведения.

Понятие алгоритма такое же основополагающее для информатики, как и понятие информации.

Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации.

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

§  От компьютера, как от любого другого исполнителя, требуется четкое выполнение команд алгоритма. А от вас, как от разработчиков, требуется знание и соблюдение правил их составления. Эти правила заключаются в том, что алгоритм должен обладать пятью свойствами (требованиями). Требования к алгоритму объясняются тем, что компьютер (ваш исполнитель) не имеет своего интеллекта, его возможности всегда ограничены.

Свойства алгоритмов (требования к алгоритмам).

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

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

3. Определенность (детерминированность). Будучи понятным, алгоритм не должен содержать команды, смысл которых может восприниматься неоднозначно. (Например, робот будет поставлен в тупик командой "Взять два-три инструмента": что значит "два-три"?, какого инструмента?) Кроме того, недопустимы ситуации, когда после выполнения очередной команды исполнителю не ясно, какую команду выполнять на следующем шаге. Нарушение составителем алгоритма этих требований приводит к тому, что одна и та же команда после выполнения разными исполнителями дает неодинаковый результат.

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

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

Что такое "Исполнитель алгоритма"?

Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя характеризуют:

·         элементарные действия;

·         система команд;

·         отказы.

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

После вызова команды исполнитель совершает соответствующее элементарное действие.

Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов "почему" и "зачем".

В информатике универсальным исполнителем алгоритмов является компьютер.

2. Задания.

1. Внимательно изучите теоретический материал.

2. Опишите алгоритм приготовления чая.

3. Опишите алгоритм выключения компьютера на вашем рабочем месте.

4. Составьте алгоритм выполнения какой-либо технологической операции по вашей специальности.

Вопросы:

1. В чем отличие понятия «алгоритм» от понятия «метод решения».

2. Назовите основное свойство алгоритма характерное только для решения задач на ЭВМ.

3. В расчете на кого должен строиться алгоритм?

а) в расчете на ЭВМ;

б) в расчете на умственные способности товарища;

в) в расчете на конкретного исполнителя.

Выберите правильный ответ.

4. Исполнитель выполняет команды алгоритма формально. Как это вы понимаете?

3. Оформление отчета:

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

2. Выполнить п.п. 2-4 задания.

3. Дать ответы на вопросы задания и объяснить их.

4. Контрольные вопросы.

1. Что такое алгоритм?

2. Назовите основные свойства алгоритма. Поясните каждое свойство на каком-либо конкретном примере.

3. Что такое или кто такой «исполнитель алгоритма»?