Пожалуйста, приостановите работу AdBlock на этом сайте.

В этом уроке разберём некоторые теоретические понятия, которые формализуют понятие программирования. Заодно точнее сформулируем основную задачу вашего обучения.

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

Рис.1 Скриншот игрового поля на code.org

Надеюсь, у вас всё получилось. Теперь на этом примере опишем несколько основных понятий:

• исполнитель;
• система команд исполнителя;
• алгоритм.

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

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

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

Необходимо заострить внимание на нескольких моментах.

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

Это означает, например, что нельзя написать исполнителю-птичке: «Иди к свинье!». Точнее записать можно, но только ничего не произойдёт, т.к. исполнитель таких команд не знает.

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

Исполнитель выполняет точно то, что предписывает ему алгоритм.

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

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

Теперь от наглядного примера перейдём к компьютерным реалиям. Мы пишем программы для компьютера, а значит, компьютер в нашем случае является исполнителем. Система команд – стандартные функции и конструкции языка Си.

В чём состоит основная задача вашего обучения основам программирования? Овладеть навыком алгоритмического мышления. То есть научиться записывать решение различных задач в виде алгоритма для конкретного исполнителя (в нашем случае компьютера).

Итак, подытожим:

Компьютерная программа – алгоритм решения какой-либо задачи, записанный на языке программирования.

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

Исполнитель – человек или некоторое устройство, которое может понимать и выполнять определённый набор команд.

Алгоритм и его свойства.

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

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

Система команд исполнителя (СКИ) - это вся совокупность команд, которые исполнитель умеет выполнять.

Свойства алгоритма: понятность, точность, конечность.

Понятность: алгоритм составляется только из команд, входящих в СКИ исполнителя.

Точность: каждая команда алгоритма управления определяет однозначное действие исполнителя.

Конечность (или результативность): выполнение алгоритма должно приводить к результату за конечное число шагов.

Среда исполнителя: обстановка, в которой функционирует исполнитель.

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

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

Способы записи алгоритмов.

Наибольшую распространенность получили способы: графический , словесный и в виде программ для ЭВМ .

Графический способ предполагает использование определенных графических символов - блоков.

Наименование блока	Обозначение блока	Содержание
Процесс		Обработка информации
Принятие решения		Логический блок проверки истинности или ложности некоторого условия
Передача данных		Ввод или вывод информации
Пуск, остановка		Начало или конец программы
Модификация		Организация циклического процесса - заголовок цикла

Совокупность блоков образует так называемую блок-схему алгоритма .

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

При записи алгоритмов в виде программ для ЭВМ используются языки программирования - системы кодирования предписаний и правила их использования. Для записи алгоритмов в виде программ характерна высокая степень формализации.

Алгоритмы работы с величинами. Основные алгоритмические структуры.

Величина - это отдельный информационный объект, который имеет имя, значение и тип.

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

Величины бывают постоянными и переменными.

Постоянная величина (константа) не изменяет своего значения в ходе выполнения алгоритма. Константа может обозначаться собственным значением (числа 10, 3.5) или символическим именем (число ).

Переменная величина может изменять значение в ходе выполнения алгоритма. Переменная всегда обозначается символическим именем (X, A, R5 и т.п.).

Тип величины определяет множество значений, которые может принимать величина, и множество действий, которые можно выполнять с этой величиной. Основные типы величин: целый, вещественный, символьный, логический.

Выражение - запись, определяющая последовательность действий над величинами. Выражение может содержать константы, переменные, знаки операций, функции. Пример:

А + В; 2*X-Y; K + L - sin(Х)

Команда присваивания - команда исполнителя, в результате которой переменная получает новое значение. Формат команды:

имя переменной>:=выражение>

Исполнение команды присваивания происходит в таком порядке: сначала вычисляется, затем, полученное значение присваивается переменной.

Пример. Пусть переменная А имела значение 6. Какое значение получит переменная А после выполнения команды: А:= 2 * А - 1?
Решение. Вычисление выражения 2*А - 1 при А=6 даст число 11. Значит новое значение переменной А будет равно 11.

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

