dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 3
Текст из файла (страница 3)
С этой целью мы заменили часть довольно сложных для понимания тем из предыдущей книги актуальными примерами применения этих идей на практике. В то время как приложения теории автоматовСтр. 14и языков для компиляторов сегодня настолько понятны и естественны, что входят вовсякий стандартный курс по компиляторам, существует немало и совершенно новыхприложений.
Например, алгоритмы проверки моделей, используемые для верификациипротоколов, и языки описания документов, построенные по образцу контекстносвободных грамматик.И, наконец, последнее объяснение одновременного увеличения объема книги иуменьшения ее фактического содержания состоит в том, что при ее верстке использовались все преимущества издательских систем TEX и LATEX, которые поощряют “открытый” стиль печати, благодаря чему книга увеличивается в объеме, но становится удобнеедля чтения. Мы с благодарностью отмечаем труд создателей этих издательских системДона Кнута и Леса Лампорта.Êàê ïîëüçîâàòüñÿ êíèãîéЭта книга рассчитана на полусеместровый или семестровый курс лекций для студентов второго года обучения и выше.
На ее основе в Стэндфордском университете Радживом и Джеффом читается полусеместровый курс (CS154) по теории автоматов и языков.Ввиду ограниченности по времени в этом курсе не охвачены глава 11 и часть материалаглавы 10, например, довольно сложные вопросы о полиномиально-временной сводимости. На Web-сайте книги (см. ниже) помещено несколько сокращенных вариантов этогокурса с замечаниями.Несколько лет назад мы столкнулись с тем, что многие студенты, поступившие вСтэнфорд после окончания колледжа, прошли курс теории автоматов, не содержавшийтеорию сложности.
Преподавательский состав Стэнфорда полагает, что для всякого, ктосерьезно занимается информатикой, эти идеи чрезвычайно важны. Тут недостаточнознать лишь то, что “для решения NP-полной задачи требуется очень много времени”.Специально для таких студентов был разработан курс лекций (CS154N), который содержит материал только 8, 9 и 10 глав. Фактически, для того, чтобы освоить курс CS154N,они прослушивают лишь последнюю треть курса CS154. И по сегодняшний день на каждом курсе находится несколько студентов, желающих заниматься именно таким образом.Мы рекомендуем этот подход, поскольку он не требует чрезмерных усилий.Òðåáîâàíèÿ ê óðîâíþ ïîäãîòîâêèЧтение этой книги не вызовет затруднений у студентов, освоивших основы дискретной математики, в том числе изучивших графы, деревья, логику и методы доказательств.Кроме того, мы предполагаем, что читатель в достаточной степени знаком спрограммированием и, в частности, имеет представление об общих структурах данных,рекурсии и роли таких главных системных компонентов, как компиляторы.
Эта суммазнаний соответствует стандартной программе первых двух лет обучения для студентов,изучающих информатику.ÏÐÅÄÈÑËÎÂÈÅСтр. 1515ÓïðàæíåíèÿКнига содержит большое число упражнений, по несколько почти в каждом разделе.Упражнения или части упражнений повышенной сложности отмечены восклицательнымзнаком. Наиболее трудные из них отмечены двумя восклицательными знаками.Некоторые упражнения отмечены звездочкой. Их решения мы намерены поместитьна 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), Брет Тейлор (BretTaylor), Джейсон Таунсенд (Jason Townsend) и Эрик Узурео (Erik Uzureau), которые высказали свои замечания и указали на ряд опечаток в черновом варианте книги.
Ошибки,оставшиеся незамеченными, авторы безусловно относят на свой счет.Джон ХопкрофтРаджив МотваниДжефри УльманИтака, Нью-Йорк и Стэнфорд, КалифорнияСентябрь, 2000.16Стр. 16ÏÐÅÄÈÑËÎÂÈÅÃËÀÂÀ 1Àâòîìàòû:ìåòîäû è ïîíÿòèÿТеория автоматов занимается изучением абстрактных вычислительных устройств, или“машин”. В 1930-е годы, задолго до появления компьютеров, А. Тьюринг исследовал абстрактную машину, которая, по крайней мере в области вычислений, обладала всемивозможностями современных вычислительных машин. Целью Тьюринга было точноописать границу между тем, что вычислительная машина может делать, и тем, чего онане может. Полученные им результаты применимы не только к абстрактным машинамТьюринга, но и к реальным современным компьютерам.В 1940-х и 1950-х годах немало исследователей занимались изучением простейшихмашин, которые сегодня называются “конечными автоматами”.
Такие автоматы вначале были предложены в качестве модели функционирования человеческого мозга.Однако вскоре они оказались весьма полезными для множества других целей, которыебудут упомянуты в разделе 1.1. А в конце 1950-х лингвист Н. Хомский занялся изучением формальных “грамматик”. Не будучи машинами в точном смысле слова, грамматики, тем не менее, тесно связаны с абстрактными автоматами и служат основой некоторых важнейших составляющих программного обеспечения, в частности, компонентов компиляторов.В 1969 году С. Кук развил результаты Тьюринга о вычислимости и невычислимости.Ему удалось разделить задачи на те, которые могут быть эффективно решены вычислительной машиной, и те, которые, в принципе, могут быть решены, но требуют для этоготак много машинного времени, что компьютер оказывается бесполезным для решенияпрактически всех экземпляров задачи, за исключением небольших. Задачи последнегокласса называют “трудно разрешимыми” (“труднорешаемыми”) или “NP-трудными”.Даже при экспоненциальном росте быстродействия вычислительных машин (“закон Мура”) весьма маловероятно, что нам удастся достигнуть значительных успехов в решениизадач этого класса.Все эти теоретические построения непосредственно связаны с тем, чем занимаютсяученые в области информатики сегодня.
Некоторые из введенных понятий, такие, например, как конечные автоматы и некоторые типы формальных грамматик, используются при проектировании и создании важных компонентов программного обеспечения.Другие понятия, например, машина Тьюринга, помогают нам уяснить принципиальныевозможности программного обеспечения.
В частности, теория сложности вычисленийСтр. 17позволяет определить, можем ли мы решить ту или иную задачу “в лоб” и написатьсоответствующую программу для ее решения (если эта задача не принадлежит классу“трудно разрешимых”), или же нам следует искать решение данной трудно разрешимой задачи в обход, используя приближенный, эвристический, или какой-либо другойметод, с помощью которого удастся ограничить время, затрачиваемое программой наее решение.В этой вводной главе дается обзор содержания теории автоматов и ее приложений.Основная часть главы посвящена рассмотрению различных методов доказательств испособов их нахождения. Рассматриваются дедуктивные доказательства, утверждения,получаемые переформулировкой, доказательства от противного, доказательства поиндукции и другие важные понятия.
В последней части вводится ряд основополагающихпонятий теории автоматов: алфавиты, цепочки и языки.1.1. Çà÷åì èçó÷àåòñÿ òåîðèÿ àâòîìàòîâ?В силу ряда причин теория автоматов и теория сложности являются важнейшей частью ядра информатики. В этом разделе мы познакомим читателя с главными мотивами,побуждающими нас к их изучению, а также обрисуем в общих чертах основные темы,затрагиваемые в книге.1.1.1. Ââåäåíèå â òåîðèþ êîíå÷íûõ àâòîìàòîâКонечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения. Ниже (начиная со второй главы) мы рассмотрим примеры ихиспользования, а сейчас просто перечислим наиболее важные из них.1.Программное обеспечение, используемое для разработки и проверки цифровыхсхем.2.“Лексический анализатор” стандартного компилятора, т.е.
тот компонент компилятора, который отвечает за разбивку исходного текста на такие логические единицы,как идентификаторы, ключевые слова и знаки пунктуации.3.Программное обеспечение для сканирования таких больших текстовых массивов,как наборы Web-страниц, с целью поиска заданных слов, фраз или других последовательностей символов (шаблонов).4.Программное обеспечение для проверки различного рода систем (протоколы связиили протоколы для защищенного обмена информацией), которые могут находиться вконечном числе различных состояний.С точными определениями автоматов различного типа мы встретимся вскоре. Аначнем с краткого описания того, что представляет собой конечный автомат, и как ондействует. Существует множество различных систем и их компонентов, например,18Стр.
18ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßтолько что перечисленные, которые можно рассматривать, как находящиеся в каждыймомент времени в одном из конечного числа “состояний”. Назначением каждого состояния является запоминание определенного момента истории системы. Посколькучисло состояний конечно, то запомнить всю историю системы невозможно, а значит,необходимо строить систему тщательно, чтобы хранить только действительно важнуюинформацию и забывать несущественную. Преимущество конечности числа состоянийзаключается в том, что систему можно реализовать, имея ограниченные ресурсы. Например, ее можно реализовать “в железе” как схему или же в виде простой программы,принимающей решения на основе ограниченного количества данных или текущей команды машинного кода.Пример 1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
