Блок-схемный метод алгоритмизации

Лекция 14. Этапы решения задач на ЭВМ. Понятие алгоритма. Языки программирования.

Этапы решения задач на ЭВМ.

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

1) Постановка задачи. Определяются цели и условия решения задачи, раскрывается ее содержание, выявляются факторы, оказывающие влияние на ход вычислений или конечный результат;

2) Формализация. По результатам выяснения сущности задачи определяется объем и специфика исходных данных, вводится система условных обозначений, устанавливается принадлежность поставленной задачи к одному из известных классов задач и выбирается математический аппарат описания;

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

4) Составление алгоритма. Часто процесс решения задачи не удается получить в виде явной формулы. В этом случае метод решения задачи преобразуется в последовательность действий ЭВМ, называемой алгоритмом. Главное назначение алгоритма – точное и детальное описание процесса переработки исходных данных в результат;

5) Составление программы. Составленный алгоритм записывается на языке программирования, после чего программа компилируется в коды ЭВМ. В результате получается рабочая программа;

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

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

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

Понятие алгоритма является одним из основных понятий совре­менной информатики. Термин алгоритм (алгорифм) происходит от латинской формы имени среднеазиатского математика IX в. аль-Хорезми, который разработал правила выполнения четырех ариф­метических действий в десятичной системе счисления.

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

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

Правильно составленный алгоритм обладает рядом свойств:

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

2) Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Это свойство названо понятностью. Таким образом, при создании алгоритма необходимо учитывать возможности и способности исполнителей, на которых он рассчитан;

3) Алгоритм должен быть представлен в виде конечной последовательности шагов. Это свойство названо дискретностью;

4) Выполнения алгоритма должно завершаться после выполнения определенного числа шагов. Это свойство названо конечностью;

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

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

Блок-схемный метод алгоритмизации

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

Таблица 14.1.

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

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

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

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

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

Для примера на рис. 14.1 представлена блок-схема вычисления корней одного квадратного уравнения вида ах² + bх + с = 0. В блоке 1 задаем исходные данные, в блоках 2 и 3 вычисляется значение дискриминанта «дискр», в блоке 4 — значение вспомога­тельных переменных р и q. В блоке 5 проверяется значение дискриминанта: если оно меньше нуля, в блоках 6 и 7 вычисляются мо­дуль и аргумент комплексной пары корней «кор1» и «кор2»; если «дискр» больше или равен нулю, в блоке 8 вычисляются значения двух действительных корней, также обозначаемых «кор1» и «кор2». В блоке 9 в переменной «призн» сохраняется знак дискриминанта, который вместе с «кор1» и «кор2» выводится в блоке 10.

Рис. 14.1. Вычисление корней квадратного уравнения

В качестве другого примера на рис. 14.2 представлена блок-схе­ма поиска максимального числа из чисел a_i (i = 1, 2,..., п).

Здесь сначала вводятся две дополнительные переменные: т — значение максимального числа и i - порядковый номер (индекс) числа в последовательности (i = 1, 2,..., п). Присваивается т значе­ние «ноль», а i — значение 1 (блок 3).

В блоке 4 сравнивается текущее значение т с очередным чис­лом из заданной последовательности. Например, пусть в начале последовательности указаны а₁ = 3, а₂ = 6, а₃ = 2, ...

Рис. 14.2. Поиск максимального числа

При первом выполнении блока 4 проверяется условие а₁ > т (т. е. 3 > 0). В результате проверки переменной т будет присвоено значение а_i (т. е. т = 3). Далее зна­чение i увеличивается на единицу (блок 6). Если i не больше п (блок 7), снова выпол­няется блок 4. На втором шаге a_i = 6, т. е. a_i > т, и т примет значение 6. На третьем шаге а_i = 2 (a_i < т), и т сохранит значение 6. Как только i превысит число элементов последовательности (все числа просмотре­ны), выполнение алгоритма заканчивается, а переменная т сохраняет значение макси­мального числа последовательности.

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

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

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

Синтаксис языка — совокупность правил, определяющих допу­стимые конструкции (слова, предложения) языка.

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

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

■ на машинные, воспринимаемые аппаратной частью компью­тера (машинные коды);

■ машинно-ориентированные, структура операторов которых определяется форматами команд конкретной ЭВМ (мнемо­коды, автокоды, язык ассемблера);

■ процедурно-ориентированные, имеющие возможность описа­ния программы как совокупности процедур (подпрограмм) (Фортран, Бейсик, Паскаль и др.);

■ объектно-ориентированные, базирующиеся на объектной де­композиции предметной области программы (Delphi, Visual С++, Visual Basic и др.);

■ проблемно-ориентированные, предназначенные для решения задач определенного класса, например задач искусственного интеллекта (Пролог, Лисп и др.).

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

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

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

Трансляторы реализуются в виде компиляторов или интерпретаторов. С точки зрения выполнения работы компилятор и интерпретатор суще­ственно различаются.

Компилятор (англ. compiler — составитель) формирует полный текст программы в машинных кодах, лишь после этого она может быть выпол­нена.

Интерпретатор (англ. interpreter — истолкователь) последовательно преобразует каждый отдельный оператор входной программы в машин­ный код и сразу его выполняет.

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

Откомпилированные программы работают быстрее, но интерпретиру­емые проще исправлять и изменять.

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

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

Язык Фортран (Formula Translation — переводчик формул) — один из самых старых языков высокого уровня (первая версия была создана в 50-е гг. XX в.), активно используемый на персональных компьютерах. При­меняется главным образом при разработке прикладных систем, ориенти­рованных на научные исследования, автоматизацию проектирования и другие области, где уже накоплены обширные стандартные библиотеки программ.

Язык Бейсик (Beginners Allpurpose Symbolic Instruction Code, BASIC — многоцелевой язык символических команд для начинающих) разработан в начале 60-х гг. XX в. как простейший язык для обучения программиро­ванию. Благодаря своей простоте, минимальным требованиям к оператив­ной памяти получил широкое распространение как основной язык общения с микроЭВМ. В настоящее время Бейсик остается наиболее широко используемым в мире языком высокого уровня.

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

Язык Си, первоначально разработанный для реализации операционной системы Unix, послужил главным инструментом для создания многих операционных систем и программных продуктов. В этом языке имеются более гибкие средства для эффективного использования особенностей аппаратуры, чем, например, в Паскале. Благодаря этому порождаемые машинные программы, как правило, более компактны и работают быст­рее, чем программы, полученные Паскаль-трансляторами. Вместе с тем синтаксис языка Си менее прозрачен, чем у Паскаля, возможностей для внесения ошибок больше; чтение текстов программ требует определенно­го навыка. В связи с этим язык Си применяется главным образом для со­здания системных и прикладных программ, в которых скорость работы и объем памяти являются критическими параметрами.

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

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

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

Дальнейшим развитием технологий программирования, основан­ных на объектном подходе, стало визуальное программирование. Наиболее полное отражение концепция объектно-ориентированного программирования и визуального подхода к построению приложе­ний нашла в языках для разработки Windows-приложений: Visual Basic, Delphi, Visual С++, С++ Builder. Данные языки позволяют создавать программы с применением визуальных средств добавле­ния и настройки специальных библиотечных компонентов. Резуль­татом визуального проектирования является заготовка будущей программы, в которую уже внесены соответствующие коды.

Несмотря на идентичность идеологии, заложенной в Visual Basic, Delphi, Visual С++, С++ Builder, в их применении имеются отличия. Современные тенденции показывают, что Delphi ориентируется фирмой Inprise (прежнее название Borland) как средство создания полноценных распределенных корпоративных систем доступа к данным. Visual Basic (фирмы Microsoft) применяется в основном для создания приложений и расширений для готовых программных продуктов под Windows и Веб-приложения, a Visual С++ (Microsoft) и Borland C++ Builder использу­ются для разработки интернет-обозревателей, корпоративных приложе­ний и операционных систем.

Другим примером объектно-ориентированного языка может слу­жить созданный в 1990-х гг. на основе С++ язык программирова­ния Java (Джава, Ява). Разработанные с его помощью приложения

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

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

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

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