Зарегистрироваться
Восстановить пароль
FAQ по входу

Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход

  • Файл формата djvu
  • размером 4,94 МБ
  • Добавлен пользователем
  • Отредактирован
Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход
СПб.: Наука и Техника, 2006. — 320 с.: ил.
Книга посвящена описанию фундаментальных основ компьютерной науки и их применению на практике. Рассмотрено большое количество алгоритмов и моделей, которые можно использовать в повседневном программировании. При этом показано, как их использовать.
Практически все книги подобной направленности имеют ярко выраженную теоретическую ориентацию. В них много формул, теорем и доказательств, но крайне мало листингов программ. Особенность же этой книги заключается в том, что автор изложил материал максимально доступным языком (насколько это возможно в рамках темы), по возможности делая акцент на реализуемые алгоритмы и модели, а не на формулы и теоремы. Приведены конкретные примеры.
Эта книга, с одной стороны, позволяет расширить кругозор и углубить понимание основных принципов и проблем компьютерной науки, а с другой стороны — пополнить собственный инструментарий, предназначенный для ежедневного применения. Книга
предназначена всем, кто интересуется и занимается программированием.
Введение
О чем эта книга?
О структуре книги
Регулярные языки и регулярные выражения
Начальные понятия
Регулярные выражения в теории
Регулярные выражения на практике
Небольшая прелюдия
Расширенные регулярные выражения
Ленивое и жадное поведение
Группы, ссылки, подстановки

Регулярные выражения в программных продуктах
Итоги
Конечные автоматы
Детерминированные конечные автоматы
Неформальное введение
Представление детерминированного конечного автомата в виде графа
FAQ по конечным автоматам (первая часть)
Описание языка с помощью конечного автомата
Детерминированный конечный автомат на языке C#
Еще немного теории
Минимизация детерминированного конечного автомата

Недетерминированные конечные автоматы
Добавим немного магии
От магии — к реальному миру
ε-автомат
Детерминизация недетерминированного автомата (теория)
Детерминизация недетерминированного автомата (практика)
Непосредственная имитация недетерминированного автомата
Формальное определение недетерминированного автомата
FAQ по конечным автоматам (вторая часть)

Проект JFLAP и конечные автоматы
Итоги
Связь конечных автоматов и регулярных выражений
Преобразование регулярного выражения в конечный автомат
Преобразование конечного автомата в регулярное выражение
Практические следствия. Поиск подстрок, удовлетворяющих заданному регулярному выражению
Постановка задачи
Метод обращенного регулярного выражения
«Regex-directed»- механизм

Функции конвертирования в JFLAP
Итоги
Конечные автоматы на практике
Простейшие автоматные модели
Наглядная модель: лифт
Кофейный автомат

Немного об автоматном программировании
Несколько общих слов
Что же такое «автоматное программирование»?
Практическое применение автоматного программирования: автоматное описание компьютерной игры

Итоги
Нерегулярные языки и контекстно-свободные грамматики
Нерегулярные языки. Лемма о накачке
Языки и задачи; модели вычислений
Контекстно-свободные грамматики
Регулярные грамматики
Что такое регулярные грамматики: польза ограниченности
Создание конечного автомата из регулярной грамматики
Создание регулярной грамматики из конечного автомата
Регулярность леволинейных грамматик
Поддержка регулярных грамматик в системе JFLAP

Итоги
Автоматы с магазинной памятью
Устройство автомата с магазинной памятью
Общие положения
Отличия автоматов с магазинной памятью от обычных конечных автоматов
Пример автомата, распознающего нерегулярный язык

Преобразование контекстно-свободной грамматики в магазинный автомат
Преобразование магазинного автомата в контекстно-свободную грамматику
Детерминированные и недетерминированные автоматы с магазинной памятью: две большие разницы
Автоматы с магазинной памятью в JFLAP
Распознавание детерминированных контекстно-свободных языков
Итоги
Синтаксический анализ
Однозначные и неоднозначные грамматики
Левый вывод, правый вывод
LL, LR и прочие технические подробности
Типы синтаксических анализаторов (парсеров)
Практические аспекты

Синтаксический анализатор для LR(1) грамматик
Предварительные замечания
Считывание грамматики
Удаление е-правил
Синтаксический анализ
Таблицы ACTION и GOTO
Процедура синтаксического анализа
Программирование синтаксического анализа

