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

      Введение. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Линейная алгоритмическая  структура. 

      Алгоритмы могут отличаться не только по способу  записи, но и по структуре. Алгоритмические  структуры различаются на:

1. линейные (следования);
2. разветвляющиеся (выбора);
3. циклические повторения).

      Рассмотрим данные алгоритмические структуры подробнее.

      Для решения любых задач достаточно этих трех видов структур.

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

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

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

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

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

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

3. Разветвляющаяся алгоритмическая структура. 

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

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

      Условие — выражение, находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь».

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

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

      В общем случае схема разветвляющего алгоритма будет выглядеть так: «если условие, то..., иначе...». Такое представление алгоритма получило название полной формы.

      Неполная форма, в которой действия пропускаются: «если условие, то...».

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

      Например: вы в детстве учились суммировать  единицы, затем десятки, чтобы суммировать  двузначные числа содержащие единицы  вы не учились новому методу суммирования, а воспользовались старыми методами.

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

4. Циклические алгоритмические структуры. 
 

      Алгоритмы, при исполнении которых отдельные  команды или серии команд выполняются  неоднократно, называют циклическими. Для организации циклических  алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответствует блок-схемам типа «итерация»

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

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

      Условие — выражение, находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь».

      Рассмотрим  алгоритм нахождения суммы первых натуральных нечетных чисел до n.

     В схеме циклического процесса блоки имеют следующее назначение:

     1 - блок задания начального значения  параметра цикла;

     2 - тело цикла, то есть участок вычислительного процесса, который многократно повторяется;

     3 - блок изменения параметра цикла;

     4 - блок проверки условия выхода  из цикла.

      Цикл  программы – последовательность команд (серия, тело цикла), которая  может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия. 

  5. Основные операторы  циклов и ветвлений. 

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

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

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

      Имеется 3 вида циклов:

• Цикл с предварительным условием (с предусловием);
• Цикл с последующим условием (с постусловием);
• Цикл с параметром.

1. Операторы с предусловием.

1. Оператор  цикла «Пока» (с предусловием).

      Самым «строгим» циклом (в смысле его  соответствия правилам структуры программирования) является цикл «Пока». Его синтаксис следующий:

      while <условие> do <оператор>,

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

      <оператор> - любой допустимый оператор или блок операторов языка программирования.

      Приведем  схему выполнения оператора «while».

1. Вычисляется выражение-условие ВЫРАЖЕНИЕ.
2. Если оно истинно, то выполняются операторы блока БЛОК и осуществляется возврат к пункту 1.
3. Если выражение-условие ложно, то оператор цикла завершает свою работу и передает управление следующему после него оператору программы.

      Таким образом, оператор цикла «while» является управляющей конструкцией цикла с предусловием: сначала проверяется условие завершения цикла, и потом только выполняется тело цикла, определяемое блоком БЛОК. Поэтому может оказаться, что тело цикла не будет выполнено ни одного раза, если при первом вхождении в цикл условие окажется ложным. Это обстоятельство следует учитывать при программировании с циклом «while».

      Для корректной работы цикла «while» необходимо, чтобы на каждом шаге цикла изменялось выражение-условие, иначе мы получим бесконечный цикл, если при вхождении в него это выражение истинно. Изменение выражения-условия на каждой итерации цикла можно реализовать либо непосредственно в самом выражении, например, использовать операцию чтения из стандартного входного потока <>, либо при выполнении операторов блока БЛОК обеспечить изменение значений переменных, входящих в выражение-условие.

      На  блок-схеме оператор цикла «Пока» - имеет вид, приведенный на рис.5.1.:

      Рис. 5.1. Оператор цикла «пока» на блок-схеме.  

      Для реализации цикла «пока» должны быть выполнены следующие условия:

• условие входа в цикл;
• условие выхода из цикла;
• последнее условие должно меняться в теле цикла.

1.2. Оператор цикла  «До … пока»  (с предусловием).

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

      do <оператор> while <условие>

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

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

      На  блок-схеме цикл «До … пока» имеет следующий вид, изображенный на рис.5.2.: 

      Рис. 5.2. Оператор цикла «До … пока» на блок-схеме.

2. Оператор цикла с постусловием («repeat»).