Средства представления алгоритмов

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

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

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

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

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

Визуальное представление алгоритмов

При проектировании визуальных алгоритмов используют специальные графические элементы, называемые графическими блоками, которые представ-лены в таблице. Существует Государственный стандарт (ГОСТ 19.002-80 и ГОСТ 19.003-80), определяющий правила выполнения схем и обозначения для отдельных операций.

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

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

Источник

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

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	10.11.2016
Размер файла	1,1 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://allbest.ru

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

ВВЕДЕНИЕ

алгоритм программа массив уравнение

Сегодня большинство людей считает, что алгоритмы используются только математиками и программистами, однако это совсем не так. Каждый из нас, начиная от агронома и заканчивая топ-менеджером, ежедневно сталкивается с алгоритмами. Данный факт обусловлен тем, что весь мир в настоящее время переживает эпоху глобальной информатизации. Современная цивилизация представляет собой цивилизацию алгоритмов, которые тесно связаны с любой человеческой деятельностью [14, с.6].

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

Сегодня большинство задач человек перекладывает на вычислительную технику. При этом компьютеру или какому-либо другому вычислительному устройству передается специальное предписание — последовательность действий, в результате которой должен быть получен необходимый человеку результат. Данное предписание называется программой. Оно должно очень точно отражать последовательность действий, выполняемых машиной. Для того чтобы человек мог объяснить машине последовательность действий, необходимых для решения той или иной задачи, были разработаны специальные языки описания.

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

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

Объектом исследования в данной работе является алгоритм.

Предмет исследования — формы и способы представления алгоритмов, способы записи алгоритмов.

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

Для достижения поставленной цели предстоит решить ряд задач:

— проанализировать литературу по заданной теме;

— дать понятие алгоритма;

— определить свойства алгоритма;

— изучить формы представления алгоритмов;

— изучить способы записи алгоритмов;

— привести примеры известных алгоритмов.

В качестве опорных источников при выполнении данной работы были использованы следующие материалы, которые наиболее полно раскрывают данную тему и содержат яркие примеры: М.П. Белов — «Основы алгоритмизации в информационных системах» и Т.А. Волосатова — «Информатика. Программирование на VBA. Учебное пособие для лабораторного практикума и подготовки к тестированию».

1. АЛГОРИТМ

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

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

Под алгоритмом принято понимать четкую конечную систему правил, определяющую последовательность действий, которая за конечное число шагов способна привести к достижению поставленной цели [11, с.10].

Сам термин «алгоритм» пошел от имени мыслителя Мухаммеда аль Хорезми, проживающего в средние века. Именно он является родоначальником алгебры — науки, в которой были сформулированы правила математических вычислений в позиционных системах счисления. В Европе эти правила получили название алгоритмов (от латинского написания имени аль Хорезми — «algoritmi»).

Исполнителем алгоритма является тот объект, для управления действиями которого этот алгоритм составлен. Чтобы исполнитель мог выполнить тот или иной алгоритм, он должен четко понимать все шаги алгоритма. Набор команд исполнителя, которые он способен понимать и выполнять, принято называть системой команд исполнителя [13, с.5].

Разработка алгоритма предполагает разбиение одной большой задачи на несколько мелких, более простых.

Из определения алгоритма формируются его свойства:

— результативность — в результате выполнения алгоритма должен быть получен успешный результат решения поставленной задачи, либо информация о том, что данный алгоритм не подходит для решения этой задачи;

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

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

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

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

— массовость — алгоритм должен разрабатываться для решения целого класса задач, которые отличаются только исходными данными;

— эффективность — время выполнения алгоритма должно быть сравнительно небольшим, при этом должен выбираться наиболее простой и короткий способ решения задачи [7, с.11-12].

1.2 Виды

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

В зависимости от цели и начальных условий существует несколько видов алгоритмов (см. рисунок 1):

Размещено на http://allbest.ru

Рисунок 1 — Виды алгоритмов

— механические (детерминированные) алгоритмы — алгоритмы, задающие выполняемые действия в единой достоверной последовательности;

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

В основе всех алгоритмов лежат универсальные способы принятия решений и логические функции, которые строятся по опыту решения предыдущих задач аналогичного типа [2, с.7-8].

Любой алгоритм разбивается на определенные шаги — алгоритмические конструкции. Наиболее распространенными являются следующие конструкции:

— следование — определяет линейные алгоритмы, определяющие последовательное выполнение шагов, независимо от исходных данных и промежуточных вычислений;

