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

Теория вычислений для программистов
Теория вычислений для программистов - фото 1
352 грн
12041
ISBN
Издательство
ДМК Пресс
Категория
Программирование
Год
2013
Страниц
384
Формат
60х90 1/16 (145х215 мм)
Обложка 
Мягкая
1 человек
  • По ХарьковуДоставка курьером - 50 грн
    Бесплатно - от 1000 грн
  • По УкраинеБесплатно - от 1000 грн
    Новая Почта - от 30 грн
    Укрпочта - от 20 грн
  • Международная доставкаУкрпочта...
Подробнее о доставке
Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования. В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они отражаются на том, чем программист изо дня в день занимается на работе. Вместо математической нотации или незнакомого академичного языка программирования типа Haskell или Lisp в этой книге для объяснения формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный к минимуму. Это идеальное решение для программистов, знакомыххотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике.

Содержание

Предисловие ....................................................................... 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
объяснить информатику, а не наоборот. Это также не учебник и не
энциклопедия, поэтому вместо формальных рассуждений и строгих
доказательств я попытаюсь раскрыть некоторые интересные идеи и
побудить вас к более углубленному изучению.

 

Вы можете купить книгу с доставкой курьером новой поштой укрпочтой Кривой Рог, Львов, Полтава, Житомир, Черкассы, Харьков, Чернигов, Винница, Тернополь, Киев, Луцк, Ровно, Хмельницкий, Херсон, Кировоград, Николаев, Днепропетровск, Ужгород, Запорожье, Суммы, Черновцы, Одесса, Ивано-франковск, другие города Украины. только в нашем магазине низкие цены, возможен торг, прямые поступления от издательства,книги под заказ, печать книг на заказ, компьютерные книги на английском языке.

Ви можете купити придбати книгу з доставкою кур'єром нова пошта Укрпошта Кривий Ріг, Львів, Полтава, Житомир, Харків, Чернігів, Вінниця, Тернопіль, Київ, Луцьк, Рівне, Хмельницький, Херсон, Кіровоград, Миколаїв, Дніпропетровськ, Ужгород , Запоріжжя, Суми, Чернівці, Черкаси, Одеса, Івано-франківськ, інші міста України. тільки в нашому магазині низькі ціни, можливий торг, прямі надходження від видавництва, книги під замовлення, друк книг на замовлення, комп'ютерні книги англійською мовою.