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

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

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

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

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

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

При этом каждый пример ИТ базируется на фундаментальном понятии – понятии алгоритма.

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

Объект исследования – теория алгоритмов и структур данных.

Предмет исследования – структуры алгоритмов.

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

В соответствии с поставленной целью выделены такие задания:

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

– описать методы подачи алгоритмов;

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

– провести рассмотрение операторов для реализации основных структур алгоритмов на языке С++;

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

В работе используется язык С++, так как он на данное время является одним из самых используемых.

Проблему использования базовых структур алгоритмов изучали разные ученые: Б. Страуструп, Дж.Прата, Г Шилдт. Как результат исследования ими были выпущены учебники по изучению языка программирования С++.

1.Основные понятия теории алгоритмов

1.1.Понятие алгоритма

Образование, работа, личные дела – каждодневное, ежечасное решение самых различных задач.

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

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

Оно возникло намного ранее до появления ПК, но с развитием компьютерной техники его роль возросла во много раз.

Происхождение понятия алгоритма тесно связано с именем ученого Мухамеда Муссы (Аль Хорезми). Им были впервые сформулированы правила для выполнения основных арифметических действий.

Стоит отметить, что точное математическое определение данного понятия "алгоритм" выработано только в 30-х годах 20 века.

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

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

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

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

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

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

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

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

Алгоритм – фундаментальное понятие программирования. Ученые выделяют 3 основных класса алгоритмов:

– информационные;

– вычислительные;

– управляющие [3].

Вычислительные алгоритмы – алгоритмы, что работают со сравнительно простыми форматами данных.

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

Эффективность работы таких алгоритмов прямо зависит от организации информации в программе.

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

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

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

Заметим, что алгоритм характеризуется такими свойствами (рисунок 1):

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

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

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

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

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

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

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

Все временные характеристики алгоритма могут определять временную сложность и длительность решения.

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

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

Рис.2. Временная сложность алгоритма

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

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

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

К примеру, при зависимости, которая записывается, как f(n)= 2n увеличение уровня производительности в 10 раз может увеличить размерность задачи, только на 15 %.[19]

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

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

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

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

Заметим, что при недостатке памяти для носителей информации применяется сегментация программы.

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

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

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

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

2.Базовые структуры алгоритмов

2.1.Методы описания алгоритмов

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

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

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

– словесный;

– псевдокоды;

– графический;

– программный.

Часто на практике применяется также и иной способ описания:

– таблицы автоматов;

– табличный;

– циклограммы работы.[17]

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

Для примера рассмотрим записи нахождения общего делителя для двух чисел.

Алгоритм может задаваться так:

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

– определить максимальное число;

– заменить максимальное число разностью между большим и меньшим числом;

– реализовать алгоритм сначала.

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

Рассмотренный способ записи удобно применять на начальном этапе создания алгоритма.[13]

К недостаткам применения словесного способа записи относят следующее:

– подробное полное описание алгоритма обработки данных получается очень большим;

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

– при переходе непосредственно к этапу написания программ требуется дополнительная работа для формализации алгоритма, поскольку словесное описание понятно человеку, а также "непонятно" ПК.

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