Книга Теория алгоритмов - Крупский, Плиско
Название: Теория алгоритмов
Автор: Крупский В.Н., Плиско В.Е.
Страниц: 208
Формат: PDF
Размер: 20.3 Мб
Качество: Нормальное
Язык: Русский
Год издания: 2009
В учебном пособии изложены основы качественной и количественной теории алгоритмов; рассмотрены основные модели вычислений (машины Тьюринга, машины с неограниченными регистрами, рекурсивные функции) и связанные с ними подходы к формализации понятия алгоритма;
даны начала алгоритмической теории множеств; представлены наиболее известные результаты об алгоритмической неразрешимости, а также элементы теории сложности вычислений.
Для студентов высших учебных заведений. Может быть полезно широкому кругу читателей, интересующихся основами теории вычислимости.
ОГЛАВЛЕНИЕ
Предисловие............................... 3
Глава 1. Начальные понятия теории алгоритмов...... 9
1.1. Неформальное понятие алгоритма................ 9
1.2. Конструктивные объекты.....................11
1.3. Алгоритмический процесс.....................19
1.4. Вычислимые функции.......................21
1.5. Сигнализирующее множество...................24
Глава 2. Алгоритмическая теория множеств ........26
2.1. Разрешимые множества......................26
2.2. Полу разрешимые множества...................31
2.3. Перечислимые множества.....................35
2.4. Равнообъемность понятий полу разрешимостии перечислимости...... 40
2.5. Теорема о графике.........................44
2.6. Основные факты о разрешимых и перечислимых множествах......46
Глава 3. Машины Тьюринга................... 48
3.1. Определение одноленточной машины Тьюринга........ 48
3.2. Вычисление функций на машинах Тьюринга.......... 53
3.3. Синтез машин Тьюринга...................... 56
3.4. Тезис Тьюринга........................... 57
3.5. Универсальная машина Тьюринга................ 58
3.6. Теорема о компиляции....................... 62
3.7. Многоленточные машины Тьюринга............... 65
Глава 4. Рекурсивные функции.................73
4.1. Введение...............................73
4.2. Примитивно рекурсивные функции ...............74
4.3. Частично-рекурсивные функции.................89
4.4. Нормальная форма Клини.....................98
Глава 5. Машины с неограниченными регистрами .... 102
5.1. Определение и примеры программ...............102
5.2. МНР-вычислимость частично-рекурсивных функций .... 107
Глава 6. Нумерации вычислимых функций........113
6.1. Нумерации вычислимых функций натурального аргумента ......113
6.2. Нумерации, порожденные машинами Тьюринга ....... 117
6.3. Нумерации, порожденные МНР................. 120
Глава 7. Неразрешимые алгоритмические проблемы . . 125
7.1. Примеры невычислимых функций............... 125
7.2. Проблема остановки....................... 128
7.3. Теорема Раиса .......................... 129
Глава 8. Алгоритмические проблемы в математикеи логике... 133
8.1. Диофантово представление множеств и десятая проблема Гильберта.. 133
8.2. Проблема равенства слов в полугруппах............ 135
8.3. Арифметические множества и функции............ 141
Глава 9. Элементы теории сложности вычислений . . . 152
9.1. Некоторые предварительные сведения............. 152
9.2. Меры сложности вычислений.................. 155
9.3. Оценка эффективности вычислительных алгоритмов .... 160
Глава 10. Легко- и трудноразрешимые задачи ...... 170
10.1. Класс Р ............................. 170
10.2. Булевы схемы полиномиального размера........... 179
10.3. Класс NP ............................ 186
10.4. Примеры заведомо трудных задач............... 194
Список литературы.......................... 203
Предметный указатель........................ 204
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12808 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Иомудская лошадь Туркмении
Название: Иомудская лошадь Туркмении Автор: Шацкий Ю.В. Издательство: Туркмениздат Год: 1934 Страниц: 148 Формат: pdf Размер: 73 Мб Качество: хорошее Язык: русский Книга является одной из первых детал . . .
-
Кузина Светлана - На грани хаоса. Все врут! (аудиокнига)
Все врут! 93% людей лгут и дома, и на работе регулярно! Остальные семь процентов – в зависимости от обстоятельств! Эта книга – первый самый полный практикум настоящего лжеца! Как узнать, когда человек . . .
-
Серия «Таинственный мир" (19 томов)
Название: Серия «Таинственный мир" (19 томов) Автор: Санди Ж., Вогэн А.К. и др. Издательство: Крон-Пресс Год выпуска: 1998 Страниц: Много Формат: pdf, fb2 Размер: 30.2 Mb Качество: отличное Язык: . . .
-
Мартенс Людо - Запрещённый Сталин (аудиокнига)
Людо Мартенс (нидерл. Ludo Martens; 12 марта 1946, Винген, Западная Фландрия — 5 июня 2011) — бельгийский коммунист и историк. Основатель и руководитель Партии Труда Бельгии. Эта тема под негласным за . . .
-
Кулинарные советы моей свекрови № 9, 2014. Грибы
Название: Кулинарные советы моей свекровиНомер/год: № 9 (297) 2014Изд-во: ФЛП Шульц Р.Г.Серия: "Вкусная еда"Страниц: 32Язык: русскийФормат: PDFРазмер: 18.34 MBПростая магия гениальной кухни: кулинарны . . .
-
Радиолоцман №8 2014
Название: РадиолоцманГод / месяц: 2014 / августНомер: 8Формат: PDFРазмер: 8,1 МБЖурнал «Радиолоцман» будет интересен всем, кто интересуется электроникой. Разнообразная тематика статей охватывает облас . . .
-
Великие шутят. Сборник 5 книг
Название: Великие шутят. Сборник 5 книг Автор: коллектив Издательство: Алгоритм Год издания: 2014 Страниц: 728 Язык: Русский Формат: rtf, fb2, pdf Качество: хорошее Размер: 15,42 Мб Описание: Велики . . .
-
Наследие конунгов
Название: Наследие конунгов Автор: Холт К., Тюсберн Х. Серия или выпуск: Викинги Издательство: Терра Год издания: 1997 Страниц: 560 Язык: Русский Формат: djvu Качество: хорошее Размер: 7,54 Мб Описа . . .
-
Бубела Олег - Собрание сочинений (9 книг)
Название: Бубела Олег - Собрание сочинений (9 книг) Автор: Олег Николаевич Бубела Год издания: 2010-2014 Язык: Русский Формат: FB2, PDF. Размер: 25 Мб Описание: Олег Бубела живет на Украине. По профе . . .
-
Последняя тайна храма
Название: Последняя тайна храма Автор: Сассман Пол Серия или выпуск: Юсуф Халиф. Книга 2 Издательство: ACT ISBN: 978-5-17-081234-9 Год издания: 2014 Страниц: 480 Язык: Русский Формат: fb2,epub,pdf,r . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Книга Теория алгоритмов - Крупский, Плиско. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.