Алгоритмизация вычислительных процессов

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

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

     Базовыми  элементарными структурами являются структуры: следование, ветвление и  повторение (цикл), изображенные на рис.5. Они обладают функциональной полнотой, т.е. любой алгоритм может быть реализован в виде композиции этих трех конструкций. 

     

     Рис. 5 

     Первая (а) структура - тип последовательность (или просто последовательность), вторая (б) – структура выбора (ветвление), третья (в) – структура цикла с предусловием.

     При словесной записи алгоритма указанные  структуры имеют соответственно следующий смысл:

     «выполнить  ; выполнить »,

     если  , то выполнить , иначе выполнить »,

     «до тех пор, пока , выполнять »,

     где - условие; , , - действия.

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

     Достаточно  часто структурное программирование подразумевает использование более  трех базисных структур. Применительно к языку Паскаль, в котором наиболее полно нашли свое отражение идеи структурного программирования, целесообразно при проектировании алгоритмов дополнительно использовать еще четыре элементарные структуры: сокращенную запись разветвления (рис. 16, ); структуру варианта (рис. 16, ); структуру повторения или цикла с параметром (рис. 16, ); структуру цикла с постусловием (рис. 6, ). Каждая из этих структур имеет один вход и один выход. В языке Паскаль имеются средства, позволяющие непосредственно реализовывать в программе любую из этих структур, поэтому правильное использование типовых структур в процессе разработки алгоритма обеспечивает упрощение этапов решения задачи на ЭВМ. 

     

     Рис. 6

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

     В зависимости от типа и числа проверяемых  условий различают:

     - ветвление с простым условием (условие - выражение отношения);

     - ветвление с составным условием (условие - логическое выражение);

     - сложное ветвление (несколько  условий).

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

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

     - - логическое сложение (ИЛИ), дизъюнкция;

     - - логическое умножение (И), конъюнкция;

     - I - отрицание (не).

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

     Повторяющийся участок вычисления называется циклом. Операции, осуществляемые в цикле, составляют тело цикла.

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

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

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

     Все циклические процессы по признаку определения  количества повторений (М) разделяются  на два класса.

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

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

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

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

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

     В соответствии с видом задания (изменения) параметра цикла арифметические циклы подразделяются на:

• циклы с аналитическим изменением параметра;
• циклы с табличным заданием параметра.

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

5. Предпрограммная подготовка задачи

     На  ЭВМ могут решаться задачи различного характера, например: научно-инженерные; разработки системного программного обеспечения; обучения; управления производственными процессами и т. д. В процессе подготовки и решения на ЭВМ научно-инженерных задач можно выделить следующие этапы [1]:

1. постановка задачи;
2. формирование математической модели задачи;
3. выбор и обоснование метода решения;
4. алгоритмизация вычислительного процесса;
5. программирование;
6. отладка и тестирование программы;
7. решение задачи на ЭВМ и анализ результатов;
8. сопровождение программы.

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

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

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

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

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

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

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

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

     Полученная  математическая модель должна отвечать следующим требованиям:

• вначале составляется модель исходных данных, затем - расчетные зависимости;
• в модели исходных данных не изменяются размерности данных и не используются никакие математические операции;
• обозначение всех входящих в зависимости величин именами, определяющими их суть;
• указание размерностей всех используемых величин для контроля и дальнейшей модернизации решения;

     Выбор и обоснование метода решения  - этап разработки или выбора из уже имеющихся метода решения, в том числе выбор стандартных структур вычислительных процессов (линейной, ветвящейся, циклической). Критерии выбора определяются математической моделью решения (предыдущий этап), требованиями к универсальности метода и точности результата, ограничениями технического и программного обеспечении. При обосновании выбора метода необходимо учитывать различные факторы и условия, в том числе точность вычислений, время решения задачи на ЭВМ, требуемый объем памяти и другие. Здесь следует указать альтернативные методы и аргументы сделанного выбора. Одну и ту же задачу можно решить различными методами, при этом в рамках каждого метода можно составить различные алгоритмы.

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

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

1. Программа должна быть универсальной, то есть не зависящей от конкретного набора данных. Например, если количество обрабатываемых данных может меняться, то следует предусмотреть хранение максимально возможного их количества. Универсальная программа должна уметь обрабатывать ошибки, которые могут возникнуть в процессе обработки информации.
2. Вместо констант лучше использовать переменные. Если в программе используются константы, то при их изменении нужно изменять в исходной программе каждый оператор, содержащий прежнюю константу. Эта процедура отнимает много времени и часто вызывает ошибки. В программе следует предусмотреть контроль вводимых данных (в частности, программа не должна выполняться, если данные выходят за пределы допустимого диапазона).
3. Некоторые простые приемы позволяют повысить эффективность программы (то есть уменьшить количество выполняемых операций и время работы программы). К таким приемам относится: