Каждый алгоритм создается человеком или группой людей. Алгоритм выполняется исполнителями алгоритмов.
Исполнитель алгоритма — человек или техническое устройство, которые понимают команды алгоритма и умеют правильно их выполнять.
Примерами таких исполнителей могут быть: Учебный исполнитель Робот, Черепашка и проч ь.
Выполнять алгоритм может не только человек (группа людей), но и робот, станок, детская игрушка, стиральная машина и т. д. Исполнителем алгоритма может быть животное (например, дрессированная собака, лошадь), которое понимает и умеет выполнять набор команд.
Человека окружает множество технических устройств: телевизор, телефон, автомобиль, фотоаппарат и т. д.
Каждое устройство имеет свое назначение, свой набор выполняемых функций ( команд ). Команды, которые понимает и может выполнить исполнитель команд, образуют систему команд исполнителя.
Любой исполнитель имеет ограниченную систему команд . Команды алгоритма исполнитель выполняет последовательно, в порядке записи команд алгоритма.
ИНФОРМАТИКА 8 класс: Алгоритмы и исполнители | Видеоурок
Исполнитель выполняет команды формально, не рассуждая над их смыслом . Поэтому процесс исполнения алгоритма можно автоматизировать.
Источник: www.sites.google.com
Определение алгоритма и понятие его исполнителя
Алгоритм – заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.
Название «алгоритм» произошло от латинской формы имени среднеазиатского математика аль-Хорезми – Algorithmi.
Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки.
Основные свойства алгоритмов следующие:
— Понятность – исполнитель алгоритма должен знать, как надо действовать для выполнения этого алгоритма.
— Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).
— Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола и не требовать никаких дополнительных указаний или сведений о решаемой задаче.
— Результативность (или конечность) состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
— Универсальность (массовость) — означает, что алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом, исходные данные могут выбираться из некоторой области, которая называется областью применения алгоритма.
Алгоритм. Исполнитель алгоритмов (6 класс)
В алгоритме отражаются логика и способ формирования результатов решения с указанием необходимых расчетных формул, логических условий, соотношений для контроля достоверности выходных результатов. В алгоритме обязательно должны быть предусмотрены все ситуации, которые могут возникнуть в процессе решения комплекса задач.
Исполнитель алгоритма – это некоторая абстрактная или реальная (технически, биологически или биотехническая) система, способная выполнять действия, предписываемые алгоритмом.
Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д.
Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции.
Это – важная особенность алгоритмов. Наличие алгоритма формализует процесс решения задачи, исключает рассуждение исполнителя. Использование алгоритма дает возможность решать задачу формально, механически исполняя команды алгоритма в указанной последовательности. Целесообразность предусматриваемых алгоритмом действий обеспечивается точным анализом со стороны того, кто составляет этот алгоритм.
Среда (или обстановка) – это «место обитания» исполнителя, которое характеризуется состоянием среды.
Каждый исполнитель может выполнять команды только из некоторого строго заданного списка – системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды.
После вызова команды исполнитель совершает соответствующие элементарные действия.
Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
Наиболее распространенными и привычными являются алгоритмы работы с величинами – числовыми, символьными, логическими и т.д., а универсальным исполнителем алгоритмов является компьютер.
КЛАССЫ МОДЕЛЕЙ АЛГОРИТМОВ.
Результатами теоретических исследований явились три основных класса математических моделей.
Первый класс моделей основан на арифметизации алгоритмов. Предполагается, что любые данные можно закодировать числами, и как следствие – всякое их преобразование становится в этом случае арифметическим вычислением, алгоритм в таких моделях есть вычисление значения некоторой числовой функции, а его элементарные шаги – арифметические операции.
Последовательность шагов определяется двумя способами. Первый способ – суперпозиция, т.е. подстановка функции в функцию. Второй – рекурсия, т.е. определение значения функции через «ранее» вычисленные значения этой же функции.
Второй класс моделей основан на однозначности алгоритма и его техническом исполнении ЭВМ. Одной из таких машин явилась абстрактная машина Тьюринга, представленная на рисунке 1. Она состоит из трех частей: ленты, головки и управляющего устройства. Лента бесконечна и разбита на ячейки. В каждой ячейке может быть записан только один символ.
Элементарный шаг машины Тьюринга состоит из следующих действий:
— головка считывает символ, записанный в ячейке, над которой она находится;
— считанный символ а k и текущее состояние головки q j однозначно определяют новое состояние q i, новый записываемый символ а1 и перемещение головки d p (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).
Устройство управления хранит и выполняет команды машины вида q j a k ® q i a1 d p.
Полное состояние машины Тьюринга называется конфигурацией и включает в себя состояние головки, состояние ленты (слово, записанное на ней) и положение головки на ленте.
Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Он основан, например, на нормальных алгоритмах Маркова.
Для нормального алгоритма задается алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения. Если в качестве алфавита взять алфавит русского языка, а в качестве множества подстановок следующие правила замены букв:
то, используя правила:
— проверить возможность подстановок в порядке возрастания их номеров, и если она возможна (левая часть подстановки обнаружена в исходном слове), произвести подстановку (заменив левую часть на правую);
— если в примененной подстановке имеется символ «!», то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;
— если ни одна подстановка не применима, то процесс преобразования завершен;
можно обнаружить, что по заданному алгоритму исходное слово «слон» превращается в слово «муха» по следующей цепочке:
«слон» ® «суон» ® «муон» ® «мухн» ® «муха».
В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентны машине Тьюринга и другим моделям, уточняющим понятия алгоритма.
Появление точного понятия алгоритма позволило сформулировать алгоритмически не разрешимые проблемы, т.е. задачи, для решения которых невозможно построить алгоритм. Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова), которая ее решает.
Например, неразрешимой оказалась проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который по любым двум алгоритмам выяснял бы, вычисляют они одну и туже функцию или нет.
Знание основных неразрешимостей теории алгоритмов необходимо для специалиста, чтобы предостеречь его от всеобщей алгоритмизации, как знание основных законов физики предостерегает от попыток создания вечного двигателя.
ФОРМЫ ЗАПИСИ АЛГОРИТМОВ
На практике наиболее распространены следующие формы представления алгоритмов:
— словесная (запись на естественном языке);
— графическая (изображения из графических символов);
— псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.)
— программная (тексты на языках программирования).
Словесный способ записи
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Описательный алгоритм не имеет широкого распространения, так как такие описания:
— строго не формализуемы;
— страдают многословностью записей;
— допускают неоднозначность толкования отдельных предписаний.
Источник: cyberpedia.su
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Основные алгоритмические структуры
Исторический обзор. Первым дошедшим до нас алгоритмом в его интуитивном понимании — конечной последовательности элементарных действии, решающих поставленную задачу, — считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось слово «метод».
Слово «алгоритм», «algorithm» происходит от имени выдающегося ученого IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского Мухаммед, сын Мусы из Хорезма). По латинскому переводу его труда (XII век) Западная Европа познакомилась с десятичной позиционной системой счисления и правилами (algorismi) выполнения в ней арифметических действий.
Формализация понятия алгоритма. Во всех сферах своей деятельности, в частности, в сфере обработки информации, человек сталкивается с различными методами решения задач. Они определяют порядок выполнения действий для получения желаемого результата — мы можем трактовать это как первоначальное или интуитивное определение алгоритма.
Определение 1. Алгоритм — это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.
Варианты словесного определения алгоритма, принадлежащие российским ученым-математикам А. Н. Колмогорову и А. А. Маркову:
Определение 2 (Колмогоров). Алгоритм — это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 3 (Марков). Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Дискретность. Алгоритм состоит из последовательных команд, только выполнив одну команду, исполнитель может приступить к выполнению следующей. То есть структура алгоритма является дискретной (прерывной).
Конечность. Алгоритм содержит конечное количество элементарных выполнимых предписаний, т. е. удовлетворяет требованию конечности записи. Исполнитель алгоритма должен выполнять конечное количество шагов при решении задачи, т. е. алгоритм удовлетворяет требованию конечности действий.
Точность (определенность). Каждая команда алгоритма должна определять однозначное действие исполнителя. Этим свойством часто не обладают предписания и инструкции, которые составляются для людей.
Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм не рассчитан на принятие самостоятельных решений исполнителем, не предусмотренных составителем алгоритма.
Универсальность (массовость). Алгоритм должен быть единым для всех допустимых исходных данных. Разработка алгоритма — процесс творческий, но требующий значительных затрат времени и умственных усилий, поэтому желательно, чтобы он обеспечивал решение задач данного типа. Это свойство не является обязательным; не менее важными являются алгоритмы уникальные, разработанные для решения одной задачи.
Алгоритм предполагает наличие исполнителя — человека или технического устройства (автомат, робот, компьютер) со строго определенным набором возможных команд. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя (СКИ). Исполнитель может исполнять команды из СКИ и ничего более.
Автоматическое исполнение алгоритма
Алгоритм позволяет формализовать выполнение процесса обработки исходных данных и получения результата. На этом основана работа программно управляемых исполнителей-автоматов, например промышленных роботов. От исполнителя не требуется понимания сущности алгоритма, он должен точно выполнять команды в заданной последовательности.
Примером исполнителя, автоматически выполняющего различные алгоритмы, является компьютер. Рассмотрим запись на жесткий диск компьютера телевизионной передачи с помощью ТВ-тюнера. Указав в расписании время начала и окончания записи, поставив «флажок» возле позиции «Выключить компьютер после записи», пользователь может быть уверен, что передача будет записана и компьютер будет выключен. Всю заданную работу выполнит компьютер по разработанному ранее алгоритму, не внося никаких изменений (другая передача, другое время, невыключение компьютера).
Способы описания алгоритмов
Словесное описание применимо лишь для простейших алгоритмов. В случае, когда связи между действиями усложняются, высокая степень детализации приводит к громоздкому описанию.
Описание на алгоритмическом языке (псевдокоде) осуществляется с помощью слов естественного языка, но в специальной форме, отображающей структуру алгоритма. Всё чаще словесное описание и запись на алгоритмическом языке сводят к одному способу — словесному.
Основные блоки, используемые при графической форме записи алгоритмов:
Описание в виде программы для компьютера на языке программирования (например, Паскаль, Бейсик, Си).
Основные алгоритмические структуры
Алгоритм может быть реализован в виде комбинации трех базовых алгоритмических конструкций: линейной, разветвленной, циклической.
Алгоритм линейной структуры — алгоритм, в котором предписываемые действия выполняются последовательно: Оператор1 — Оператор2 —. — Оператор N. Такой порядок выполнения действий называется естественным.
Алгоритм разветвленной структуры — алгоритм, в котором предусмотрено разветвление выполняемой последовательности действий в зависимости от результата проверки какого-то условия. Условие — это некоторое логическое выражение. Если условие (логическое выражение) принимает значение «истина», то выполняется Оператор1, в противном случае — значение «ложь» — выполняется Оператор2. Oпeратор1 и Оператор2 могут представлять собой группу операторов, а также могут быть условными операторами. В случае отсутствия Оператора2 получаем конструкцию с неполным ветвлением.
Алгоритм циклической структуры (цикл с повторением) — алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. Эту последовательность действий называют телом цикла.
Если количество повторений известно, то используют цикл со счетчиком, иначе — цикл с предварительной или последующей проверкой условия повторения.
Циклическую структуру реализуют операторы трех типов.
Оператор FOR. DO действует следующим образом. Тело цикла выполняется для каждого значения параметра цикла I от его начального M1 до конечного значения М2 включительно. I, Ml, M2 — чаще всего переменные целого типа. Шаг изменения переменной цикла I равен +1 или -1.
Оператор WHILE. DO действует следующим образом. Каждый раз предварительно проверяется значение логического выражения. Пока оно истинно, выполняется тело цикла. Как только оно становится ложным, происходит выход за пределы цикла.
Если с самого начала значение логического выражения является ложным, то тело цикла не выполняется ни разу.
Оператор REPEAT. UNTIL действует следующим образом. Тело цикла выполняется, пока значение логического выражения ложно. Тело цикла выполняется как минимум один раз.
Все алгоритмические конструкции имеют общее свойство: один вход и один выход. Допускается неограниченное соединение структур и их вложение друг в друга, что позволяет проектировать сложные алгоритмы.
Источник: studopedia.info