Введение

Книга содержит изложение основных вопросов теории вычислений, лежащих на стыке математики и компьютерной науки (информатики) и широко используемых во многих областях информатики и дискретной математики. В ней рассматриваются основы теории автоматов, формальных языков, сложности вычислений и сетей Петри. Теория автоматов занимается изучением абстрактных устройств дискретного действия для переработки информации (или “вычислительных машин”). В 30-е годы прошлого века, задолго до появления компьютеров, А. Тьюринг исследовал абстрактную вычисли-тельную машину, которая обладала всеми возможностями современных компьютеров (по крайней мере, в области вычислений). Целью Тьюринга было точно описать границу между тем, что вы-числительная машина может делать, и тем, чего она делать не может. Полученные им результаты применимы не только к абстрактным машинам Тьюринга, но и к реальным современным компьютерам.

В 40-х и 50-х годах прошлого века исследователи занимались изучением простейших вычислительных машин, имеющих конечную память, которые сегодня называются “конечными автоматами”. Такие автоматы вначале были предложены в качестве модели функционирования мозга. Однако вскоре они оказались весьма полезными и чрезвычайно удобнымы для моделирования многих систем аппаратного и программного обеспечения. Несмотря на свою простоту, модель конечного автомата успешно используется в огромном числе приложений не только в информатике, но и во многих других областях дискретной математики и инженерной деятельности. Большой интерес к этой теории объясняется именно широкими возможностями ее применения.

Основоположником теории формальных языков по праву считается Н. Хомский. Именно он в 50-е годы прошлого века положил начало математическому исследованию формальных грамматик, введя некоторые важные для этого понятия (в частности, понятия порождающей грамматики и автомата с магазинной памятью) и доказав ряд основополагающих результатов. Возникнув в результате усилий, направленных на разработку точных методов описания естественных языков, теория грамматик является активно развиваемым направлением математической лингвистики и теории алгоритмов, занимающимся конструктивными способами задания множеств “правильно построенных выражений” (формальных языков) и получившим широкое применение для описания языков программирования и автоматизации программирования методами трансляции.

Найдется немного научных терминов, так быстро завоевавших широкую известность, как понятие “NP-полная задача”. За короткий промежуток времени с момента введения этого понятия С. Куком в начале 70-х годов прошлого века оно стало символом тех трудностей, которые встречаются на пути создания достаточно общих и эффективных методов решения задач информатики и дис-кретной математики.

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

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

Первые примеры труднорешаемых разрешимых задач были получены в начале 60-х годов прошлого века в работах Дж. Хартманниса и Р. Стирнза по “иерархии” сложности. Однако их примеры включали только “искусственные” (специально построенные) задачи. Только через десять лет А. Мейеру, Л.`Стокмейеру, М. Фишеру, М. Рабину и ряду других исследователей удалось показать, что некоторые “естественные” разрешимые задачи труднорешаемы. Было доказано существование для любого $k$ таких труднорешаемых задач, временная сложность решения которых больше чем $2^{2^{...2^{n}}}$, где $k$ - высота башни степеней, а $n$ - размер входа задачи.

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

Все известные к настоящему времени труднорешаемые задачи (т. е. задачи, труднорешаемость которых уже доказана), попадают в один из рассмотренных выше классов: они либо вовсе неразрешимы, либо труднорешаемы даже на недетерминированном вычисли-тельном устройстве. Вместе с тем большинство представляющихся труднорешаемыми практических задач дискретной математики лежит вне этих классов и может быть решено за полиномиальное время с помощью недетерминированной машины. Это так называемые переборные задачи. Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть разрешена алгоритмом полного перебора. Так, в задаче о выполнимости логических формул решение можно отыскать среди $2n$ булевских векторов длины $n$, где $n$ — число переменных формулы, и, перебрав это экспоненциальное множество векторов при вычислении значения формулы, мы обязательно решим задачу. Переборный алгоритм имеет экспоненциальную временную сложность и может хорошо работать на практике для задачи небольших размеров. Но с ростом размера задачи число вариантов быстро растет, и она становится практически неразрешимой рассмотренным методом перебора.

Поэтому в конечной области аналогом алгоритмической неразрешимости является необходимость перебора экспоненциального числа вариантов, а аналогом разрешимости — существование алгоритма решения задачи за полиномиальное время на детерминированном вычислительном устройстве. При этом NP-полные задачи являются эталоном сложности класса переборных задач. На центральный вопрос о том, можно ли исключить перебор при решении дискретных задач из этого класса, можно ответить либо построив полиномиальный алгоритм решения одной из NP-полных задач, либо доказав невозможность построения эффективного алгоритма для этой задачи. До настоящего времени эта важная проблема дискретной математики остается открытой.

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

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

Указанным свойствам удовлетворяют так называемые сети Петри, которые разрабатывались специально для моделирования систем, содержащих взаимодействующие параллельные компоненты.

Впервые сети Петри предложил Карл Адам Петри в 1962 г. в своей докторской диссертации “Kommunikation mit Automaten” (“Связь автоматов”), содержащей основные понятия теории связи асинхронных компонент вычислительной системы. В частности, в ней он подробно рассмотрел описание причинных связей между событиями. Его диссертация была посвящена главным образом теоретической разработке основных понятий, с которых начали развитие сети Петри.

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

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