Основные свойства и способы представления алгоритма
Любой алгоритм должен обладать следующими свойствами:
• определенностью –за конечное число шагов либо должен быть получен результат, либо доказано его отсутствие;
• результативностью– обязательным получением некоторого результата (числа, таблицы, текста, звука, изображения и т. д.) или сигнала о том, что данный алгоритм неприменим для решения поставленной задачи;
• массовостью– возможностью получения результата при различных исходных данных для некоторого класса сходных задач;
• формальностью– отвлечение от содержания поставленной задачи и строгое выполнение некоторого правила, инструкции;
• дискретностью— возможностью разбиения алгоритма на отдельные элементарные действия.
Существуют следующие формы представления алгоритма:
• словесная (вербальная) на неформальном языке;
• на языках программирования;
Словесная формапредставления алгоритма имеет ряд недостатков. Для достаточно сложных алгоритмов описание становится слишком громоздким и не является наглядным. Эта форма представления обычно используется лишь на начальных стадиях разработки алгоритма.
Пример словесной формы описания алгоритма: Чтобы перейти улицу, нужно посмотреть налево, убедиться в отсутствии приближающегося транспорта, дойти до середины улицы, посмотреть направо, убедиться в отсутствии близко идущего транспорта, продолжить движение через улицу. При наличии движущихся транспортных средств нужно ждать, когда транспорт проедет.
Алгоритм, записанный на языке программирования, называется программой.
Графическая формапредставления алгоритмов является более наглядной и строгой. Алгоритм изображается в виде последовательности связанных между собой блоков, каждый из которых соответствует выполнению одного или нескольких операторов. Такое графическое представление называется блок-схемой алгоритма.
Условные графические обозначения символов, используемых для составления блок-схемы алгоритма, стандартизированы.
Для записи алгоритма существует общая методика:
— каждый алгоритм должен иметь имя, которое раскрывает его смысл;
— необходимо обозначить начало и конец алгоритма;
— описать входные и выходные данные;
— указать команды, которые позволяют выполнять определенные действия над выделенными данными.
БЛОК-СХЕМЫ АЛГОРИТМОВ
Среди универсальных форм представления или записи алгоритмов можно выделить так называемые блок-схемы алгоритмов. Универсальность этой формы обусловлена тем, что в ней заранее не определяются абстракции, которые могут специфицироваться в блоках даже с применением обычного разговорного языка. Блоки являются всего лишь шаблоном для описания действий в процессе решения задачи, а связи между блоками определяют последовательность этих действий.
Такая форма часто используется в профессиональной среде программистов. Она позволяет с достаточной степенью свободы описывать решения, получаемые в процессе нисходящего проектирования алгоритмов и соответствующих им программ, абстрагируясь от средств, предоставляемых конкретным языком программирования. Палитра ее средств (допустимых шаблонов) в этом случае может быть достаточно широка, однако для записи алгоритмов необходимым является минимальное подмножество средств, т.е. только два вида блоков — операторный и условный.
Операторный блок – это прямоугольник, в который вписывается некоторое действие или выражение. Этот блок может иметь несколько входов и только один выход, что обеспечивает однозначность в определении последовательности выполняемых действий. Исключение составляют начальный и конечный блоки. Первый не имеет входов, второй – выхода.
Условный блок обозначается ромбом, в который вписывается некоторое условие. Поскольку результатом проверки условия может быть либо “да”, либо “нет” (“истина” или “ложь”, “0” или “1”), блок имеет два соответствующих этим ответам выхода.
Если операторный или условный блоки имеют более одного входа, то изображение входов совмещается. На связях, определяющих последовательность выполнения блоков, стрелки не обязательны, если их направление соответствует продвижению “сверху-вниз” и “слева-направо”. Ограничения на геометрические размеры блоков в этом случае не вводятся.
Такая форма представления алгоритмов очень удобна в тех случаях, когда рассматриваются верхние уровни в иерархической структуре процесса проектирования программ и даже на нижних уровнях, если по каким-то причинам не определены средства их описания. Кроме того, блок-схемы наиболее удобны для записи алгоритмов на начальных стадиях обучения программированию.
ОСНОВНЫЕ БЛОКИ БЛОК — СХЕМЫ
Рис.1. Основные блоки блок – схемы
Рис.1. — Основные блоки блок – схемы
Отдельные блоки алгоритмов соединяются между собой линиями потоков, которые проводятся параллельно внешней рамке чертежа. Направления линий потока помечаются стрелкой.
«Процесс» (этап вычисления) изображается прямоугольником, внутри которого записывается набор действий (блок оператора присваивания). Ромбом изображается «решение», внутри которого осуществляется проверка условия (логический блок). Ввод исходных данных изображается параллелограммом, внутри которого пишется слово «ввод» и перечисляются переменные, подлежащие вводу.
Представление алгоритма в виде блок-схемы является промежуточным, так как алгоритм в таком виде не может быть непосредственно выполнен компьютером, но помогает пользователю при создании (написании) программы для ПК.
Использование блок-схем дает возможность:
• наглядно отобразить базовые конструкции алгоритма;
• сосредоточить внимание на структуре алгоритма, а не на синтаксисе языка;
• анализировать логическую структуру алгоритма;
• преобразовывать алгоритм методом укрупнения (сведения к единому блоку) или детализации – разбиения на ряд блоков;
• использовать принцип блочности при коллективном решении сложной задачи;
• осуществить быструю проверку разработанного алгоритма (на уровне идеи);
• разобрать большее число учебных задач.
Составление блок-схемы алгоритма является важным и в большинстве случаев необходимым этапом решения сложной и большой задачи на ЭВМ, значительно облегчающим процесс составления программ.
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.
Папиллярные узоры пальцев рук — маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.
Источник
3. Формы представления алгоритмов
Чтобы довести алгоритмы до пользователя, в зависимости от их назначения они должны быть формализованы по некоторым правилам (соглашениям) посредством конкретных изобразительных средств. При этом существует множество способов, отличающихся по простоте, наглядности, компактности, степени формализации, ориентации на машинную реализацию и другим показателям. Наибольшее распространение получили следующие виды записи: словесная, формульно-словесная, блок-схемная, табличная, программы для микрокалькуляторов (МК), язык операторных схем и языки программирования.
Словесная запись. Самая распространенная форма представления алгоритмов, адресуемых человеку, – обычная словесная запись. При этом содержание последовательных этапов вычислений задается в произвольной форме на естественном языке, но с тщательно отобранным набором слов и фраз, не допускающим повторений, двусмысленностей, синонимов, лишних слов. Недостаток словесного способа заключается в отсутствии более или менее строгой формализации и наглядности вычислительного процесса. Вместе с тем с его помощью могут быть описаны любые алгоритмы, в том числе и вычислительные.
Например, если предположить, что правила арифметических операций и действия извлечения квадратного корня являются элементарными, то алгоритм вычисления значения у по формуле:
может иметь такой вид:
1. Умножить x на 3
2. Из результата первого действия извлечь квадратный корень
3. К результату второго действия прибавить 1
4. Умножить x на x
5. Из результата четвертого действия вычесть 3
6. Результат пятого действия разделить на результат третьего действия, полученный результат считать значением y.
Формульно-словесная запись. Этот способ основан на задании предписаний о выполнении конкретных действий в определенней последовательности с использованием математических формул и словесных пояснений. Формулы в сочетании с правилами их написания представляют собой, по существу, своеобразный алгоритмический язык, применяемый, как правило, для задания вычислительных алгоритмов. Этот способ общепринят при описании математических выкладок, доказательств теорем.
При этом способе записи алгоритма достигается любая степень детализации вычислительного процесса. Он более компактен и нагляден по сравнению со словесным.
Табличная запись (решающие таблицы) – весьма удобный способ. Существует несколько типов таблиц. Два простейших из них выглядят следующим образом. Первый обычно используют при организации вычислений по формуле с пооперационной регистрацией промежуточных результатов. Разбиение ее на последовательность элементарных действий и дает последовательность предписаний. Подобная запись алгоритма вычисления объема усеченного конуса представлена в таблице.
Например, выражение 
задает объем усеченного конуса. Здесь Н — высота усеченного конуса, R и r – радиусы соответственно нижнего и верхнего оснований.
Такая форма цeлeсообразна прежде всего тогда, когда требуется вычислить несколько значений одного выражения для различных значений входящих величин.
В 
торой тип – решающая таблица. В простейшем случае она включает четыре части: перечень и указатель условий, перечень и указатель действий. Ее структура отражена на рисунке.
Перечень условий содержит все условия, а перечень действий – все действия, проверка и выполнение которых необходимы в процессе решения задачи. Они располагаются один за другим, причем в строке записывается лишь одно условие или действие. Правая часть делится на несколько столбцов. Содержимое каждого из них составляет одно правило, определяющее, какие условия следует проверять и какие действия в зависимости от результатов проверки в дальнейшем нужно произвести. Правило представляется с помощью специальных символов. Когда условие входит в него как элемент, на пересечении строки и столбца ставится либо Y (YES), либо N (NО). Первое означает, что оно должно быть выполнено, второе – не должно. Если условие не учитывается правилом, то в соответствующей позиции делается прочерк ( – ). Когда правило требует выполнения некоторого действия, на пересечении соответствующих строки и столбца помещается символ Х. В случае отсутствия действия позиция остается незаполненной.
Если формулировка условий такова, что возможны лишь два ответа – «да» и «нет», таблицы называются таблицами с ограниченными входами. Если же предполагаемых ответов несколько, удобнее пользоваться таблицами с расширенными входами. При этом простые условия записываются так же, как в таблицах первого вида, начало сложного условия – в перечне условий, а его продолжение распределяется между столбцами указателя условий.
Блок-схемы. Записи алгоритма на формальных языках часто предшествует его не вполне формальное описание. Языки, используемые для такого описания, называются не вполне формализованными. К ним относятся так называемые блок-схемы и применяемые программистом содержательные обозначения,
Блок-схема представляет собой графическое изображение алгоритма, при котором он расчленен на отдельные укрупненные части – «блоки», которые снабжены содержательными обозначениями и связаны между собой специальными знаками – линиями со стрелками, указывающими последовательность выполнения блоков. Эти линии могут быть снабжены надписями, определяющими условия, при которых реализуется данная последовательность выполнения. Блоки изображаются в виде прямоугольников, ромбов и т. п.
Другими словами, блок-схемой называется графическое изображение алгоритма, дополненное элементами словесной записи, в котором каждый этап процесса переработки данных представляется в виде геометрических фигур (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций (отображаемых функций). Условные обозначения, используемые для составления блок-схем, принято называть символами. Перечень символов, их форма, размеры и отображаемые ими функции определяются ГОСТ 19.003 – 80 «Схемы алгоритмов и программ. Обозначения условные графические», а правила оформления схем – ГОСТ 19.002 – 80 «Схемы алгоритмов и программ. Правила выполнения».
Блок-схема является исключительно наглядным и простым способом представления алгоритма. При этом не делается никаких ограничений степени детализации в его изображении. Если блок-схема получается очень сложной и теряет свойство иллюстративности, вначале составляют укрупненную блок-схему всего вычислительного процесса, а затем каждый ее блок представляют в виде отдельной блок-схемы вычислений.
Для блок-схем обязательны два правила.
1. Каждый блок имеет только один вход, и выполнение описанных в нем действий всегда начинается с первого. Входить в середину блока, минуя часть вычислений, нельзя.
2. Установлена следующая последовательность:
– первым выполняется блок, к которому ведет стрелка от блока «начало»;
– затем выполняется преемник этого блока, указанный стрелкой, исходящей из него; если преемников несколько, то из блоков должно выходить несколько стрелок и на каждой из них дается условие, при выполнении которого вычислительный процесс будет продолжен по этой стрелке;
– завершается вычислительный процесс блоком, от которого идет стрелка к блоку «конец».
По связи между блоками выделяются три существенно отличных типа. К первому относятся равного рода линейные блоки. Характерная их особенность – наличие только одного блока-преемника. Их обычно изображают как прямоугольник с одним входом и одним выходом. Этот элемент блок-схемы называют также элементом общей обработки (или арифметическим). В виде линейных блоков, как правило, графически представляются арифметические предписания,
Второй тип объединяет различные блоки условий. У каждого из них – не менее двух преемников. Они имеют форму ромба, одну вершину которого использует для обозначения входа, а остальные две или три – выхода из блока. Этот элемент называют также элементом принятия решения (или логическим). Так изображаются преимущественно логические предписания, применяемые для организации разветвлений.
Третий тип – вспомогательный. Он не описывает вычислительный процесс, а служит для указания мест разрыва связей между блоками.
Операторные схемы записи алгоритмов. В настоящее время также широко используются логические или операторные схемы алгоритмов. Операторная схема алгоритма представляет собой последовательность операторов, каждый из которых изображает более или менее крупную группу элементарных операций. Такая запись достаточно наглядно отражает логическую структуру алгоритма и позволяет при введении дополнительных требований и ограничений применить формальные методы для его анализа и преобразований.
В 1953 г. известный математик А.А.Ляпунов ввел в теорию программирования понятие оператора, пользуясь которым можно переходить от алгоритма, представляющего некоторый процесс, к программе ЭВМ. Первоначально операторный метод применялся на этапе программирования и алгоритмизации.
Операторами называются описания функционально однородных этапов изучаемого процесса. Операторная схема – это аналитическая форма представления алгоритма с помощью операторов, описывающих содержание автономных этапов вычислительного процесса, выделенных при решении задачи. Аналогично тому, как это делается при составлении блок-схем, алгоритм разбивается на части (участки), каждая из которых реализуется посредством определенного оператора.
При построении операторных схем в зависимости от своего назначения операторы делятся на: действующие (или арифметические), логические и варьирующие. Арифметические операторы или операторы счета обозначают действия, связанные с вычислениями по заданной группе формул. Действующие (арифметические) операторы определяют изменения, происходящие в объектах. Они описывают участки, включающие вычисления с помощью арифметических операций. Существенным свойством арифметических операторов является то, что после выполнения этого оператора независимо от результатов расчета происходит переход к выполнению следующего за ним (правого) в операторной схеме оператора и только к нему.
Логические операторы представляет собой описание условий, от которых зависит направление процесса. Сфера их действия – участки вычислений, предназначенные для проверки некоторых условий, выполнение которых обеспечивает переход от одного этапа переработки данных к другому. Варьирующие операторы предусматривают изменения вспомогательных величин, называемых параметрами.
Языки программирования. Рассмотренные способы представления алгоритма широко применяются в практике программирования, особенно на начальных этапах разработки программ. Изобразительным средством, служащим для непосредственной реализации алгоритма на ЭВМ, является язык программирования.
Понимание алгоритма как системы правил или предписаний определяет использование для его представления некоторого языка, на котором эти правила формулируются. Этот язык должен быть таким, чтобы правила, сформулированные с его помощью, обладали ранее перечисленными свойствами, т.е. составляли алгоритм.
Для записи алгоритма применяют языки, смысл фразы в которых однозначно определяется ее формой. Такие языки называют формальными. К формальным языкам относятся алгоритмические языки машин – коды. Простейшим языком программирования является язык команд конкретной ЭВМ, или машинный. Однако запись на нем получается труднопонимаемой, так как представляет собой последовательность команд, каждая из которых выражена определенным набором цифр.
Команда – это инструкция, поданная в форме, позволяющей ввести ее в машину, и регулирующая действия ЭВМ в течение некоторого времени. Каждая команда – это элементарная часть процесса обработки информации, называемая машинной операцией. Исходной информацией обычно служит набор конкретных значений, называемых исходными данными. В команде в общем случае должны быть указаны вид действия (код операции), место хранения в машине (адрес) исходной информации, над которой производится операция, адрес результата, а также следующая команда.
Используя систему команд, программист может описать ход всего процесса вычислений, т.е. правила, по которым протекает вычислительный процесс, обладающие свойствами детерминированности, массовости и результативности, – алгоритм решения задачи.
Знаковые системы, применяющиеся для описания алгоритма решения задачи на ЭВМ, называют языками программирования. Наибольшее распространение получили формальные алгоритмические языки программирования, к которым относятся:
а) алгоритмические языки машин;
б) машинно-ориентированные алгоритмические языки;
в) проблемно-ориентированные алгоритмические языки;
г) универсальные алгоритмические языки.
Каждый алгоритмический язык имеет собственный алфавит, синтаксис и семантику.
Алфавит – это набор основных символов. Любая запись выполняется с использованием только этих символов.
Синтаксис – совокупность правил, обусловливающих их последовательность, т.е. характер допустимых конструкций.
Семантика – система истолкования отдельных конструкций языка и целых фраз. Она позволяет однозначно воспроизвести процесс переработки данных, который предусмотрен алгоритмом, записанным на алгоритмическом языке.
Источник
