Все виды обработки данных могут быть разделены на следующие классы:         

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

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

Рекурсия — метод определения или вычисления функции, процедуры или решения задачи посредством той же функции, процедуры и т.п.

Итерация– это организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя.

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

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

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

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

Особенности рекурсивной формы

· при каждом рекурсивном вызове содержимое всех регистров ЭВМ сохраняется, а при возврате — восстанавливается, как и при любом вызове подпрограммы;

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

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

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

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

МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ

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

· «разделяй и властвуй»

· последовательных приближений

· наискорейшего спуска

· обратного прохода

· динамического программирования

· поиска с возвратом

· выделения подцелей

· моделирования

· «жадных» алгоритмов

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

Метод «разделяй и властвуй»

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

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

Примерами использования этого метода может быть решение задач:

· численного интегрирования;

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

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

· сортировки слиянием, выполняющейся разделением n элементов списка на две группы, их отдельной сортировки и последующего слияния;

· сортировки Шелла, основанной на разбиении списка на n/2 подсписков, содержащих по два элемента каждый, их сортировки и на последующих циклах сортировки n/4 четырехэлементных, затем n/8 восьмиэлементных списков;

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

· составления графика проведения теннисного турнира и др.