Генерация таблиц ACTION и GOTO
Множества FIRST
Множество ситуаций и его замыкание
Функция GoTo И последовательность С
Алгоритм создания таблиц ACTION и GOTO
Генерация LR(1)-таблицы
Тестирование готового анализатора

LR(1) анализатор и автомат с магазинной памятью
Синтаксический анализатор для LL(1) грамматик
Грамматики пригодные и непригодные для LL(1) анализаторов
Пишем парсер для LL(1)-грамматики
Как это выглядит на практике (на характерном примере)
Правила, помогающие привести грамматику к LL(1) виду

Синтаксический анализатор для любых контекстно-свободных грамматик
Нормальная форма Хомского
Правила, составляющие нормальную форму Хомского
Алгоритм преобразования в нормальную форму Хомского
Программирование преобразования в нормальную форму Хомского
Нормальная форма Хомского в JFLAP
Алгоритм Кока-Янгера-Касами

Итоги
Генерация компиляторов. Практика создания своего компилятора
Основные понятия
Трансляторы, компиляторы, интерпретаторы
Проект Coco/R
Идеология компилятора

Практический пример: транслятор простейшего языка программирования
Выбор конструкций языка
Выбор промежуточного представления

Генерация лексического и синтаксического анализаторов
Основные правила описания языка в Coco/R
Полное описание языка TinyCode в стандарте Coco/R
Генерация и компиляция синтаксического анализатора
Тестирование синтаксического анализатора

Создание промежуточного представления программы
Предварительные замечания
Программирование генератора промежуточного кода
Описания переменных
Переходы, присваивания и ветвления
Вывод промежуточного кода
Итоговое описание генератора промежуточного кода

Интерпретация промежуточного кода
Замечания о качестве синтаксического анализатора
Программирование интерпретатора

Итоги
Системы Линденмайера (L-системы)
Грамматики как средство порождения арок
Графическая интерпретация арок
Внутреннее устройство L-систем
Эволюция объектов
Порождение и визуализация строк
Порождение строк
Визуализация строк

Инструменты визуализации L-систем
Фрактальные узоры
Разновидности и дополнительные возможности L-систем
Стохастические L-системы
Контекстно-зависимые правила
Передача численных параметров
Отделение логики от графики
Трехмерная визуализация
Дополнительные графические команды

Итоги
Машины Тьюринга
Оглядываясь назад
За пределами контекстно-свободных языков
Машина Тьюринга. Детерминированная машина Тьюринга
Машина Тьюринга и задача распознавания
Распознавание регулярного языка
Распознавание контекстно-свободного языка
Распознавание контекстно-зависимых языков

Формальное определение машины Тьюринга
Эмулятор машины Тьюринга
Программирование машины Тьюринга
Определение разности целых чисел
Дублирование входной строки
Сортировка данных

Недетерминированная машина Тьюринга
Вариации машины Тьюринга
Бесконечная лента
Многомерная лента
Несколько головок
Несколько лент
Имитация машины Тьюринга системой JFLAP

Кодирование машин и универсальная машина Тьюринга
Итоги
Разрешимость и сложность
Разрешимость и неразрешимость языков
Проблема останова
Машина Тьюринга и разрешимость
Что такое алгоритм?
Историческая перспектива
Неформальная инструкция как алгоритм
Машина Тьюринга как алгоритм
Машина Тьюринга и языки программирования

Машина Тьюринга и персональный компьютер
Проблема останова и программисты
Человек против компьютера
Сильная версия тезиса Черча-Тьюринга

Формализм Черча и функциональное программирование
Альтернативные модели вычисления
Совсем чуть-чуть о лямбда-исчислении
Декларативный подход к программированию
Основания формализма Черча
Лямбда-выражения
Правило редукции

Примеры функциональных программ
Простейший пример: вычисление факториала
Условная операция. Сокращенная схема вычислений
Функции высших порядков
Операции со списками
Сортировка списка
Композиции функций

Сложность задач и сложность систем
Классы Р и NP
Определение классов Р и NP. Задачи из класса Р
Решение NP-задач на практике
NP-трудные и NP-полные задачи
Феномен сложности
У истоков сложности
Одномерный клеточный автомат
Принцип вычислительной несводимости

Итоги
Послесловие
Обработанный скан, добавлено оглавление.
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация