Теория алгоритмов

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

Если подобного рода инструкции представить в некотором стандартном виде, удовлетворяющим определённым условиям, то получится алгоритм.

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

Свойства алгоритма:

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

· Детерминированность — система величин, получаемая на каждом шаге алгоритма, однозначно определяется величинами, полученными на предыдущих шагах.

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

· Результативность — если на некотором шаге преобразование системы величин неопределенно, то должно быть явно указано, что считать результатом работы алгоритма в таком случае.

· Массовость — исходные данные для работы алгоритма можно выбирать из некоторого потенциально бесконечного множества.

Для задания шагов в алгоритме обращаются к символьным языкам, наиболее распространёнными из которых являются:

· Формульное описание, предназначается для представления процесса решения несложных задач, базирующихся на локальных вычислениях;

· Задание алгоритмов в виде блок-схем, широко распространённое для представления большого числа логических условий;

· Словесное описание правил в виде фраз естественного языка с ограниченным синтаксисом.

Например, для выражения

алгоритм вычисления будет состоять из следующих шагов:

1.

2.

3.

4..

Естественно изображать алгоритмы в виде блок-схем, которые представляют собой графические представления последовательности действий. Блоки отражают содержание элементарного действия, а связывающие их линии — последовательность выполнения. Стандартными графическими изображениями являются: начало процесса, действия, которые следует выполнить, ввод/вывод информации, логический блок.

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

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

Дата добавления: 2014-01-20