Классика программирования - алгоритмы, языки, автоматы, компиляторы - Мозговой М.В.

Название: Классика программирования - алгоритмы, языки, автоматы, компиляторы.

Автор: Мозговой М.В.

2006.

    Книга, которую вы держите в руках, посвящена описанию фундаментальных основ компьютерной науки и их применению на практике. Рассмотрено большое количество алгоритмов и моделей, которые можно использовать в повседневном программировании. При этом показано, как их использовать.
Практически все книги подобной направленности имеют ярко выраженную теоретическую ориентацию. В них много формул, теорем и доказательств, но крайне мало листингов программ. Особенность же этой книги заключается в том, что автор изложил материал максимально доступным языком (насколько это возможно в рамках темы), по возможности делая акцент на реализуемые алгоритмы и модели, а не на формулы и теоремы. Приведены конкретные примеры.
Эта книга, с одной стороны, позволяет расширить кругозор и углубить понимание основных принципов и проблем компьютерной науки, а с другой стороны — пополнить собственный инструментарий, предназначенный для ежедневного применения. Книга предназначена всем, кто интересуется и занимается программированием.

     Компьютерная наука — область весьма прагматичная. В далеко не чуждой ей математике до сих пор существует (хотя и весьма условное) разделение на «чистую» и «прикладную» ветви. Насколько мне известно, многие математики и поныне занимаются лишь абстрактными моделями, не имеющими видимого применения в современном мире. Некоторые из таких, казалось бы, абсолютно бесполезных конструкций, изученных в прошлом, пришлись весьма кстати сейчас; другие все еще ждут своего момента, третьи, вероятно, не окажутся востребованными никогда, оставаясь не более чем затейливыми интеллектуальными игрушками.
Компьютерная наука не витает в облаках, а прочно стоит на земле. Здесь всегда действует марксистский принцип «практика — критерий истины». Любое, даже самое, на первый взгляд, абстрактное понятие призвано содействовать решению практических задач. Иногда, впрочем, компьютерные модели могут увести далеко от реальности; бывают и ситуации, когда изначально искусственные конструкции вызывают живые аналогии с процессами, происходящими в природе. Тогда компьютерная наука, оторвавшись от привычного жонглирования числами, начинает претендовать на роль мощного инструмента, с помощью которого можно попытаться познать мир и даже самих себя. Так или иначе, любая модель, любая умозрительная конструкция в конечном итоге подлежит реализации на компьютере и проверке практикой. Тогда становится ясно, какие идеи содержат в себе здравое зерно, а какие являются всего лишь неадекватной решаемой задаче игрой воображения.

