Алгоритмы и программирование

Глава 5. АЛГОРИТМЫ И ПРОГРАММИРОВАНИЕ

Содержание главы



5.1 Алгоритм................................................................................................................................................. 21 5.2 Свойства алгоритма........................................................................................................................... 23 5.3 Роль алгоритмов в науке и технике............................................................................................... 26 5.4 Способы записи алгоритма............................................................................................................... 26 5.5 Виды алгоритмов.................................................................................................................................. 29 5.6 Реализация простейших алгоритмов на языке BASIC............................................................ 29 5.7 Основные операторы........................................................................................................................... 30 5.8 Сортировка данных............................................................................................................................ 32 5.9 Искусственные языки. Формальные языки.................................................................................. 33 5.10 Языки программирования. Классификация языков программирования.......................... 34 5.11 Задачи программирования............................................................................................................... 39

Основные понятия:

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

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

3) сформулированная на некотором языке последовательность действий, строгое выполнение которой даёт точное решение задач.

4) организованная последовательность действий.

Блок-схемы — графическое описание алгоритмов, как последовательностей дейст­вий.

Алгоритмические языки — языки описания алгоритмов.

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

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

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

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

Результативность — завершение работы алгоритмов с определенными результатами.

Правильность — правильность результатов, получаемых по заверше­нии выполнения алгоритма.

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

Понятность – алгоритм должен быть понятен исполнителю.

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

5.1 Алгоритм

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

-

 

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

Приведем еще несколько используемых определений алгоритма:

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

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

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

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

-

 

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

Отсюда исполнителем можно назвать довольно большую группу объектов (включая и человека).

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

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

1. Вывод просьбы о вводе имени.

2. Ввод имени

3. Вывод подтверждения.

Как видим, в задаче применяется 2 элементарных действия: ввод и вывод на экран. Введём две операции: «запрос» и «вывод». Параметры будем записывать в скобках. В результате имеем:

1. Вывод («Введите имя»)

2. Запрос (имя)

3. Вывод (имя)

Таким образом, видим, что наша задача свелась к последовательному выполнению двух действий с разными параметрами. Можно предположить, что любую задачу можно свести к определённой последовательности элементарных действий.

Алгоритм решения задачи имеет ряд обязательных свойств:

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

*  определенность алгоритма - однозначность выполнения каждого отдельного шага преобразования информации;

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

*  массовость - пригодность алгоритма для решения определенного класса задач.

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

Вычислительные алгоритмы — алгоритмы, задающие процессы вычислений на ЭВМ.

Диалоговые алгоритмы — алгоритмы ведения диалога с ЭВМ.

Графические алгоритмы — алгоритмы построения графических изображений на дисплеях ЭВМ.

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

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

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

Но вернемся к анализу тех предметов, которые могут быть исходными данными и результатами. Очевидно, для каждого алгоритма можно брать различные варианты исходных данных. Это видно из того, что; например, для алгоритма приготовления детской пищи можно слова «граммы» при описании исходных данных понимать как «весовые части». Качество получаемой пищи при этом не изменится. Может измениться только ее количество. Для рецепта приготовления лимонного желе, очевидно, так и сделано. Многие алгоритмы остаются в силе для различных вариантов исходных данных. Алгоритм сложения можно применить к парам любых положительных чисел. Алгоритм дополнительного кормления щенят годится не только, например, для Рексика и Бобика, но и для других щенят.

Замеченное нами свойство алгоритмов, в § 1 (их применимость к большому числу вариантов исходных данных), называют их массовостью. Долгое время считали, что пригодность алгоритмов для многих частных случаев является настолько существенной и важной их чертой, что должна войти в научное определение алгоритма. Это исключало многие правила из компетенций науки ( из-за их «недостаточной» массовости) и затрудняло как научные исследования, так и применение их результатов на практике (а вдруг перед нами именно ненаучный случай?), что представляет собой серьезные неудобства.

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

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

Займемся вопросом о том, что представляет собой класс возможных исходных данных. Мы видели, что иногда ис­ходными данными являются наборы предметов или мате­риалов, иногда — числа. То же справедливо и для получаемых результатов. Что общего между этими предметами? Это общее обнаружится, если принять во внимание, что алгоритмы — это правила, и, следовательно, они сформулированы на каких-то языках. Мы уже несколько раз говорили о том, насколько важно точное выполнение этих правил. Но такое точное выполнение возможно лишь при условии, что исходные данные (а с ними и искомые результаты) поддаются исчерпывающему описанию на каком-то языке, может быть на новом. При этом каждому исходному данному, каждому промежуточному результату и, наконец, искомому результату соответствует некоторое предложе­ние. Нужно, чтобы «смысл» указанного предложения был однозначен.

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

Допустима ли такая подмена с точки зрения практики? Безусловно допустима. Ведь в самом алгоритме присутствуют не исходные данные, а их названия, а для выполнения процесса достаточно знать названия операций и получаемых результатов. В некоторых случаях подмена и не нужна: в различных алгоритмах кодирования и декодиро­вания.

Могут сказать, что описанный прием приводит к суже­нию понятия алгоритма. Такое мнение тоже правомерно. Но это сужение несущественно, потому что не уменьшает возможностей, даваемых алгоритмами.

При таком подходе мы делаем значительно меньшим разнообразие исходных данных и результатов, хотя они по-прежнему могут обладать различной физической при­родой, но для нас, при их теоретическом рассмотрении, это будут предложения различных языков. Разнообразие предметов мы свели к разнообразию языков. Правда, и язы­ков немало. Можно считать, что их бесконечное множество (не только существующих, но и таких, которые могли бы существовать, т. е. возможны). Но каждый алгоритм связан только с двумя языками: на одном он сформулиро­ван сам, а предложения другого являются допустимыми для него вариантами исходных данных. Первый язык обычно называют алгоритмическим, а второй — языком операндов.

-

 

Операндами называют те объекты, над кото­рыми выполняются операции, предписываемые алгорит­мом.

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

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

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

Будем говорить, что алгоритм применим к допустимому исходному данному, если с его помощью, отправляясь от этого исходного данного, можно получить искомый резуль­тат. Если же результат получить нельзя, хотя исходное данное и допустимо, то алгоритм к нему неприменим.

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

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

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

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

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

Понятность алгоритма

Анализируя интуитивное понятие алгоритма, мы за­мечаем еще одну особенность. Предполагается, что испол­нитель правила всегда знает, как его выполнять. Говорят, что алгоритм понятен для исполнителя. В первых книгах по теории алгоритмов говорится даже об их общепонятно­сти. С таким утверждением согласиться нельзя. Даже свойство понятности не так просто, как кажется на первый взгляд.

Представим себе, что нами получен некоторый письменный текст. Можно ли утверждать, что он понятен и в ка­ких случаях? Если алфавит, буквы которого использо­ваны в тексте, нам незнаком, то ответ будет один: текст непонятен. Но если все буквы принадлежат знакомому алфавиту, может оказаться, что составляющие его слова нам незнакомы. В этом случае текст тоже непонятен. А если все слова знакомы? Тогда возникает вопрос о способе их со­единения в предложения. Если он противоречит граммати­ческим правилам, опять текст непонятен. А если все грам­матические правила соблюдены? В этом случае неизвестно, понятен текст или нет. Ведь может оказаться, что он явля­ется кодом какого-то другого текста и его скрытый истин­ный смысл не совпадает с его непосредственным смыслом. Если о тексте (кроме него самого) ничего не известно, то назвать его понятным нельзя. Если известно, что текст представляет собой алгоритм, то неопределенность его уменьшается, но незначительно. Полная ясность будет лишь тогда, когда будет известно, что надо делать для того, чтобы этот алгоритм выполнить.

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

Определенность алгоритма

Обратим внимания еще на одну особенность, присущую каждому алгоритму. Исполнитель алгоритма не только не нуждается в какой-либо фантазии или сообразитель­ности, но, более того, алгоритм не оставляет места для проявления этих качеств, если исполнитель ими обладает. Выполняя алгоритм, действуют механически. Может быть, по мнению читателя это плохо? Может быть, эта черта алгоритма в какой-то мере подавляет творческие способности людей? Ни в коем случае! Люди могут в полной мере проявлять свои творческие способности, разрабатывая алгоритмы. Но после того как они созданы, такое проявление творческих способностей было бы неоправданным расходом психической энергии. Алгоритмы позволяют ее экономить. Таким образом, формулировка алгоритма так точна, что полностью определяет все действия исполнителя.

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

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

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

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

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

Выводы

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

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

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

