ОСНОВНЫЕ ПРИНЦИПЫ И СПОСОБЫ РАЗРАБОТКИ АЛГОРИТМОВ

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

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

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

Сложность алгоритма — свойство алгоритма, которое определяется как порядок функции, выражающей время его работы.

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

Временная сложность алгоритма — «время» выполнения алгоритма, выполняемое в шагах (инструкциях алгоритма), которые необходимо выполнить алгоритму для достижения запланированного результата.

Типы алгоритмов

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

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

1.отсутствие элементов, вносящих неопределенность;

2.невозможность произвольности в выборе решений, определяющих последовательность действий;

3.недопустимостью применения методов проб и ошибок,

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

ОСНОВНЫЕ ПРИНЦИПЫ И СПОСОБЫ РАЗРАБОТКИ АЛГОРИТМОВ

Важное значение для эффективного решения задач имеет правильный выбор соответствующих принципов, подходов и способов разработки алгоритмов. Здесь на первое место выходит системный подход с использованием декомпозиции и синтеза. Реализация методов декомпозиции для разработки алгоритмов осуществляется на известном принципе нисходящего проектирования,или «сверху-вниз». Он предполагает процесс пошагового разбиения алгоритма на все более мелкие части до уровня элементарных конструкций, для которых возможно составить элементарные команды. Реализация методов декомпозиции для разработки алгоритмов основано на идее уровней абстракции, которые становятся уровнями модулей в разрабатываемой программе. То есть если для некоторой функции f существует ее композиция через две другие функции g и h, то проблема разработки алгоритма f сводится к разработке алгоритмов для g и h. ходе проектирования строится схема иерархии, которая изображает эти уровни. При этом исходная, подлежащая решению задача разбивается на ряд подзадач, подчиненных по своему содержанию главной задаче. Этот принцип в литературе получил название «метод частных целей». Рассмотренный процесс называется детализацией или декомпозицией. В разрабатываемых алгоритмах необходимо избегать произвольных связей и передач управления между модулями.

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

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

При разработке алгоритмов используют известные дедуктивный и индуктивный методы (подходы).

Дедуктивный способ (подход)— при заданных предположениях известный алгоритм приспосабливается к условиям решения задачи.

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

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

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

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

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