автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Мультиэвристический подход к звёздно-высотной минимизации недетерминированных конечных автоматов

005008919

На правах рукописи

(/ *

Баумгертнер Светлана Викторовна

МУЛЬТИЭВРИСТИЧЕСКИЙ подход К ЗВЁЗДНО-ВЫСОТНОЙ МИНИМИЗАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

2 ФЕВ

Тольятти 2012

005008919

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Мельников Борис Феликсович

доктор технических наук, профессор Сытник Александр Александрович

кандидат физико-математических наук Белозёрова Алла Равильевна

Уральский федеральный университет имени первого Президента России Б. Н. Ельцина

Защита диссертации состоится «21» февраля 2012 года в 13:00 часов на заседании диссертационного совета Д 212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14.

С диссертацией можно ознакомиться в библиотеке Тольяттинского государственного университета, с авторефератом - на сайте диссертационного совета http://edu.tltsu.ru/sites/site.php?s=1496.

Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, Тольятти, ул. Белорусская, 14, ТГУ, диссертационный совет Д 212.264.03.

Автореферат разослан «20» января 2012 года

Учёный секретарь /

диссертационного совета Д 212.264.03 0у

к.п.н., доцент ^ / Пивнева С. В.

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Конечные автоматы и регулярные языки широко применяются во многих приложениях. Например, в лексическом и синтаксическом анализе, программах обработки текста, языках запросов и т. д. В некоторых приложениях важен способ представления конечных автоматов в памяти компьютера. В частности, актуальна минимизация автоматов по различным критериям. Такая минимизация позволяет увеличить эффективность работы конкретного программного приложения. В качестве одного из критериев минимизации конечных автоматов может выступать звёздная высота -максимальная вложенность операции «звезда Клини» (обозначение - *) в эквивалентном регулярном выражении.1

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

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

1 Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986. 159 с.

2 Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. : Мир, 1982.416 с.

3 Lombardy S., Sakarovitch 3. Star Height of Reversible Languages and Universal Automata // 5lh Latin American Theoretical Informatics Symposium. LNCS, 2002. Vol. 2286.

4 Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (НАН Украины). 2006. № 3. С. 32-42.

3 Kirsten D. Distance desert automata and the star height problem // Theoret. Informatics Appl. 2005. №39. P. 455-509.

диссертационной работе алгоритмы могут быть полезны при разработке нового подхода к решению проблемы звёздной высоты.

Таким образом, решение поставленной задачи имеет как теоретическое, так и практическое значение.

В диссертационной работе также приводится описание обобщённых регулярных выражений и предлагается вариант модели обобщённого конечного автомата. Данные варианты конечных автоматов и регулярных выражений позволяют задавать такие описания регулярных языков, которые могут содержать дополнения регулярных множеств. В некоторых случаях (например, при контекстном поиске) описание языка в таком виде удобнее, чем описание языков с помощью классических конечных автоматов и регулярных выражений. Разработан алгоритм поиска обобщённого регулярного выражения для заданного обобщённого конечного автомата, в котором также могут быть применены алгоритмы звёздно-высотной минимизации.

Цель работы

Целью работы является разработка и реализация эвристических алгоритмов для решения задачи звёздно-высотной минимизации недетерминированных конечных автоматов (далее по тексту - «задача»).

Основные задачи исследования:

- Исследование и реализация переборных методов решения рассматриваемой задачи, исследование их эффективности.

- Разработка и реализация эвристик для определения порядка удаления состояний автомата в методе элиминации вершин, позволяющих получить приближённое решение.

- Исследование и реализация методов усреднения количественных результатов работы эвристических алгоритмов, в частности применение динамических оценок состояний автомата.

- Разработка и реализация апуйте-алгоритма, позволяющего найти лучшее решение за указанный промежуток времени или точное решение.

- Проведение вычислительных экспериментов и анализ работы разработанных алгоритмов.

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

Объект исследования

Объектами исследования являются регулярные языки и формализмы для их описания - недетерминированные конечные автоматы и регулярные выражения. ’•

Предмет исследования

Предметом исследования являются алгоритмы построения псевдооп-тимального регулярного выражения по недетерминированному конечному автомату.

Методы исследования

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

Научная новизна

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

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

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

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

4. Разработан программный комплекс, реализующий предложенные модели и алгоритмы.

Практическая значимость исследования

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

Разработанные алгоритмы и модели могут быть полезны в контекстном поиске по нескольким образцам или по регулярному выражению. В

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

Данные алгоритмы также вносят свой вклад в поиск эффективных алгоритмов для решения проблемы звёздной высоты. Кроме того, предложенные подходы могут найти применение и в других предметных областях.

Достоверность результатов

Достоверность результатов подтверждается результатами экспериментов, сравнением результатов работы алгоритмов с применением разработанных эвристик и результатов решения задачи другими методами.

Основные положения, выносимые на защиту:

- Описание эвристик для приближённого решения рассматриваемой задачи.

- Методы усреднения нескольких эвристик. Применение динамических оценок состояний автомата и динамических функций риска.

- Применение незавершённого метода ветвей и границ и вспомогательных эвристик для этого метода в рассматриваемой задаче. Описание соответствующего anytime-алгоритма.

- Определение обобщённого конечного автомата и описание алгоритма построения эквивалентного ему обобщённого регулярного выражения.

- Результаты вычислительных экспериментов, показывающие эффективность разработанных алгоритмов.

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на:

1) XXIV международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, декабрь 2009);

