Теория вычислений для программистов

Теория алгоритмов.

Том Стюарт «Теория вычислений для программистов» ДМК Пресс, 2014 год, 384 стр. (15,5 мб. pdf)

С этой книгой вы сможете с легкостью изучать теорию вычислений и проектирование языков программирования. Подача материала по теоретической информатике дается в общедоступном для изучения контексте. Вы сможете самостоятельно оценить, почему теория вычислений важна для повседневной работы программиста изо дня в день выполняющего свою работу. Вместо нудных математических выкладок сухим академическим языком по образцу Haskell или Lisp, код в книге даётся в простом и понятном виде.

Все объяснения и формальной семантики, и теории автоматов, и функционального программирования совместно с лямбда-исчислением написаны на Ruby — современном и гибком языке программирования. Автор задумал книгу, как неформальное руководство по теории вычислений, без излишнего математического контента. Оно предназначено для практикующих программистов разного уровня квалификации изучающих информатику.

Оглавление книги

Глава 1. Все, что нужно знать о Ruby 14
Интерактивная оболочка Ruby 14
Значения 15
Простые данные 15
Структуры данных 16
Процедуры 17
Поток управления 18
Объекты и методы 18
Классы и модули 20
Прочее 21
Локальные переменные и присваивание 22
Строковая интерполяция 22
Инспектирование объектов 22
Печать строк 23
Методы с переменным числом аргументов 23
Блоки 24
Модуль Enumerable 25
Класс Struct 26
Партизанское латание 27
Определение констант 28
Удаление констант 28

Часть I. ПРОГРАММЫ И МАШИНЫ 30

Глава 2. Семантика программ 32
В чем смысл слова «смысл» 33
Синтаксис 35
Операционная семантика 36
Семантика мелких шагов 37
Выражения 39
Предложения 50
Корректность 60
Приложения 61
Семантика крупных шагов 62
Выражения 63
Предложения 65
Приложения 68
Денотационная семантика 70
Выражения 71
Предложения 75
Сравнение способов определения семантики 76
Приложения 77
Формальная семантика на практике 79
Формализм 79
Поиск смысла 80
Альтернативы 81
Реализация синтаксических анализаторов 82

Глава 3. Простейшие компьютеры 88
Детерминированные конечные автоматы 88
Состояния, правила и входной поток 89
Вывод 90
Детерминированность 91
Моделирование 92
Недетерминированные конечные автоматы 96
Недетерминированность 96
Свободные переходы 104
Регулярные выражения 108
Синтаксис 109
Семантика 112
Синтаксический анализ 122
Эквивалентность 124
Минимизация ДКА 134

Глава 4. Кое-что помощнее 136
Детерминированные автоматы с магазинной памятью 140
Память 140
Правила 142
Детерминированность 144
Моделирование 145
Недетерминированные автоматы с магазинной памятью 152
Моделирование 156
Неэквивалентность 159
Разбор с помощью автоматов с магазинной памятью 160
Лексический анализ 161
Синтаксический анализ 163
Применение на практике 168
Насколько мощнее 169

Глава 5. Окончательная машина 172
Детерминированные машины Тьюринга 172
Память 173
Правила 176
Детерминированность 180
Моделирование 180
Недетерминированные машины Тьюринга 187
Максимальная мощность 188
Внутренняя память 189
Подпрограммы 192
Несколько лент 194
Многомерная лента 195
Машины общего назначения 196
Кодирование 198
Моделирование 200

Часть II. ВЫЧИСЛЕНИЯ И ВЫЧИСЛИМОСТЬ 201

Глава 6. Программирование на пустом месте 203
Имитация лямбда-исчисления 204
Работа с процедурами 205
Задача 207
Числа 209
Булевы значения 213
Предикаты 217
Пары 218
Операции над числами 219
Списки 228
Строки 231
Решение 234
Более сложные приемы программирования 238
Реализация лямбда-исчисления 245
Синтаксис 245
Семантика 247
Синтаксический разбор 253

Глава 7. Универсальность повсюду 256
Лямбда-исчисление 257
Частично рекурсивные функции 260
SKI-исчисление 266
lota 276
Таг-системы 280
Циклические таг-системы 289
Игра «Жизнь» Конвея 300
Правило 110 303
Вольфрамова 2,3 машина Тьюринга 307

Глава 8. Невозможные программы 308
Факты как они есть 309
Универсальные системы могут выполнять алгоритмы 309
Программы могут замещать машины Тьюринга 313
Код — это данные 314
Универсальные системы могут зацикливаться 316
Программы могут ссылаться сами на себя 323
Разрешимость 329
Проблема остановки 331
Построение анализатора остановки 331
Это никогда работать не будет 334
Другие неразрешимые проблемы 339
Печальные следствия 342
Почему так происходит 345
Жизнь в условиях невычислимости 346

Глава 9. Программирование в игрушечной стране 349
Абстрактная интерпретация 350
Планирование маршрута 351
Абстракция: умножение знаков 352
Аппроксимация и безопасность: сложение знаков 356
Статическая семантика 361
Реализация 363
Достоинства и ограничения 371
Приложения 374
Послесловие 376
Предметный указатель 378

Скачать книгу бесплатно15,5 мб. pdf)
Теория вычислений. Видео

Похожая литература