книга Теория алгоритмов - Крупский, Плиско

А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
0-9 A B C D I F G H IJ K L M N O P Q R S TU V WX Y Z #


Теория алгоритмов - Крупский, Плиско

скачать Теория алгоритмов бесплатно
Название: Теория алгоритмов
Автор: Крупский В.Н., Плиско В.Е.
Страниц: 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



    [turbobit] [prestigefile.com] [dfiles]




С этой книгой бесплатно скачивают:



1

 

 

Электронная библиотека Kodges.ru — интересный ресурс для тех, кто не любит тратить много времени на поиск необходимого издания. В каталогах представлено огромное количество книг различной тематики, которые можно скачать совершенно бесплатно в нужном формате. В разделе «Компьютерная литература» можно скачать как книги для профессионалов, так и книги с ответами на популярные вопросы, например, «Теория алгоритмов - Крупский, Плиско». Благодаря удобной навигации библиотеки, каждый читатель моментально найдет необходимое издание.


Поделитесь ссылкой на книгу со своими друзьями:

HTML ссылка:


Ссылка для форумов:


Прямая ссылка:



Имя:*
E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent



Навигация по сайту


Читательские рекомендации

Информация