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

Реклама. Продолжение ниже
3. П одход заключается в использовании общих решений определенных рекуррентных
Рекуррентные соотношения, характерные для двух основных принципов организации рекурсии
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
Анализ ресурсной эффективности рекурсивных алгоритмов методом подсчета вершин дерева рекурсии
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
3. П одход заключается в использовании общих решений определенных рекуррентных
1/17
Средняя оценка: 4.0/5 (всего оценок: 87)
Код скопирован в буфер обмена
Скачать (805 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации

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

Изображение слайда
1/1
2

Слайд 2: Рекуррентные соотношения, характерные для двух основных принципов организации рекурсии

В общем виде значение функции сложности рекурсивного алгоритма вычисляется по формуле: «Разделяй и властвуй» Идея метода состоит в разделении задачи на части меньшей размерности n/k, где k > 1, получении решений для частей и объединение решений.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
3

Слайд 3

Аддитивное уменьшение параметра рекурсии на константу

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
4

Слайд 4

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
5

Слайд 5

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
6

Слайд 6

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
7

Слайд 7: Анализ ресурсной эффективности рекурсивных алгоритмов методом подсчета вершин дерева рекурсии

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

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8

Трудоемкость рекурсивных реализаций алгоритмов связана с количеством операций рекурсивных вызовов и возвратов, выполняемых при одном рекурсивном обращении, а также с количеством таких обращений. При вызове функции в стек помещается адрес возврата, состояние необходимых регистров процессора, состояние локальных ячеек вызывающей функции, адреса возвращаемых значений и передаваемые параметры. Введем следующие обозначения: p — количество передаваемых фактических параметров, r — количество сохраняемых в стеке регистров, k — количество возвращаемых по адресной ссылке значений, l — количество локальных ячеек процедуры. Трудоемкость, связанная с обслуживанием одного вызова и одного возврата, обозначается через F с / b = 2*(p+r+k+l+1). Где дополнительная единица учитывает операции с адресом возврата.

Изображение слайда
1/1
9

Слайд 9

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

Изображение слайда
1/1
10

Слайд 10

Будем использовать следующие обозначения для конкретного входного параметра N : R( N ) – общее число вершин дерева рекурсии, R V ( N ) – объем рекурсии без листьев (внутренние вершины), R L ( N ) – количество листьев дерева рекурсии, H R ( N ) – глубина рекурсии. Очевидно, что R(N)= R V (N)+ R L (N), H R (N)  R V (N)+ R L (N). Требуемый объем памяти в области программного стека определяется не общим количеством вершин порождённого дерева рекурсии, а максимальной глубиной его листьев. V ( N ) = H R ( N ) *( p + r + k + l +1) * u  – оценка требуемой памяти, где N – вход, u  - длина слова в байтах.

Изображение слайда
1/1
11

Слайд 11

Анализ трудоемкости методом подсчета вершин дерева рекурсии. В отличии от оценки объема памяти, которая зависит от максимальной глубины рекурсивного дерева, для функции трудоемкости количество операций со стеком на один вызов/возврат F с / b должно быть учтено для всех вершин рекурсивного дерева. Метод получения ресурсных функций для рекурсивных алгоритмов на основе анализа порожденного дерева рекурсии заключается в определении ресурсных затрат в каждой вершине дерева и их суммировании. Таким образом, основная задача при использовании этого метода состоит в теоретическом построении функций R V ( N ), R L ( N ) и H R ( N ) — как функций от характеристик множества входных данных.

Изображение слайда
1/1
12

Слайд 12

Для построения ресурсных функций рекурсивных алгоритмов необходимо учесть ряд особенностей рекурсивной реализации, а именно: - ресурсные затраты на обслуживание рекурсивных вызовов-возвратов, передачу параметров и возврат значений рекурсивных функций (ресурсные затраты обслуживания рекурсии) ; - специфику фрагмента останова рекурсии, приводящую к необходимости отдельного учета ресурсных затрат в листьях дерева рекурсии. Трудоемкость алгоритма A на конкретном входе N — F A (N) определяется трудоемкостью обслуживания дерева рекурсии, зависящей от общего количества его вершин, и трудоемкостью продуктивных вычислений, выполненных во всех вершинах дерева рекурсии.

Изображение слайда
1/1
13

Слайд 13

Обозначим через F R (N) — трудоемкость порождения и обслуживания дерева рекурсии, F C (N) — трудоемкость продуктивных вычислений алгоритма, тогда трудоемкость всего алгоритма : F А (N)= F R (N)+ F C (N) (*) Трудоемкость обслуживания дерева рекурсии: F R (N) = R(N) * F с / b При подсчете трудоемкости продуктивных вычислений необходимо учесть, что для листьев рекурсивного дерева трудоемкость отлична от трудоемкости во внутренних вершинах. Пусть F CV (N) — трудоемкость продуктивных вычислений (обработки данных) во внутренних вершинах, F CL (N) — трудоемкость вычислений в листьях дерева рекурсии, тогда F C (N) = F CV (N) + F CL (N).

Изображение слайда
1/1
14

Слайд 14

Пусть F CL (1) трудоемкость алгоритма в одном листе порожденного дерева (как правило выражается фиксированным числом базовых операций). Зная количество листьев порожденного дерева рекурсии, можно определить F CL ( N ) = F CL (1)* R L ( N ). Во внутренних вершинах дерева выполняются некоторые действия, связанные с подготовкой параметров для следующих рекурсивных вызовов и обработкой возвращаемых результатов. Трудоемкость такой обработки может зависеть как от обрабатываемых в этой вершине данных, так и от положения вершины в дереве рекурсии. С целью учета этой зависимости, введем нумерацию внутренних вершин, начиная с корня, по уровням дерева.

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
15

Слайд 15

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
16

Слайд 16

Изображение слайда
Изображение для работы со слайдом
1/2
17

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

Этапы анализа трудоемкости рекурсивного алгоритма методом анализа порожденного дерева рекурсии: 1. Анализ порождаемого данным алгоритмом дерева рекурсии с целью получения теоретических зависимостей для характеристик дерева как функций от длины входа N и/или характеристических особенностей множества входных данных. 2. Определение трудоемкости обслуживания рекурсии на один вызов-возврат F с / b. 3. Определение трудоемкости алгоритма при останове рекурсии F CL (1). 4. Исследование трудоемкости продуктивных вычислений во внутренних вершинах дерева рекурсии. 5. Получение функции трудоемкости рекурсивного алгоритма.

Изображение слайда
1/1
Реклама. Продолжение ниже