Содержание
Введение
О чем эта книга?
О структуре книги
Глава 1. Регулярные языки и регулярные выражения
1.1. Начальные понятия
1.2. Регулярные выражения в теории
1.3. Регулярные выражения на практике
Небольшая прелюдия
Расширенные регулярные выражения
Ленивое и жадное поведение
Группы, ссылки, подстановки
1.4. Регулярные выражения в программных продуктах
Итоги
Глава 2. Конечные автоматы
2.1. Детерминированные конечные автоматы
Неформальное введение
Представление детерминированного конечного автомата
в виде графа
FAQ по конечным автоматам (первая часть)
Описание языка с помощью конечного автомата
Детерминированный конечный автомат на языке С#
Еще немного теории
Минимизация детерминированного конечного автомата
2.2. Недетерминированные конечные автоматы
Добавим немного магии
От магии — к реальному миру
е-автомат
Детерминизация недетерминированного автомата (теория)
Детерминизация недетерминированного автомата (практика)
Непосредственная имитация недетерминированного автомата
Формальное определение недетерминированного автомата
FAQ по конечным автоматам (вторая часть)
2.3. Проект JFLAP и конечные автоматы
Итоги
Глава 3. Связь конечных автоматов и регулярных выражений
3.1. Преобразование регулярного выражения в конечный автомат
3.2. Преобразование конечного автомата в регулярное выражение
3.3. Практические следствия. Поиск подстрок, удовлетворяющих заданному регулярному выражению
Постановка задачи
Метод обращенного регулярного выражения
"Regex-directed" - механизм
3.4. Функции конвертирования в JFLAP
Итоги
Глава 4. Конечные автоматы на практике
4.1. Простейшие автоматные модели
Наглядная модель: лифт
Кофейный автомат
4.2. Немного об автоматном программировании
Несколько общих слов
Что же такое «автоматное программирование»?
Практическое применение автоматного программирования:
автоматное описание компьютерной игры
Итоги
Глава 5. Нерегулярные языки и контекстно-свободные грамматики
5.1. Нерегулярные языки. Лемма о накачке
5.2. Языки и задачи; модели вычислений
5.3. Контекстно-свободные грамматики
5.4. Регулярные грамматики
Что такое регулярные грамматики: польза ограниченности
Создание конечного автомата из регулярной грамматики
Создание регулярной грамматики из конечного автомата
Регулярность леволинейных грамматик
Поддержка регулярных грамматик в системе JFLAP
Итоги
Глава 6. Автоматы с магазинной памятью
6.1. Устройство автомата с магазинной памятью
Общие положения
Отличия автоматов с магазинной памятью
от обычных конечных автоматов
Пример автомата, распознающего нерегулярный язык
6.2. Преобразование контекстно-свободной грамматики в магазинный автомат
6.3. Преобразование магазинного автомата в контекстно-свободную грамматику
6.4. Детерминированные и недетерминированные автоматы
с магазинной памятью: две большие разницы
6.5. Автоматы с магазинной памятью в JFLAP
6.6. Распознавание детерминированных контекстно-свободных языков
Итоги
Глава 7. Синтаксический анализ
7.1. Однозначные и неоднозначные грамматики
7.2. Левый вывод, правый вывод
7.3. LL, LR и прочие технические подробности
Типы синтаксических анализаторов (парсеров)
Практические аспекты
7.4. Синтаксический анализатор для LR(1) грамматик
7.4.1. Предварительные замечания
7.4.2. Считывание грамматики
7.4.3. Удаление е-правил
7.4.4. Синтаксический анализ
Таблицы ACTION и GOTO
Процедура синтаксического анализа
Программирование синтаксического анализа
7.4.5. Генерация таблиц ACTION и GOTO
Множества FIRST
Множество ситуаций и его замыкание
Функция GoTo и последовательность С
Алгоритм создания таблиц ACTION и GOTO
Генерация LR(1)-таблицы
7.4.6. Тестирование готового анализатора
7.5. LR(1) анализатор и автомат с магазинной памятью
7.6. Синтаксический анализатор для LL(1) грамматик
Грамматики пригодные и непригодные для LL(1) анализаторов
Пишем парсер для LL( 1 )-грамматики
Как это выглядит на практике (на характерном примере)
Правила, помогающие привести грамматику к LL(t) виду
7.7. Синтаксический анализатор для любых контекстно-свободных грамматик
7.7.1. Нормальная форма Хомского
Правила, составляющие нормальную форму Хомского
Алгоритм преобразования в нормальную форму Хомского
Программирование преобразования в нормальную форму Хомского
Нормальная форма Хомского в JFLAP
Алгоритм Кока-Янгера-Касами
Итоги
Глава 8. Генерация компиляторов. Практика создания своего компилятора
8.1. Основные понятия
Трансляторы, компиляторы, интерпретаторы
Проект Coco/R
Идеология компилятора
8.2. Практический пример: транслятор простейшего языка программирования
Выбор конструкций языка
Выбор промежуточного представления
8.3. Генерация лексического и синтаксического анализаторов
Основные правила описания языка в Coco/R
Полное описание языка TinyCode в стандарте Coco/R
Генерация и компиляция синтаксического анализатора
Тестирование синтаксического анализатора
8.4. Создание промежуточного представления программы
Предварительные замечания ,
Программирование генератора промежуточного кода
Описания переменных
Переходы, присваивания и ветвления
Вывод промежуточного кода
Итоговое описание генератора промежуточного кода
8.5. Интерпретация промежуточного кода
Замечания о качестве синтаксического анализатора
Программирование интерпретатора
Итоги
Глава 9. Системы Линденмайера (L-системы)
9.1. Грамматики как средство порождения строк
9.2. Графическая интерпретация строк
9.3. Внутреннее устройство L-систем
9.3.1. Эволюция объектов
9.3.2. Порождение и визуализация строк
Порождение строк
Визуализация строк
9.4. Инструменты визуализации L-систем
9.5. Фрактальные узоры
9.6. Разновидности и дополнительные возможности L-систем
Стохастические L-системы
Контекстно-зависимые правила
Передача численных параметров
Отделение логики от графики
Трехмерная визуализация
Дополнительные графические команды
Итоги
Глава 10. Машины Тьюринга
10.1. Оглядываясь назад
10.2. За пределами контекстно-свободных языков
10.3. Машина Тьюринга. Детерминированная машина Тьюринга
10.4. Машина Тьюринга и задача распознавания
Распознавание регулярного языка
Распознавание контекстно-свободного языка
Распознавание контекстно-зависимых языков
10 5. Формальное определение машины Тьюринга
10.6. Эмулятор машины Тьюринга
10.7. Программирование машины Тьюринга
Определение разности целых чисел
Дублирование входной строки
Сортировка данных
10.8. Недетерминированная машина Тьюринга
10.9. Вариации машины Тьюринга
Бесконечная лента
Многомерная лента
Несколько головок
Несколько лент
Имитация машины Тьюринга системой JFLAP
10.10. Кодирование машин и универсальная машина Тьюринга Итоги
Глава 11. Разрешимость и сложность
11.1. Разрешимость и неразрешимость языков
11.2. Проблема останова
11.3. Машина Тьюринга и разрешимость
11.4. Что такое алгоритм?
Историческая перспектива
Неформальная инструкция как алгоритм
Машина Тьюринга как алгоритм
Машина Тьюринга и языки программирования
11.5. Машина Тьюринга и персональный компьютер
11.6. Проблема останова и программисты
Человек против компьютера
Сильная версия тезиса Черча-Тьюринга
11.7. Формализм Черча и функциональное программирование
11.7.1. Альтернативные модели вычисления
11.7.2. Совсем чуть-чуть о лямбда-исчислении
Декларативный подход к программированию
Основания формализма Черча
Лямбда-выражения
Правило редукции
11.7.3. Примеры функциональных программ
Простейший пример: вычисление факториала
Условная операция. Сокращенная схема вычислений
Функции высших порядков
Операции со списками
Сортировка списка
Композиции функций
11.8. Сложность задач и сложность систем
11.8.1. Классы Р и NP
Определение классов Р и NP. Задачи из класса Р. Решение NP-задач на практике
11.8.2. NP-трудные и NP-полные задачи
11.8.3. Феномен сложности
У истоков сложности
Одномерный клеточный автомат
Принцип вычислительной несводимости
Итоги
Послесловие



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Классика программирования - алгоритмы, языки, автоматы, компиляторы - Мозговой М.В. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать книгу Классика программирования - алгоритмы, языки, автоматы, компиляторы - Мозговой М.В. - depositfiles

Скачать книгу Классика программирования - алгоритмы, языки, автоматы, компиляторы - Мозговой М.В. - letitbit




Теги: учебник по программированию :: программирование :: Мозговой :: форма Хомского