Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Линейная алгоритмическая конструкция)

Содержание:

Введение

Я выбрал эту тему, потому что она актуальна и представляет научный и практический интерес.

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

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

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

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

Глава 1. Понятие алгоритма и его свойства

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

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

Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными аббасидским математиком Муха́ммад ибн Муса́ аль-Хорезми́. Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

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

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

Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.

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

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

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

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

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

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

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

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

Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

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

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

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

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем.

Блок, характеризующий начало/конец алгоритма (для

Начало

Конец

подпрограмм - вызов/возврат):

<Действие>

Блок — процесс, предназначенный для описания

отдельных действий:

Блок — предопределенный процесс, предназначенный для обращения к _______________________________________________________________________________________________________________________________вспомогательным алгоритмам (подпрограммам):

Блок — ввода/вывода с неопределенного носителя:

Блок - ввод с клавиатуры:

Блок — вывод на монитор:

Блок — вывод на печатающее устройство:

Блок — решение (проверка условия или условный блок):

Нет Да

<тело цикла>

Блок, описывающий цикл с параметром:

Блок — границы цикла, описывающий циклические

<тело цикла>

процессы типа: «цикл с предусловием», «цикл

с постусловием»:

Соединительные блоки:

Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем она настолько достаточна, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования.

Программа — описание структуры алгоритма на языке алгоритмического программирования.

Глава 3. Основные алгоритмические конструкции

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

3.1 Линейная алгоритмическая конструкция

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

Линейные вычислительные процессы имеют место, например, при вычислении арифметических выражений, когда имеются конкретные числовые данные и над ними выполняются соответствующие условию задачи действия. На рисунке 1 показан пример линейного алгоритма, определяющего процесс вычисления арифметического выражения у=(b²-ас):(а+с).

Рисунок 1 – Линейный алгоритм

3.2 Разветвляющаяся алгоритмическая конструкция

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

Условие

Действие 2

Действие 1

Ложь (Нет) Истина (Да)

Рисунок 2 - Полное ветвление

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

Условие

Действия

Истина (Да)

Ложь (Нет)

Рисунок 3 - Неполное ветвление

В зависимости от типа и числа проверяемых условий различают:

- ветвление с простым условием (условие - выражение отношения);

- ветвление с составным условием (условие - логическое выражение);

- сложное ветвление (несколько условий).

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

3.3 Алгоритмическая конструкция «Цикл»

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

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

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

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

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

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

Все циклические процессы по признаку определения количества повторений разделяются на два класса.

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

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

На приведенных ниже рисунках показаны примеры циклических процессов.

Рисунок 4 - Блок-схема цикла с предусловием

Рисунок 5 - Блок-схема цикла с постусловием

Заключение

Использовав специальную литературу по теме моей курсовой работы «Основные структуры алгоритмических конструкций: сравнительный анализ и примеры их использования», проанализировав дополнительные материалы, основательно разобрав каждый её пункт, я пришёл к выводу, что уровень внедрение автоматизации на Земле растет с каждым годом. Она была присуща человеку с момента его зарождения, однако бурный скачок состоялся во времена научно-технической революции двадцатого столетия.

Сегодня любое предприятие связано с огромными объёмами информации, которые нужно оперативно и должным образом обрабатывать. Количество информации варьируется от размера конкретного предприятия и вида деятельности. Основным средством помощи человеку в наши дни является ЭВМ, профессионально разработанная информационная система значительно облегчает жизнь людям, ответственным за подобную работу. Но всё же стоит учитывать, что сама информационная система вторична, прежде чем приступать к реализации этой системы, должна быть разработана система, способная качественно управлять спроектированной информационной системой.

Библиография

Алгоритмы. Построение и анализ. Изд. Вильямс. Автор: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. 2005 год.

Алгоритмы и структуры данных. А.Вирт. 1989 год.

Основы алгоритмизации и программирования : учебное пособие / Г.

Р. Кадырова. – Ульяновск : УлГТУ, 2014.

Белов П.М. Основы алгоритмизации в информационных системах:

Учебн. Пособие.- Спб.: СЗТУ, 2003.