УДК 519.688 ПАРАЛЛЕЛЬНЫЕ ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ ЗАДАЧИ ВЕРШИННОЙ МИНИМИЗАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ А. В. <...> Цыганов, О. И. Булычов Тольяттинский государственный университет Поступила в редакцию 06.04.2010 г. Аннотация. <...> В статье рассматриваются параллельные версии генетического алгоритма и метода имитационной нормализации для задачи вершинной минимизации недетерминированных конечных автоматов. <...> Предложенные алгоритмы реализованы в виде проекта с использованием библиотеки параллельных метаэвристик HeO. <...> In the present paper, we consider parallel versions of the genetic algorithm and the simulated annealing method for the state minimization of nondeterministic finite automata. <...> The proposed algorithms are implemented as a project that uses the library of parallel metaheuristics HeO. <...> ВВЕДЕНИЕ Конечные автоматы (КА) находят широкое применение в системах обработки информации. <...> Во многих приложениях важную роль играет способ представления КА в памяти компьютера. <...> Прежде всего, перед разработчиками встаёт вопрос о выборе между двумя эквивалентными (с точки зрения описываемых ими языков) типами автоматов: недетерминированными конечными автоматами (НКА) и детерминированными конечными автоматами (ДКА). <...> В процессе работы с обоими типами КА может потребоваться их минимизация, которая может выполняться по разным критериям, например, по числу состояний (вершин), по числу переходов и др. <...> Для ДКА минимизация числа состояний может быть выполнена за полиномиальное время, в то время как для НКА аналогичная задача является NP-трудной. <...> ПОСТАНОВКА ЗАДАЧИ Задача вершинной минимизации НКА состоит в построении такого автомата, который описывал бы тот же самый регулярный язык, что и исходный автомат, но имел бы при этом меньшее число состояний. <...> По двум КА, ассоциированным с исходным НКА, строится специальная таблица (матрица RAM в [1], отношение # в [2]), для которой минимизируется число прямоугольных блоков, содержащих все ее непустые элементы, затем по блокам, входящим в найденное покрытие, строится НКА. <...> Если язык построенного <...>