Что является в информатике исполнителем алгоритма. Презентация на тему "алгоритм и его исполнение". Что такое алгоритм

Понятие исполнителя невозможно определить с помощью какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим свойством, характеризующим любого из этих исполнителей, является то, что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выполнять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык программирования Бейсик - команды PRINT, END, LIST и другие аналогичные. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ).

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

Рис. 1.11

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

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

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

Графическое представление алгоритмов

Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на алгоритмическом языке (языке программирования). Остановимся на графическом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ благодаря наглядности, обеспечивающей, в частности, высокую «читаемость» алгоритма и явное отображение управления в нем.

Прежде всего определим понятие блок-схемы. Блок-схема - это ориентированный граф, указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного из трех типов (рис. 1.12).

Рис. 1.12

На рис. 1.12 изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -).

Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 1.13), имеющих особое значение для практики алгоритмизации.

Рис. 1.13

На рис. 1.13 изображены следующие блок-схемы: а - композиция, или следование; б - альтернатива, или развилка, в и г - блок-схемы, каждую из которых называют итерацией, или циклом (с предусловием (в), с постусловием (г)). S1 и S2 представляют собой в общем случае некоторые серии команд для соответствующего исполнителя, В - это условие, в зависимости от истинности (Т) или ложности (F) которого управление передаётся по одной из двух ветвей. Можно доказать, что для составления любого алгоритма достаточно представленных выше четырех блок-схем, если пользоваться их последовательностями и/или суперпозициями.

Блок-схема «альтернатива» может иметь и сокращенную форму, в которой отсутствует ветвь S2 (рис. 1.14, а). Развитием блок-схемы типа альтернатива является блок-схема «выбор» (рис. 1.14, б).

Рис. 1.14.

На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки (некоторые из них приведены на рис. 1.15).

Рис. 1.15. Некоторые дополнительные конструкции для изображения блок-схем алгоритмов

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

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

1. Одно из первых требований, которое предъявляется к алгоритму, состоит в том, что описываемый процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную совокупность четко разделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только выполнив требования одного предписания, можно приступить к выполнению следующего. Дискретная структура алгоритмической записи может. Например, подчеркиваться сквозной нумерацией отдельных команд алгоритма, хотя это требование не является обязательным. Рассмотренное свойство алгоритмов называют дискретностью.
2. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.
3. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, т.е. одна и та же команда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат.

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

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

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

Понятие алгоритма - одно из основных понятий информатики. Это фундаментальное «первоначальное» понятие, которому нельзя дать строгого определения. Существуют описательные определения алгоритма, которые уточняют это понятие.

Например:

Алгоритм – последовательность действий со строго определёнными правилами выполнения.

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

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

В начальных классах школы дети изучают порядок выполнения арифметических действий над многозначными числами. Этот порядок был предложен выдающимся математиком средневекового Востока Мухаммедом аль-Хорезми (9 век) и по латинскому написанию его имени (Alhorithmi ) был назван алгоритмом. В дальнейшем это понятие в значительной мере расширилось.

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

Понятие алгоритма неразрывно связано с понятием исполнителя.

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

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

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

Слова «понятное предписание» означают, что команда может быть выполнена.

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

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

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

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

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

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

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

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

Алгоритмические языки

Алгоритмы. Алгоритмизация.

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

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

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

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

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

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

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

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

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

сpеда;
элементаpные действия;
cистема команд;
отказы.

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

Система команд . Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаныpезультаты выполнения команды . Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат - смещение Pобота на одну клетку ввеpх.

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

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

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

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

Название "алгоритм" произошло от латинской формы имени среднеазиатского математика аль-Хорезми - Algorithmi. Алгоритм - одно из основных понятий информатики и математики.

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

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

- сpеда;
- элементаpные действия;
- cистема команд;
- отказы.

Система команд . Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды . Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат - смещение Pобота на одну клетку ввеpх.

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

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

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

7.3. Какими свойствами обладают алгоpитмы?
Основные свойства алгоритмов следующие:

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

Дискpетность (прерывность, раздельность) - т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

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

Pезультативность (или конечность). Это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.

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

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

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

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

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

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

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

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

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

В непосредственную (сенсорную) память человека поступает информация от различных сенсоров: зрительных, слуховых, обонятельных и т.д. Затем эта информация переводится в оперативную память (память сознания). Далее она пересылается в долговременную память с привлечением подсознания («укладывается на полочки» с соответствующими названиями «Формы поведения», «Объекты и образы», «Правила и процедуры обнаружения и идентификации объектов», «Правила выборки и организации информации», «Жизненный опыт», «Бытовые навыки и умения», «Профессиональные навыки и умения» и др.).

Пример . Увиденный человеком конкретный компьютер ассоциируется с абстрактным понятием «Компьютер» (из долговременной памяти) – например, со сведениями об этом устройстве – информационными кодами, которые определяют объект (связь, понятие). Коды связываются между собой, создавая образ конкретного компьютера.

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