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

ВВЕДЕНИЕ

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

Компьютеры невероятно быстры в манипулировании данными. Однако объем данных, используемых компьютерами, зачастую столь огромен, что не имеет значения, насколько быстрым является устройство – потребуется слишком много времени, чтобы изучить каждый фрагмент данных (такие компании, как Google, Facebook и Twitter, регулярно обрабатывают миллиарды фрагментов данных в день, а в некоторых случаях, даже в минуту) [3.]. Именно здесь в дело и вступают алгоритмы. Если компьютер использует наиболее подходящий для обработки данных алгоритм, то не будет иметь значения, какой объем информации он должен просматривать – как правило, он будет в состоянии сделать это в разумные сроки. Скорость работы запущенного приложения на компьютере также имеет большое значение для пользователя. Если выпущенное на рынок приложение будет работать слишком медленно, пользователи будут разочарованы этим фактом и не будут его покупать. Таким образом, потребность в создании и развитии алгоритмов является актуальной.

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

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

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

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

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

Для достижения цели в курсовой работе были поставлены следующие задачи:

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

В процессе выполнения работы все поставленные задачи были успешно выполнены.

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

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

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

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

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

Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. К ним относятся следующие способы записи [17.] алгоритмов: словесный, формульно-словесный, графический, язык операторных схем, алгоритмический язык.

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

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида [14.] вычислительных процессов:

• линейный;
• ветвящийся;
• циклический.

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

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

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

1.3 Ветвящиеся алгоритмы

Алгоритм программы, которая реализует простейшую игру-угадайку может выглядеть следующим образом:

1. Напечатать «Загадайте число от 1 до 10»;
2. Присвоить переменной guess значение 6;
3. Напечатать «Ваше число равно <guess>?»;
4. Получить ответ;
5. Если ответ «да», то напечатать «Я угадал!»;
6. Иначе, если ответ «нет», то напечатать «Ошибочка вышла…»;
7. Напечатать: «Конец игры.».

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

Наиболее распространенный способ принятия решений в Python – использование условного оператора if. Оператор if позволяет спросить, является ли истинным какое-либо условие. Если это так, то будет выполнено тело оператора if. Например, с его помощью можно реализовать псевдокод игры в угадайку, приведенный выше, как показано в листинге 1.

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

print "Загадайте число от 1 до 10."

guess = 6

answer = raw_input("Ваше число равно " \ + str(guess) + "? ")

if answer == "да":

print "Я угадал!"

if answer != "да":

print "Ошибочка вышла..."

print "Конец игры."

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

Условный оператор используется для, чтобы решить, что именно необходимо сделать. Два условия в листинге 1 – это answer == "да" и answer != "да". Эти записи означают «ответ – да» и «ответ – нет» соответственно.

Операторы печати с отступом print не выполняются, если условие if ложно. Эти операторы составляют тело каждого оператора if. Последняя печать выполняется несмотря ни на что: она не является частью if.

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

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

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

Чтобы проверить, равны ли два значения, используется оператор ==, в то время как оператор != проверяет неравенство. Знаки «меньше» (<) и «больше» (>) делают именно то, что от них ожидается. Для <, если левый операнд меньше правого операнда, возвращается истина. Есть также логические операторы меньше или равно (<=) и больше или равно (>=). В языке Python есть разница между = и ==. Символ = используется для присваивания переменных (значение помещается в переменную), в то время как символ == используется для сравнения двух операндов. Функции и методы также могут возвращать True или False.

Чаще всего требуется выполнить одно действие, если пользователь ответил «да», и другое, если он ответил что-нибудь еще. Комбинация двух if из листинга 1 может быть заменена на ветвление (листинг 2).