Теория на програмите Дичев 1998
Сумата се прибавя директно в кошницата
5.25 €
За повече информация: order@kopiebg.com
Съдържание
Предговор , 5
Глава 0. Основни означения и дефиниции
Част 1
Теория на изчислимостта
Глава 1. Машина с неограничени регистри
§0. Въведение ... ..., . ! . . . 15
§1. Изчислимост на функции с помощта на машина с неограничени регистри 16
§2. Стандартни програми за машина с неограничени регистри 22
§3. Композиция на програми за машина с неограничени регистри 25
§4. Цикли в програми за машина с неограничени регистри 28
Задачи 32
Глава 2. Частично рекурсивни функции
§0. Въведение 34
§1. Операцията суперпозиция 35
§2. Операцията примитивна рекурсия. Примитивно рекурсивни функции 37
§3. Ограничена минимизация и едновременна рекурсия 46
§4. Изчислимост на примитивно рекурсивните функции 5.0
§5. Операцията минимизация. Изчислимост на частично рекурсивните функции.... 57
Задачи 60
Глава 3. Номерация на изчислимите функции
§0. Въведение ....... 63
§1. Кодиране на наредени &-орки и редици от естествени числа. Възвратна
рекурсия 64
§2. Кодиране на команди и програми. Номерация на изчислимите функции . 70
§3. 5^-теорема. Теорема за рекурсивната определимост . .. 74
§4. Теорема за универсалната функция. Теорема на Клини 79
§5. Приложения на теоремата за универсалната функция ....-¡-.■ ■;V.г^. 84
§6. Вътрешна дефиниция на примитивно рекурсивните функции 90
§7. Построяване на компилатор за езика БЬ 94
Задачи ; ^ 97
Глава 4. Разрешими и полуразрешими множества
§0. Въведение ....101
§1. Разрешими множества 102
§2. Полуразрешими множества 104
§3. Номерация на полуразрешимите множества. Неразрешими проблеми .... 112
§4. Теорема на Райс-Шапиро 117
Задачи 121
Глава 5. Сложност на изчисленията
§0. Въведение 124
§1. Сложността мерки ^ 125
§2. Теореми на Рабин и Вородин .....; 129
§3. Теорема за ускорението 132
Задачи . 138
Част 2
Семантика на езиците за програмиране Глава б. Рекурсивни оператори
§0. Въведение 143
§1. Компактни оператори ... 1. 145
§2. Теорема на Майхил-Шефердсън. Първа теорема за рекурсията 149
§3. Индукционно правило на Скот 151
Задачи 156
Глава 7. Области на Скот
§0. Въведение 159
§1= Дефиниция и примери за области на Скот 160
§2. Конструкции на области на Скот 161
§3. Свойства на непрекъснатите изображения в области на Скот 164
§4. Първа теорема за рекурсията за системи от уравнения 167
Задачи 159
Глава 8. Рекурсивни програми
§0. Въведение ............ 171
§1. Синтаксис и операционна семантика на рекурсивните програми . 171
§2. Денотационна семантика на рекурсивните програми с предаване на параметрите по стойност .........; 178
§3, Денотационна семантика на рекурсивни програми с предаване на параметрите по име 184
§4. Правило на Скот за доказване на свойства на рекурсивни програми.* 195
Задачи ■....' 199
Глава 9. Семантичен анализ на логическите програми
§0. Въведение ....... .". 201
§1. Предварителни сведения ....... 201
§2. Логически програми ..... 204
§3. Минимален ербранов модел 206
Задачи \ 211
Глава 10. Схеми на програми
§0. Въведение ; 214
§1. Стандартни схеми 215
§2. Рекурсивни схеми .... 219
§3. Транслируемост на стандартни схеми в рекурсивни . 221
§4. Пример на Патерсон и Хюит 227
Задачи ............ 232
Азбучен указател 236
