Реферат на тему: Построение алгоритмов и их реализации на компьютере
Баранов Влад 28 группа
Что такое алгоритм, виды алгоритмов
Алгоритм (лат. algorithmi — от арабского имени математика Аль-Хорезми[1]) — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Ранее в русском языке писали «алгори т м», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек (а может быть и некоторый механизм, ткацкий станок, и пр.).
Можно выделить алгоритмы вычислительные (о них в основном идет далее речь), и управляющие. Вычислительные по сути преобразуют некоторые начальные данные в выходные, реализуя вычисление некоторой функции. Семантика управляющих алгоритмов существенным образом может отличаться и сводиться к выдаче необходимых управляющих воздействий либо в заданные моменты времени, либо в качестве реакции на внешние события (в этом случае, в
Исполнитель алгоритмов
Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя, ведь выполнимость алгоритма зависит от того, какие действия может совершить исполнитель. Например, прочесть алгоритм решения системы линейных уравнений графическим методом сможет и первоклассник, а выполнить его, конечно же, нет. С другой стороны, малыш четырех-пяти лет не сможет прочесть правила (алгоритм) поведения за столом во время еды, но выполнить их сможет, если ему о них рассказать и показать, что они означают. Но исполнителем алгоритмов может быть не человек, а автомат. Например, исправный автомат по продаже газированной воды работает согласно разработанному специально для него алгоритму. Алгоритмом описывается работа любого механического устройства. В ряду всевозможных автоматов компьютер является лишь частным (хотя и наиболее впечатляющим) примером исполнителя, чье поведение реализуется на основе алгоритма. Более того, создание компьютеров оказало воздействие на развитие теории алгоритмов — одной из областей математики. От компьютера, как от любого другого исполнителя, требуется четкое выполнение команд алгоритма. А от нас, как от разработчиков алгоритмов работы компьютера, требуется знание и соблюдение правил их составления. Эти правила заключаются в том, что алгоритм, предназначенный для исполнения автоматом, должен обладать пятью свойствами (удовлетворять пяти требованиям). Эти требования нашли отражение и в приведенном выше определении алгоритма. Требования к алгоритму объясняются тем, что такой исполнитель не имеет своего интеллекта, его возможности всегда ограничены.
Исполнитель. Точное определение исполнителя дать очень трудно, да и в этом нет необходимости. Важно понять основные характеристики исполнителя: среда, элементарные действия, система команд, отказы.
Согласно учебнику Кушниренко, "исполнитель - это устройство, приспособление, робот, организация и т. п., способное выполнять определенные действия". Отсюда исполнителем можно назвать довольно большую группу объектов (включая и человека). Современные учебные системы в основном предоставляют нам один вид исполнителей, которые устроены так: вы вводите команду и какой-нибудь человечек (или робот) начинает выполнять соответствующие действия.
Каждый исполнитель имеет следующее:
Среда - это «место обитания» исполнителя. Например, исполнитель Дежурик обитает в так называемой классной комнате, исполнитель Черепаха имеет свою определенную систему координат, а исполнитель Муравей имеет клетчатое поле.
Система команд исполнителя
Команды, которые может выполнить определенный исполнитель, образуют систему команд исполнителя (СКИ). Класс исполнителей чрезвычайно разнообразен. Прежде всего, в немвыделяют два типа исполнителей формальных и неформальных. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель можетвыполнять команду по-разному.
Например, при многократном прослушивании кассеты с любимой мелодией, вы можете быть уверены, что она воспроизводится носителем (формальным исполнителем) всегдаодинаково. Но вряд ли кому-нибудь из певцов (неформальному исполнителю) удастся несколько раз совершенно одинаково исполнить песню из своего репертуара.
Как правило, человек выступает в роли неформального исполнителя. Формальными исполнителями являются, как правило, технические приспособления и устройства. Человек в ролинеформального исполнителя сам отвечает за свои действия. За действия формального исполнителя отвечает управляющий им объект.
Формальные исполнители чрезвычайно разнообразны, но для каждого из них можно указать круг решаемых задач, среду, систему команд, систему отказов, режим работы.
Свойство Алгоритмов
Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Определенность — каждое правило алгоритма должно быть четким, однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость — алгоритм решения задачи разрабатывается в общем виде, то есть он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.