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

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

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

Частное учреждение образовательная организация высшего образования "Омская гуманитарная академия"

Контрольная работа

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

Выполнил(а): Учкунов М.Ш.

Направление подготовки:

Прикладная Информатика

Форма обучения: заочная

Омск - 2021

1. Алгоритмы и способы их описания

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

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

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

1. Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных.

2. Дискретность - процесс решения задачи по алгоритму разбит на отдельные действия.

3. Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются.

4. Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.

5. Выполнимость (эффективность) - результата алгоритма достигается за конечное число шагов.

6. Детерминированность (определенность) - алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.

7. Последовательность - порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.

3. Классы алгоритмов

алгоритм графический запись

1. вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;

2. информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).

Для задания алгоритма необходимо описать следующие его элементы:

1. набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

2. правило начала;

3. правило непосредственной переработки информации (описание последовательности действий);

4. правило окончания;

5. правило извлечения результатов.

4. Способы описания алгоритмов

Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).

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

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

Виды блоков

Правила создания блок - схем:

1. Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводится параллельно линиям рамки.

2. Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.

3. В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков.

4. Из блока (кроме логического) может выходить только одна линия.

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

6. Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.

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

5. Виды алгоритмов

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

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

1. «да» -- условие выполнено.

2. «нет» -- условие не выполнено.

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

6. Классификация алгоритмов

Как правило, основой для классификации алгоритмов является порядок выполнения команд (шагов). На основании данного признака специалисты в данной области выделяют три основных типа алгоритмов:

Линейные алгоритмы;

Алгоритмы с разветвлением;

Циклические алгоритмы.

Каждый из типов алгоритмов имеет свои особенности, которые будут рассмотрены далее.

Линейные алгоритмы

Линейным алгоритмом называется алгоритм, в котором последовательность записанных команд (действий) осуществляется строго согласно порядка их записи без каких-либо изменений. Как правило, такой алгоритм составляется из нескольких базовых структур следования.

Простым примером линейного алгоритма может выступить алгоритм утренних действия:

Проснуться;

Встать с постели;

Обуть тапочки;

Зайти в ванную;

Почистить зубы;

Вернуться в комнату;

Застелить постель;

Одеться;

Приготовить завтрак;

Позавтракать.

Т. е. действия выполнятся последовательно, одно за другим.

Пример записи линейного алгоритма представлен на рисунке

Рисунок 1

Для составления линейного алгоритма необходимо:

Определить тип и присвоить имена переменных;

Определить тип окончательного результата, присвоить имя этой переменной;

Определить и обозначить связь между исходными переменными и переменной результата; При необходимости ввода промежуточных переменных, определить их тип, присвоить имена, обозначить связь с исходными переменными и переменной результата;

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

Протестировать полученный алгоритм на предмет его корректного функционирования. ЗАМЕЧАНИЕ 1 Исключительно линейные алгоритмы применяются достаточно редко, обычно при расчете простых формул и решения простейших задач

Алгоритмы с разветвлением

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

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

Простым примером разветвляющегося алгоритма может выступить алгоритм выбора одежды перед выходом на улицу:

Есть ли на улице дождь?

Если дождь идет, то необходимо надеть плащ.

Если дождя нет, холодно на улице? Если холодно, надеть джемпер;

Если не холодно, надеть футболку.

ЗАМЕЧАНИЕ 2 В структуре такого алгоритма может быть любое количество условий. Таким образом, сначала проверяется выполнение логического выражения (Есть ли на улице дождь?), затем выполняется одно из условий в соответствии с выбором ответа.

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

Рисунок 2. Алгоритм с разветвлением

Для составления разветвляющегося алгоритма необходимо:

Установить какие могут быть варианты операций и их количество;

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

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

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

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

Стоит отметить, разветвляющиеся алгоритмы могут быть как полными, так и неполными. Пример таких алгоритмов представлен на рисунках 3-4.

Рисунок 3. Алгоритм с полным разветвлением

Рисунок 4. Алгоритм с неполным разветвлением

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

Циклические алгоритмы

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

Пример записи циклического алгоритма представлен на рисунке

Для составления циклического алгоритма необходимо:

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

Установить условие окончания выполнения заданного цикла;

Установить вводные переменные;

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

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

Заключение

Изучив материал про алгоритмы, мы уточнили смысл следующих понятий:

Алгоритм;

Алгоритмическое предписание;

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

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

Список литературы

1. Вирт Н. Алгоритмы и структуры данных. М.: ДМ К Пресс, 2011; Кнут Д. Искусство программирования. Т. 1. Основные алгоритмы = The Art of Computer Programming. V. 1. Fundamental Algorithms. 3-е изд. M.: Вильямс, 2006.

2. Кнут Д. Искусство программирования. Т. 1. Основные алгоритмы ; Хопкрофт Дж. Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002.

3. Аракелян Г. Математика и история золотого сечения. М.: Логос, 2014; Бадд Т. Объектно-ориентированное программирование в действии. СПб.: Питер, 2006.

4. Марков A.A. Нагорный H. M. Теория.

5. Информация взята с сайта биржи Автор24: https://spravochnick.ru/informatika/algoritmizaciya/tipy_algoritmov/. Взято со страницы: https://spravochnick.ru/informatika/algoritmizaciya/tipy_algoritmov/.

Размещено на Allbest.ru