Реферат Курсовая Конспект
Понятие алгоритма - Контрольная Работа, раздел Государство, КОНТРОЛЬНАЯ РАБОТА № 1 Под Алгоритмом, Как Правило, Понимается Точное Предписание, Которое Задает Вы...
|
Под алгоритмом, как правило, понимается точное предписание, которое задает вычислительный процесс, начинающийся из некоторой совокупности исходных данных и направленный на получение полностью определяемого исходными данными результата. Обосновывать принципы алгоритмизации целесообразно в рамках анализа свойств алгоритмов. Выделяют следующие свойства алгоритмов.
1. Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.
2. Детерминированность – свойство, означающее, что на каждом шаге любой полученный результат определяется результатами, полученными на предшествующих шагах.
3. Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.
4. Направленность – свойство, обуславливающее необходимость указания, что является результатом того шага, на котором нельзя выполнить определенную в нем операцию.
5. Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.
Одной и той же задаче может соответствовать множество алгоритмов, поэтому, для обоснования выбора одного из них для решения конкретной задачи, применяют совокупность показателей, основными из которых являются следующие.
1. Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.
2. Емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма.
3. Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.
Для представления алгоритма используют различные средства, в том числе граф-схемы алгоритмов, каждая из которых представляет собой граф. Понятие элементарного графа дополнено введением надстройки, которая задает вычисления, каждому из которых соответствует путь в этом графе и последовательность меток узлов, лежащих на этом пути. Узлы графа, с помощью введения типизации, интерпретируются как действия, а дуги задают порядок передачи управления. Для каждого алгоритма существует одна начальная дуга и одна или множество конечных. В табл.1 представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».
Таблица 1
Символ | название | интерпретация |
данные | данные, носитель данных неопределен | |
процесс | функция обработки данных любого вида (выполнение определенной операции или группы операций, приводящие к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться) | |
предопределенный процесс | предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле) | |
Подготовка | модификация команды или группы команд с целью воздействия на некоторую последующую функцию | |
Решение | решение или функция переключательного типа, имеющая один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа; соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути | |
граница цикла | начало и конец цикла; обе части имеют один и тот же идентификатор; условия инициализации, приращения, завершения, и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие | |
соединитель | выход в часть схемы и вход из другой части этой схемы; используется для обрыва линии и продолжения ее в другом месте; соответствующие символы-соединители должны содержать одно и то же уникальное обозначение | |
терминатор | выход во внешнюю среду и вход из внешней среды (начало и конец программы) | |
линия | поток данных или управления; для направлений справа-налево и снизу-вверх добавляются стрелки | |
пунктирная линия | используется для обведения аннотируемого участка | |
комментарий | пояснительные записи и примечания | |
пропуск | пропуск символа или группы символов, в которых не определены ни тип, ни число символов; используется только в символах линии или между ними; служит для отображения общих решений с неизвестным числом повторений |
Приведем основные свойства граф-схем.
1. Графическое представление.
2. Поддержка описания управляющей части алгоритма.
3. Возможность реализации синтаксического контроля.
4. Возможность проверки управляющей части алгоритма.
5. Отсутствие возможности верификации информационной части.
Необходимо отметить, что по граф-схеме алгоритма можно произвести оценку таких характеристик алгоритма, как временная сложность и сложность описания, однако, возможность оценки емкостной сложности отсутствует. На рис. 1 представлен пример граф-схемы алгоритма.
– Конец работы –
Эта тема принадлежит разделу:
На сайте allrefs.net читайте: КОНТРОЛЬНАЯ РАБОТА № 1...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Понятие алгоритма
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов