Теория вычислений для программистов (3000,00 руб.)

Стр.5

Стр.6

Стр.7

Стр.8

Стр.9

Стр.10

УДК 004.421.2 ББК 32.973-018 С759 С759 Стюарт, Том. Теория вычислений для программистов / Т. Стюарт ; пер. с англ. А. А. Слинкина. — 2-е изд., эл. — 1 файл pdf : 387 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный. ISBN 978-5-89818-356-1 Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования! В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе. Вместо математической нотации или незнакомого академичного языка программирования типа Haskell или Lisp в этой книге для объяснения формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Издание предназначено для программистов любой квалификации, знакомых хотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике. УДК 004.421.2 ББК 32.973-018 Электронное издание на основе печатного издания: Теория вычислений для программистов / Т. Стюарт ; пер. с англ. А. А. Слинкина. — Москва : ДМК Пресс, 2014. — 384 с. — ISBN 978-594074-979-0. — Текст : непосредственный. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации. ISBN 978-5-89818-356-1 © 2013 Tom Stuart © Оформление, перевод, ДМК Пресс, 2014

Стр.5

Содержание Предисловие ....................................................................... 10 Для кого предназначена эта книга ........................................... 10 Графические выделения .......................................................... 10 О примерах кода ..................................................................... 11 Как с нами связаться ............................................................... 11 Благодарности ........................................................................ 12 Глава 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

Стр.6

6 Содержание Часть 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

Стр.7

Содержание 7 Глава 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

Стр.8

8 Содержание Предикаты ........................................................................ 217 Пары ................................................................................. 218 Операции над числами ..................................................... 219 Списки .............................................................................. 228 Строки .............................................................................. 231 Решение ........................................................................... 234 Более сложные приемы программирования ..................... 238 Реализация лямбда-исчисления ........................................... 245 Синтаксис ......................................................................... 245 Семантика ........................................................................ 247 Синтаксический разбор .................................................... 253 Глава 7. Универсальность повсюду ............................. 256 Лямбда-исчисление .............................................................. 257 Частично рекурсивные функции ............................................ 260 SKI-исчисление ..................................................................... 266 Iota ........................................................................................ 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

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

Стр.10