Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

1. Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.

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

3. Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.

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

5. Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.

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

1. Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.

2. Емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма.

3. Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.

Для представления алгоритма используют различные средства, в том числе граф-схемы алгоритмов, каждая из которых представляет собой граф. Понятие элементарного графа дополнено введением надстройки, которая задает вычисления, каждому из которых соответствует путь в этом графе и последовательность меток узлов, лежащих на этом пути. Узлы графа, с помощью введения типизации, интерпретируются как действия, а дуги задают порядок передачи управления. Для каждого алгоритма существует одна начальная дуга и одна или множество конечных. В табл.1 представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

Таблица 1

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

Приведем основные свойства граф-схем.

1. Графическое представление.

2. Поддержка описания управляющей части алгоритма.

3. Возможность реализации синтаксического контроля.

4. Возможность проверки управляющей части алгоритма.

5. Отсутствие возможности верификации информационной части.

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