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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§ И отказы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Математические основы информатики

А.Г. Гейн

Учебный план

№_ГАЗЕТЫ

Лекция

Лекция 1. Что такое “математические основы информатики”. Почему информатику нередко считают близкой род-
ственницей математики? Верно ли это? Возможна ли информатика без математики? Какая математика нужна для освоения
информатики? Может ли школьная математика дать основу для информатики?

Информация и ее кодирование. Математика кодов. Коды, исправляющие ошибки. Экономное кодирование.
Лекция 2 . Математические модели формальных исполнителей. Что такое формальная обработка информации? Конеч-
ные автоматы. Что первично: язык или исполнитель? Грамматика языка. Распознаваемые языки. Универсальные исполни-
тели (машина Тьюринга, машина Поста).
Лекция 3 . Алгоритм и его свойства. Алгоритмическая неразрешимость. Вычислимость. Сложность.
Контрольная работа № 1.
Лекция 4. Графы . Графы и орграфы. В каких задачах они возникают? Различные свойства графов (эйлеровость, гамильто-
новость, планарность, двудольность). Сети. Потоки в сетях. Представление графов. Основные алгоритмы на графах.
Лекция 5 . Логические модели в информатике. Алгебра высказываний. Булевы функции. Нормальные формы. Полные
классы булевых функций. Релейно-контактные схемы. Вентили. Математические модели процессора и памяти компьютера. Предикаты и отношения. Реляционная алгебра. Теоретические основы реляционных СУБД. Языки логического программирования и их математическое основание.
Контрольная работа № 2.
Лекция 6 . Компьютерная теория чисел и вычислительная геометрия. Зачем нужна теория чисел в компьютерных
науках? Гонка за простыми числами. Как разложить число на множители? Чем отличается теоретическая геометрия от
вычислительной? Почему гладко на бумаге, но коряво на компьютере? Основные правила и алгоритмы вычислительной
геометрии.
23/2007 Лекция 7 . Защита информации . Защита символьной информации. Что нужно защищать? Электронная подпись. Системы
верификации. Криптосистемы с открытым ключом. Защита графической информации. Математика электронных водяных знаков.
24/2007 Лекция 8 . Основы методики преподавания математических основ информатики.
Итоговая работа

Лекция 2.
Математические модели формальных исполнителей

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

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

Но всегда ли плохо быть формальным исполнителем? Будет ли рад хозяин овчарки, когда по команде “Фас!” его четвероногий друг задумается, стоит ли связываться с бандитом. Или когда самолет в ответ на движение пилотом штурвала продолжит лететь прежним курсом, потому что разворот делать не хочется. А оператор ядерного реактора, забросив инструкцию, будет управлять им по наитию. Согласитесь, что даже человеку временами быть формальным исполнителем просто необходимо. Что касается устройств для автоматической обработки информации, для них неформальный путь просто невозможен. Напомним, что, как отмечалось в лекции 1, информатика занимается изучением как раз процессов автоматизированной обработки информации.

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

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

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

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

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

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

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

§ 3. Формальный исполнитель: автомат

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

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

С точки зрения информатики совершенно все равно, из чего сделан автомат. Важно лишь то, что он воспринимает некоторые сигналы как команды и по каждой команде выполняет некоторое действие, переходя из одного состояния в другое. Поэтому можно считать, что каждый автомат описывается набором возможных состояний, списком допустимых команд и перечислением того, из какого состояния в какое переходит автомат под воздействием каждой команды. Например, если команд только две, то их можно обозначить буквами, скажем, a и b , или цифрами, состояния автомата - буквами q 1, q 2, ..., qm , а перечислить варианты перехода из одного состояния в другое можно с помощью таблицы (см. табл. 1).

Таблица 1

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

Автомат можно описать и другой информационной моделью - орграфом*. Вершинами орграфа являются состояния автомата, дугами - переходы из одного состояния в другое. На каждой дуге имеется отметка, показывающая, по какой команде осуществляется переход. Тогда автомат, описанный табл. 2, изобразится так, как показано на рис. 1.

Таблица 2

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

Ясно, что целью управления автоматом является выдача ему такой последовательности команд, которая переводит его из начального состояния в какое-либо конечное. Поскольку каждая команда обозначена буквой, то набор команд, понимаемых данным автоматом, можно считать некоторым алфавитом А . Тогда последовательность команд, т.е. программа, будет записываться как слово в этом алфавите. Например, слово abа переводит автомат, описанный табл. 2, из начального состояния q 1 в состояние q 4 . Можно сказать, что слово abа задает на орграфе данного автомата некоторый маршрут из состояния q 1 в состояние q 4 .

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

