|
Прикладная дискретная математика, 2013, номер 4(22), страницы 56–66
(Mi pdm429)
|
|
|
|
Вычислительные методы в дискретной математике
Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана–Люкхардта
В. В. Быкова Институт математики и фундаментальной информатики Сибирского федерального университета, г. Красноярск, Россия
Аннотация:
Обсуждаются проблемы решения рекуррентных соотношений, возникающих в анализе вычислительной сложности рекурсивных алгоритмов. Класс рассматриваемых алгоритмов ограничен алгоритмами расщепления, а именно DPLL-алгоритмами, предназначенными для решения задачи пропозициональной выполнимости. Исследована техника Кульмана–Люкхардта, традиционно применяемая при исследовании вычислительной сложности алгоритмов расщепления. Предложена теорема, устанавливающая верхние оценки времени выполнения DPLL-алгоритма в случае сбалансированного расщепления. Теорема расширяет возможности техники Кульмана–Люкхардта, так как учитывает неоднородность рекуррентного соотношения, описывающего время работы DPLL-алгоритма.
Ключевые слова:
вычислительная сложность рекурсивных алгоритмов, алгоритмы расщепления, решение рекуррентных соотношений.
Образец цитирования:
В. В. Быкова, “Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана–Люкхардта”, ПДМ, 2013, № 4(22), 56–66
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm429 https://www.mathnet.ru/rus/pdm/y2013/i4/p56
|
Статистика просмотров: |
Страница аннотации: | 466 | PDF полного текста: | 200 | Список литературы: | 64 | Первая страница: | 1 |
|