Книга Теория алгоритмов - Крупский, Плиско
Название: Теория алгоритмов
Автор: Крупский В.Н., Плиско В.Е.
Страниц: 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 оценок |
| Формат: | Книга |
| Уже скачали: | 12799 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Neue tolle Topflappen. Mit Hakelschriften.
Название:Neue tolle Topflappen. Mit Hakelschriften.Автор:Anne ThiemeyerИздательство:Urania, StuttgartISBN:3332012835Дата издания:2001-09-01Страниц:46Язык:GermanФормат:PDFРазмер: 14,4 MB Topflappen in . . .
-
Rhinoplasty- Text
Название:Rhinoplasty- TextАвтор:Trenite NolstИздательство:Not AvailISBN:9062992064Дата издания:2005-01Страниц:427Язык:АнглийскийФормат:PDFРазмер:34.75 MBThis third edition of Rhinoplasty, edited by Gi . . .
-
Русь и Литва.
Название: Русь и Литва Автор: Александр Широкорад Издательство: Вече ISBN: 978-5-9533-3490-7 Год издания: 2008 Страниц: 400 Язык: Русский Формат: rtf Размер: 6.72 МбОписание: Как Киевская Русь разде . . .
-
Разум против догмы.
Название: Разум против догмы Автор: Владимиров С.В., Волков В.А. Издательство: Наука Год издания: 1982 Страниц: 168 Язык: Русский Формат: djvu Размер: 5,38 МбОписание: В серии очерков прослеживается . . .
-
Management and Organisational Behaviour
Название:Management and Organisational BehaviourАвтор:Laurie J. MullinsИздательство:Financial Times ManagementISBN:0273688766Дата издания:2004-06Страниц:1120Язык:АнглийскийФормат:PDFРазмер: 11,65 MB"H . . .
-
The Leadership Training Activity Book: 50 Exercises for Building Effective Leaders
Название:The Leadership Training Activity Book: 50 Exercises for Building Effective LeadersАвтор:Lois B. Hart Ed.D., Charlotte S. Waisman Ph.D.Издательство:AMACOMISBN:0814472621Дата издания:2004-12-30 . . .
-
Team Leadership in the Game Industry
Название:Team Leadership in the Game IndustryАвтор:Seth (Seth Spaulding) SpauldingИздательство:Course Technology PTRISBN:1598635727Дата издания:2009-01-06Страниц:288Язык:АнглийскийФормат:PDFРазмер: 1, . . .
-
Planning for Climate Change: Strategies for Mitigation and Adaptation for Spatial Planners
Название:Planning for Climate Change: Strategies for Mitigation and Adaptation for Spatial PlannersАвтор:Simin Davoudi, Jenny Crawford, Abid MehmoodИздательство:Earthscan Publications Ltd.ISBN:1844076 . . .
-
Manichaean Texts from the Roman Empire
Название:Manichaean Texts from the Roman EmpireАвтор:Iain Gardner, Samuel N. C. LieuИздательство:Cambridge University PressISBN:0521568226Дата издания:2004-06-14Страниц:334Язык:АнглийскийФормат:PDFРаз . . .
-
Mechatronics - An Introduction
Автор:Bishop R.H.Название: Mechatronics: An IntroductionИздательство: Taylor & Francis GroupГод: 2006Формат: pdfРазмер: 14,8 Мбязык: АнглийскийISBN: 0-8493-6358-6Mechatronics has evolved into a way of . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Книга Теория алгоритмов - Крупский, Плиско. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.