— ветвление — определяет алгоритмы ветвления, предполагающие выполнение того или иного действия в зависимости от какого-либо условия. Принято выделять полное и неполное ветвление. В первом случае алгоритм предусматривает все возможные варианты условия. На естественном языке это можно записать следующим образом: если условие выполняется, то необходимо запустить процесс 1, иначе — запустить процесс 2. Вариант неполного ветвления: если условие выполняется, то необходимо запустить вычислительный процесс. Кроме того, существуют алгоритмы, содержащие более двух ветвей в блоке ветвления;

— цикл — определяет циклические алгоритмы — это такие алгоритмы, в которых одни и те же операторы выполняются многократно. Выполнение цикла состоит из нескольких этапов:

o подготовка — на данном этапе происходит установка начального значения параметра цикла;

o тело цикла — непосредственное выполнение каких-либо действий;

o подготовка к следующему циклу — предполагает изменение значения параметра цикла;

o проверка условия — признак выхода из цикла.

Операторы цикла бывают нескольких видов:

o цикл с предусловием — проверка условия выполняется сразу же после установки значения параметра цикла;

o цикл с постусловием — проверка условия выполняется после прохода тела цикла. Такие циклы всегда отрабатывают как минимум один раз;

o цикл с параметром — цикл, в котором изначально задается число необходимых итераций [17, с. 7-9].

1.3 Характеристики

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

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

Размещено на http://allbest.ru

Рисунок 2 — Характеристики алгоритмов

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

Очень важное значение эта характеристика имеет при решении сложных задач, потому что ее изменение сильно влияет на время, затрачиваемое на выполнение алгоритма. Так, например, при зависимости (1)

увеличение производительности в 10 раз приводит к увеличению размерности задачи, решаемой за то же самое время, всего на 15%.

Другой тип характеристик алгоритма — объемные характеристики. Данные характеристики отвечают за информационную сложность. Эта сложность может быть связана с несколькими процессами:

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

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

Отдельно стоит выделить сложность структуры алгоритма — это характеристика, определяемая числом возможных путей, по которым может быть реализован алгоритм, с учетом сложности каждого отдельно взятого пути [3, с.9-10].

1.4 Роль алгоритма в построении программы

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

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

— математическая формализация — на данном этапе формируется математическая модель задачи, которая может быть передана компьютеру. Здесь важно четко определить все необходимые параметры, проанализировать их сущность и характер. Важно, чтобы модель адекватно отражала поставленную задачу и не была перегружена параметрами. На этом же этапе создается математическое описание модели при помощи формул, отражающих существующие взаимосвязи между параметрами. После получения модели предлагаются различные варианты решения задачи, оценивается их эффективность и сложность;

Размещено на http://allbest.ru

Рисунок 3 — Этапы решения задачи на компьютере

— построение алгоритма — в зависимости от выбранного варианта решения задачи, составляется алгоритм, четко описывающий процесс решения;

— составление программы на языке программирования — на данном этапе готовый алгоритм преобразуется в код программы. При этом можно выделить несколько стадий выполнения:

o выбор языка программирования;

o уточнение способов организации данных;

o запись алгоритма на выбранном языке программирования;

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

o трансляция исходного текста программы;

o выполнение программы с целью выявления логических ошибок;

o тестирование на контрольных примерах (контрольные примеры предполагают выполнение всех возможных путей алгоритма);

— проведение расчетов — данный этап заключается в исполнении программы и последующих расчетов для различных входных параметров;

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

— сопровождение программы — данный этап является оптимизационным и заключается в поддержке программы после сдачи в эксплуатацию. Здесь происходит устранение неисправностей, выявленных в процессе использования программы, добавление каких-либо новых функциональных возможностей, а также повышение удобства использования в соответствии с пожеланиями пользователей [7, с. 4-6].

1.5 Краткие выводы

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

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

— описание основных свойств алгоритма;

— виды алгоритмов (детерминированные и эвристические);

— характеристики, отражающие эффективность применения алгоритмов;

— роль алгоритма при написании программы.

2. ПРЕДСТАВЛЕНИЕ И ЗАПИСЬ АЛГОРИТМОВ

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

Для примера рассмотрим словесную форму алгоритма нахождения наибольшего общего делителя двух натуральных чисел А и В:

— проверить числа на равенство. Если они равны, в качестве ответа можно взять любое из этих чисел, если нет, то продолжить выполнение алгоритма;

— определить, какое число больше — А или В;

— заменить число с предыдущего шага модулем разности чисел А и В;

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

Недостатки словесного метода:

— полное описание сложных алгоритмов является достаточно объемным;

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

— при переходе к этапу программирования необходимо проводить дополнительную работу, которая заключается в формализации алгоритма [3, с.10-11].

2.2 Графический способ

Графический способ записи алгоритма отражает выполнение последовательности шагов в виде некоторого изображения. Подобную запись можно встретить на инструкциях по сборке чего-либо, на упаковках с едой и т.п. (см. рисунок 4) [13. с. 7].

Рисунок 4 — Графическая форма записи алгоритма

Частным (и наиболее популярным) графическим способом является блок-схема, где алгоритм изображается в виде функциональных блоков, логически связанных между собой. При этом каждому отдельному действию соответствует своя геометрическая фигура. Определение этих фигур можно найти в ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации». Наиболее распространенные символы приведены на рисунке 5 [2, с. 11]:

— «Начало алгоритма» и «Конец алгоритма» — применяются для обозначения начала, конца, а также прерывания процесса обработки данных или же исполнения программы;

Рисунок 5 — Операторы блок-схем

— «Ввод (вывод) данных» — применяется с целью преобразования данных в форму, которая пригодна для отображения или обработки результатов. Различным устройствам ввода/вывода компьютера соответствует различная геометрическая форма данного блока, при этом принято отображать тип используемого устройства или файла с данными, а также тип используемой информации и вид операции обмена;

— «Операция» — данный блок используется для обозначения некоторой последовательности действий, основной задачей которых является изменение значения, размещения или формы представления данных. В большинстве случаев несколько таких одинаковых блоков, идущих друг за другом, принято объединять в один;

— «Разветвление» — применяется с целью обозначения условных переходов. Внутри такого блока обязательно должно указываться условие, в зависимости от значения которого осуществляется переход по той или иной ветке. Кроме того, стрелки, которые выходят из данного блока, обязательно должны иметь метки с возможными вариантами ответа, например, «да» и «нет», учитывая при этом все возможные исходы;

— «Цикл» — применяется для выполнения операций, повторяющихся многократно. Внутри такого блока обязательно необходимо отражать параметр цикла — условие, по которому определяется выход из блока. Линии переходов в рамках данного блока отражают порядок действий. По стандарту их следует располагать сверху вниз и слева направо;

— «Ссылка» — данный оператор применяется в том случае, когда невозможно напрямую отразить переход к блоку, следующему в алгоритме, например, при разрыве страницы. Используя данный блок, важно давать ему метку, являющуюся ссылкой на следующий для исполнения блок;

— «Соединитель» — применяется в тех случаях, когда схема алгоритма представляет собой отдельные автономные части, либо в случаях, когда разработчик алгоритма старается избежать излишних пересечений в линиях перехода между блоками. Важно, чтобы блоки соединителей не нарушали структурность при отображении схем;

— «Комментарий» — отражает пояснения разработчика к блокам схемы. Не рекомендуется часто использовать комментарии, т.к. они сильно загромождают схему и делают ее менее наглядной [3, с. 11-14].

В промышленных системах применяются особые виды графических схем:

— диаграммы — описывают какие-либо зависимости входных и выходных переменных, отражают пошаговый процесс выполнения процесса и т.п.;

— схемы блокировки — служат для изображения взаимосвязанности процессов включения/выключения (см. рисунок 6);

Рисунок 6 — Схема блокировки

структурные схемы — отражают структуру и описывают функционирование непрерывных систем (см. рисунок 7);

Рисунок 7 — Структурная схема

— графы автоматов — описывают дискретные состояния системы, а также возможные переходы между ними вместе с изменяющимися параметрами и условиями переходов между состояниями (см. рисунок 8);

Рисунок 8 — Граф автомата

— сети Петри — представляют собой аппарат для моделирования дискретных динамических систем. При помощи сетей Петри можно определить какие именно действия происходят в системе, какие состояния может принимать система после этих действий и т.п. [5, с.123].

Пример сети Петри приведен на рисунке 9;

Рисунок 9 — Сеть Петри

схемы работы — схемы, описывающие процессы, которые протекают линейно и соответствуют системам управления (см. рисунок 10) [3, с.16-18].

Рисунок 10 — Схема работы

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

В качестве примера рассмотрим табличную форму записи алгоритма нахождения площади прямоугольника. При этом входными данными являются длины сторон, а результатом — величина площади (см. таблицу 1) [13, с.7].

Таблица 1 — Пример табличной записи алгоритма

Источник