Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.

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

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

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

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

Виды алгоритмов: 1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке); 2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание); 3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий) 4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).

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

Вид стандартного графического объекта	Назначение
	Начало алгоритма
	Конец алгоритма
	Выполняемое действие записывается внутри прямоугольника
	Условие выполнения действий записывается внутри ромба
	Ввод-вывод

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

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

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

Идеальными исполнителями являются машины, роботы, компьютеры...

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

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

Компьютер – автоматический исполнитель алгоритмов.

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

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

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

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

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

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

41 .

Формальный аналог машины Тьюринга.

Машина Тьюринга (МТ) состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний qo, q1,..., qs, принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний). При этом qо называется начальным состоянием.

Читающая и пишущая головка может читать буквы рабочего алфавита А = [а0, a1,..., аt}, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква a0 - «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты - текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты. При этом возможна ситуация выхода за левый край ленты (ЛК), которая является аварийной (недопустимой), или машинного останова (МО), когда машина выполняет предписание об остановке.

Порядок работы МТ (с рабочим алфавитом a0, a1,..., аt и состояниями q0, q1,..., qs) описывается таблицей машины Тьюринга. Эта таблица является матрицей с четырьмя столбцами и (s + 1) (t + 1) строками. Каждая строка имеет вид

Функции, вычислимые по Тьюрингу. Тезис Тьюринга.

Тезис Тьюринга: абстрактная машина Тьюринга способна выполнять любые операции, которые подчиняются некоторым правилам и в этом смысле являются чисто механическими.

Машина работает по программе следующим образом.

В начальный момент времени на ленте записывается некоторая цепочка из множества V * , все остальные клетки ленты заполнены символом #. Управление в начальный момент находится в состоянии q 0 , считывающая – записывающая головка обозревает крайний слева символ записанной цепочки. Работа машины состоит в повторе следующего цикла элементарных действий:

1. Чтение головкой символа из ячейки напротив неё.

2. Поиск применимой команды, а именно команды qa → q’a’d , где q- некоторое состояние управления, a- считываемый символ.

3. Выполнение найденной команды, которая состоит в следующем. В обозреваемую головкой ячейку записывается символ a’ , символ a- стирается, управление переходит в состояние q’ и головка смещается относительно d . Если d=r головка смещается на одну ячейку вправо, если l - смещается на одну ячейку влево, p – перемещение не производится. Остановка производится в том случае, если на очередном шаге ни одна команда программы не является применимой. Результатом работы машины Тьюринга является цепочка, записанная на ленте.

| § 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/)

Основной вопрос: ?

Направляющие вопросы:

§ Какие бывают исполнители?

§ Что характеризует исполнителя?

§ Как сделать так, чтобы исполнитель понял и выполнил алгоритм?

Цели исследования:

§ Найти примеры различных исполнителей.

§ Определить чем отличаются исполнители.

§ Выяснить чем характеризуются исполнители.

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

§ Привести примеры алгоритмов и определить в них исполнителя.

Примеры исполнителей

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

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

Но исполнителем может быть не только человек. Разнообразные устройства, в том числе и компьютер, также могут выполнять заданные им алгоритмы. Например, "Луноход" - самоходный автоматический аппарат, доставленный на Луну в 1970 году, выполнял сложнейшие алгоритмы, перемещаясь по лунной поверхности и собирая необходимую людям информацию. Промышленные роботы заменяют людей на производстве, в быту на помощь хозяйкам также приходят устройства, способные действовать по заданным алгоритмам.

Исполнители из сказок

Исполнители часто встречаются в сказках. В одной из них Иван-Царевич говорит Избушке-На-Курьих-Ножках: “Избушка, избушка! Встань к лесу задом, ко мне передом!”. При этом команда должна быть задана очень точно, чтобы исполнитель ее понял. В сказке “Али-Баба и сорок разбойников” волшебная дверь открывалась по команде “Сезам, откройся!”. Жадный Касым, тайно проникший в пещеру, забыл эту фразу и не смог выйти из пещеры.

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

Кто такой исполнитель?

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

Исполнителями могут быть:

§ машины: станки, роботы, бытовые приборы (стиральная машина, магнитофон, плеер и т. п.), компьютеры;

§ растения: подсолнечник (разворачивается на солнце), кувшинки (закрываются на ночь);

§ животные: дрессированная собака (санитар, розыскная, охотничья), кошка;

§ люди: ученик, рабочий, солдат, учитель, ...

Все исполнители одинаковые?

Животные и человек как исполнители отличаются от всех остальных исполнителей тремя основными признаками:

§ Они понимают команды в различных вариантах (например "Сядь!", "Садись!", "Присядь!").

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

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

Исполнители бывают двух видов!

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

Формальные и неформальные

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

Итак, выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает и тем не менее получать нужный результат. В таком случаи говорят, что исполнитель действует формально, т. е. отвлекается от содержания поставленной задачи и только выполняет строгой последовательности все действия. Это формальный исполнитель.

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

