Введение в сложность вычислений

Купить бумажную книгу и читать

Название: Введение в сложность вычислений

Автор: Крупский В.Н.

Издательство: М.: Факториал Пресс

Год: 2006

Страниц: 128

ISBN: 5-88688-083-6

Формат: PDF

Размер: 10 Мб

Язык: русский

Серия: Методы современной

математики; Вып. 2

Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности "Защита информации". Излагаются основные идеи и методы теории сложности вычислений.

Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.

ОГЛАВЛЕНИЕ

I. Модели вычислений ... 8

Глава 1. Машины Тьюринга ... 9

Глава 2. Время и память ... 19

Глава 3. Универсальные машины Тьюринга ... 29

Глава 4. Моделирование других языков ... 37

II. Сложностные классы ... 44

Глава 5. Класс Р ... 45

Глава 6. Класс Р/Poly ... 53

Глава 7. Класс NР ... 59

Глава 8. Примеры NР-полных задач ... 67

Глава 9. Класс ВРР ... 75

Глава 10. Распознавание простоты ... 83

Глава 11. Конечные игры и класс РН ... 91

Глава 12. Полиномиальная иерархия ... 99

Глава 13. Класс PSPАСЕ ... 109

Глава 14. РSРАСЕ-полные задачи ... 117

Список литературы ... 125

Предметный указатель ... 127