И прежде всего о такой особенности, как простота дейст­вий, выполняемых на каждом шаге.

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

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

В чем же неточность интуитивного понятия алгоритма? В неточности тех терминов, в которых мы его выразили. До сих пор идут споры о том, что такое язык. Неясен смысл таких слов, как «понятность» и «точность». Научный смысл неясен. А интуитивное значение этих слов ясно.

5.3 Роль алгоритмов в науке и технике

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

Особое значение имеют алгоритмы, накопленные в математике, потому что математика пронизывает другие науки и ее богатство является богатством всех наук. Уже довольно давно ученые и инженеры заметили, что если удалось получить алгоритм решения какой-нибудь задачи, то можно создать машину, которая решала бы эту задачу, т. е. можно автоматизировать ее решение. Практика уп­рямо подтверждала этот факт. Наука его объяснила полностью только недавно. Читатель познакомится с этим в § 3 гл. 6.

Алгоритмы являются:

1)  формой изложения научных результатов;

2)  руководством к действию при решении уже изученных проблем и, как следствие:

3)  средством, позволяющим экономить умственный труд;

4)  необходи­мым этапом при автоматизации решения задач;

5)  сред­ством (инструментом), используемым при исследовании и решении новых проблем (особенно это касается математических алгоритмов);

6)  одним из средств обоснования математики;

7)  одним из средств описания сложных процессов.

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

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

Несмотря на то, что алгоритмы очень важны для прак­тики, все же утверждение, будто они изучаются и разра­батываются только в связи с требованиями практики, было бы искажением истины. Нередко создают или ищут алго­ритмы для решения задач, которые сами по себе (по крайней мере в настоящее время) не имеют практического значения. Иногда причиной для изучения той или иной проблемы служит любопытство, иногда — эстетическое чувство (например, теория кажется недостаточно «изящ­ной» без алгоритма решения какой-либо вычурной задачи, возникающей при ее разработке). Иногда большие силы ученых привлекает к себе некоторая проблема потому, что в ее решении ученые видят для себя «дело чести». Многие охотники за алгоритмами не задумываются над тем, нужны ли, и если нет, будут ли когда-либо нужны добываемые ими экземпляры. Жизнь показывает, что многие научные результаты, возникающие даже без учета нужд практики, рано или поздно находят важные прак­тические применения. Охота за алгоритмами — это увле­кательное и важное дело, которому отдают большую часть своего времени многие ученые.

5.4 Способы записи алгоритма

Словесная запись

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

Пример: значение функции определяется следующим образом: y=2, если x<1 и y=-x+3, если x³1.

Алгоритм можно записать следующим образом:

1.  Ввести в память ЭВМ значение аргумента x.

2.  Проверить справедливость неравенства x<1. Если условие x<1 выполняется, то перейти к шагу 3, если не выполняется (x³1), то перейти к шагу 4.

3.  Вычислить значение y = 2 и перейти к шагу 5.

4.  Вычислить значение y = –x+3 и перейти к шагу 5.

5.  Напечатать значение результата y.

6.  Прекратить вычисления.

Операторная запись

Представляет собой изображение алгоритма в виде последовательности символов-операторов, каждый из которых выполняет определённую функцию. Операторы обозначаются буквами: А - арифметический оператор, В - оператор ввода, Р - логический оператор, П - оператор печати и т. д. Каждый оператор имеет индекс, соответствующий его порядковому номеру в алгоритме. Распространен незначительно ввиду недостаточной наглядности. Как правило, требует словесных пояснений.

Блок-схемы

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

Название блока	Обозначение (ГОСТ 19.003-80)	Выполняемая функция
Процесс		Вычислительное действие или последовательность действий.
Решение		Проверка условия и выбор направления хода вычислительного процесса.
Модификация		Начало цикла.
Предопределённый процесс		Использование ранее созданных и отдельно описанных алгоритмов.
Ввод-вывод		Ввод или вывод данных.
Документ		Вывод данных на печатающее устройство.
Соединитель		Указание связи между прерванными линиями потока.
Пуск, останов		Начало, конец, останов, вход и выход в отдельно описанных алгоритмах и подпрограммах.
Комментарий		Пояснения, содержание подпрограмм, формулы.

Таблица 5.2.1 Элементы блок-схем.

Примечание! Размеры, указанные в таблице, являются рекомендательными и не обязательны к запоминанию.

