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

Понятие алгоритма – одно из фундаментальных понятий информатики.

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

Название «алгоритм» произошло от латинской формы имени среднеазиатского математика IX века аль-Хорезми – Algorithmi, который сформулировал правила выполнения арифметических действий.

Любой алгоритм должен обладать следующими основными свойствами:

· понятностью – т.е. исполнитель алгоритма должен знать, как его исполнять;

· определенностью или детерминированностью – однозначностью получаемого результата при одних и тех же исходных данных;

· результативностью – обязательным получением некоторого искомого результата либо сигнала о том, что данный алгоритм неприменим для решения поставленной задачи;

· массовостью – возможностью получения искомого результата при различных исходных данных для некоторого класса задач;

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

Формы представления алгоритмов:

· содержательная (текстуальная) форма;

· графическая форма (схемы алгоритмов);

· представление алгоритмов на языках программирования ЭВМ;

· с помощью псевдокодов (алгоритмический язык).

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

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

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

Алгоритмические базовые структуры и типовые конструкции

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

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

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

Третья базовая структура повторение или цикл обеспечивает повторное выполнение или, другими словами, циклическую работу операторов, необходимую для большинства программ ЭВМ. Различают две разновидности этой структуры: цикл-пока, цикл-до и цикл-для. Оператор или группа операторов, повторяющаяся в цикле, называется телом цикла. Циклическая структура позволяет существенно сократить размер записи алгоритма, представить его компактно путем соответствующей организации повторения предписываемых действий. Естественно, что повторять какие-либо действия имеет смысл при различных значениях параметров, изменяемых при каждом новом выходе на повторение. Такие изменяемые параметры называются параметрами цикла. Для организации цикла необходимы управляющие операторы задания начального значения параметра цикла, изменения параметра цикла и проверки условия окончания цикла. Основное отличие структуры цикл-пока от структуры цикл-до заключается в том, что в первой структуре операторы тела цикла в зависимости от условия могут не выполняться совсем, тогда, как в структуре цикл-до тело цикла должно обязательно выполняться хотя бы один раз. Алгоритмы, имеющие в своем составе базовую структуру цикл, называются циклическими алгоритмам, а соответствующие им вычислительные процессы – циклическими вычислительными процессами.

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

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

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

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

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

Вопросы для самоконтроля

1. Дать определение алгоритма, указать и объяснить смысл его основных свойств. Привести примеры алгоритмов с нарушением того или иного свойства.

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

3. Как можно образовывать из трех базовых алгоритмических структур более сложные алгоритмические конструкции? Привести примеры.

Дата добавления: 2014-11-24; просмотров: 912; Нарушение авторских прав

Мы поможем в написании ваших работ!