Отличительной особенностью данного издания является то, что в нем основное внимание уделяется той части теории алгоритмов, которая относится к изучению возможностей вычислительных машин, к сложности вычислений, к нижним оценкам сложности и оптимизации алгоритмов. Перечисленные вопросы имеют важное значение для специалистов, использующих вычислительную технику в своей практической деятельности.
Оглавление § 1. ВВЕДЕНИЕ § 2 МАШИНА ТЬЮРИНГА И ФУНКЦИИ, ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ § 3 МАШИНЫ ПРОИЗВОЛЬНОГО ДОСТУПА И ВЫЧИСЛИМЫЕ ФУНКЦИИ. § 4.ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ И ИХ ВЫЧИСЛИМОСТЬ § 5. НУМЕРАЦИЯ НАБОРОВ ЧИСЕЛ И СЛОВ.. § 6 ВЫЧИСЛЕНИЕ ПО ТЬЮРИНГУ ЧАСТИЧНО РЕКУРСИВНЫХ ФУНКЦИЙ . § 7.АРИФМЕТИЗАЦИЯ МАШИН ТЬЮРИНГА И ЧАСТИЧНАЯ РЕКУРСИВНОСТЬ ФУНКЦИЙ, ВЫЧИСЛИМЫХ ПО ТЬЮРИНГУ § 8 НОРМАЛЬНЫЕ АЛГОРИТМЫ § 9 НУМЕРАЦИЯ АЛГОРИТМОВ §10 АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ § 11. ПРОБЛЕМА ТОЖДЕСТВА СЛОВ В КОНЕЧНО ОПРЕДЕЛЕННЫХ ПОЛУГРУППАХ И ДРУГИЕ ПРИМЕЧАТЕЛЬНЫЕ АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ § 12 ХАРАКТЕРИСТИКИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ § 13. НИЖНИЕ ОЦЕНКИ ВРЕМЕННОЙ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ НА МАШИНАХ ТЬЮРИНГА § 14. КЛАССЫ СЛОЖНОСТИ P И NP И ИХ ВЗАИМОСВЯЗЬ § 15. NP -ПОЛНЫЕ ЗАДАЧИ. ТЕОРЕМА КУКА § 16. ОСНОВНЫЕ NP -ПОЛНЫЕ ЗАДАЧИ. СИЛЬНАЯ NP -ПОЛНОТА § 17. СЛОЖНОСТЬ АЛГОРИТМОВ, ИСПОЛЬЗУЮЩИХ РЕКУРСИЮ § 18. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ § 19. СЛОЖНОСТЬ АЛГОРИТМОВ ВЫБОРА НА ЧАСТИЧНО УПОРЯДОЧЕННОМ МНОЖЕСТВЕ И ИХ ОПТИМАЛЬНОСТЬ § 20.ОПТИМАЛЬНОСТЬ ЖАДНОГО АЛГОРИТМА ЛИТЕРАТУРА
Название: Основы теории алгоритмов и анализа их сложности Автор: Носов В. А. Язык: Русский Издательство: кафедра Математической теории интеллектуальных систем механико-математического факультета МГУ имени М.В. Ломоносова Жанр: математика Год выхода: 1992 Формат: pdf Страниц: 140