Обсуждаются проблемы решения рекуррентных соотношений, возникающих в анализе вычислительной сложности рекурсивных алгоритмов. Класс рассматриваемых алгоритмов ограничен алгоритмами расщепления, а именно DPLL-ал-горитмами, предназначенными для решения задачи пропозициональной выполнимости. Исследована техника Кульмана — Люкхардта, традиционно применяемая при исследовании вычислительной сложности алгоритмов расщепления. Предложена теорема, устанавливающая верхние оценки времени выполнения DPLL-алго-ритма в случае сбалансированного расщепления. Теорема расширяет возможности техники Кульмана — Люкхардта, так как учитывает неоднородность рекуррентного соотношения, описывающего время работы DPLL-алгоритма.
Скачать электронную версию публикации
Загружен, раз: 79
- Title Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана — Люкхардта
- Headline Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана — Люкхардта
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 4(22)
- Date:
- DOI
Ключевые слова
solving recurrence relations, splitting algorithms, computational complexity of recursive algorithms, решение рекуррентных соотношений, алгоритмы расщепления, вычислительная сложность рекурсивных алгоритмовАвторы
Ссылки
Kullmann O. New methods for 3-SAT decision and worst-case analysis // Theor. Computer Sci. 1999. No. 223. P. 1-72.
Kullmann O. and Luckhardt H. Deciding propositional tautologies: Algorithms and their complexity // Preprint. 1997. http://www.cs.swan.ac.uk/~csoliver.
Куликов А. С., Федин С. С. Автоматические доказательства верхних оценок на время работы алгоритмов расщепления // Теория сложности вычислений. IX. Зап. научн. сем. ПОМИ. СПб., 2004. Т. 316. С. 111-128.
Бахвалов Н. С. Численные методы. М.: Бином. Лаб. знаний, 2006.
Poincare H. Sur les equations lineaires aux differentielles ordinaires et aux differences finies // Amer. J. Math. 1885. V. 7. P. 203-258.
Perron O. Uber einen Satz des Herrn Poincare // J. Reine Angewand. Math. 1909. B. 136. S.17-34.
Быкова В. В. Эластичность алгоритмов // Прикладная дискретная математика. 2010. №2(8). С. 87-95.
Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Бином. Лаб. знаний, 2006.
Гельфонд А. О. Исчисление конечных разностей. М.: Физматлит, 1959.
Головешкин В. А., Ульянов М. В. Теория рекурсии для программистов. М.: Физматлит, 2006.
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журнал Сибирского федерального университета. Сер. Математика и физика. 2008. № 1(3). С. 236-246.
Куликов А. С., Куцков К. Новые верхние оценки для задачи максимальной выполнимости // Дискретная математика. 2009. №21(1). С. 139-157.
Hirsch E. A. New worst-case upper bounds for SAT // J. Automated Reasoning. 2000. No. 24(4). P. 397-420.
Алексеев В. Б., Носов В. А. NP-полные задачи и их полиномиальные варианты. Обзор // Обозрение прикладной и промышленной математики. 1997. Т. 4. Вып. 2. С. 165-193.
Franco J. and Gelder A. V. A perspective on certain polynomial-time solvable classes of Satisfiability // Discr. Appl. Math. 2003. V. 125. Iss. 2-3. P. 177-214.
Davis M. and Putman H. A computing procedure for quantification theory // J. ACM. 1960. No. 7(3). P. 201-215.
Davis M., Logemann G., and Loveland D. A machine program for theorem-proving // Comm. ACM. 1962. No. 5(7). P. 394-397.
Всемирное М. А., Гирш Э. А., Данцин Е. Я., Иванов С. В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Теория сложности вычислений. VI. Зап. научн. сем. ПОМИ. СПб., 2001. Т. 277. С. 14-46.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильямс, 2012.
Отпущенников И. В., Семёнов А. А. Технология трансляции комбинаторных проблем в булевы уравнения // Прикладная дискретная математика. 2011. № 1(11). С. 96-115.
Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана — Люкхардта | Прикладная дискретная математика. 2013. № 4(22).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 335