Теория вычислений для программистов
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Стюарт Том
Перевод:
Слинкин Алексей Александрович
Год издания: 2023
Кол-во страниц: 386
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
Профессиональное образование
ISBN: 978-5-89818-356-1
Артикул: 606407.03.99
Доступ онлайн
439 ₽
В корзину
Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования! В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе. Вместо математической нотации или незнакомого академичного языка программирования типа Haskell или Lisp в этой книге для объяснения формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Издание предназначено для программистов любой квалификации, знакомых хотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике.
- Полная коллекция по информатике и вычислительной технике
- ДМК Пресс. Информационные системы и технологии
- ДМК Пресс. ИТ-технологии для профессионалов
- Интермедиатор. Информационные системы и технологии (сводная)
- Интермедиатор. ИТ-технологии для профессионалов (сводная)
- Программирование
- Программирование и алгоритмизация
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Теория вычислений для программистов Том Стюарт
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 ₽
В корзину