2) XXVI международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, декабрь 2010);

3) VII международной научно-практической конференции «Динамика научных исследований - 2011» (Белгород, июль 2011);

4) тринадцатой международной научно-технической конференции «Моделирование, идентификация, синтез систем управления - 2011» (пос. Канака, Украина, сентябрь 2011);

5) международной научно-практической конференции «Молодёжь и наука: модернизация и инновационное развитие страны» (Пенза, сентябрь 2011).

Публикации

По теме диссертации опубликовано 8 работ, из них 2 - в изданиях, рекомендованных ВАК.

Личный вклад автора

Постановка задач осуществлялась научным руководителем. Описываемые в диссертации эвристики и подходы^ разработанные алгоритмы реше-

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

Структура и объём диссертации

Диссертация состоит из введения, 10 глав, 1 приложения и списка литературы, состоящего из 87 наименований источников отечественных и зарубежных авторов. Общий объём диссертации составляет 123 страницы.

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Вторая глава - основные определения. Здесь приводятся наиболее важные понятия и определения предметной области, такие как регулярные языки, конечные автоматы, регулярные выражения, звёздная высота конечных автоматов и регулярных выражений, а также некоторые вспомогательные определения, связанные с этими понятиями.

Определение 1. Недетерминированным конечным автоматом назовём пятёрку К = (£>, £, 6, Б, /0, где:

- {2 - некоторое конечное множество, называемое множеством состояний (вершин);

- Е - некоторый алфавит; автомат К вводится для задания некоторого языка над этим алфавитом;

- 3 - функция переходов, функция вида 8:<2х(£и{£}) -> Р(<2); значениями этой функции являются подмножества множества 0;,

- 5 - множество стартовых состояний;

- Р - множество финальных состояний.

Определение 2. Пусть задан алфавит 2. Будем говорить, что:

- строка 0 есть регулярное выражение, задающее регулярный язык 0;

- строка а для каждого а е 2 есть регулярное выражение, задающее регулярный язык {а).

Далее, пусть р ид- регулярные выражения, задающие соответственно регулярные языки Р и <2. Тогда: ,

- строка (р + <?) есть регулярное выражение, задающее регулярный язык

р и<2;

- строка (р • q) есть регулярное выражение, задающее регулярный язык

PQ.

■ - строка (р*) есть регулярное выражение, задающее регулярный язык

Р*.

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

Определение 3. Регулярным языком (множеством) называется то и только то, что может быть задано с помощью какого-либо регулярного выражения.

Определение 4. Определим по индукции звёздную высоту регулярного выражения г (обозначим её sh(r)):

- sh(0) = sh{0*) = sh(a) = 0 для всех а е Z-

Пусть гил - произвольные регулярные выражения. Тогда:

- sh((r + s)) = sh((r • s)) = max(sh(r), sh(s)).

Для любого регулярного выражения г.

- sh((r*)) = sh{r) + 1.

Определение 5. Звёздная высота регулярного языка есть минимальная из звёздных высот регулярных выражений, определяющих этот язык.6

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

Четвёртая глава посвящена описанию точного алгоритма построения псевдооптимального регулярного выражения по конечному автомату, который основан на полном переборе.

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

6 Мельников Б. Недетерминированные конечные автоматы. Тольятти : Изд-во ТГУ,

2009.160 с. -

7 Melnikov В., Vakhitova A. Some more on the finite automata II The Korean Journal of Com-putional and Applied Mathematics. 1998. Vol. 5. № 3. P. 495-506.

в котором присутствуют только стартовое состояние, финальное состояние и переход между ними, помеченный искомым регулярным выражением.

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

/(х°) = ттД*),б, х = х(д1,д2,...,дп_2)> й\(*5и^и})• Допустимыми решениями9 являются последовательности состояний автомата (ди д2, Яп-т), в которые входят ровно один раз все состояния автомата, за исключением стартового и финального. (Несложно доказывается, что для любого недетерминированного конечного автомата существует эквивалентный, имеющий ровно 1 вход и ровно 1 выход.) Целевой функцией в данном случае является звёздная высота регулярного выражения, полученного с помощью последовательного удаления состояний автомата в порядке, соответствующем рассматриваемому решению. Целью решения задачи является минимизация этой функции.

Далее рассматривается алгоритм полного перебора поставленной задачи, а также оптимизация для данного метода, позволяющая сократить полный перебор. Алгоритм заключается в переборе всех (п - 2)! (п - количество состояний) перестановок состояний конечного автомата. Для каждой перестановки находится регулярное выражение. Среди них выбирается то, которое имеет наименьшую звёздную высоту.

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

Эвристика 1. Состояния упорядочиваются в порядке возрастания количества проходящих через них циклов.

Эвристика 2. Состояния упорядочиваются в порядке возрастания количества вершин во всех циклах, проходящих через них (то есть по суммарной длине всех циклов).

Эвристика 3. Состояния упорядочиваются в порядке возрастания количества состояний во всех циклах, проходящих через них, но при этом каждое состояние учитывается только один раз.

8 Громкович Ю, Теоретическая информатика. Введение в теорию автоматов, теорию вы-

числимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. БХВ-Пегербург. 2010.336 с. 1 .

9 См. там же.

Эвристика 4. Оценка состояния является произведением значений эвристик 1 и 3.

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

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

Так как данная ситуация близка к ситуации выбора стратегии в недетерминированных играх, рассматривается применение игровых эвристик к нашей задаче. Итоговая динамическая оценка стратегии определяется на основе всех оценок, полученных с помощью разных эвристик.10

Пусть .....хк - оценки различных эвристик,/- функция риска. Тогда

динамическая оценка вычисляется следующим образом:

$]*,/(*,)

Фч....хк)-—к---------•

5>,>

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

Например, приемлемые решения часто получаются при задании статической функции риска/= 1 -0,6х.

Другой вариант - функции риска с динамической сменой стратегии:

- если получена оценка, близкая к максимальной, то мы учитываем возможность неблагоприятных факторов, поэтому функция риска убывает;

Мельников Б., Радионов А. О выборе стратегии в недетерминированных антагонистических играх//Программирование (Известия РАН). 1998. № 5. С. 55-62.

Мельников Б., Романов Н. Ещё раз об эвристиках для задачи коммивояжёра // Теоретические проблемы информатики и ее приложений. Саратов : Изд-во СГУ. 2001 Вып 4 С. 81-92. ‘ '

- если полученная оценка имеет «приблизительно среднее» значение, то функция риска близка к константе;

- если оценка, данная эвристикой, близка к минимуму, то, наоборот, мы учитываем вероятность благоприятного исхода случайных факторов -соответственно функция риска возрастает.

Возможна такая функция, применявшаяся автором:11

0,8(1 -*)2 +0,2, если х~1 1-0,6дг, если х>0

т=

- 0,2л-2 +1, если х » 0

1, если х < 0

-0,8(1-я)2 +1, если * — —1

(при этом функция динамически изменялась для всех возможных значений).

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

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

Будем называть правой задачей очередного шага метода ветвей и границ задачу, полученную при уменьшении размерности. Другую альтернативу, т. е. когда принимается решение об отсутствии некоторого элемента в оптимальном решении, назовём, соответственно, левой задачей очередного шага.12

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