Характеристики исполнителя

Исполнитель, как и любой объект, имеет свои характеристики.

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

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

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

§ Среда - условия, в которых исполнитель может выполнять команды. Среду исполнителя можно назвать еще его «Местом обитания».

§ И отказы:

1. "Не понимаю" - данной команды нет в списке команд исполнителя, и он ее не понял. Вероятно, мы ошиблись в записи текста команды команда не входит в СКИ.

2. "Не могу" - исполнитель понял команду, но не может ее выполнить. Например, роботу дана команда “вперед”, а впереди стоит стенка и он не может идти. Или собаке скомандовали “Сидеть!”, а она уже сидит.

Как исполнитель сможет выполнить алгоритм?

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

Естественный язык (русский, английский, французский, ...) - основа основ полноценного общения людей.

Естественные языки образны и многозначны. Если заглянуть в толковый словарь русского языка , то можно узнать, например, что существует более 20 значений слова "идти". Вот только несколько примеров:�Человек идет по дороге; идет дождь; время идет; ей идет это платье; опята пойдут позже, в сентябре; давай, сходим завтра на рыбалку? - идет!

В естественном языке совершенно разные понятия могут обозначаться одним и тем же словом. Как правило, человек из общего смысла текста, порою даже не задумываясь, из всего множества значений слова выделяет именно то, которое имел в виду отправитель сообщения. Но представьте себя на месте формального исполнителя, не вникающего в смысл всего сообщения. Как в этом случае вы будете понимать словосочетания: кислая мина; ранний побег; ели везде; знакомая среда?

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

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

А речь шла о простой деревянной спичке, но как было объяснить переводчику, что из всех значений слова "match" надо было выбрать не "сделка", а "спичка", из значений слова "tip" - "кончик", а не "совет", что "die" означает не только "умереть", но и "штамповать", не говоря уже о сложностях грамматических конструкций?

Что такое программа?

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

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

Чтобы научиться писать программы на том или другом языке, нужно изучить алфавит , словарь и грамматические правила, по которым строятся предложения в этом языке, при этом не допускаются никакие отклонения от правил написания слов и предложений, иначе исполнитель просто откажется выполнять ваши инструкции и не станет недоумевать и переживать за ошибки, как это делает приятель Мишки из стихотворения А. Шибаева:

Пришло письмишко мне,
Гляжу -
Из лагеря от Мишки...
Здесь чудный лук и я лижу,
-Написано в письмишке.
Лук лижет? Что за чудеса?
Наверно, шутит плут...
Читаю дальше:
Здесь лиса, красивый длинный прут...
На днях в лесу нашел я грусть
и очень был доволен...
Нет, нет, не шутит он! Боюсь,
Мой друг серьезно болен.
Вернется - надо подлечить:
Заставить правила учить…

§ Исполнители бывают двух видов: формальные и не формальные.

§ Исполнитель характеризуется системой команд, средой обитания и отказами.

§ Чтобы исполнитель понял нас необходимо написать алгоритм на языке исполнителя, то есть написать программу.

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

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

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

Система команд исполнителя - CD-плеера приведена на рис. 56.

Рис. 56

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

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

Ещё один пример исполнителя - компьютер . Его отличительная черта - универсальность . Вы знакомы с компьютерными программами, предназначенными для обработки текстовой, числовой и графической информации, с обучающими программами и компьютерными играми. Кроме того, существуют программы, с помощью которых компьютер управляет работой других связанных с ним устройств (исполнителей).

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

1. остановись на тротуаре;
2. посмотри налево;
3. если транспорта нет, то иди до середины улицы и остановись, иначе выполняй п. 2;
4. посмотри направо;
5. если транспорта нет, то иди до противоположного тротуара, иначе выполняй п. 4.

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

Формальные исполнители

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

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

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

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

1. Круг решаемых задач . Каждый исполнитель создается для решения определенного класса задач.
2. Среда исполнителя . Область, обстановку, условия, в которых действует исполнитель, принято называть средой данного исполнителя.
3. Система команд исполнителя . Предписание о выполнении отдельного законченного действия исполнителя называется командой. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует СКИ - систему команд исполнителя.
4. Система отказов исполнителя . Отказ «не понимаю» возникает тогда, когда исполнителю подается команда, не входящая в его СКИ. Отказ «не могу» возникает тогда, когда команда из СКИ не может быть им выполнена в конкретных условиях среды.
5. Режимы работы исполнителя . Для большинства исполнителей предусмотрены режимы непосредственного и программного управления. В первом случае исполнитель ожидает команд от управляющего объекта и немедленно выполняет каждую поступившую команду. Во втором случае исполнителю сначала задаётся полная последовательность команд (программа), а затем он выполняет все эти команды в автоматическом режиме. Ряд исполнителей работает только в одном из названных режимов.

Автоматизация

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

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