Файл: Алгоритмизация как основной этап разработки программ.pdf

ВВЕДЕНИЕ

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

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

• постановку задачи;
• формализацию задачи;
• алгоритмизацию (разработку алгоритма решения задачи);
• программирование (разработку программного кода задачи на языке программирования);
• составление описания (документации).

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

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

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

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

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

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

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

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

Роль этапа алгоритмизации в процессе разработки программ

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

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

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

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

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

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

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

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

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

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

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

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

Программа и данные

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

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

Вывод относится к данным, отправленным с процессора компьютера на автоматические устройства хранения данных или на внешнее устройство [7.]. Вывод может быть напечатан, отображен на экране компьютера, записан на накопитель, диск или дискету, нанесен на карту (визуализирован) на графическом устройстве или использован для управления автоматическим устройством. Внутренняя перестановка данных, во время которой значения копируются из одной ячейки памяти в другую, достигается главным образом с помощью инструкций присваивания, которые выглядят как простые уравнения. Например, инструкция языка Си «a = b;» не означает, что a и b – это одно и то же, а то, что a присваивается (назначается) то же значение, что и b. Фактически значение, содержащееся в ячейке памяти с именем b, копируется в ячейку памяти с именем a. После того как оператор выполнит оператор a = b, ячейка памяти a будет содержать то же значение, что и ячейка памяти b. Арифметические инструкции состоят из основных арифметических операций сложения, вычитания, умножения, деления, остатка и возведения в степень (возведения в степень), а также присваивания значения переменной. Таким образом, инструкция «а = 2,5 + 6,5 / 3,25;» означает, что значение 4,5 рассчитывается как значение, назначенное для переменной a. Арифметические выражения оцениваются компьютером с тем же приоритетом, что и в математике. В этом примере деление выполняется перед сложением. Команды управления используются для переключения с одного набора команд на другой в зависимости от логического сравнения значений данных. Например, компьютер может выбирать между сложением или вычитанием в зависимости от того, является ли число положительным или нет: «if (x > 0) z = x + 5; else z = x – 5;»

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

Сбор связанной между собой информации, подлежащей обработке прикладной программой, такой как температура, усредненная за определенный период времени, называется данными [9.]. Данные обычно хранятся в файле на диске. Файл данных представляет собой хранилище и содержит структурированную коллекцию данных. Входные данные должны быть систематизированы. Каждая программа включает в себя описание структуры данных, чтобы компьютер знал, как ее интерпретировать. Если программа должна найти свои входные данные на диске, данные должны быть введены в файл данных. Входные данные также могут быть введены непосредственно в исполняющую программу. Когда значения данных вводятся напрямую, особенно важно, чтобы программа проверяла данные перед их использованием. В любом случае конец входных данных должен быть узнаваемым. Когда значения данных вводятся напрямую, в качестве конечного символа используется специальный управляющий символ.

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

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

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