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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 14.1.

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

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

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

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

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

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

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

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

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

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

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

При первом выполнении блока 4 проверяется условие а1т (т. е. 30). В результате проверки переменной т будет присвоено значение аi (т. е. т = 3). Далее значение i увеличивается на единицу (блок 6). Если i не больше п (блок 7), снова выполняется блок 4. На втором шаге ai = 6, т. е. aiт, и т примет значение 6. На третьем шаге аi = 2 (aiт), и т сохранит значение 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 — обработка списков). В настоящее время имеется большое количество систем программирования на Лиспе, реализованных для компьютеров различных типов.

Статьи к прочтению:

Основы Программирования — #1 — Логика. Алгоритмы

Похожие статьи: