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

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

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

По кнопке выше можно купить бумажные варианты этой книги и похожих книг на сайте интернет-магазина "Читай Город".

Using the button above you can buy paper versions of this book and similar books on the website of the "Labyrinth" online store.

Реклама. ООО «Новый Книжный Центр», ИНН: 7710422909, erid: MvGzQC98w3Z1gMq1kx5ACoy5.

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

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

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

Год: 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

Дата создания страницы: