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

Введение

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

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

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

Объектом курсовой работы является базовые алгоритмические структуры.

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

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

• провести литературный обзор по основным понятиям алгоритмов;
• рассмотреть и проанализировать базовые структуры алгоритмов;
• привести примеры использования базовых структур алгоритмов.

1. Теоретические понятия алгоритмов

Современное формальное определение алгоритма было дано в 30 - 50-х гг. XX века в работах А. Тьюринга [9], А. Черча [10], Н. Винера [1], А.Н. Колмогорова [5].

Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 г. он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр») [8].

---

Алгоритм (процедура) - решение задач в виде точных последовательно выполняемых предписаний.

Это интуитивное определение сопровождается описанием интуитивных свойств (признаков) алгоритмов: эффективность, определенность, ко­нечность [6].

Эффективность - возможность исполнения предписаний за конеч­ное время.

Например, алгоритм - процедура, состоящая из "конечного числа команд, каждая из которых выполняется механически за фиксированное время и с фиксированными затратами" [4].

В теоретических подходах к построению строгого определения понятия алгоритма исторически выделились три основных направления. Первое направление связано с рассмотрением алгоритмов, позволяющих вычислить значение числовых функций, зависящих от целочисленных значений аргументов – такие функции получили название вычислимых. Понятие вычислимой функции не является строгим, как и понятие алгоритма. Однако, благодаря работам А.Черча, К.Геделя, С.Клини, была обоснована тождественность класса всюду определенных вычислимых функций с классом частично рекурсивных функций, который определяется строго.

Это позволило свести проблему алгоритмической разрешимости к доказательству возможности (или невозможности) построения рекурсивной функции, решающей задачу. Именно этим путем А.Черчу удалось доказать неразрешимость одной из проблем математической логики – исчисления истинности предикатов. Второе направление связано с машинной математикой.

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

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

---

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

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

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

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

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

Определенность - возможность точного математического определе­ния или формально описания содержания команд и последовательности их применения в этой процедуре.

Конечность - выполнение алгоритма при конкретных исходных дан­ных за конечное число шагов.

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

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

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

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

♦ алгоритмом называется предписание, определяющее порядок выполнения операций над данными с целью получения искомого результата^[1];

♦ алгоритм – это точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим процессом), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата^[2];

---

♦ алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи^[3].

Любой алгоритм должен иметь следующие основные свойства:

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

- дискретность - процесс, определяется алгоритмом, можно разделить на отдельные элементарные этапы (шаги), каждый из которых называется шагом алгоритмического процесса или алгоритма;

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

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

Сущность алгоритмов состоит в следующих действиях, которые отражают ее свойства:

- Выделение законченных частей вычислительного процесса;

- Формальной записи каждого из них;

- Назначение детерминированного порядка выполнения выделенных частей;

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

Рассмотрим способ составления алгоритма на языке блок-схем.

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

Правила построения алгоритмов на языке блок-схем:

1. Блок-схема строится сверху вниз.

2. В любой блок-схеме имеется только один элемент, соответствующий началу алгоритма, и один элемент, соответствующий концу алгоритма.

3. Должен быть хотя бы один путь из начала блок-схемы к любому элементу.

4. Должен быть хотя бы один путь от каждого элемента блок-схемы в конец блок-схемы.

---

Основные элементы, которые будут использованы при построении блок-схемы решения задачи, представлены в табл. 1.

Таблица 1

Основные элементы для построения блок-схем

Обозначение	Описание обозначения
	Процесс–формирование новых значений, выполнение арифметических или логических операций или действий, результаты которых запоминаются в оперативной памяти ЭВМ.
	Ветвление – проверка условия: выбор одного из двух направлений выполнения алгоритма в зависимости от некоторого условия.
	Модификация – организация циклических конструкций (начало цикла).
	Предопределенный процесс – вычисление по подпрограмме, использование ранее созданных и описанных алгоритмов.
	Начало-конец программы или вход и выход в подпрограммах.
	Ввод–вывод данных – связь алгоритма с внешним миром. Вывод может осуществляться на бумагу, экран монитора, на USB носитель.
	Комментарий – пояснения, содержание подпрограмм.

2. Виды структур алгоритмов: сравнительный анализ

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

К основным структурам алгоритмов относятся [3]:

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

---