Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования.pdf

Введение

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

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

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

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

2. Обозначить классификацию структур алгоритмов: линейную, разветвляющую и циклическую;

3. Выделить общие параметры структур алгоритмов и провести сравнительный анализ на основе примеров.

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

1. Алгоритм и его свойства, способы записи

1.1. Алгоритм и его свойства

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

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

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

Алгоритм – четкое описание последовательности действий, которые необходимо выполнить для получения результата [4, с.6]. Непосредственно термин «алгоритм» происходит от имени Хорезмского математика-ученого Аль-Хорезми – Algorithmi жившего в VIII – XI веках н.э., внесший немалый вклад в алгебру, геометрию и прочие науки.

Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое «точное предписание» или «последовательность действий, обеспечивающая получение требуемого результата». Поэтому обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций [8, с.5].

Порядок действий считается алгоритмом в том случае, если он обладает определёнными свойствами [3, с.8].

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

Само выражение «свойства алгоритма» не совсем корректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм – искусственная конструкция, которую мы сооружаем для достижения определенных целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить все же не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму [8, с.6].

К различным алгоритмам в разных явных и не явных формах предъявляются следующие требования:

• конечность
• определенность
• дискретность
• массовость
• эффективность

1) Конечность алгоритма или результативность. Означает, что алгоритм должен иметь возможность своего завершения после определенного количества шагов, как и каждое его действие.

Это требование происходит из теории вычислений, которая пытается провести грань между правильными и неправильными алгоритмами. Алгоритм считают правильным, если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. Неправильный алгоритм для некоторого входа может вовсе не остановиться или дать неправильный результат [7, с.42].

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

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

2) Определенность алгоритма каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче [8, с.5].

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

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

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

4) Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма [3, с.9]. Например, можно взять алгоритм вычисления площади круга по формуле S=πR², где R будет является входными данными, а S преобразованными выходными.

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

5) Эффективность алгоритма. Алгоритм, который выполняет действие за меньшее число шагов признается более эффективным [7, с.43].

Очевидно, что при выборе алгоритмов нужно учитывать не только их характеристики качества, но и способ реализации алгоритма. Например, многие итерационные алгоритмы удобны для ПК, но слишком трудоемки для человека. Тип используемой ПК также может влиять на выбор алгоритма (иногда имеет место и обратный вариант, когда сначала определяется алгоритм и лишь затем способ реализации) [2, с.10].

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

1.2. Способы записи алгоритмов

Для строгого задания различных структур данных и алгоритмов их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно [2, с.10].

Алгоритм является абстракцией и поэтому один и тот же алгоритм можно представить многими способами. Если с алгоритмом работает человек, то это может быть традиционный язык (русский, английский), язык картинок и пиктограмм, а также математические формулы [7, с.43].

В настоящее время распространены следующие формы представления алгоритмов:

• словесная
• графическая;
• псевдокоды;
• программная.

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

Данный способ получил значительно меньшее распространение из-за его многословности и отсутствия наглядности [8, с.9].

Примером может служить алгоритм задачи про волка, козу и капусту:

Дано:

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

1. Переправить козу

2. Возвратиться самому

3. Переправить волка

4. Возвратиться с козой

5. Переправить капусту

6. Возвратиться

7. Переправить козу

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

Примером может служить алгоритм вычисления площади треугольника по формуле Герона:

1. Задать численные значения a, b, c.

2. Вычислить p по формуле:

p = (a + b + c)/2.

3. Вычислить S по формуле:

S = √p(p - a)(p - b)(p - c)

4. Вывести результат.

Графический способ записи (изображения из графических символов или блок-схем).

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

Классические действия алгоритма изображаются следующими геометрическими фигурами по ГОСТ 19.701–90 (ИСО 58-7 85) [1] «Единая система программной документации», согласно которому каждой группе действий ставится в соответствие блок особой формы.