3 Программирование рекурсивных алгоритмов.

Рек-ый алг-м - алгоритм,в описании которого прямо или косвенно содержится обращение к самому себе.

• В тексте ф-ции -вызов этой же функции, но с другим набором фактических параметров – прямая рекурсия. (пример: нахождение суммы натуральных чисел: S_n=S_n-1+n)

• При косвенном обращении функция содержит вызовы других функций из своего тела (например: поиск max-го эл-та в массиве)

Разработке рекурсивных алгоритмов предшествует рекурсивная триада:

• Параметризация – из постановки задачи выделяют параметры, которые описывают исходные данные

• Выделение базы – нахождение тривиальных случаев

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

Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии.

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

4. Модульные программы

Модульные программы

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

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

Основные характеристики модуля

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

2. Функциональная завершенность (модуль выполняет набор определенных операций)

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

4. Слабоинф-ые связи с другими модулями (обмен информацией между модулями должен быть минимален //является следствием его функциональной завершенностью)

5. Размеры и сложность модуля в разумных рамках.

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

Характеристики модуля

1. Размер модуля – измеряется числом, содержащихся в нем операторов от нескольких десятков до сотен операторов

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

3. Сцепление модуля - это мера его завис-ти по способу передачи данных от других модулей.

Есть шесть видов сцепления

1. По данным

2. По образцу

3. По управлению

4. По внешним ссылкам

5. По общ. области данных

6. По содержимому (худший вид сцепления)

4. Рутинность модуля - независимость модуля от предыстории обращения к нему

5. Связность модулей - мера прочности соед-ия функциональных и инф-ых объектов внутри одного модуля

6. Логическая связь. строиться на основе объединения данных или действий в 1-ую логарифмическую группу

7. Случайная. Нет ни каких, ни логарифмических, ни ф-ых зависимостей.

5. Виды сцепления модулей

Сцепление модулей — это мера зависимости между модулями.

Сцепление модулей

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

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

Виды сцеплений охарактеризуем в порядке уменьшения сцепления.

1. Сцепление по содержимому — модуль ссылается на данные (содержимое) другого модуля. Большинство языков программирования высокого уровня делает такое сцепление практически невозможным.

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

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

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

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

4. Сцепление по формату — модули ссылаются на одну и ту же структуру данных. Если модуль А вызывает модуль В и передает ему запись анкетных данных служащего и при этом как А так и В чувствительны к изменению структуры или формата записи, то А и В сцеплены по формату.

Такого сцепления, по возможности, следует избегать, поскольку оно создает ненужные связи между модулями.

5. Сцепление по данным — передаваемые параметры — простые (неструктурированные) данные.

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

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