5.5 Виды алгоритмов

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

Рисунок 5.3.2 Алгоритм ветвления

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

Рисунок 5.3.1 Линейные алгоритмы

Рисунок 5.3.3 Алгоритм цикла

 

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

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

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

5.6 Реализация простейших алгоритмов на языке BASIC

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

Одно из ключевых понятий в программировании является понятие «переменной».

-

 

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

Переменные подразделяются по типам данных. Основные типы переменных - числовые, символьные и логические. Числовые, в свою очередь, подразделяются на целочисленные (integer) и с плавающей запятой (real, double). Реализация типов данных зависит от конкретного языка программирования, но обычно целочисленная переменная может принимать значения от -32767 до 32768 или от 0 до 65байта - 216). Логическая (1 бит) может принимать только два значения - true (истина) и false (ложь). В силу особенностей представления информации в ЭВМ, логическая переменная имеет длину 1 байт, из которых используется только один бит, последний. Первые 7 бит равны нулю. Символьные переменные - это строки. В BASICе символьные переменные обозначаются знаком $ после имени переменной, например: a$=«привет!».

Рассмотрим случай обработки однотипных данных (матриц, полей баз данных и т. п.). Пусть дана матрица 3x3.

a11	a12	a13
a21	a22	a23
a31	a32	a33

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

-

 

Массив - это упорядоченная последовательность величин, обозначенная одним именем.

То есть вместо введения 9 переменных (a­1, a2,..., a9) мы вводим один массив из 9 элементов. Массивы характеризуют размерностью (количеством измерений матрицы). Отдельные величины, образующие массив, называются элементами массива. К каждому элементу массива можно обратиться, указав имя массива и индексы, указывающие положение элемента. a= {a(1),a(2),a(3),a(4),...,a(n)}. Например, пусть у нас есть одномерный массив а, содержащий 10 элементов. Тогда, чтобы получить доступ к 5 элементу, нам необходимо написать a(5). Аналогично, обращение к элементу, расположенному в 1 строке и 5 столбце двумерной матрицы, будет выглядеть как а(5,1).

5.7 Основные операторы

Оператор присваивания

Синтаксис: a = b. После выполнения этого оператора переменной a присвоится значение выражения b.

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

Условное обозначение в блок-схемах:

Оператор вывода

Синтаксис: print <значение1>,<значение2>,...

Осуществляет вывод данных на экран. Допускается выводить переменные и строки. Строки необходимо заключать в кавычки.

Пример: print «Значение а=», a

Условное обозначение в блок-схемах:

Оператор ввода

Синтаксис: input <значение1>,<значение2>,...

Осуществляет ввод данных с клавиатуры. Допускается выводить поясняющее сообщение в кавычках.

Пример: input «Введите а:», a

Условное обозначение в блок-схемах:

Оператор ветвления

Синтаксис: Оператор ветвления:

if <условие> then <оператор1>.

Альтернативный оператор ветвления:

if <условие> then <оператор1> {else <оператор2>}.

Если <условие> выполняется, то выполняется <оператор1>, иначе, в случае употребления ключевого слова else выполняется <оператор2>.

Пример: if a<b then print «a меньше b»

if a<b then print «a меньше b» else print «b меньше a»

Условное обозначение в блок-схемах:

Оператор перехода

Синтаксис: goto метка

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

Пример: if a<b then goto 10

print «a не превышает b»

10 print «a больше b»

Условное обозначение в блок-схемах: стрелка

Операторы цикла

Цикл FOR...NEXT - цикл с заранее заданным числом количеством повторений.

Синтаксис:

for <переменная> =<начальное значение> to <конечное значение> step <шаг>

оператор1

оператор2

...

next <переменная>

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

Пример: a=0

for i=1 to 10

a=a+2 ü

print a ý Тело цикла

... þ

next i

В результате выполнения данной программы на экран 10 раз будет выведено значение переменной a.

Цикл DO...LOOP - цикл с заранее неизвестным числом повторений. Он выполняется до тех пор, пока истинно условие в начале или конце цикла. Из цикла возможен альтернативный выход оператором EXIT DO, который передаёт управление на оператор, следующий за LOOP.

Пример: DO

INPUT «Введите число N:»; n

LOOP WHILE n<=10

Этот цикл повторяется до тех пор, пока пользователь не введёт число, превышающее 10 (LOOP WHILE n<=10) - повторять, пока n меньше или равно 10.

Условное обозначение оператора цикла в блок-схемах:

Вызов процедуры или функции

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

Синтаксис: function name [(список_параметров)]

тело функции

name = выражение

end function

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

Пример: 1. Пусть нам необходимо вычислить корни квадратного уравнения. Даны коэффициенты a, b,c. Необходимо вычислить корни, если таковые имеются. Итак, пишем функцию equation.

function equation (a, b,c)

discr=b2-4×a×c

if discr < 0 then print «Действительных корней нет.»: goto end_func

x1= (-b+sqr(discr))/(2×a)

x2= (-b-sqr(discr))/(2×a)

print «Корни уравнения: »; x1; x2

end_func:

end function

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

Пример: 2. Вычисление факториала.

function fakt (a)

for i = 1 to a

f = f × i

next i

fakt = f

end function

5.8 Сортировка данных

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

do change = false for j = z to max if x(j-1) <= x(j) then goto 10 a = x(j-1) x(j-1) = x(j) x(j) = a change = true 10 next j while not change

Метод «пузырька»

 

 

Если массив уже упорядочен, то во внутреннем цикле не меняется местами ни одна пара элементов и значение замена остается false. Сортировка закончится.

5.9 Искусственные языки. Формальные языки.

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

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

Выбирая некоторые предложения естественного языка, мы можем получить вполне удовлетворяющий нас язык. Но, конечно, можно построить и искусственный язык, удоб­ный для целей теории алгоритмов. Каким же должен быть этот язык? Во-первых, потребуем от языка, чтобы он подчинялся вполне строгим и точно сформулированным син­таксическим правилам. Во-вторых, число этих правил долж­но быть конечно, и эти правила никак не должны зависеть от смысла получаемых с их помощью или используемых в соответствии с ними предложений или их частей. В-третьих, будем требовать, чтобы между формой предложений и их смыслом существовало однозначное соответствие. Можно мириться с тем, чтобы различные предложения имели один и тот же смысл, но нельзя допустить, чтобы некоторое предложение имело несколько смыслов. Если даже какое-либо предложение может быть получено несколькими путями, это не должно делать его многозначным.

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

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

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

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

-

 

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

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

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

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

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

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

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

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

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

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

5.10 Языки программирования. Классификация языков программирования

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

-

 

Программирование (programming) - теоретическая и практическая деятельность, связанная с созданием программ.

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

-

 

Программа (program, routine) - упорядоченная последовательность команд (инструкций) компьютера для решения задачи.

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

-

 

Язык программирования — формализованный язык для описания алгоритма решения задачи на компьютере.

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

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

·  машинные языки (computer language) - языки программирования, воспринимаемые аппаратной частью компьютера (машинные коды);

·  машинно-ориентированные языки (computer-oriented language) - языки программирования, которые отражают структуру конкретного типа компьютера (ассемблеры);

·  алгоритмические языки (algorithmic language) - не зависящие от архитектуры компьютера языки программирования;

·  процедурно-ориентированные языки (procedure language) - языки программирования, где имеется возможность описания программы как совокупности процедур (подпрограмм);

·  проблемно-ориентированные языки (universal programming language) - языки программирования, предназначенные для решения задач определенного класса (Лисп, РПГ, Симула и др.);

·  интегрированные системы программирования.

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

-

 

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

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

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

-

 

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

Системы программирования (programming system) включают:

·  компилятор;

·  интегрированную среду разработчика программ;

·  отладчик;

·  средства оптимизации кода программ;

·  набор библиотек;

·  редактор связей;

·  сервисные средства (утилиты) для работы с библиотеками, текстовыми и двоичными файлами;

·  справочные системы;

·  документатор исходного кода программы;

·  систему поддержки и управления проектом программного комплекса.

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

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

5.11 Для любознательных

Процедурное программирование

Процедурное (императивное) программирование является отражением архитектуры традиционных ЭВМ, которая была предложена Джоном фон Нейманом в 40-х гг. Теоретической моделью процедурного программирования служит алгоритмическая система под названием «машина Тьюринга».

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

Процедурные языки характеризуются:

·  значительной сложностью;

·  отсутствием строгой математической основы;

·  необходимостью явного управления памятью, в частности необходимостью описания переменных;

·  малой пригодностью для символьных вычислений;

·  высокой эффективностью реализации на традиционных ЭВМ.

К основным процедурным языкам можно отнести следующие:

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

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

Языки Ассемблера и Макроассемблера применяются системными программистами-профессионалами с целью использования всех возможностей оборудования ЭВМ и получения эффективной, как по времени выполнения, так и по потребному объему памяти, программы.

Язык программирования С был разработан в фирме Bell Laboratories в 1972 г. Денисом Ритчи и в последующем приобрел высокую популярность среди системных, а также (частично) среди прикладных программистов. Первоначально язык программирования С разработан для реализации ОС UNIX. В настоящее время этот язык реализован в рамках большинства ОС ЭВМ и особенно ПЭВМ. Язык программирования С имеет внутреннее единство, присущее обычно языкам «для любого человека», примерами которых могут служить языки Лисп, Паскаль, АПЛ. Одна из наиболее существенных особенностей языка С состоит в нивелировании различий между выражениями и операторами, что приближает его к функциональным языкам.

Язык программирования Basic (Beginner’s All-purpose Symbolic Code - многоцелевой язык символических инструкций для начинающих) представляет собой простой язык программирования, разработанный в 1964 г. для использования новичками. На ранних этапах своего развития Basic применялся только для обработки числовых величин; позднее он был расширен средствами обработки строк. В Basic’е широко используются разного рода умолчания, что считается плохим тоном в большинстве современных языков. Несмотря на это, Basic очень популярен, в особенности на ПЭВМ. Существует множество его диалектов, несовместимых между собой. Не без оснований этот язык иногда сравнивают с питоном, заглатывающим и переваривающим все новое, что появляется в других языках программирования. Поэтому Basic является одним из наиболее динамичных, а его уровень нельзя определить однозначно. Современные диалекты Basic’а весьма развиты и мало чем напоминают своего предка.

Язык Fortran был разработан в 1956 г. сотрудником фирмы IBM Дж. Бэкусом. В 1958 г. появилась версия Fortran-II, в 1966 г. Fortran 66. Он стал поистине «рабочей лошадью» научных работников и широко используется в настоящее время. Со временем появилась следующая версия языка Fortran-77, а в1988 г. - новые версии - Fortran 8х и Fortran 88.

Язык программирования Pascal - один из наиболее популярных, среди прикладных программистов, процедурных языков программирования. Он разработан в 1970 г. швейцарским специалистом в области вычислительной техники профессором Н. Виртом. Язык по замыслу автора предназначался для обучения программированию. Однако язык получился настолько удачным, что стал одним из основных инструментов прикладных, а зачастую и системных программистов при решении задач как вычислительного, так и информационно-логического характера.

Язык Ada разработан в 1979 г. ведущими специалистами в области программирования по заказу Министерства обороны США для использования во встроенных системах с управляющими ЭВМ, что требует режима реального времени. Язык Ada рассматривается как универсальный язык программирования.

Язык программирования APL (A Programming Language) был создан Иверсоном в 1969 г. и сразу получил широкое распространение. К числу его основных преимуществ относятся богатый набор мощных операторов, позволяющих работать с многомерными массивами как с единым целым, а также предоставление пользователю возможности определять собственные операторы.

Многими разработчиками программного обеспечения для ПЭВМ используется язык FORTH (четвертый), разработанный Ч. Муром в 1971 г. Программа на этом языке имеет вид строк в обратной польской записи. Основной структурой данных при организации вычислений является стек (магазин). Язык FORTH используется для решения задач информационно-логического характера.

Некогда популярный на больших ЭВМ язык PL/1 в настоящее время практически не используется. Ориентированным на обработку коммерческой информации является язык Cobol; язык SNOBOL предназначен для обработки текстовых данных. С целью обучения детей в 1967 г. разработан и используется по настоящее время язык LOGO. Специально для генерации отчетов служит язык программирования RPG (Report Program Generator). Интересные возможности предоставляет система GPSS, ориентированная на моделирование систем массового обслуживания. Представляет интерес параллельный язык OCCAM, используемый для программирования транспьютеров английской фирмы Inmos, которые могут выполнять роль акселераторов для ПЭВМ.

Функциональное программирование

