Алгоритм и его свойства. Способы записи алгоритма

      Введение. 

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

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

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

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

      1.Алгоритм и его свойства. Способы записи алгоритма.

      «Алгоритм»  является фундаментальным понятием информатики. Представление о нем необходимо для эффективного применения вычислительной техники к решению практических задач.

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

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

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

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

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

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

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

      Свойства  алгоритма (отличающие его от любых  других предписаний):

      1) понятность (для конкретного исполнителя);

      2) дискретность (команды последовательны, с точной фиксацией моментов начала и конца выполнения команды);

      3) точность (после выполнения каждой команды точно известно, завершено ли исполнение алгоритма или же какая команда должна выполниться следующей);

      4) результативность (после конечного числа шагов задача решается или же становится ясно, что процесс решения не может быть продолжен);

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

      Рассмотрим  свойства алгоритмов подробнее.

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

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

      3. Понятность - однозначное понимание  и исполнение каждого шага  алгоритма его исполнителем. Алгоритм  должен быть записан на понятном  для исполнителя языке.

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

      5. Массовость - применение алгоритма  к решению целого класса однотипных задач.

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

      На  практике наиболее распространенными  являются следующие формы записи алгоритмов:

      1) графическая запись (блок-схемы);

      2) словесная запись (псевдокоды);

      3) язык программирования.

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

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

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

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

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

      3. Язык программирования - язык, используемый для формальной записи алгоритмов. Большинство языков программирования относятся к алгоритмическим языкам. Запись алгоритма на алгоритмическом языке называют программой.

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

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

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

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

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

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

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

      Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

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

      Шаги  бывают «безусловными» (изображаются прямоугольниками, параллелограммами) и «условными» (изображаются ромбами). Из ромба всегда выходят две стрелки - одна означает дальнейший путь, в случае выполнения условия (обозначается обычно словом "да" или "+"), другая - невыполнение (словом "нет" или "-"). Ввод с клавиатуры или вывод на экран значения выражения изображается параллелограммом. Команда, выполняющая обработку действий (команда присваивания), изображается в прямоугольнике.