Презентация на тему: Место и значение алгоритмов в вычислительных задачах

в записи Q(ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением Q.

Методы решения рекурсивных соотношений

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

а) Метод индукции

Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:

f(0)=1 f(n+1)=2*f(n)

Предположение: f(n)=

Базис: если f(n)= , то f(0)=1, что выполнено по определению.

Индукция: Пусть f(n)= , тогда для n+1 f(n+1)= 2 * =

Заметим, что базис существенно влияет на решение, так, например:

Если f(0)=0, то f(n)=0;

если f(0)=1/7, то f(n)=(1/7)* ; если f(0)=1/64, то f(n)=(2)

б) Метод итерации (подстановки)

б) Метод итерации (подстановки)

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

Пусть f(n)=3*f(n/4)+n, тогда:

f(n)=n+3*f(n/4)=n+3*[n/4+3*f(n/16)]=n+3*[n/4+3{n/16+3*f(n/64) }],

и раскрывая скобки, получаем:

f(n)=n+3*n/4+9*n/16+27*n/64+…+ *n/

Остановка рекурсии произойдет при , в этом случае последнее слагаемое не больше, чем

, то окончательно:

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

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

общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид:

fA(n )= a * fA( n/b )+d(n)+U(n) (9.1), где:

d(n) – трудоемкость алгоритма деления задачи на подзадачи, U(n) – трудоемкость алгоритма объединения полученных решений.