На рис. 2 изображен автомат, имеющий два состояния - q 1 (К) и q 2 - и понимающий две команды, которые обозначены цифрами 0 и 1. Легко сообразить, что распознаваемый этим автоматом язык состоит из тех и только тех слов, которые содержат четное количество единиц и любое количество нулей. Иными словами, этот автомат подсчитывает сумму цифр в числе, записанном в двоичной системе счисления.

Пусть теперь у нас имеется фиксированный алфавит А , и L - некоторое множество слов, составленное из символов данного алфавита. Всегда ли можно построить такой автомат, чтобы множество L было для него распознаваемым языком? Ответ отрицателен.

Теорема. Пусть А = {a , b }, L = {a n b n , где n пробегает множество всех натуральных чисел}. Множество L не является распознаваемым языком.

Запись a n , фигурирующая в формулировке этой теоремы, означает, что буква а повторена n раз.

Доказательство теоремы использует один из важнейших математических методов - от противного. Итак, предположим, что L - распознаваемый язык. Значит, существует такой автомат, который любым словом этого языка переводится в некоторое конечное состояние. Пусть этот автомат имеет k состояний. Рассмотрим слово a k b k . Оно принадлежит языку L и, следовательно, переводит этот автомат из начального состояния q 1 в некоторое конечное состояние q s . Поскольку буква а повторяется не меньшее число раз, чем количество состояний автомата, найдется такое состояние q t , которое за первые k применений буквы а будет пройдено дважды (см. рис. 3). Пусть первый раз автомат перейдет в состояние q t в результате применения a u , а следующий раз окажется в том же состоянии после применения a u + v . Рассмотрим слово a k + v b k . Ясно, что применение этого слова к начальному состоянию q 1 переведет его в то же самое конечное состояние q s . Это означает, что данное слово также распознаваемо данным автоматом и, значит, должно принадлежать языку L . Но в множестве L такого слова нет. Полученное противоречие показывает, что сделанное допущение неверно, т.е. автомата, для которого данное множество служило бы распознаваемым языком, не существует.

Рис. 3. Маршрут на орграфе автомата от начального состояния q 1 до конечного состояния q s (до состояния q t буква а на дугах стоит u раз, на цикле - еще v раз)

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

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

1. Какими двумя информационными моделями может быть представлен автомат?

2. Что такое язык, распознаваемый данным автоматом?

3. Какой язык называется распознаваемым?

4. Для автомата, изображенного на рис. 1, определите, в каком состоянии он будет находиться после исполнения последовательности команд

а) abba ; в) babaabaaa ;

б) ababbabbb ; г)* a n b n .

5. Для автомата, изображенного на рис. 2, составьте описание в форме таблицы.

6. Постройте в виде графа информационную модель автомата, заданного табл. 3.

Таблица 3

7. Какой язык над двухсимвольным алфавитом {0, 1} распознается автоматом, изображенным на рис. 4?

Рис. 4

8. Какой язык над двухсимвольным алфавитом {a , b } распознается автоматом, заданным табл. 3?

9. Изобразите в виде графа информационную модель автомата, который бы распознавал язык над алфавитом {0, 1}, состоящий из всех слов, содержащих ровно 5 подряд идущих единиц.

10. Изобразите в виде графа информационную модель автомата, который бы распознавал язык над алфавитом {0, 1}, состоящий из всех слов, содержащих ровно 5 единиц.

11. Изобразите в виде графа информационную модель автомата, который бы распознавал язык над алфавитом {0, 1}, состоящий из всех слов, начинающихся с единицы (т.е. этот автомат отличает натуральные числа, записанные в двоичной системе счисления, от произвольных последовательностей символов 0 и 1).

12. Среди перечисленных ниже языков L 1 , L 2 , L 3 , L 4 , определенных над двухсимвольным алфавитом {1; 2}, укажите распознаваемые. Для каждого из распознаваемых языков постройте распознающий его автомат, для каждого из нераспознаваемых языков докажите, что он нераспознаваем.

а) L 1 состоит из всех слов, которые представляют собой четные натуральные числа, начинающиеся с цифры 1;

б) L 2 состоит из всех слов, количество единиц в которых - это натуральное число, оканчивающееся цифрой 3;

в) L 3 состоит из всех слов, в которых количество двоек является простым числом;

г) L 4 состоит из всех слов, которые представляют собой натуральные числа, делящиеся на 3.

13. В чем с точки зрения информатики заключается разница “в жизни по законам” и “в жизни по понятиям”?

§ 4. Универсальный исполнитель

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

Если попытаться сформулировать, что значит один исполнитель имитируется с помощью другого, то получится следующее. Говорят, что формальный исполнитель А имитирует формального исполнителя В , если

Каждому объекту, над которым выполняет действия исполнитель В , однозначно соответствует объект, над которым выполняет действия исполнитель А (имитация среды исполнителя);

Каждому допустимому действию исполнителя В над тем или иным объектом среды однозначно сопоставлено допустимое действие исполнителя А над соответствующим объектом его среды (имитация действий);

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

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

Один из важнейших вопросов теоретической информатики звучит так: существует ли такой формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя? Такого исполнителя естественно назвать универсальным . Легко понять, что как физическое устройство универсальный исполнитель не существует - ведь информация может кодироваться как угодно длинными сообщениями, а любой физический носитель конечен. Если же вести речь об универсальном исполнителе как идеальном объекте, то оказывается, что ответ на заданный вопрос положителен. И получен он был почти одновременно и независимо двумя выдающимися учеными - А.Тьюрингом (в 1936 г.) и Э.Постом (в 1937 г.). Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное - имитировать вообще любого формального исполнителя.

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

Итак, можно считать, что у нас имеется сообщение, записанное в некотором алфавите, и его требуется преобразовать в другое сообщение. Конечно, написать инструкцию формальному исполнителю для обработки конкретной пары сообщений - дело нехитрое. Но вы уже знаете, что реальный интерес представляют инструкции (т.е. алгоритмы), позволяющие решать целый класс однотипных задач, - так называемое “свойство массовости алгоритма”. Например, такая задача: к любому сообщению приписать справа еще один заранее заданный символ. Если, скажем, последовательность одинаковых символов выступает кодом натурального числа - количество символов в последовательности и есть кодируемое натуральное число, - то фактически речь идет о создании алгоритма увеличения числа на 1.

Естественно считать, что сообщение записано на ленту. Более того, удобно представлять себе эту ленту разделенной на одинаковые клетки, и в каждой клетке записан ровно один символ сообщения. Поскольку сообщения могут быть как угодно длинными, то ленту договоримся представлять себе бесконечной. Пустые клетки будем считать заполненными символом “пробел”. Тем самым, мы объявили, что любой алфавит, который будет использоваться нами для записи сообщений на этой ленте, обязательно содержит “пробел”. Договоримся обозначать его а 0 . Остальные символы алфавита, используемого для записи сообщений на ленту, будем обозначать а 1 , а 2 , ..., а n . Если, к примеру, нам требуется записать задачу вычисления суммы двух чисел, то алфавит можно взять таким: а 0 ; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =. Для конкретной пары данных (т.е. двух чисел) запись на ленте может выглядеть, например, так, как показано на рис. 5.

Рис. 5

Мы, конечно, не будем на ленте в пустых клетках писать символ а 0, подразумевая его там. Кроме того, договоримся, что первый символ сообщения, отличный от пробела, всегда стоит в одной и той же клетке - на рис. 4 она отмечена Ї. Эту клетку будем называть начальной.

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

Вы уже знаете, что каждый автомат описывается набором состояний. Принято обозначать состояния указанного считывающе-печатающего автомата буквами q 0 , q 1 , q 2 , ..., q m . При этом договоримся, что при включении автомата, т.е. в начале работы, он всегда находится в одном и том же состоянии, которое мы будем обозначать q 0 , и располагается напротив начальной клетки.

Таким образом, машина Тьюринга формально описывается набором двух алфавитов: А = {а 1 , а 2 , ..., а } и Q = {q 0 , q 1 , q 2 , ..., q m }. Алфавит А называется внешним и служит для записи исходных сообщений, алфавит Q называется внутренним и описывает набор состояний считывающе-печатающего устройства. Изображать машину Тьюринга будем так, как показано на рис . 6.

Рис. 6

На рис. 6 показан момент работы машины Тьюринга, когда считывающе-печатающее устройство обозревает третью клетку от начальной (в ней к этому моменту оказался символ а s 3) и находится в состоянии q k .

Итак, допустимые действия машины Тьюринга таковы:

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

Сместиться в соседнюю секцию;

Сменить состояние на одно из обозначенных символом внутреннего алфавита;

Прекратить работу (остановиться).

Конечно, в этом перечислении в каждой строке указано не одно действие, а группа действий одного вида - действий “записать символ внешнего алфавита” столько, сколько этих символов, сместиться в соседнюю секцию можно вправо, а можно влево, действий по изменению состояния столько, сколько этих состояний (т.е. сколько символов внутреннего алфавита).

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

Фактически команды выглядят так:

a i q j - в обозреваемую секцию записать a i , сместиться вправо (к следующей секции) и перейти в состояние q j ;

a i q j - в обозреваемую секцию записать a i , сместиться влево и перейти в состояние q j ;

a i Sq j - в обозреваемую секцию записать ai , остановиться и перейти в состояние q j .

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

Рис. 7. Операционно-логический блок машины Тьюринга

Поскольку у этого блока всего лишь два входа, его реакцию на символы, подаваемые на них, удобно представлять в виде прямоугольной таблицы, в которой строки и столбцы помечены символами внешнего и внутреннего алфавитов соответственно (см. табл. 4). В клетки таблицы записываются команды. Если машина находится напротив клетки, где написано a i , а ее состояние при этом есть q j , то выполняется команда, стоящая на пересечении строки, отмеченной символом ai , и столбца, отмеченного символом q j .

Таблица 4

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

Пусть, к примеру, на ленте записана последовательность из некоторого количества одного и того же символа “*”. Тогда функциональная схема, приведенная в табл. 5, заставляет машину Тьюринга увеличить на одну количество звездочек в этой последовательности.

Таблица 5

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

Вопросы и задачи

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

2. Что такое машина Тьюринга?

3. Чем одна машина Тьюринга отличается от другой?

4. Что называют функциональной схемой машины Тьюринга?

5. Верно ли, что машина Тьюринга с написанной для нее функциональной схемой является конечным автоматом?

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

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

8. Работа машины Тьюринга описана следующей функциональной схемой:

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

Рис. 8

Рис. 9

9. На ленте машины Тьюринга записана строка, состоящая из нескольких подряд идущих символов “*”, за ними следует несколько символов “#”, а в конце строки стоит символ “е” (один из возможных вариантов такой строки приведен на рис. 5).

Рис. 10

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

10. Пусть внешний алфавит состоит из символа “a 0 ” и цифр 0, 1, 2, ..., 9. На ленту записывается натуральное число. Придумайте машину Тьюринга и составьте для нее функциональную схему, согласно которой данное число будет увеличено на 1.

11. Пусть внешний алфавит состоит из символа “a 0 ” и цифр 0, 1, 2, ..., 9. На ленту записано натуральное число. Составьте функциональную схему для машины Тьюринга, с помощью которой на ленте будет записана сумма цифр этого числа. Ответ требуется записать правее исходного числа, отделив от него пробелом.

Рис . 11

P.S. Ощутить себя в роли машины Тьюринга небесполезно, но утомительно. Мы рекомендуем задания 8 и 9 проделать вручную. Что касается заданий 10 и 11, то ручное тестирование составленных вами функциональных схем может оказаться неэффективным. В связи с этим мы предлагаем воспользоваться компьютерной реализацией машины Тьюринга, созданной Р.Зартдиновым. Ее можно получить на сайте газеты “Информатика” (inf.1september.ru ). Вот как, к примеру, выглядит на этой машине функциональная схема из задания 8 в) - отличия состоят в том, что вместо буквы S изображен дорожный знак, а вместо символа “a 0 ” пишется “_” (при занесении команды в клетку таблицы нажимать, однако, надо клавишу “пробел”, а не “_”). Программа снабжена подробной справкой о том, как с ней работать. Интерфейс этой программы очень прост. Кроме того, описание данной реализации машины Тьюринга вы можете найти в газете “Информатика” № 8, 2006. Там же вы найдете разбор еще нескольких задач на программирование машины Тьюринга; надо только иметь в виду, что в них используется несколько иная (что совершенно непринципиально) система команд.

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

1. Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, кратное 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5. Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число - максимальное число, кратное 5.

3. Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, кратных 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 4. Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число - количество чисел, кратных 4

5.Напишите программу, которая в последовательности натуральных чисел определяет сумму чисел, кратных 3. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 3. Количество чисел не превышает 100. В ведённые числа не превышают 300. Программа должна вывести одно число - сумму чисел, кратных 3.

7. Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, кратное 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 4. Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число - максимальное число, кратное 4.

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

13. Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, оканчивающихся на 6. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 6. Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число - количество чисел, оканчивающихся на 6.

15. Напишите программу, к оторая в последовательности натуральных чисел определяет сумму чисел, кратных 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5. Количество чисел не превышает 100. В ведённые числа не превышают 300. Программа должна вывести одно число - сумму чисел, кратных 5.

17. Напишите программу, которая в последовательности натуральных чисел определяет определяет сумму всех чисел, кратных 6 и оканчивающихся на 4. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число: сумму всех чисел, кратных 6 и оканчивающихся на 4.

19. Напишите программу для решения следующей задачи. Камера наблюдения регистрирует в автоматическом режиме скорость проезжающих мимо неё автомобилей, округляя значения скорости до целых чисел. Необходимо определить максимальную зарегистрированную скорость автомобиля. Е сли скорость хотя бы одного автомобиля была меньше 30 км/ч, выведите «YES», иначе выведите «N0». Программа получает на вх од число проехавших автомобилей N (1 < N < 30), затем указываются их скорости. Значение скорости не может быть меньше 1 и больше 300.Программа должна сначала вывести максимальную скорость, затем Y E S или NO.

Входные данные Выходные данные
no

21. Напишите программу для решения следующей задачи. Камера наблюдения регистрирует в автоматическом режиме скорость проезжающих мимо неё автомобилей, округляя значения скорости до целых чисел. Необходимо определить максимальную зарегистрированную скорость автомобиля. Если скорость хотя бы одного автомобиля была не меньше 60 км/ч, выведите «YES», иначе выведите «N0».

Программа получает на вход число проехавших автомобилей N (1 =< N =< 30), затем указываются их скорости. Значение скорости не может быть меньше 1 и больше 300. Программа должна сначала вывести среднюю скорость с точностью до одного знака после запятой, затем «YES» или «N0».

23.

Входные данные Выходные данные

25. Напишите программу, которая в последовательности целых чисел определяет их сумму и количество чётных чисел, кратных 5. Программа получает на вход целые числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа по модулю не превышают 30 000. Программа должна вывести два числа: сумму последовательности и количество чётных чисел, кратных 5.

27. Напишите программу, которая в последовательности целых чисел определяет их сумму и подсчитывает разность количества положительных и отрицательных чисел последовательности. Программа получает на вход целые числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа по модулю не превышают 30 000. Программа должна вывести два числа: сумму чисел и разность количества положительных и отрицательных чисел.

28. Напишите программу, которая в последовательности целых чисел определяет их количество и подсчитывает сумму положительных чётных чисел, не превосходящих 256. Программа получает на вход целые числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа по модулю не превышают 30 000. Программа должна вывести два числа: длину последовательности и сумму положительных чётных чисел, не превосходящих 256.

29. Напишите программу, которая в последовательности натуральных чисел определяет количество всех чётных чисел, кратных 5. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число: количество всех чётных чисел, кратных 5.

31. Напишите программу, которая в последовательности натуральных чисел определяет сумму всех чисел, кратных 7 и оканчивающихся на 2. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число: сумму всех чисел, кратных 7 и оканчивающихся на 2.

33. Напишите программу, которая в последовательности натуральных чисел определяет сумму всех чисел, кратных 8 и оканчивающихся на 6. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число: сумму всех натуральных чисел, кратных 8 и оканчивающихся на 6.

35. Введите с клавиатуры 5 положительных целых чисел. Вычислите сумму тех из них, которые делятся на 4 и при этом заканчиваются на 6. Программа должна вывести одно число: сумму чисел, введенных с клавиатуры, кратных 4 и оканчивающихся на 6.

Входные данные Выходные данные

37. Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, оканчивающееся на 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 4. Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число - минимальное число, оканчивающееся на 4.

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

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

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

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

Рис. 56

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вид стандартного графического объекта

Назначение

Начало алгоритма

Конец алгоритма

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

Условие выполнения действий записывается внутри ромба

Ввод-вывод

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

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

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

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

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

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

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

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

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