Функциональное (аппликативное) программирование базируется на одной из первых алгоритмических систем - l-исчислении А. Черча, а также родственном ему исчислении комбинаторов, предложенном советским математиком еще в 1924 г. и развитом Х. Карри. роль основной конструкции в функциональных языках играет выражение. Любой аппликативный язык программирования включает следующие элементы:

1.  классы констант;

2.  набор базовых функций;

3.  правила построения новых функций из базовых;

4.  правила формирования выражений на основе вызовов функций.

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

1.  вызовы базовых функций заменяются соответствующими значениями;

2.  вызовы небазовых функций заменяются их телами, в которых параметры замещены аргументами.

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

Самым первым языком функционального программирования явился LISP (List Processing - обработка списков), разработанный и реализованный группой авторов под руководством Дж. Маккарти в Массачусетском технологическом институте в 1959 г. цель его создания состояла в удобстве обработки символьной информации. Существенная черта LISP’а - предельная унификация программных структур и структур данных. Этот язык рассматривается специалистами как основной язык программирования систем искусственного интеллекта. LISP непрерывно совершенствовался и сейчас существует множество развитых его версий с превосходной средой программирования. LISP послужил стартовой площадкой для разработки языков PLANNER и CONNIVER, которые используются для реализации процедурных моделей знаний.

Сейчас известно множество функциональных языков, значительно более мощных, чем LISP. Наиболее интересны и проработаны среди них ML (Milner Language) Милнера и Miranda Д. Тернера.

С аппликативными тесно связаны языки машин потока данных. Среди последних известность приобрели VALID, VAL, ID и LUCID. Разработка аппаратных и программных средств функционального программирования вошла составной частью в проекты ЭВМ пятого поколения.

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

Логическое программирование

В 1973 г. французским ученым А. Кольмероэ был создан язык программирования PROLOG (PROgramming in LOGic - программирование в терминах логики), первоначально предназначенный для работы с естественными языками. Ориентация PROLOG’а - «нетрадиционное» применение вычислительной техники: понимание естественного языка, базы знаний, экспертные системы и другие задачи, которые принято относить к проблематике искусственного интеллекта. Принципиальное отличие PROLOG’а от традиционных языков программирования заключается в том, что программа на PROLOG’е описывает не процедуру решения задачи, а логическую модель предметной области - некоторые факты относительно свойств предметной области и отношений между этими свойствами, а также правила вывода новых свойств и отношений из уже заданных. Таким образом, PROLOG - описательный язык.

С момента создания PROLOG’а большое число программистов выбрали PROLOG для использования при решении задач в различных областях символьных вычислений, включающих:

·  реляционные базы данных;

·  математическую логику;

·  решение абстрактных задач;

·  понимание естественного языка;

·  автоматизацию проектирования;

·  символьное решение уравнений;

·  анализ биохимических структур;

·  различные области искусственного интеллекта.

Задача написания программы на PROLOG’е не похожа на спецификацию алгоритма при программировании на традиционном языке программирования. Используемый в PROLOG’е подход состоит главным образом в описании известных фактов и отношений, касающихся решаемой задачи, а не в предписании последовательности шагов, выполняя которые ЭВМ решит задачу. При реализации программы на PROLOG’е последовательность вычислений, выполняемая ЭВМ, определяется частично логической декларативной семантикой PROLOG’а, частично новыми фактами, которые PROLOG может «вывести» из заданных ему фактов, и лишь отчасти управляющей информацией, явно заданной программистом.

Для ПЭВМ существует около пятнадцати реализаций PROLOG’а. компиляция предусматривается в следующих трех системах: Arity/Prolog 5.0 фирмы Arity, Turbo Prolog 2.0 фирмы Borland International и Prolog-2 английской компании Expert Systems. Остальные же системы обеспечивают только интерпретацию PROLOG-программ. В Венгрии разработан модульный вариант Prolog’а - М PROLOG.

Объектно-ориентированное программирование

Прототипом объектно-ориентированного программирования послужил ряд средств, содержащихся в языке SIMULA-67. Но оформилось оно в самостоятельный стиль программирования в связи с появлением языка SMALLTALK, первоначально предназначенного для реализации функций машинной графики и разработанного А. Кеем. Объектно-ориентированное программирование является методом программирования, имитирующим то, как человек выполняет какую-либо работу. Объектно-ориентированное программирование - результат естественной эволюции более ранних методологий программирования: оно более структурировано и более модульное и абстрактное, чем традиционное программирование.

