dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 2
Текст из файла (страница 2)
От МП-автоматов к грамматикам6.3.3. Упражнения к разделу 6.36.4. Детерминированные автоматы с магазинной памятью6.4.1. Определение детерминированного МП-автомата6.4.2. Регулярные языки и детерминированные МП-автоматыÑÎÄÅÐÆÀÍÈÅСтр. 919119319419519719719920020120220520720720821021121321922022022222522622822923023323323323523723824124224224424424724925125125525926026026196.4.3. Детерминированные МП-автоматы и КС-языки6.4.4. Детерминированные МП-автоматы и неоднозначные грамматики6.4.5.
Упражнения к разделу 6.4РезюмеЛитератураГЛАВА 7. Свойства контекстно-свободных языков2697.1. Нормальные формы контекстно-свободных грамматик7.1.1. Удаление бесполезных символов7.1.2. Вычисление порождающих и достижимых символов7.1.3. Удаление ε-продукций7.1.4. Удаление цепных продукций7.1.5. Нормальная форма Хомского7.1.6. Упражнения к разделу 7.17.2. Лемма о накачке для контекстно-свободных языков7.2.1. Размер деревьев разбора7.2.2. Утверждение леммы о накачке7.2.3.
Приложения леммы о накачке к КС-языкам7.2.4. Упражнения к разделу 7.27.3. Свойства замкнутости контекстно-свободных языков7.3.1. Подстановки7.3.2. Приложения теоремы о подстановке7.3.3. Обращение7.3.4. Пересечение с регулярным языком7.3.5. Обратный гомоморфизм7.3.6. Упражнения к разделу 7.37.4. Свойства разрешимости КС-языков7.4.1.
Сложность взаимных преобразований КС-грамматик и МПавтоматов7.4.2. Временная сложность преобразования к нормальной формеХомского7.4.3. Проверка пустоты КС-языков7.4.4. Проверка принадлежности КС-языку7.4.5. Обзор неразрешимых проблем КС-языков7.4.6. Упражнения к разделу 7.4РезюмеЛитератураГЛАВА 8. Введение в теорию машин Тьюринга8.1. Задачи, не решаемые компьютерами8.1.1. Программы печати “Hello, world”8.1.2. Гипотетическая программа проверки приветствия мира8.1.3. Сведение одной проблемы к другой8.1.4. Упражнения к разделу 8.18.2.
Машина Тьюринга8.2.1. Поиски решения всех математических вопросов8.2.2. Описание машин Тьюринга10Стр. 10262263264265266269269271273276280284287287288290293295295297298298302304306306308309311314315316317319319320322325328328329330ÑÎÄÅÐÆÀÍÈÅ8.2.3. Конфигурации машин Тьюринга8.2.4. Диаграммы переходов для машин Тьюринга8.2.5. Язык машины Тьюринга8.2.6. Машины Тьюринга и останов8.2.7. Упражнения к разделу 8.28.3. Техника программирования машин Тьюринга8.3.1.
Память в состоянии8.3.2. Многодорожечные ленты8.3.3. Подпрограммы8.3.4. Упражнения к разделу 8.38.4. Расширения базовой машины Тьюринга8.4.1. Многоленточные машины Тьюринга8.4.2. Эквивалентность одноленточных и многоленточных машинТьюринга8.4.3. Время работы и конструкция “много лент к одной”8.4.4. Недетерминированные машины Тьюринга8.4.5. Упражнения к разделу 8.48.5.
Машины Тьюринга с ограничениями8.5.1. Машины Тьюринга с односторонними лентами8.5.2. Мультистековые машины8.5.3. Счетчиковые машины8.5.4. Мощность счетчиковых машин8.5.5. Упражнения к разделу 8.58.6. Машины Тьюринга и компьютеры8.6.1. Имитация машины Тьюринга на компьютере8.6.2. Имитация компьютера на машине Тьюринга8.6.3. Сравнение времени работы компьютеров и машин ТьюрингаРезюмеЛитератураГЛАВА 9. Неразрешимость9.1. Неперечислимый язык9.1.1. Перечисление двоичных цепочек9.1.2.
Коды машин Тьюринга9.1.3. Язык диагонализации9.1.4. Доказательство неперечислимости Ld9.1.5. Упражнения к разделу 9.19.2. Неразрешимая РП-проблема9.2.1. Рекурсивные языки9.2.2. Дополнения рекурсивных и РП-языков9.2.3. Универсальный язык9.2.4. Неразрешимость универсального языка9.2.5. Упражнения к разделу 9.29.3. Неразрешимые проблемы, связанные с машинами Тьюринга9.3.1. Cведения9.3.2. Машины Тьюринга, допускающие пустой язык9.3.3.
Теорема Райса и свойства РП-языковÑÎÄÅÐÆÀÍÈÅСтр. 11331334337338339340340342344346346347348349351353355356358361362364365365366371374376377378378379380381382382383385387389390392392394397119.3.4. Проблемы, связанные с описаниями языков в виде машинТьюринга9.3.5. Упражнения к разделу 9.39.4. Проблема соответствий Поста9.4.1. Определение проблемы соответствий Поста9.4.2. “Модифицированная” ПСП9.4.3. Завершение доказательства неразрешимости ПСП9.4.4.
Упражнения к разделу 9.49.5. Другие неразрешимые проблемы9.5.1. Проблемы, связанные с программами9.5.2. Неразрешимость проблемы неоднозначности КС-грамматик9.5.3. Дополнение языка списка9.5.4. Упражнения к разделу 9.59.6. Резюме9.7. ЛитератураГЛАВА 10.
Труднорешаемые проблемы10.1. Классы P и NP10.1.1. Проблемы, разрешимые за полиномиальное время10.1.2. Пример: алгоритм Крускала10.1.3. Недетерминированное полиномиальное время10.1.4. Пример из NP: проблема коммивояжера10.1.5. Полиномиальные сведения10.1.6. NP-полные проблемы10.1.7. Упражнения к разделу 10.110.2.
Первая NP-полная проблема10.2.1. Проблема выполнимости10.2.2. Представление экземпляров ВЫП10.2.3. NP-полнота проблемы ВЫП10.2.4. Упражнения к разделу 10.210.3. Ограниченная проблема выполнимости10.3.1. Нормальные формы булевых выражений10.3.2. Преобразование формул в КНФ10.3.3. NP-полнота проблемы ВКНФ10.3.4. NP-полнота проблемы 3-выполнимости10.3.5. Упражнения к разделу 10.310.4. Еще несколько NP-полных проблем10.4.1. Описание NP-полных проблем10.4.2. Проблема независимого множества10.4.3. Проблема узельного покрытия10.4.4. Проблема ориентированного гамильтонова цикла10.4.5.
Неориентированные гамильтоновы циклы и ПКОМ10.4.6. Вывод относительно NP-полных проблем10.4.7. Упражнения к разделу 10.410.5. Резюме10.6. Литература12Стр. 12399400401402404407412413413413416418420421423424424424429429431432434436436438439445445446447450455456457458458462464470472473477478ÑÎÄÅÐÆÀÍÈÅГЛАВА 11. Дополнительные классы проблем11.1. Дополнения языков из NP11.1.1.
Класс языков co-NP11.1.2. NP-полные проблемы и co-NP11.1.3. Упражнения к разделу 11.111.2. Проблемы, разрешимые в полиномиальном пространстве11.2.1. Машины Тьюринга с полиномиальным пространством11.2.2. Связь PS и NPS с определенными ранее классами11.2.3. Детерминированное и недетерминированное полиномиальноепространство11.3. Проблема, полная для PS11.3.1. PS-полнота11.3.2. Булевы формулы с кванторами11.3.3. Вычисление булевых формул с кванторами11.3.4. PS-полнота проблемы КБФ11.3.5.
Упражнения к разделу 11.311.4. Классы языков, основанные на рандомизации11.4.1. Быстрая сортировка — пример рандомизированного алгоритма11.4.2. Вариант машины Тьюринга с использованием рандомизации11.4.3. Язык рандомизированной машины Тьюринга11.4.4. Класс RP11.4.5. Распознавание языков из RP11.4.6.
Класс ZPP11.4.7. Соотношение между RP и ZPP11.4.8. Соотношения с классами P и NP11.5. Сложность проверки простоты11.5.1. Важность проверки пустоты11.5.2. Введение в модулярную арифметику11.5.3. Сложность вычислений в модулярной арифметике11.5.4. Рандомизированная полиномиальная проверка простоты11.5.5. Недетерминированные проверки простоты11.5.6. Упражнения к разделу 11.5РезюмеЛитератураПредметный указательÑÎÄÅÐÆÀÍÈÅСтр. 1348148248248348448548548648748949049149249449849949950050250450650650750950951051251451551651952052152313ÏðåäèñëîâèåВ предисловии к своей книге 1979 года, предшествовавшей данному изданию,Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее послевыхода их первой книги в 1969 году, произошел взрыв в развитии теории автоматов.Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутыхв предыдущей работе, и по объему была почти вдвое больше.
Сравнив эту книгу с книгой 1979 года, вы увидите, что она, как автомобили 1970-х “больше снаружи, но меньшеизнутри”. И хотя это может показаться шагом назад, мы считаем такие изменения целесообразными в силу ряда причин.Во-первых, в 1979 году теория автоматов и языков еще активно развивалась, и одной изцелей той книги было пробудить интерес математически одаренных студентов к исследованиям в этой области. На сегодня в теории автоматов имеется лишь узкое направление дляисследований (чего не скажешь о ее приложениях). Поэтому, на наш взгляд, не имеетсмысла сохранять здесь лаконичный, сугубо математический стиль книги 1979 года.Во-вторых, за последние двадцать лет изменилась роль теории автоматов и языков.
В1979 году это был сложный предмет, требующий от читателя высокого уровня подготовки. Читатель нашей книги, в особенности последних ее глав, представлялся нам хорошоподготовленным студентом-старшекурсником. Сегодня же этот предмет входит в стандартную вузовскую программу для младших курсов. Поэтому содержание книги должнобыть по возможности доступным, а следовательно, содержать больше подробных доказательств и обоснований по сравнению с предыдущей книгой.В-третьих, за два последних десятилетия информатика (Computer Science) невообразимо разрослась.
И если в 1979 году вузовскую программу приходилось искусственнозаполнять предметами, которые, как нам казалось, могли послужить новой волне развития технологий, то сегодня таких дисциплин уже слишком много.В-четвертых, за эти годы информатика стала практическим предметом, и многие изучающие ее студенты настроены прагматически.
Мы по-прежнему убеждены, что теорияавтоматов является мощным инструментом для исследований во множестве новых областей. А упражнения теоретического, развивающего плана, которые содержит обычныйкурс теории автоматов, сохраняют свое значение вне зависимости от того, предпочитаетли студент изучать лишь практические, “денежные” технологии. Однако для того, чтобыобеспечить данному предмету достойное место среди прочих дисциплин, изучаемыхстудентами-информатиками, нам представляется необходимым, наряду с математической частью, подчеркнуть и практические приложения теории.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
