Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 606407.03.99
Доступ онлайн
439 ₽
В корзину
Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования! В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе. Вместо математической нотации или незнакомого академичного языка программирования типа Haskell или Lisp в этой книге для объяснения формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Издание предназначено для программистов любой квалификации, знакомых хотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике.
Стюарт, Т. Теория вычислений для программистов : практическое руководство / Т. Стюарт ; пер. с англ. А. А. Слинкина. - 2-е изд. - Москва : ДМК Пресс, 2023. - 386 с. - ISBN 978-5-89818-356-1. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2103589 (дата обращения: 11.12.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Теория вычислений 
для программистов

Том Стюарт

Understanding 
Computation

Tom Stuart

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

Москва, 2023

Том Стюарт

2-е издание, электронное

УДК 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

Содержание

Предисловие ....................................................................... 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

Содержание

Часть 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
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. Программирование в игрушечной 
стране ................................................................................. 349
Абстрактная интерпретация .................................................. 350
Планирование маршрута .................................................. 351
Абстракция: умножение знаков ......................................... 352
Аппроксимация и безопасность: сложение знаков ............ 356
Статическая семантика ......................................................... 361
Реализация ....................................................................... 363
Достоинства и ограничения .............................................. 371
Приложения .......................................................................... 374

Послесловие ..................................................................... 376

Предметный указатель ................................................... 378

Предисловие

Для кого предназначена эта книга

Это книга для программистов, интересующихся языками программирования и теорией вычислений, в особенности для тех, у кого нет 
формальной подготовки в области математики или информатики.
Если вам интересно расширить кругозор, познакомившись с разделами информатики, в которых изучаются программы, языки и 
машины, но пугает математический формализм, часто сопутствующий изложению этих тем, то эта книга для вас. Вместо сложной 
нотации мы будем использовать код для объяснения теоретических 
идей, превратив их тем самым в интерактивные инструменты, с которыми вы можете экспериментировать в удобном для себя темпе.
Предполагается, что вы знаете хотя бы один современный язык 
программирования, например: Ruby, Python, JavaScript, Java или C#. 
Все примеры написаны на Ruby, но если вы знакомы с любым другим 
языком, то все равно сможете понять код. Однако эта книга не является руководством ни по правильному написанию программ на 
Ruby, ни по объектно-ориентированному проектированию. Я стремился, чтобы код был кратким и ясным, но необязательно удобным 
для сопровождения; задача состояла в том, чтобы с помощью Ruby 
объяснить информатику, а не наоборот. Это также не учебник и не 
энциклопедия, поэтому вместо формальных рассуждений и строгих 
доказательств я попытаюсь раскрыть некоторые интересные идеи и 
побудить вас к более углубленному изучению.

Графические выделения

В книге применяются следующие графические выделения:
Курсив обозначает новые термины, URL-адреса, адреса электронной почты, имена и расширения файлов.

Доступ онлайн
439 ₽
В корзину