11 Мельников Б. Эвристики в программировании недетерминированных игр И Программирование (Известия РАН). 2001. № 5. С. 63-80.

12 Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (НАН Украины). 2006. № 3. С. 32-42.

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

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

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

Определение 6. Определим обобщённый конечный автомат следующим образом:

С = (б, 1,^,5, Л 7’,^"", Г"), (1)

где <2 - конечное множество состояний автомата;

X - рассматриваемый алфавит;

ё - функция переходов д: £)х(1и{£}) —> Р(());

5’ с б - множество стартовых состояний;

Т”1 с 2 - множество финальных состояний;

Т cN - конечное множество, где N— множество натуральных чисел;

£‘а и - функции, определяемые как , £ош: 0 хТ <2-

В рамках нашей модели мы будем считать, что (V/€ Т)(31 д,ре 0(Г(<7,0 = р) И (V/е Г)(3!д,ре <2)(Г"(<М) = р) ■

Определим язык, задаваемый обобщённым конечным автоматом. V/ е Т рассмотрим состояния я,, /¡,щ,ом1 множества б, такие что =

Определение 7. Пусть О - обобщённый конечный автомат (1). Для некоторых 5',^' с б обозначим К(Б',Р') = ((2, Е, 5,5', Т7'), К, - Я({з,},{//}).

Определение 8. Пусть б - обобщённый конечный автомат (1). Тогда К(0) ~ ((), Е, 3,5,Р) будет соответствовать «обычному» конечному автомату.

13 Сапомаа А. Жемчужины теории формальных языков. М.: Мир, 1986.159 с.

Определение 9. Язык ЦСг)р,ля автомата (1) определяется следующим образом:

Ц0) = ЦК(О)11

У Ц АГ(5, {т,} ШК,)ЦКаоШ,}, ^))

.16 т

Очевидно, что язык, определяемый обобщённым конечным автоматом, является регулярным.14

Определение 10. Пусть С7 - обобщённый конечный автомат (1). Для некоторого к 6 Г обозначим б.* обобщённый конечный автомат, полученный из б в результате удаления всех значений функций С°“‘, где вторым аргументом является к.

0_к = (й, Ъ,д, 5, *■, Г.,, Й , СГ), (2)

где: Г* =Т\{к}\

П (9.0 = С'" (9.0 Для всех д е 0,1 е Г к;

£7 (9.0 = Г“' (9,0 Для всех ^ е б, I е Г ^.

Определение 11. Определим обобщённое регулярное выражение. К операциям *, • , + для регулярных выражений добавляется операция дополнения ~.

Пусть р - регулярное выражение, определяющее язык Р. Тогда обобщённое регулярное выражение (~р) определяет язык Р = X* \ Р, где X - рассматриваемый алфавит.

В диссертации рассматривается алгоритм построения обобщённых регулярных выражений, эквивалентных обобщённым конечным автоматам. Здесь будем рассматривать автоматы, в которых вторым, аргументом функции переходов является не символ алфавита, а обобщённое регулярное выражение. Далее для всех г е Т:

1. Строим конечный автомат £({$,-},{/;}), удаляем недостижимые и

бесполезные состояния.

2. Находим для него эквивалентное регулярное выражение г.

3. Получаем автомат С_, согласно (2).

4. Добавляем переход <5(ш, ,-/■) = ом/,..

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

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

6. Применяя алгоритм последовательного удаления вершин, получаем обобщённое регулярное выражение, эквивалентное обобщённому конечному автомату (1).

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

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

Будем генерировать некоторое множество конечных автоматов определённой размерности. Для данных автоматов будем строить регулярные выражения различными методами и для каждого метода вычислять среднее значение некоторых характеристик полученных решений. Это позволит сравнить различные подходы к построению регулярного выражения по конечному автомату и сделать выводы об их эффективности.

Таблица 1

Зависимость среднего времени поиска оптимального решения от размерности автомата для метода полного перебора ___________________и апуНте-алгоритма___________________

Количество состояний автомата Среднее время решения задачи (в секундах):

методом полного перебора anytime-алгоритма

3 0,0004 0,0008

4 0,0012 0,0017

5 0,014 0,015

6 0,12 0,07

7 1,15 0,48

8 14,72 4,93

9 274,47 51,68

10 3297,15 498,23

15 Champamaud J„ Hansel G., Paranthoen Т., Ziadi D. Random generation models for NFA's // Journal of Automata, Languages and Combinatorics. 2004. № 9. P. 203-216.

Zijl L. van, Raitt L. Random Generation of Unary DFAs // South African Computer Journal. 2008. V. 41. P. 57-63.

Мельников Б., Пивнева С., Рогова О. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике (СПбГУ). 2010. Т. 6. С. 74-82.

Для автоматов с количеством состояний от 3 до 10 были получены точные решения методом оптимизированного полного перебора и точные решения апуйше-алгоритма. Вычислено среднее время поиска оптимального регулярного выражения для автоматов различной размерности. Результаты приведены в табл. 1, где видно, что время точного решения задачи апуйте-алгоритма значительно меньше времени решения методом полного перебора.

Для автоматов с количеством состояний от 3 до 10 были найдены точные решения, для автоматов размерности от 3 до 13 были получены приближённые решения с применением эвристик. Для каждого из данных методов было вычислено среднее значение звёздной высоты полученных регулярных выражений. Результаты эксперимента приведены в табл. 2.

Таблица 2

Зависимость среднего значения звёздной высоты от размерности автомата для приближённых решений,

'______полученных эвристическими методами_______

Количество состояний автомата Среднее значение звёздной высоты для регулярных выражений, полученных методами:

Точное решение Эвристика 1 Эвристика 2 Эвристика 3 Эвристика 4 Случайное решение

3 1,51 1,51 1,51 1,77 1,51 1,84

4 1,89 2,04 2 2,51 2,03 2,51

5 2,25 2,41 2,46 3,04 2,44 3,16

6 2,69 3,03 3,08 3,96 3,02 3,9

7 3,18 3,72 3,77 4,73 3,72 4,84

8 3,75 4,37 4,41 5,56 4,37 5,84

9 4,48 5,14 5,13 6,68 5,14 6,74

10 5,17 5,97 5,94 7,59 5,97 7,85

11 _ 6,94 6,9 8,81 6,94 8,78

12 _ 7,8 7,74 9,61 7,8 9,65

13 - 8,5 8,58 10,6 8,5 10,7

Для автоматов размерности от 3 до 12 были получены приближённые решения с применением динамических оценок, а также приближённые решения апуите-алгоритма с различным ограничением по времени. Вычислена средняя звёздная высота полученных решений (табл. 3).

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

Зависимость среднего значения звёздной высоты от размерности автомата для различных методов решения

Количество состояний автомата Среднее значение звёздной высоты для решений:

Точное решение С применением динамических оценок Anytime-алгоритм с ограничением времени:

1с Зс 5с Юс 30с 60с

3 1,51 1,51 1,51 1,51 1,51 1,51 1,51 1,51

4 1,89 2,01 1,89 1,89 1,89 1,89 1,89 1,89

5 2,25 2,46 2,25 2,25 2,25 2,25 2,25 2,25

6 2,69 3,09 2,69 2,69 2,69 2,69 2,69 2,69

7 3,18 3,7 3,18 3,18 3,18 3,18 3,18 3,18

8 3,75 4,61 3,79 3,76 3,75 3,75 3,75 3,75

9 4,48 5,33 4,55 4,5 4,5 4,49 4,48 4,48

10 5,17 6,16 5,38 5,34 5,32 5,28 5,22 5,19

11 - 6,94 6,46 6,27 6,22 6,13 5,93 5,82

12 - 7,8 7,69 7,47 7,34 7,26 7,1 6,97

Рис. 1. Зависимость среднего значения звёздной высоты от времени решетя апуйте-алгоритма для автоматов размерности 10

Из результатов видно, что эвристические методы работают довольно хорошо на задачах небольшой размерности. Решение апуйте-алгоритма даже за достаточно короткие промежутки времени даёт хорошее приближение к оптимальному решению по сравнению с методом динамических оценок.

В десятой главе описывается реализация разработанных алгоритмов. Приводится описание наиболее важных функций, классов и структур данных. ' ,

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Предложены эвристические алгоритмы для поиска приближённых решений задачи построения псевдооптимального регулярного выражения по заданному конечному автомату.

2. Рассмотрены различные варианты усреднения количественных результатов работы эвристических алгоритмов. Сделан вывод о том, что в рассматриваемой задаче данные методы не улучшили результаты работы алгоритмов и при дальнейшей разработке алгоритмов для задачи звёздновысотной минимизации конечных автоматов нецелесообразно придавать большое значение усреднению эвристик.

3. Предложен апуПте-алгоритм построения псевдооптимального регулярного выражения по заданному конечному автомату, основанный на мультиэвристическом подходе. Данный алгоритм предназначен для поиска псевдооптимального решения с заданным ограничением по времени, а также для точного решения рассматриваемой задачи. Время поиска точного решения увеличивается в зависимости от размерности задачи гораздо медленнее, чем время решения переборными методами. За достаточно короткие промежутки времени алгоритм позволяет получить решение, близкое к оптимальному.

4. Разработан комплекс программ, реализующих предложенные алго-

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

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

4. ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК:

1. Баумгертнер С., Мельников Б. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных

автоматов // Вестник Воронеж, гос. ун-та. Серия: системный анализ и информационные технологии. - 2010. - № 1. - С. 5-7.

2. Баумгертнер С. Дополнительные эвристики в задаче звёздновысотной минимизации недетерминированного конечного автомата // Вектор науки Тольяттинского гос. ун-та. - 2010. - № 3 (13). - С. 37-39.

Публикации в рецензируемых научных журналах и изданиях:

3. Баумгертнер С. Мультиэвристический подход в задаче звёздновысотной минимизации // Математические методы и информационные технологии в экономике, социологии и образовании : сб. ст. XXIV между-народ. научно-технич. конф. - Пенза : Приволжский дом знаний, 2009. -С. 107-110.

4. Баумгертнер С. Об одном подходе к задаче звёздно-высотной минимизации недетерминированных конечных автоматов // Математические методы и информационные технологии в экономике, социологии и образовании : сб. ст. XXVI международ. научно-технич. конф. - Пенза : Приволжский дом знаний, 2010. - С. 208-211.

5. Баумгертнер С. Мультиэвристический подход к проблеме звёздновысотной минимизации недетерминированных конечных автоматов / С. Баумгертнер, Б. Мельников, С. Пивнева // Математические и компьютерные методы в технических, гуманитарных и общественных науках : монография. - Пенза : Приволжский дом знаний, 2011. - С. 101-112.

6. Баумгертнер С., Мельников Б. Anytime-алгоритм поиска псевдооп-тимального регулярного выражения для заданного конечного автомата // Dynamika naukowych badan - 2011 : mater. VII miedzynarod. naukowi-praktycz. konf. 7—15 lipca 2011 roku. - Przemysl : Nauka I studia. - Vol. 18. -P. 16-18.

7. Баумгертнер С., Мельников Б. Поиск псевдооптимального регулярного выражения для недетерминированного конечного автомата I/ Молодёжь и наука: модернизация и инновационное развитие страны : матер, научно-практич. конф. (г. Пенза, 15-16 сентября 2011 г.). Ч. 1. - Пенза : Изд-во ПГУ, 2011. - С. 113-116.

8. Баумгертнер С., Мельников Б. Об одном подходе к «звёздновысотной» минимизации конечного автомата // Моделирование, идентификация, синтез систем управления : сб. тез. четырнадцатой международ. на-учно-технич. конф. 11-18 сентября 2011 г. - Донецк : Изд-во Ин-та прикладной матем. и механики НАН Украины, 2011. - С. 196-197.

Подписано в печать с электронного оригинал-макета 16.01.2012. Бумага офсетная. Печать трафаретная.

Уел. печ. л. 1,0. Тираж 120 экз. Заказ 52/02.

Отпечатано в Издательско-полиграфическом центре Поволжского государственного университета сервиса. 445677, г. Тольятти, ул. Гагарина, 4. rio@tolgas.ru, тел. (8482) 222-650.

61 12-1/615

Тольяттинский государственный университет

На правах рукописи

Баумгертнер Светлана Викторовна

МУЛЬТИЭВРИСТИЧЕСКИЙ ПОДХОД К ЗВЁЗДНО-ВЫСОТНОЙ МИНИМИЗАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ

Специальность 05.13.18 -«Математическое моделирование, численные методы и комплексы программ»

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д. ф.-м. н., профессор Мельников Б.Ф.

Тольятти - 2012

Содержание

Глава 1. Введение....................................................................................4

1.1. Подходы к решению задач дискретной оптимизации..............................11

1.2. Основные вопросы и результаты, связанные с проблемой звёздной высоты.....................................................................................................15

1.3. Актуальность темы.......................................................................................19

Глава 2. Фундаментальные понятия предметной области...........23

2.1. Формальные языки и конечные автоматы..................................................23

2.2. Регулярные выражения.................................................................................26

2.3. Звёздная высота регулярных выражений...................................................27

2.4. Метод ветвей и границ.................................................................................28

Глава 3. Эквивалентность конечных автоматов и регулярных выражений. Специальное доказательство теоремы Клини......................................................................................30

3.1. Построение конечного автомата, эквивалентного заданному регулярному выражению.......................................................................................30

3.2. Построение регулярного выражения, эквивалентного заданному конечному автомату. Теорема Клини..................................................................32

Глава 4. Преобразование конечного автомата к регулярному выражению. Точный алгоритм построения оптимального регулярного выражения по заданному конечному автомату.............................................................................35

4.1. Метод последовательного удаления вершин.............................................35

4.2. Задача звёздно-высотной минимизации недетерминированного конечного автомата в терминах дискретного программирования...................37

4.3. Метод оптимизированного полного перебора...........................................38

Глава 5. Эвристические алгоритмы для приближённого решения задачи поиска псевдооптимального регулярного выражения по конечному автомату..................................................41

Глава 6. Методы усреднения эвристик. Динамические оценки состояний автомата................................................................48

Глава 7. Апуйте-алгоритм.................................................................54

звёздно-высотной минимизации недетерминированного конечного автомата..............................................................................54

7.1 Незавершённый метод ветвей и границ.......................................................54

7.2 Пошаговое описание апу1лте-алгоритма.....................................................58

Глава 8. Обобщённые конечные автоматы и обобщённые регулярные выражения. Алгоритм построения обобщённого регулярного выражения для заданного обобщённого конечного автомата..................... ................................63

8.1. Основные определения.................................................................................63

8.2. Алгоритм построения обобщённого регулярного выражения, эквивалентного обобщённому конечному автомату..........................................65

Глава 9. Описание вычислительных экспериментов и их результатов............................................................................................67

9.1. Алгоритм генерации случайного конечного автомата.............................67

9.2. Результаты вычислительных экспериментов.............................................68

Глава 10. Описание программной реализации разработанных алгоритмов................................................................74

Заключение............................................................................................84

Приложение............................................................................................85

Литература...........................................................................................116

Глава 1. Введение

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

При этом в различных приложениях желательно использовать разные способы представления регулярного языка - а для каждого из этих способов очень часто важным является максимально экономичное задание.

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

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

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

Впервые проблема звёздной высоты была поставлена в 1963 г., а первое решение опубликовано в 1988 г. - см. [71]. В [85] решение из [71] было названо «чрезвычайно сложным». А в [76] это решение охарактеризовано следующим образом. Процедура, предложенная Хашигучи, приводит к вычислениям, которые невозможны даже для маленьких примеров. Например, если язык Ь определяется автоматом с 4 состояниями и вложенностью циклов 3, то наименьшее количество языков, ко-

igio СЮ10" 1'

торые будут сравниваться с L, равно (10 )

Более удачное решение проблемы звёздной высоты получено в [75]. В этой работе рассматриваются т.н. distance desert automata. При этом оба варианта (т.е. т.н. distance automata и desert automata, специальная комбинация которых и даёт необходимые distance desert automata) могут рассматриваться как специальные расширения недетерминированных конечных автоматов. С помощью описанного в [75] решения мы можем оценить сложность важных вспомогательных алгоритмов, которые применяются при решении проблемы. Согласно [75], для заданного регулярного языка L и натурального числа h существует алгоритм, определяющий, не превосходит ли звёздная высота языка L значения h. Поэтому алгоритм, вычисляющий звёздную высоту языка L, состоит в последовательном поиске соответствующего ответа для значений h = 1,2, ... И так как отсутствуют априорные границы для значения h,

(Ю10 )

оценка стоимости может быть вычислена только для вспомогательных алгоритмов - но не для всего алгоритма в целом.

Задачу поиска звёздной высоты регулярного языка можно представить в виде двух задач:

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

2. Построение регулярного выражения с наименьшей звёздной высотой по полученному конечному автомату.

В данной работе рассматривается вторая задача. А именно, будет предложен апуйте-алгоритм ([34] и др.) построения псевдооптималъного регулярного выражения для заданного недетерминированного конечного автомата. Эта задача тесно связана с общей проблемой звёздной высоты, и поэтому предложенные автором алгоритмы могут быть применены при построении общего алгоритма решения проблемы звёздной высоты.

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

Основные задачи исследования:

• Исследование и реализация переборных методов решения рассматриваемой задачи, исследование их эффективности.

• Разработка и реализация эвристик для определения порядка удаления состояний автомата в методе элиминации вершин, позволяющих получить приближённое решение.

• Исследование и реализация методов усреднения количественных результатов работы эвристических алгоритмов, в частности, при-

менение динамических оценок состояний автомата.

• Разработка и реализация апуйте-алгоритма, позволяющего найти лучшее решение за указанный промежуток времени или точное решение.

• Проведение вычислительных экспериментов и анализ работы разработанных алгоритмов.

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

Объектами исследования являются регулярные языки и способы их представления: регулярные выражения и конечные автоматы.

Научная новизна

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

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

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

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

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

4. Разработан программный комплекс, реализующий предложенные модели и алгоритмы.

Практическая значимость исследования

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

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

Данные алгоритмы также вносят свой вклад в поиск эффективных алгоритмов для решения проблемы звёздной высоты. Кроме того, предложенные подходы к разработке эвристических алгоритмов могут найти применение и в других предметных областях.

Краткое содержание диссертации

Диссертация имеет следующую структуру.

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

Вторая глава — основные определения. Здесь приводятся наиболее важные понятия и определения данной предметной области - такие как регулярные языки, конечные автоматы, регулярные выражения, звёздная высота регулярных выражений и конечных автоматов, а также другие определения, связанные с этими понятиями.

В третьей главе приводится вариант доказательства эквивалентности конечных автоматов и регулярных выражений, необходимый для описания алгоритмов. Для этого рассматривается специальное доказательство теоремы Клини [84].

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

Далее рассматривается алгоритм полного перебора, в котором может применяться один из приведённых выше алгоритмов, а также оптимизация для данного метода, позволяющая сократить полный перебор.

В пятой главе рассматриваются эвристические алгоритмы, необ-

ходимые для приближённого решения задачи. Для определения эвристик рассматриваются различные характеристики, вычисляемые по состояниям автомата.

Эвристика 1. Состояния упорядочиваются в порядке возрастания количества проходящих через них циклов.

Эвристика 2. Состояния упорядочиваются в порядке возрастания количества вершин во всех циклах, проходящих через них (то есть по суммарной длине всех циклов).

Эвристика 3. Состояния упорядочиваются в порядке возрастания количества состояний во всех циклах, проходящих через них, - но при этом каждое состояние учитывается только один раз.

Эвристика 4. Оценка состояния является произведением значений эвристик 1 и 3.

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

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

Т.к. данная ситуация близка к ситуации выбора стратегии в недетерминированных играх, рассматривается применение в нашей задаче игровых эвристик.

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

вольно близкими к оптимальным.

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

В восьмой главе описываются классические обобщённые регулярные выражения и введённые автором обобщённые конечные автоматы. Рассматривается алгоритм построения обобщённого регулярного выражения по обобщённому конечному автомату.

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

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

1.1. Подходы к решению задач дискретной оптимизации

Рассматриваемая нами задача относится к задачам дискретной оптимизации. Большинство рассматриваемых различными авторами задач дискретной оптимизации являются труднорешаемыми (см. подробную библиографию, напр., в [73]). Труднорешаемыми задачами называются либо такие, которые не могут быть решены за полиномиальное время (т.е. за время, ограниченное полиномиальной функцией, зависящей от размера входных данных), либо такие, для которых пока не найдены алгоритмы, решающие их за полином