Корни объектно-ориентированного программирования уходят в одну из ветвей логики, в которой первичным считается не отношение (как для логического программирования), а объект. По сравнению с исчислением предикатов объектно-ориентированные логические системы обладают более сложным синтаксисом и правилами вывода. С объектно-ориентированным программированием тесно связана теория акторов.

Основными особенностями объектно-ориентированных языков являются

1)   наличие активных объектов (акторов);

2)   формирование объектов путем наследования свойств;

3)   посылка сообщений от объекта к объекту как механизм организации вычислительного процесса.

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

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

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

Интерес к объектно-ориентированному программированию растет, что объясняется и что отчасти явилось причиной появления систем программирования Turbo Pascal 6.0 и 7.0, Turbo C++, а также BORLAND C++.

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

Сложные алгоритмы обработки в среде Microsoft Office выполняются с помощью программ, разработанных на языке Visual Basic и его диалектах:

Visual Basic for Applications - для электронных таблиц;

Word Basic - для текстового редактора;

Visual Basic - для баз данных.

Для создания эффективных запросов к базе данных используются также реляционные языки, в частности QBE (Query by Example), SQL (Structured Query Language).

Visual Basic for Applications (VBA) является общей языковой платформой для всех приложений (Excel 5.0, Word 6.0, Mail, Power Point). Visual Basic for Applications (VBA) - развитая система визуального программирования для создания прикладных программ в среде Microsoft Office.

SQL (Structured Query Language) - это язык программирования, который используется при работе с реляционными базами данных в современных СУБД (ORACLE, dBASE IY, dBASE Y, Paradox, Access и др.).

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

5.12 Задачи программирования

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

·  нисходящее программирование;

·  восходящее программирование;

·  технология пакетов прикладных программ.

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

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

В общем случае язык программирования - это фиксированная система обозначений для описания алгоритмов и структур данных. Такой язык имеет два «лица». Одно из них обращено к человеку, использующему язык для записи своих программ, а другое адресовано ЭВМ, которая должна понимать эти программы. Уже разработаны тысячи языков программирования. Существуют различные их классификации.

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

Контрольные вопросы

1.  Что понимают под термином "алгоритм"?

2.  Перечислите свойства алгоритма.

3.  Какие Вы знаете способы записи алгоритмов?

4.  Опишите словесно алгоритм, изображённый на рисунке 4.

5.  Изобразите в виде блок-схемы следующий алгоритм:

a)  Ввести значения t, z

b)  проверить условие t³z. Если условие выполняется, то перейти к шагу 4, иначе перейти к шагу 3.

c)  Вычислить значение p=t2+z2 и перейти к шагу 5.

d)  Вычислить значение p=t2-z2.

e)  Напечатать результат p.

f)  Прекратить вычисления.

6.  Что такое тело цикла?

7.  Назовите виды циклов.

8.  Что такое функция?

9.  Что такое рекурсия?

Литература

  , Информатика. Вводный курс: В 2-х ч. Пер. с нем. - М.: Мир, 1990.

  Богумирский пользователя ПЭВМ: В 2-х ч. Ч. 1. - Санкт-Петербург: Ассоциация OILCO, 19с. : ил.

  Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. - М.: Мир, 19с., ил.

  , Широчкин и ЭВМ. - К.: Техника, 19с.: ил. - (Б-ка инженера). Библиогр.: с. 338-343.

  , Трифонов программирования. М., 19с. с ил.

  Программирование на языке Пролог: Пер. с англ. - М.: Мир, 19с.

  Информатика: Учебник / Под ред. проф. . -М.: Финансы и статистика, 19с.: ил.

  TURBO PASСAL и объектно-ориентированное программирование. -М. Финансы и статистика, 19с.: ил.

  Логическое программирование в системе / Пер. с англ. и др. под ред. и -Буры. Изд. 2-ое; изд-во «Мир» М. 1979.

  Введение в программирование на языке Си: Пер. с англ. - М.: Радио и связь, 19с.: ил.

  Язык ассемблера для персонального компьютера фирмы IBM: Пер. с англ. - М. Мир, 19с.: ил.

  Психология программирования: Человеческие факторы в вычислительных и информационных системах. Пер. с англ. - М.: Радио и связь, 19с.: ил.