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

Введение

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

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

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

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

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

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

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

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

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

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

---

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

- изучить понятие алгоритма и его свойства;

- рассмотреть виды алгоритмов и способы их описания;

- исследовать основные структуры алгоритмов;

- определить случаи применения и использования алгоритмических структур и их различия.

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

Теоретическую основы курсовой работы составили труды авторов: Аузяк А.Г., Белова М.П., Голицыной О.Л., Ждановой Т.А., Калмыковой Е.А., Коврижных А.Ю., Паклиной В.М., Парфиловой Н.И., Полякова В.И., Рогозина С.А., Семакина И.Г., Трофимова В.В., Фофанова О.Б

Глава 1. Понятие об алгоритмах в программировании

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

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

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

Сам термин «алгоритм» связан с именем арабского математика аль-Хорезми, жившего в 783-850гг. «В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком» [13, с. 4]. Им были описаны общие правила выполнения основных арифметических действий в десятичной системе счисления. Эти правила позднее стали называться алгоритмами.

На самых первых ступенях развития математики (Древнего Египта, Вавилона, Греции) стали появляться вычислительные процессы чисто механического характера. Искомые величины различных задач с их помощью вычислялись последовательно по определенным правилам и инструкциям. [4, с. 8]

Поэтому первые алгоритмы в математике – это сложение, вычитание, умножение «столбиком», деление «уголком» многозначных чисел, а также правила алгебраических преобразований и вычислений корней уравнений. [10, с. 7]

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

---

1. присвоить переменным X и Y значения, НОД которых ищется;
2. если X > Y, то перейти на шаг 5;
3. если X < Y, то перейти на шаг 6;
4. здесь X = Y. Выдать X в качестве результата. Конец работы;
5. заменить пару (X ,Y) парой (X – Y, Y) и вернутся на шаг 2;
6. заменить пару (X ,Y) парой (X, Y - X) и вернутся на шаг 2;

[11, с. 8]

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

Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. [13, с. 4]

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

Этап постановки задачи предполагает четкое определение, что именно надо и требуется найти. Важно описать полный набор исходных данных, необходимых для решения задачи. Здесь формируются правила начала и окончания решения задач. Ведется поиск метода решения задачи: метод вычислений, метод перебора вариантов, метод распознавания образов. Выбранный метод является основой для разработки алгоритма, который реализуется с помощью ПК. При разработке исходного алгоритма и даже при выборе модели пользователь, т.е. человек, решающий конкретную задачу, должен иметь представление о математическом обеспечении ПК. [3, с. 5]

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

Каждый алгоритм составляется для конкретного исполнителя. Для компьютера программист составляет программу на специальном языке, на который ориентирована система программирования. Например, программа на языке Паскаль для системы программирования на языке Паскаль.

---

Алгоритм решения любой задачи на компьютере может быть одинаков независимо от того, на каком языке программирования будет написана программа. Такой алгоритм будет содержать в себе следующие команды: присвоение, ввод, вывод, обращение к вспомогательному алгоритму, цикл, ветвление. [10, c. 9 – 10]

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

Указанные критерии являются критериями качества алгоритма. Другими критериями выступают адаптируемость алгоритма к различным компьютерам, его простота, изящество и т.д. [2, с. 8]

Таким образом, алгоритм в работе компьютера, как определяет его Белов М.В., представляет собой «точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить задачу фиксированного типа. Команда алгоритма – предписание о выполнении отдельного законченного действия исполнителя». [3, с. 5]

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

Основными свойствами алгоритмов являются:

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

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

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

- результативность (или конечность) означает приведение к решению задачи за конечное число шагов;

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

---

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

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

И такое свойство как эффективность. Оно говорит о том, что одну и ту же задачу можно решить по-разному и за разное время с различными затратами памяти. Это свойство характеризуется минимальным числом шагов алгоритма, точностью решения, минимальными затратами других ресурсов. [11, с. 9]

Не совсем правильно применять к понятию «алгоритм» понятие «свойства», как полагает Аузяк А.Г., т.к. свойства присущи какому-нибудь веществу. Алгоритм же искусственная конструкция. И чтобы благодаря алгоритму можно было достичь определенных целей, его надо строить по определенным правилам – правилам построения алгоритма. [13, c. 6]

Первым является то, что при построении алгоритма нужно задать множество объектов, с которыми будет работать алгоритм. Закодированное представление этих объектов называется данными. Работа алгоритма начинается с определенного набора данных, называемых входными. А по результатам своей работы алгоритм выдает данные, называемые выходными. Получается, что алгоритм преобразует входные данные в выходные.

Например, при решении квадратного уравнения ax² + bx + c = 0 исходными данными являются коэффициенты a, b, c, результатами – корни уравнений x_1, x₂, а промежуточными данными – дискриминант уравнения D = b² – 4ac. [10, с. 7]

Вторым правилом построения алгоритма является память. В ней размещаются входные данные. Работая с ними, алгоритм выдает промежуточные данные и выходные, которые также храниться в памяти. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка называется переменной. Размер памяти в теории алгоритмов не ограничен. Это значит, что можно предоставить алгоритму любой объем памяти необходимый для работы. [13, с. 6]

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

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

---