Команда ввода - команда, по которой значения переменных задаются через устройства ввода (например, клавиатуру).

Пример: ввод А - ввод значения переменной А с клавиатуры компьютера.

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

Пример: вывод X - значение переменной X выводится экран.

Команда ветвления - разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгоритма выходит на общее продолжение. Ветвление бывает полное и неполное. Описание ветвления в блок-схемах и на Алгоритмическом языке:

Здесь под серией понимается одна или несколько последовательных команд; кв - конец ветвления.

Команда цикла обеспечивает повторное выполнение последовательности команд (тела цикла) по некоторому условию.

Цикл с предусловием - цикл, выполнение которого повторяется, пока истинно условие цикла:

Цикл с параметром - повторное выполнение тела цикла, пока целочисленный параметр пробегает множество всех значений от начального (In) до конечного (Ik):

Пример. Даны две простые дроби. Составить алгоритм получения дроби, являющейся результатом их деления.
Решение. В алгебраической форме решение задачи выглядит следующим образом:
а/в: с/d = а*d/b*c = m/n
Исходными данными являются четыре целые величины: а, b, с, d. Результат - два целых числа m и n.

алг деление дробей
цел а, b, с, d, m, n
нач ввод а, b, с, d
m:=a*d
n:=b*c
вывод "Числитель=", m
вывод "Знаменатель=", n
кои

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

1. Ефимова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. - М.: ООО "Издательство АСТ"; АВF, 2000 г.
2. Задачник-практикум по информатике. В 2-х томах/Под ред. И.Семакина, Е.Хеннера. - М.: Лаборатория Базовых Знаний, 2001 г.
3. Угринович Н. Информатика и информационные технологии. 10-11 класс- М.: Лаборатория Базовых Знаний, АО "Московские учебники", 2001 г.

Задачи и тесты по теме "Алгоритмы и исполнители"

• Управление исполнителем Чертёжник - Алгоритмы 6 класс

  Уроков: 4 Заданий: 9 Тестов: 1

• 2 Заданий: 9 Тестов: 1

Уважаемый ученик!

Знание Темы "Алгоритмы и исполнители" необходимо прежде всего для дальнейшего изучения программирования. В качестве базы для изучения программирования выбран язык программирования QBasic. Мы отказались от идеи включить в наш курс Visual Basic или какой-либо другой язык объектно-ориентированного программирования, так как такой подход пока не получил широкого применения в большинстве средних школ РФ. Кроме того, в основе объектно-ориентированного программирования лежат принципы классического программирования в Dos.

Наш курс рассчитан на общеобразовательную программу. При подготовке ко вступительным экзаменам по информационным технологиям в ВУЗы необходимо ознакомиться со спецификой изучения программирования в данном ВУЗе. В некоторых случаях необходимо углубленное изучение ряда тем, например, таких как "Массивы". На это следует обратить внимание при изучении литературы по программированию, возможно, следует воспользоваться методическими рекомендациями по подготовке к экзаменам, которые в настоящее время издаются в большинстве высших учебных заведений.

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

>> Типы алгоритмов

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

Линейные алгоритмы;
алгоритмы с ветвлениями;
алгоритмы с повторениями.

Линейные алгоритмы

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

Например, линейным является следующий алгоритм посадки дерева:

1) выкопать в земле ямку;
2) опустить в ямку саженец;
3) засыпать ямку с саженцем землей;
4) полить саженец водой.

С помощью блок-схемы данный алгоритм можно изобразить так:

Алгоритмы о ветвлениями

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

Логику принятия решения можно описать так:

ЕСЛИ <условие> ТО <действия 1> ИНАЧЕ <действия 2>

Примеры:

ЕСЛИ хочешь бытьздоров , ТО закаляйся, ИНАЧЕ валяйся весь день на диване;
ЕСЛИ низко ласточки летают, ТО будет дождь, ИНАЧЕ дождя не будет;
ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.

В некоторых случаях <действия 2> могут отсутствовать;

ЕСЛИ <условие> ТО <действия 1>

Пример :

ЕСЛИ назвался груздем, ТО полезай в кузов.

Форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов, называется ветвлением.

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

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

Из трёх монет одинакового достоинства одна фальшивая (более легкая). Как ее найти с помощью одного взвешивания на чашечных весах без гирь?

Алгоритмы с повторениями

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

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

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

Рассмотрим пример из математики.

Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число1.

2, 3, 5, 7 - простые числа; 4, 6, 8 - нет. В III веке до нашей эры греческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых чисел, меньших заданного числа n:

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

Это циклический алгоритм. При его выполнении повторение шагов 3-5 происходит, пока в исходном списке остаются неотмеченные числа.

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

Напомним, что число 1 не относят ни к составным (имеющим более двух делителей), ни к простым числам.

Самое главное

В зависимости от порядка выполнения команд можно выделить три типа алгоритмов:

> линейные алгоритмы;
> алгоритмы с ветвлениями;
> алгоритмы с повторениями.

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

Форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов, называется ветвлением.

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

Вопросы и задания

1. Какие алгоритмы называют линейными?
2. Приведите пример линейного алгоритма,
3. Исполнитель «Вычислитель» умеет выполнять только две команды: умножать на 2 и прибавлять Придумайте для него наиболее короткий план получения из О числа 50.
4. Какая форма организации действий называется ветвлением?
5. Какие условия должна была выполнить героиня скази «Гуси-лебеди»?
6. Приведите пример алгоритма, содержащего ветвление»
7. Прочитайте отрывок из стихотворения Дж. Родари «Чем пахнут ремесла?»:

У каждого дела запах особый:
В булочной пахнет тестом и сдобой.
Мимо столярной идешь мастерской -
Стружкою пахнет и свежей доской.
Пахнет маляр скипидаром и краской.
Пахнет стекольщик оконной замазкой.
Куртка шофера пахнет бензином,
Блуза рабочего - маслом машинным.

Перефразируйте о профессиях с помощью слов «ЕСЛИ... ТО»/

8. Вспомните, герои каких русских народных сказок совершают выбор, определяющий их судьбу.
9. Из 9 монет одинакового достоинства одна фальшивая (более легкая). За сколько взвешиваний на чашечных весах без гирь вы можете ее определить?
10. Какая форма организации действий называется повторением?
11. Приведите пример алгоритма, содержащего повторение.
12. В каких известных вам литературных произведениях имеет место циклическая форма организации действий?
13. Где окажется исполнитель, выполнивший 16 раз подряд следующую группу команд?

пройти 10 метров вперед

повернуть на 90° по часовой стрелке

14. Какую группу действий и сколько раз следует повторить при решении следующей задачи?

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

15. Вспомните задачу о Вычислителе, умеющем только умножать на 2 и прибавлять 1. Разрабатывать для него рациональные алгоритмы будет значительно проще, если воспользоваться следующей блок-схемой:

Используя эту блок-схему, разработайте рациональные алгоритмы получения из числа 0 чисел 1024 и 500.

Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. - 3-е изд., испр. и доп. - М.: БИНОМ. Лаборатория знаний, 2005. - 208 с.: ил.

Содержание урока конспект урока и опорный каркас презентация урока интерактивные технологии акселеративные методы обучения Практика тесты, тестирование онлайн задачи и упражнения домашние задания практикумы и тренинги вопросы для дискуссий в классе Иллюстрации видео- и аудиоматериалы фотографии, картинки графики, таблицы, схемы комиксы, притчи, поговорки, кроссворды, анекдоты, приколы, цитаты Дополнения рефераты шпаргалки фишки для любознательных статьи (МАН) литература основная и дополнительная словарь терминов Совершенствование учебников и уроков исправление ошибок в учебнике замена устаревших знаний новыми Только для учителей календарные планы учебные программы методические рекомендации

Слово «алгоритм» произошло от имени арабского математика 9 века аль-Хорезми, который сформулировал правила выполнения арифметический действий.

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

Примеры: распорядок дня, порядок приготовления блюда, инструкция и т.д.)

Исполнитель алгоритма – это тот, кто выполняет алгоритм (человек, животное, машина, компьютер).

Система команд исполнителя – это вся совокупность команд, которые исполнитель умеет выполнять (понимает). Алгоритм можно строить только из команд, входящих в систему команд исполнителя.

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

Свойства алгоритма:

1.Результативность (конечность) – возможность получения из исходных данных результата за конечное число шагов. (Например, при выполнении алгоритма сложения 2 чисел должны получить сумму).

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

3.Детерминированность (определенность, точность) – каждая команда должна однозначно определять действие исполнителя.

4.Понятность – команда должна быть записана на понятном компьютеру языке.

5.Дискретность – разбиение алгоритма на отдельные команды.

Способы записи алгоритма:

1) На естественном языке – запись в виде отдельных команд на понятном человеку языке.

2) Графический – на языке блок-схем, с помощью геометрических фигур (овал, прямоугольник, параллелограмм, ромб).

3) На алгоритмическом языке – язык записи алгоритмов, для обучения программированию. Команды записываются на русском языке.

4) На языке программирования - программа. Языки программирования: Basic, Pascal, Си, Visual Basic.

Б7.Основные алгоритмические структуры: следование, ветвление, цикл; изображение на блок-схемах. Разбиение задач на подзадачи. Вспомогательные алгоритмы.

Алгоритмические конструкции. Внутри алгоритмов можно выделить группы шагов, отличающиеся внутренней структурой – алгоритмические конструкции.

Основными алгоритмическими конструкциями являются линейная последовательность шагов (или следование), ветвление и цикл.

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

Так выглядит линейный алгоритм на языке блок схем:

Пример : алгоритм включения компьютера:

1. Включить питание компьютера (нажать кнопку на сетевом фильтре).
2. Включить монитор, принтер.
3. Нажать кнопку Power на системном блоке.
4. Дождаться загрузки операционной системы и появления Рабочего стола.
5. Приступить к работе.

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

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

Условие – это высказывание, которое может быть истинным или ложным. В условии два числа, две строки, две переменных или строковых выражения сравниваются между собой с использованием операций сравнения (>, <, =, >=, <=).

Запись на алгоритмическом языке: ЕслиУсловие То Серия 1 (Если Условие истинно, то выполняется Серия 1 , если Условие ложно, то ничего не выполняется). Пример: Если сегодня воскресенье, то в школу идти не надо. Полная форма ветвления

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

Циклические алгоритмические структуры бывают двух типов:

• циклы со счетчиком , в которых тело цикла выполняется определенное количество раз;
• циклы с условием , в которых тело цикла выполняется до тех пор, пока выполняется условие.

Цикл со счетчиком – используется когда заранее известно какое число повторений тела цикла необходимо выполнить.

| § 2.1. Алгоритмы и исполнители

Урок 14
§ 2.1. Алгоритмы и исполнители

Ключевые слова:

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

2.1.1. Понятие алгоритма

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

Пример 1. Задача «Найти среднее арифметическое двух чисел» решается в три шага:

1) задумать два числа;
2) сложить два задуманных числа;
3) полученную сумму разделить на 2.

Пример 2. Задача «Внести деньги на счёт телефона» подразделяется на следующие шаги:

1) подойти к терминалу по оплате платежей;
2) выбрать оператора связи;
3) ввести номер телефона;
4) проверить правильность введённого номера;
5) вставить денежную купюру в купюроприёмник;
6) дождаться сообщения о зачислении денег на счёт;
7) получить чек.

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

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

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

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

Рис. 2.1. Общая схема работы алгоритма

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

Анимации «Работа с алгоритмом» (193576), «Наибольший общий делитель» (170363), «Наименьшее общее кратное» (170390) помогут вам вспомнить некоторые алгоритмы, изученные на уроках русского языка и математики (http://sc.edu.ru/).

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

1. Вычисляется длина (в символах) исходной цепочки символов.
2. Если длина исходной цепочки нечётна, то к исходной цепочке справа приписывается цифра 1, иначе цепочка не изменяется.
3. Символы попарно меняются местами (первый - со вторым, третий - с четвёртым, пятый - с шестым и т. д).
4. Справа к полученной цепочке приписывается цифра 2.

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

Так, если исходной была цепочка А#В, то результатом работы алгоритма будет цепочка #А1В2, а если исходной цепочкой была АБВ@, то результатом работы алгоритма будет цепочка БА@В2.

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

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

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

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

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

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

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

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

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

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

Пример 5. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии.

Система команд Черепашки состоит из следующих команд:

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

Подумайте, какая фигура появится на экране после выполнения Черепашкой следующего алгоритма.
Повтори 12 [Направо 45 Вперёд 20 Направо 45]

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

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

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

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

С помощью этого алгоритма число 1 будет преобразовано в 15:

((1 3 - 1) 3 - 1) 3 = 15.

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

1 - вверх
2 - вниз
3 - вправо
4 - влево

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

Что произойдёт с Роботом, если он выполнит последовательность команд 32323 (здесь цифры обозначают номера команд), начав движение из клетки А? Какую последовательность команд следует выполнить Роботу, чтобы переместиться из клетки А в клетку В, не разрушившись от встречи со стенами?

При разработке алгоритма:

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

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

2.1.3. Свойства алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

САМОЕ ГЛАВНОЕ

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

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

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

Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека.

Вопросы и задания

1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа? Какими слайдами вы могли бы дополнить презентацию?

2. Что называют алгоритмом?

3. Подберите синонимы к слову «предписание».

4. Приведите примеры алгоритмов, изучаемых вами в школе.

5. Кто может быть исполнителем алгоритма?

6. Приведите пример формального исполнителя. Приведите пример, когда человек выступает в роли формального исполнителя.

7. От чего зависит круг решаемых задач исполнителя «компьютер»?

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

9. Что такое команда, система команд исполнителя?

10. Какие команды должны быть у робота, выполняющего функции:

а) кассира в магазине;
б) дворника;
в) охранника?

11. Перечислите основные свойства алгоритма.

12. К чему может привести отсутствие какого-либо свойства у алгоритма? Приведите примеры.

13. В чём важность возможности формального исполнения алгоритма?

14. Последовательность чисел строится по следующему алгоритму: первые два числа последовательности принимаются равными 1; каждое следующее число последовательности принимается равным сумме двух предыдущих чисел. Запишите 10 первых членов этой последовательности. Выясните, как называется эта последовательность.

15. Некоторый алгоритм получает из одной цепочки символов новую цепочку следующим образом. Сначала записывается исходная цепочка символов, после нее записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на последнем месте. Если в исходной цепочке на последнем месте стоит буква «Я», то в качестве следующей буквы записывается буква «А». Получившаяся цепочка является результатом работы алгоритма. Например, если исходная цепочка символов была «ДОМ», то результатом работы алгоритма будет цепочка «ДОММОДН». Дана цепочка символов «КОМ». Сколько букв «О» будет в цепочке символов, которая получится, если применить алгоритм к данной цепочке, а затем ещё раз применить алгоритм к результату его работы?

16. Найдите в сети Интернет анимацию шагов алгоритма Эратосфена. С помощью алгоритма Эратосфена найдите все простые числа, не превышающие 50.

17. Что будет результатом исполнения Черепашкой (см. пример 5) алгоритма?

18. Запишите алгоритм для исполнителя Вычислитель (см. пример 6), содержащий не более 5 команд:

а) получения из числа 3 числа 16;
б) получения из числа 1 числа 25.

19. Система команд исполнителя Конструктор состоит из двух команд, которым присвоены номера:

1 - приписать 2
2 - разделить на 2

По первой из них к числу приписывается справа 2, по второй число делится на 2. Как будет преобразовано число 8, если исполнитель выполнит алгоритм 22212? Составьте алгоритм в системе команд этого исполнителя, по которому число 1 будет преобразовано в число 16 (в алгоритме должно быть не более 5 команд).

20. В какой клетке должен находиться исполнитель Робот (пример 7), чтобы после выполнения алгоритма 3241 в неё же и вернуться?

Свободное программное обеспечение:

система КуМир - Комплект учебных миров (скачать архив программы с сайта) или посетить страницу КуМир ((http://www.niisi.ru/kumir/)