Введение в теорию автоматов, языков и вычислений. Второе издание

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман

Introduction to Automata Theory, Languages, and Computation, 2/E
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
книга Введение в теорию автоматов, языков и вычислений. Второе издание
(увеличить обложку)

Где купить книгу

Оглавление
Введение
Пролистать книгу

Обсуждение книги в блоге Виктора Штонда

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

Книга «Введение в теорию автоматов, языков и вычислений» будет полезна читателям различных категорий - студентам, аспирантам, научным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники.

Книга обсуждается в отдельном сообщении в блоге Виктора Штонда.


528 стр., с ил.; ISBN 978-5-8459-1969-4, 0-201-44124-1; формат 70x100/16; твердый переплетофсетная2015, 3 кв.; Вильямс.



Понравилась книга? Порекомендуйте её друзьям и коллегам:







Книги, рекомендуемые вместе с этой книгой:

Разделы каталога:



Оглавление книги "Введение в теорию автоматов, языков и вычислений. Второе издание"

Предисловие Предисловия к книге Введение в теорию автоматов, языков и вычислений, 2-е издание

Глава 1. Автоматы: методы и понятия
Глава 2. Конечные автоматы
Глава 3. Регулярные выражения и языки
Глава 4. Свойства регуляных языков Глава 4. Свойства регуляных языков
Глава 5. Контекстно-свободные грамматики и языки
Глава 6. Автоматы с магазинной памятью
Глава 7. Свойства контекстно-свободных языков
Глава 8. Введение в теорию машин Тьюринга
Глава 9. Неразрешимость
Глава 10. Труднорешаемые проблемы
Глава 11. Дополнительные классы проблем


Предисловие

В предисловии к своей книге 1979 года, предшествовавшей данному изданию, Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее после выхода их первой книги в 1969 году, произошел взрыв в развитии теории автоматов. Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутых в предыдущей работе, и по объему была почти вдвое больше. Сравнив эту книгу с книгой 1979 года, вы увидите, что она, как автомобили 1970-х "больше снаружи, но меньше изнутри". И хотя это может показаться шагом назад, мы считаем такие изменения целесообразными в силу ряда причин.

Во-первых, в 1979 году теория автоматов и языков еще активно развивалась, и одной из целей той книги было пробудить интерес математически одаренных студентов к исследованиям в этой области. На сегодня в теории автоматов имеется лишь узкое направление для исследований (чего не скажешь о ее приложениях). Поэтому, на наш взгляд, не имеет смысла сохранять здесь лаконичный, сугубо математический стиль книги 1979 года.

Во-вторых, за последние двадцать лет изменилась роль теории автоматов и языков. В 1979 году это был сложный предмет, требующий от читателя высокого уровня подготовки. Читатель нашей книги, в особенности последних ее глав, представлялся нам хорошо подготовленным студентом-старшекурсником. Сегодня же этот предмет входит в стандартную вузовскую программу для младших курсов. Поэтому содержание книги должно быть по возможности доступным, а следовательно, содержать больше подробных доказательств и обоснований по сравнению с предыдущей книгой.

В-третьих, за два последних десятилетия информатика (Computer Science) невообразимо разрослась. И если в 1979 году вузовскую программу приходилось искусственно заполнять предметами, которые, как нам казалось, могли послужить новой волне развития технологий, то сегодня таких дисциплин уже слишком много.

В-четвертых, за эти годы информатика стала практическим предметом, и многие изучающие ее студенты настроены прагматически. Мы по-прежнему убеждены, что теория автоматов является мощным инструментом для исследований во множестве новых областей. А упражнения теоретического, развивающего плана, которые содержит обычный курс теории автоматов, сохраняют свое значение вне зависимости от того, предпочитает ли студент изучать лишь практические, "денежные" технологии. Однако для того, чтобы обеспечить данному предмету достойное место среди прочих дисциплин, изучаемых студентами-информатиками, нам представляется необходимым, наряду с математической частью, подчеркнуть и практические приложения теории. С этой целью мы заменили часть довольно сложных для понимания тем из предыдущей книги актуальными примерами применения этих идей на практике. В то время как приложения теории автоматов и языков для компиляторов сегодня настолько понятны и естественны, что входят во всякий стандартный курс по компиляторам, существует немало и совершенно новых приложений. Например, алгоритмы проверки моделей, используемые для верификации протоколов, и языки описания документов, построенные по образцу контекстно-свободных грамматик.

И, наконец, последнее объяснение одновременного увеличения объема книги и уменьшения ее фактического содержания состоит в том, что при ее верстке использовались все преимущества издательских систем TEX и LATEX, которые поощряют "открытый" стиль печати, благодаря чему книга увеличивается в объеме, но становится удобнее для чтения. Мы с благодарностью отмечаем труд создателей этих издательских систем Дона Кнута и Леса Лампорта.

Как пользоваться книгой

Эта книга рассчитана на полусеместровый или семестровый курс лекций для студентов второго года обучения и выше. На ее основе в Стэндфордском университете Радживом и Джеффом читается полусеместровый курс (CS154) по теории автоматов и языков. Ввиду ограниченности по времени в этом курсе не охвачены глава 11 и часть материала главы 10, например, довольно сложные вопросы о полиномиально-временной сводимости. На Web-сайте книги (см. ниже) помещено несколько сокращенных вариантов этого курса с замечаниями.

Несколько лет назад мы столкнулись с тем, что многие студенты, поступившие в Стэнфорд после окончания колледжа, прошли курс теории автоматов, не содержавший теорию сложности. Преподавательский состав Стэнфорда полагает, что для всякого, кто серьезно занимается информатикой, эти идеи чрезвычайно важны. Тут недостаточно знать лишь то, что "для решения NP-полной задачи требуется очень много времени". Специально для таких студентов был разработан курс лекций (CS154N), который содержит материал только 8, 9 и 10 глав. Фактически, для того, чтобы освоить курс CS154N, они прослушивают лишь последнюю треть курса CS154. И по сегодняшний день на каждом курсе находится несколько студентов, желающих заниматься именно таким образом. Мы рекомендуем этот подход, поскольку он не требует чрезмерных усилий.

Требования к уровню подготовки

Чтение этой книги не вызовет затруднений у студентов, освоивших основы дискретной математики, в том числе изучивших графы, деревья, логику и методы доказательств. Кроме того, мы предполагаем, что читатель в достаточной степени знаком с программированием и, в частности, имеет представление об общих структурах данных, рекурсии и роли таких главных системных компонентов, как компиляторы. Эта сумма знаний соответствует стандартной программе первых двух лет обучения для студентов, изучающих информатику.

Упражнения

Книга содержит большое число упражнений, по несколько почти в каждом разделе. Упражнения или части упражнений повышенной сложности отмечены восклицательным знаком. Наиболее трудные из них отмечены двумя восклицательными знаками.

Некоторые упражнения отмечены звездочкой. Их решения мы намерены поместить на Web-странице книги. Они предназначены для самопроверки и доступны широкой аудитории. Отметим, что в некоторых случаях в одном упражнении Б требуется определенным образом изменить или адаптировать ваше решение другого упражнения A. Если какая-то часть упражнения A имеет решение, то естественно ожидать, что соответствующая часть упражнения Б также имеет решение.

Поддержка в World Wide Web

Адрес книги в Internet:
http://www-db.stanford.edu/~ullman/ialc.html

Здесь вы найдете решения заданий, отмеченных звездочкой, список замеченных опечаток и некоторые вспомогательные материалы. По мере чтения лекций по курсу CS154 мы постараемся размещать тут наши замечания по поводу домашних заданий, решений упражнений и экзаменов.

Благодарности

На часть материала главы 1 повлияла рукопись Крейга Сильверштейна (Creig Silverstein) о том, "как строить доказательства". Мы благодарим также следующих лиц: Зое Абрамс (Zoe Abrams), Джордж Кандеа (George Candea), Хаовен Чен (Haowen Chen), Бьен-Ган Чан (Byong-Gun Chun), Джеффри Шаллит (Jeffrey Shallit), Брет Тейлор (Bret Taylor), Джейсон Таунсенд (Jason Townsend) и Эрик Узуеро (Erik Uzureau), которые высказали свои замечания и указали на ряд опечаток в черновом варианте книги. Ошибки, оставшиеся незамеченными, авторы безусловно относят на свой счет.

Джон Хопкрофт

Раджив Мотвани

Джефри Ульман

Итака, Нью-Йорк и Стэнфорд, Калифорния

Сентябрь, 2000.


Copyright © 1992-2019 Издательская группа "Диалектика-Вильямс"

Rambler  Top100