Презентация на тему "Рекуррентные уравнения"

Содержание

• 
  Слайд 1

  Рекуррентные уравнения

• 
  Слайд 2

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

  Метод итераций; Подстановочный метод; Метод рекурсивных деревьев.

• 
  Слайд 3

  Метод итераций

  Пример 1. Найти решение рекуррентного уравнения методом итераций.

• 
  Слайд 4
  

  Решение: Пусть n=2k.

• 
  Слайд 5
  
• 
  Слайд 6
  

  Пример 2. Найти решение рекуррентного уравнения

• 
  Слайд 7
  
• 
  Слайд 8
  

  Подстановочный метод Пример 3. Решить рекуррентное уравнение Идея метода: Найти функцию g(n) наименьшего возможного порядка так, что при подстановке в рекуррентное уравнение вместо T(n) получим верное неравенство

• 
  Слайд 9
  

  Подставим функцию g(n )=cn в уравнение и получим ложное неравенство Подставим теперь функцию Получим неравенство или c>2/n, которое верно для с≥2

• 
  Слайд 10
  

  Пусть Тогда

• 
  Слайд 11
  

  Пример 4. Методом подстановок решить рекуррентное уравнение

• 
  Слайд 12

  Метод рекурсивных деревьев

  Пример 5. Решить рекуррентное уравнение:

• 
  Слайд 13
  

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

• 
  Слайд 14
  

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

• 
  Слайд 15
  

  Пример 6. Решить рекуррентное уравнение

• 
  Слайд 16
  

  Теорема 1. Пусть a, b,c, k – некоторые константы. Тогда решение рекуррентного уравнения имеет вид: