Методы анализа и разработки параметризированных алгоритмов

• Автор: Быкова, Валентина Владимировна
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2012
• Место защиты: Красноярск
• Количество страниц: 257 с. : ил.

Глава 1. Предварительные обсуждения. Алгоритмичность, конструктивность и вычислимость. Асимптотические обозначения, используемые в анализе алгоритмов. Соглашения относительно функций сложности алгоритма. Глава 2. Несколько вспомогательных утверждений. Шесть классов функций. Теорема о классификации функций на основе эластичности. Методика сравнения алгоритмов по асимптотике эластичности функций сложности. Выводы. Глава 3. Рекурсивные алгоритмы и рекуррентные соотношения
3. Глава 4. Параметризация задач и алгоритмов. Выводы. Глава 5. Метод динамического программирования по дереву декомпозиции. В8дерева. ВБдереву. Выводы. Однако если использовать яразрядное двоичное представление слагаемых, то определение их суммы потребует уже порядка 2п единиц времени и столько же единиц памяти. Обычно алгебраический подход применяют в тех ситуациях, когда числовые значения операндов вмещаются в ячейку памяти реального компьютера. Если эти значения превышают то, что можно представить реальным машинным словом, то переходят к битовым вычислениям.


Глава 1. Соглашения относительно функций сложности алгоритма. Глава 2. Глава 3. Глава 4. Параметризация задач и алгоритмов. Глава 5. Глава 6. Нижние оценки древовидной ширины и пути их уточнения. Приложение 1. П. 1. П. 1. Приложение 2. П.2. П.2. Приложение 3. П.3. П.3. П.3. В теории сложности вычислений выделяют два специальных раздела. Р, , теорию полноты. РФ от 7 июля г. А.Н. Колмогоров, Марков, Н. М. Нагорный, А. И. Мальцев, Г. С. Цейтин, Ю. Янов, Л. А. Левин, ЮЛ. Ершов, Разборов, А. Л. Семенов, В. А. Успенский, Б. Трахтенброт, Э. Л. Пост, А. М. Тьюринг, А. Черч, Р. С. Кук, М. Гэри, Д. Джонсон, Д. Кнут, Р. Тарьян, X. Пападимитриу, К. Р. Дауни и М. Феллови 3. Н. Робертсона и П. Сеймура 0, 1. Однако только Р. Ю.И. Журавлева, И. В. Сергиенко, В. Емеличева, М. М. Ковалева, М. К. Кравцова, В. К. Леонтьева, В. Л. Береснева, Э. Гимати, В. Г. Ви зинга, С. В. Севастьянова, А. А. Колоколова, И. Ю.А. Кочетова, И. Х. Сигала, А. В. Пяткина, В. В. Серваха, В. П. Ильева, В. В.А. Бондаренко, О. А. Щербины и многих других. Так, В. А. Головешкин и М. Другая проблема связана с анализом рекурсивных апгоритмов. Дж. Бентли, Д. Хакена, Дж. БРТалгоритмам. РРТалгоритмов. Г. Бодлаендер 4. Достижение заявленной цели предполагает решение следующих задач исследования. Научная новизна и выносимые на защиту положения. Укажем наиболее существенные. Личный вклад автора. Теоретическая ценность диссертации. Практическая ценность диссертации. Наука и образование РАО. Публикации. Структура и объем работы. В первой главе даны основные понятия, обозначения и соглашения. Четвертая глава содержит шесть параграфов. РРТ алгоритма утверждение 4. В заключении сформулированы основные результаты диссертационной работы. Библиографический список включает 2 наименования. Здесь даны основные понятия, обозначения и соглашения. Наиболее употребительны следующие интуитивные толкования. Определение А. Алгоритм имеет дело с данными входными, промежуточными, результирующими. Для размещения данных алгоритму необходима память. Колмогоров А. Согласно А. Различные уточнения этого понятия приводят к его сужению. С. Клини, А. Чрча, А. Э. Поста. А.Н. Колмогоров, Марков, Н. М. Нагорный, А. И. Мальцев, Г. Цейтин, Ю. И. Янов, Л. А. Левин, Ю. Л. Ершов, Разборов, А. Л. Семенов, В. Успенский, Б. А. Трахтенброг и многие другие. Выделяют массовые и индивидуальные задачи. П и т. Многие задачи изначально имеют распознавательную формулировку. О потенциальной вычислимости еще в г. Различают временную и мкостную сложности алгоритма. Тьюринга 9, , , , . РАМ. РАМпрограммы. Логарифмический битовый подход учитывает размер операндов. Очевидно, что битовый подход дает более высокую сложность, чем алгебраический.