Geum.ru

Понятие, свойства и способы описания алгоритма

Вид материалаДокументы
Подобный материал:
Понятие, свойства и способы описания алгоритма


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

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

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

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

Классическим примером словесного описания алгоритма является предложенный древнегреческим математиком Евклидом способ вычисления наибольшего общего делителя (НОД) двух натуральных чисел (А и В), включающий описанную ниже последовательность элементарных шагов, каждый из которых предписывает выполнение некоторых действий:


1. Обозначить первое число буквой А, второе - буквой В. Сравнить А и В.

2. Если А = В, то принять D = А и перейти к п. 6 алгоритма, иначе перейти к п. 3.

3. Если А <В, то принять D=А и М= В, иначе D=В и М=А. Перейти к п. 4.

4. Разделить М на D, остаток обозначить R, перейти к п. 5.

5. Если R = D, то перейти к п. 6, иначе присвоить М = D, D = R и перейти к п.4.

6. D есть искомое число. Закончить вычисления.


Здесь алгоритм словесно описан предложениями естественного языка. Объектами его обработки являются числа, обозначенные буквами. Подставив конкретные числовые значения, например 80 и 28, можно проверить его «работу»:

1. Полагаем А = 80 и В = 28.

2. Так как А ≠ В, то перейдем к п. 3 алгоритма.

3. Проверяем условие А < В. Так как ответ «нет», то присваиваем D=28 и М=80.

4. Делим 80 на 28. Частное равно 2, остаток R = 24.

5. Проверяем условие R = D. Ответ «нет», присваиваем М = 28, D = 24 и переходим к п. 4 алгоритма.

6. 28 делим на 24. Частное = 1, остаток R = 4.

7. Проверяем условие R = D. Ответ «нет», присваиваем М = 24, D=4 и переходим к п. 4 алгоритма.

8. 24 делим на 4. Частное = 6, остаток R = О.

9. Проверяем условие R = D. Ответ«да», переходим к п. 6 алгоритма.

10. НОД чисел 80 и 28 равен 4. Закончить вычисления.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из блока проверки условия может выходить два или три информационных потока, что отличает его от других блочных символов, имеющих не более одного выхода. Выходящие из блока линии должны снабжаться пояснениями о направлениях исполнения алгоритма при выполнении или невыполнении приведенного условия (например, «да», «нет», «<0», «=0», «>0», «+», «–» или др.).

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

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

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

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

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

Линии по отношению к блокам могут быть входящими и выходящи. Количество входящих линий для всех блоков не ограничено – их может быть одна, две, три и более. Выходящая же линия для большинства блоков может быть только одна (исключение – блоки проверки условия).

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

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

Алгоритмы целесообразно разрабатывать поэтапно (по шагам).

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

∆ все линии не должны иметь разрывов, все линии, должны быть замкнутыми.

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

∆ Не допускается передача управления в никуда. «Источник» передачи управления и «получатель» должны быть четко обозначены.