Способы описания алгоритмов.

Тема 2. Этапы построения алгоритма.

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

Алгоритмы и их свойства.

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

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

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

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

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

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

Способы описания алгоритмов.

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

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

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки дан­ных и задается в произвольном изложении на естественном языке.

Пример 1. Записать алгоритм нахождения наибольшего обще­го делителя двух натуральных чисел (n и m) на естественном языке. При таком словесном способе содержание алгоритма может быть следующим:

1) если числа равны, то необходимо взять любое из них в качест­ве ответа, в противном случае — продолжить выполнение алгоритма;

2) определить большее из чисел;

3) заменить большее число разностью большего и меньшего чисел;

4) повторить алгоритм сначала.

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

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

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

Язык графических символов. Для изображения структур алгоритмов используется совокупность блочных символов (блоков), соединяемых линиями передач управления. Такое изображение называется методом блок-схем. Как и псевдо­код, метод блок-схем можно применить на любом уровне абстракции. Поскольку алгоритмы воспринимаются в первую очередь визуально, их следует изображать таким образом, чтобы их структура выглядела четко и выразительно. Крат­кость, выразительность и планомерность при проектировании позволяют создавать схемы алгоритмов высокого качества.

В схеме алгоритма каждому типу действий (вводу исход­ных данных, вычислению значений выражений, проверке ус­ловий, управлению повторением действий, окончанию обра­ботки и т. п.) соответствует геометрическая фигура, пред­ставленная в виде блочного символа (блока), называемого символом действия. Символы действия соединяются линиями переходов, определяющими очередность выполнения дейст­вий. Форма символов установлена ГОСТ 19.003—80, а прави­ла составления схем алгоритмов — ГОСТ 19.002—80.

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

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

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

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

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

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

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

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

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

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

 

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

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

 

 

Поделиться:

Воспользуйтесь поиском по сайту: