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

Содержание:

Введение

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

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

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

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

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

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

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

1. Изучения основных структур алгоритмов.
2. Рассмотрение методики проведения сравнительного анализа различных структур алгоритмов.
3. Анализ применения наиболее известных структур алгоритмов.

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

В первой главе рассматривается понятие и основные свойства алгоритмов, способы их описания и основные структуры.

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

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

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

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

1.1 Понятие и основные свойства алгоритмов

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

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

Итак, в широко распространенных определениях алгоритма (в рамках школьного курса информатики) можно выделить следующие составляющие:

Алгоритм – это конечная последовательность указаний …

–… на языке понятном исполнителю, …

–… задающая процесс решения задач определенного типа …

–… и ведущая к получению результата, однозначно определяемого допустимыми исходными данными [12, C.6].

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

Слово «алгоритм» происходит от имени арабского ученого IX века Муххамеда бен Аль–Хорезми («аль–хорезми» –> «алгоритм»), который описал свод правил выполнений арифметических действий в десятичной системе счисления [1, C.8]. Словом «алгоритм» потом и стали обозначать эти правила вычислений. Однако с течением времени определение алгоритма постепенно трансформировалось и в XX веке под ним стали понимать какую-либо заданную последовательность действий, позволяющую прийти к решению поставленной задачи.

Графически эволюция понятия «Алгоритм» представлена на рис. 1.1.

XX век

Последовательность действий для решений различных задач

IX век

Правила арифметических действия

Рис. 1.1 Эволюция значения слова «Алгоритм» [5, C.7]

В первое время определение понятия алгоритма было проблемой математики, однако с течением времени теория алгоритмов стала развиваться за счет влияния открытий не только в математической науке, но и в информатике. На сегодняшний день алгоритм является одним из основных понятий информатики [12, C.4].

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

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

Под элементарной операцией понимается простое действие, которое уже не нуждается в дальнейшей детализации.

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

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

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

Решение и постановка задач на персональном ЭВМ представляет собой сложный процесс, состоящий из нескольких последовательных этапов (рис.1.2). Непосредственная разработка алгоритма – это один из этих этапов

Постановка задачи

Построение математической модели

Выбор метода решения задачи на ЭВМ

Разработка алгоритма

Уточнение (подготовка) исходной информации

Программирование

Отладка программы

Решение задачи на ЭВМ и анализ результатов

Рис.1.2 Схема процесса решения задачи на ЭВМ [14]

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

Математическая формулировка – заключается в записи условия задачи с помощью математических обозначений, формул, зависимостей, в определении начальных данных и формы выдачи результатов вычислений [14].

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

Разработка алгоритма решения задачи заключается в установлении необходимой последовательности арифметических и логических действий, строгое выполнение которых должно приводить к решению задачи [3, C.11].

Составление программы – заключается в написании программы на выбранном языке программирования.

Отладка программы – этап, необходимый для выявления и устранения ошибок в написанное программе.

Решение задачи на ЭВМ – производится по отлаженной программе для всего множества заданных исходных данных.

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

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

– дискретностью;

– определенностью (детерминированностью, точностью);

– массовостью;

– результативностью;

– формальностью [7, C.14].

Графически свойства алгоритма представлены на рис. 1.3.

Детерминированность

Дискретность

Массовость

Алгоритм

Конечность

Формальность

Результативность

Рис.1.3 Свойства алгоритма [7, C.15]

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

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

Массовость (универсальность) – применимость алгоритма ко всем задачам рассматриваемого типа при любых допустимых множествах исходных данных. Здесь необходимо подчеркнуть, что массовость означает применимость алгоритма ко всем задачам рассматриваемого типа, то есть ко всем задачам, для решения которых он предназначен. Кроме того, здесь важно иметь в виду, что реализация алгоритма возможна при любых, но допустимых множествах исходных данных [8, C.19].

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

Формальность – свойство означающее, что любой исполнитель, выполняющий алгоритм (например, компьютер), действует формально, то есть строго выполняет инструкции, предусмотренные разработчиком алгоритма [8, C.19-20].

Существуют следующие способы описания (представления) алгоритмов:

1. словесное описание;

2. описание алгоритма с помощью   математических формул;

3. графическое описание алгоритма в виде блок-схемы;

4. описание алгоритма с помощью псевдокода;

5. комбинированный способ изображения алгоритма с использованием словесного, графического и др. способов [6, C.22].

Словесное описание алгоритма представляет собой описание структуры алгоритма на естественном языке. Например, к приборам бытовой техники, как правило, прилагается инструкция по эксплуатации, т.е. словесное описание алгоритма, в соответствии с которым данный прибор должен использоваться [7, C.16].

Приведем еще один пример: записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида), который более подробно будет изучен в главе 3 данной курсовой работы.

Алгоритм может быть следующим [8, C.21]:

1. задать два числа;
2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
3. определить большее из чисел;
4. заменить большее из чисел разностью большего и меньшего из чисел;
5. повторить алгоритм с шага 2.

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

Словесный способ не имеет широкого распространения, так как такие описания:

– строго не формализуемы;

– страдают многословностью записей;

– допускают неоднозначность толкования отдельных предписаний [7, C.17].

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

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