Теория вычислений для программистов
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Стюарт Том
Перевод:
Слинкин Алексей Александрович
Год издания: 2014
Кол-во страниц: 384
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-94074-979-0
Артикул: 606407.02.99
К покупке доступен более свежий выпуск
Перейти
Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования! В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе.
Вместо математической нотации или незнакомого академичного языка программирования типа Haskell или Lisp в этой книге для объяснения формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Издание предназначено для программистов любой квалификации, знакомых хотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования! В этой
книге теоретическая информатика излагается в хорошо знакомом вам
контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе.
Вместо математической нотации или незнакомого академичного языка
программирования типа Haskell или Lisp в этой книге для объяснения
формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Это идеальное решение для программистов, знакомых
хотя бы с одним из современных языков, но не имеющих формальной
подготовки в информатике.
Интернет-магазин:
www.dmkpress.com
Книга – почтой:
orders@alians-kniga.ru
Оптовая продажа:
“Альянс-книга”
тел.(499)725-54-09
books@alians-kniga.ru
Рассматриваются следующие темы:
• Фундаментальные концепции вычислений, в том числе полнота
языков программирования по Тьюрингу
• Использование в программах динамической семантики
для сообщения смысла машине
• Исследование возможностей компьютера, сведенного
к элементам самого низкого уровня
• Путь от универсальной машины Тьюринга к современным
компьютерам общего назначения
• Выполнение сложных вычислений с помощью простых языков
и клеточных автоматов
• Какие особенности языка программирования по-настоящему
важны для вычислений
• Что такое проблема остановки и самореферентность
и почему некоторые вычислительные задачи неразрешимы
• Анализ программ с использованием абстрактной интерпретации
и системы типов
Том Стюарт
Теория вычислений для программистов
Теория вычислений
для программистов
Том Стюарт — специалист по информатике и программист, основатель компании
Codon, которая находится в Лондоне и занимается консультированием в области
цифровых продуктов. Работает консультантом, преподавателем, инструктором,
помогая различным компаниям выработать наиболее правильный подход к производству программных продуктов и повысить их качество.
Теория вычислений для программистов
9 785940 749790
ISBN 978-5-94074-979-0
www.дмк.рф
Теория вычислений для программистов Том Стюарт
Understanding Computation Tom Stuart
Теория вычислений для программистов Москва, 2014 Том Стюарт
УДК 004.421.2 ББК 32.973-018 С759 Стюарт Т. С759 Теория вычислений для программистов / Пер. с анг. А. А. Слинкин. – М.: ДМК Пресс, 2014. – 384 с.: ил. ISBN 978-5-94074-979-0 Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования! В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе. Вместо математической нотации или незнакомого академичного языка программирования типа Haskell или Lisp в этой книге для объяснения формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Издание предназначено для программистов любой квалификации, знакомых хотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике. УДК 004.421.2 ББК 32.973-018 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. ISBN 978-1-449-32927-3 (анг.) Copyrigth © 2013 Tom Stuart ISBN 978-5-94074-979-0 (рус.) © Оформление, перевод, ДМК Пресс, 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
К покупке доступен более свежий выпуск
Перейти