Агибалов Г. - О прикладной дискретной математике в ТГУ
Дается краткий обзор результатов научных исследований по прикладной дискретной математике в ТГУ за 1970-1999 гг.
Термин дискретная математика начал входить в научный обиход на рубеже 50-х и 60-х гг. XX в. для обозначения системы новых математических дисциплин, таких, как теория булевых функций, теория конечных автоматов, теория графов, теория кодирования и др.
Иногда в него вкладывают и более широкий смысл, полагая, что если в основе математики лежит понятие множества, то в основе дискретной математики лежит понятие дискретного множества. В этом смысле к дискретной математике относят и теорию чисел, и математическую логику, и всю конечную алгебру, и некоторые другие классические разделы математики. Мы этого делать не будем и под дискретной математикой далее будем подразумевать именно современную дискретную математику.
Ее основоположником следует считать, по-видимому, Клода Шеннона - американского математика и инженера, опубликовавшего в 1938 г. первые теоремы о свойствах булевых функций и переключательных схем.
Справедливости ради следует заметить, что тремя годами раньше некоторые схожие результаты получил В. И. Шестаков, доцент физфака МГУ, но смог опубликовать их лишь в 1941 г., т.к. эти результаты обосновывали применимость логики в технике, чего не могло быть по меркам тогдашней отечественной идеологии.
Позднее (1949 г.) К. Шеннон ввел в рассмотрение функцию, получившую в науке его имя, - функцию Шеннона, ставшую на все последующие годы предметом многочисленных исследований (в том числе и наших) в разных областях дискретной математики. В наиболее общем виде она определяется следующим образом.
Пусть имеются два множества -A и B и бинарное отношение рс ЛхЕ.
Пусть также каждый элемент b в B характеризуется положительным числом /(b) - сложностью b. Тогда функция Шеннона есть
L(A)=max min /(b);
aeA (beB, apb).
Целью данной публикации является краткий обзор результатов исследований по прикладной дискретной математике в Томском государственном университете за последние 30 лет (1970-1999 гг.). Освещаемые результаты отнесены условно к следующим направлениям.
1. Компьютерная дискретная математика:
1.1 автоматизация синтеза дискретных автоматов;
1.2. технология решения задач дискретной математики.
2. Теория конечных автоматов:
2.1. эксперименты с автоматами;
2.2. декомпозиция автоматов.
3. Дискретные автоматы на полурешетках.
4. Полурешеточная теория интегральных схем.
5. Диагностика дискретных автоматов:
5.1. диагностика автоматных сетей и недетерминированных автоматов;
5.2. диагностика логических схем.
6. Логический синтез.
По этим направлениям издано 8 монографий и 2 сборника статей, защищено 10 кандидатских и 5 докторских диссертаций, опубликовано около 100 статей в центральных и зарубежных журналах и представлено более 100 докладов на международных и отечественных научных конференциях. Часть этих публикаций отражена в прилагаемом списке литературы.
Автоматизация синтеза дискретных автоматов
В ТГУ исследования по дискретной математике были начаты в конце 50-х гг. тогдашним аспирантом РФФ Аркадием Дмитриевичем Закревским. Тот факт, что эти исследования зародились на РФФ, а не на ММФ, наложило определенный отпечаток на их характер. Изначально они велись как прикладные, т.е. вызывались не потребностями самой математики, но ее применениями главным образом к синтезу дискретных автоматов (тогда - релейных схем управления). Прикладной характер исследований выразился и в том, что их результатами должны были стать алгоритмы решения задач дискретной математики, аттестованные в эксперименте на вычислительной машине (ЭВМ).
Фактически уже тогда речь шла о создании нового направления в математике - компьютерной дискретной математики. А.Д.
Закревский заложил первые кирпичи в фундамент этой науки.
Чтобы правильно понять и оценить действительное значение этого вклада, надо обратить внимание на то, что в дискретной математике мало имеют дело с числами, все больше - с подмножествами множеств нечисловой природы. Это значит, что классические математические средства вычислений, включая базовые - сложение, умножение, дифференцирование и т.п., в компьютерной дискретной математике мало полезны.
Здесь нужны другие математические операции, и А.Д. Закревский их создал [1].
Для этого он сначала предложил представлять системы подмножеств конечных множеств при помощи булевых и так называемых троичных матриц, а затем разработал иерархическую систему математических операций над такими матрицами и эффективные алгоритмы их выполнения. Система охватывает широкий спектр операций: от простейших (нахождение минимального столбца и максимальной строки) до предельно сложных (кратчайшее покрытие булевой матрицы или минимальное разбиение множества ее столбцов на совместимые подмножества, например).
Фундаментальное и прикладное значение этой системы состоит в том, что через операции в ней легко выражаются алгоритмы решения многих задач как в самой дискретной математике, так и в ее приложениях, и не только к синтезу дискретных автоматов. К числу таких задач относятся: минимизация и функциональная разделимость булевых функций, минимизация конечных автоматов и кодирование их состояний, логический синтез схем и тестов для них, раскраска графов, градостроительные задачи размещения, трассировки и многие другие. Полезность этой разработки вскоре была доказана на практике, когда на ЛЯПАСе - русском языке программирования, разработанном под руководством А.Д.
Закревского [2], - был создан ряд систем автоматического синтеза и диагностики дискретных автоматов, основу математического обеспечения в ко-торых составила именно данная система операций (см., например, [3-6]). В 70-80-е гг. эти автоматические системы широко применялись на предприятиях МЭП и МРП.
А.Д. Закревский одним из первых (если не самым первым) в мировой науке предложил и осуществил на практике технологию статистического исследования алгоритмов в эксперименте на ЭВМ, ставшую отличительной особенностью и обязательным элементом деятельности его научной школы, в том числе и в ТГУ в рассматриваемый период.
За малым исключением, все публикации в списке литературы, содержащие оригинальные алгоритмы, содержат и результаты такого исследования последних. Примером этого могут служить работы [7,8].
Технология решения задач дискретной математики
Многие оптимизационные задачи дискретной математики формулируются как следующая задача о кратчайшем допустимом разбиении (ЗКДР): даны конечное множество X и ограничения P на его подмножества; требуется найти разбиение X на подмножества (блоки), удовлетворяющие P (допустимое разбиение), с наименьшим количеством блоков (кратчайшее разбиение). Примеры: минимальная раскраска графа, кратчайшее разбиение системы чисел на подсистемы с ограниченной суммой, кратчайшее разбиение сети на подсети ограниченной сложности или структуры, кратчайшее покрытие булевой матрицы, кратчайшее разбиение системы формул на подсистемы с ограниченными количественными характеристиками, кратчайшее покрытие схем свободными модулями и др.
Конкретные (с конкретными Хи P) ЗКДР, как правило, не допускают иных методов решения, кроме переборных. К числу последних относится и метод сокращенного обхода дерева поиска [9,10], разработанный нами для решения всевозможных ЗКДР. Вершины и ребра дерева поиска в нем сопоставляются подмножествам в разбиваемом множестве X, причем ребра - допустимым подмножествам, корень дерева - множеству X, его листья - пустому множеству, и разность множеств, соответствующих концам ребра, соответствует ребру. Таким образом, всякий путь от корня дерева к листу сопоставлен допустимому разбиению множества X, а всякий кратчайший такой путь - решению задачи.
Метод сокращенного обхода дерева поиска принадлежит к точным методам последовательных приближений и представляет собой общий алгоритм поиска с возвращением и сохранением лучшего приближения. Он содержит средства сокращения поиска - алгоритм начального приближения, алгоритм перечисления, операцию сокращения и функцию нижней оценки.
Алгоритм начального приближения - это эвристический алгоритм, позволяющий быстро построить некоторое допустимое, но не обязательно кратчайшее разбиение, принимаемое за начальное. Алгоритм перечисления и операция сокращения обеспечивают процесс ветвления в каждой вершине дерева поиска. Первый порождает некоторую достаточную совокупность очередных альтернативных элементов искомого решения, а вторая выбрасывает из нее лишние элементы. С их помощью для каждой достигаемой вершины дерева поиска порождается некоторая такая часть его ребер, исходящих из этой вершины, в которой есть хотя бы одно ребро, которое принадлежит хотя бы одному кратчайшему пути, проходящему через данную вершину и соединяющему корень с листом дерева.
С помощью функции нижней оценки производится отсечение каждого такого поддерева дерева поиска, для которого сумма длины пути от корня дерева к корню поддерева и значения функции нижней оценки для длины кратчайшего пути в последнем не меньше длины известного на данный момент наиболее короткого допустимого разбиения.
Эти средства сокращения входят в метод как его параметры. Для решения конкретной ЗКДР надо подобрать их подходящими данной задаче и подставить в формулировку метода.
Результатом и будет алгоритм решения этой ЗКДР. Его эффективность определяется сокращающими способностями подобранных параметров, т.е. степенью близости начального разбиения к кратчайшему, степенью точности нижней оценки и степенью ветвления вершин дерева.
Пользуясь данной технологией, нам удалось построить наиболее эффективные (на момент их создания) решающие алгоритмы для многих оптимизационных задач дискретной математики и ее приложений, в том числе для разбиения системы чисел, для раскраски графа, для покрытия схем свободными модулями, для разбиения схем на подсхемы ограниченной сложности, для синтеза схем в различных программируемых базисах - ПМВ, ППЗУ, ПЛМ, ПМЛ, для распределения элементов схем по ячейкам компоновочного пространства и др. Эти результаты отражены в монографии [10], статьях [9, 11-29] и в докладах на конференциях.
Теория конечных автоматов
L(pn (k))
2.1. Эксперименты с автоматами
Конечный автомат определяется пятеркой S=(X, Q, Y, ц, ф), где X, Q, Y - конечные множества, X - входной алфавит, Q - множество состояний, Y
- выходной алфавит, ц ф- функции, ц - функция переходов, ц/XxQ^Q, ф - функция выходов, ф. XxQ^Y. В частичном автомате функции ци ф определяются на части множества XxQ.
Инициальный автомат определяется как S=(X, Q, Y, ц, ф qo), где q0 - начальное состояние, q0eQ.
Реакция инициального автомата S на входную последовательность a=x(1)x(2)...x(t)... есть выходная последовательность e=y(1)y(2)..y(t)..., где У(і)=фх(і), q(t)),
q(t+1)=y(x(i), q(t)), t=1, 2,...q(1)=qo.
В частичном автомате она может быть не определена, и тогда входная последовательность а считается недопустимой для S; в противном случае - допустимой.
Автономный автомат удовлетворяет условию ІХІ=1. Его реакция - периодическая последовательность. В комбинационном автомате ІQІ =1 и y(t)=q(x(i)) для любого t.
Линейный автомат над конечным полем F определяется соотношениями
X=Fk, Q=F", Y=Fm, ip(x,q)=A -q+C-x, A=(ai:j)nxn, C=(cj)nxk, qix,q)=Bq+Dx, B=(bij)mXn, D=(dj)mxk, где натуральные числа k, n и m называются размерностями соответственно входного символа, состояния и выходного символа автомата.
Нормальная периодическая последовательность (н.п.п.) с параметрами k2 и n1 - это периодическая последовательность p=y(1)y(2)... с периодом k", составленная из чисел множества {0, 1,..., k-1}, в которой все слова y(i)y(i+1)...y(i+n-1) для i=1, 2,..., k" различны. Она порождается автономным автоматом с kn состояниями.
Эксперимент (простой) - это любая пара слов (а,Р) в некоторых алфавитах. Его длина /(а,Р) - это длина слова а. Эксперимент (а,Р) присущ инициальному автомату S, если а - входная последовательность для S и р - реакция на нее автомата S.
Автоматы S и S' различимы (S/S'), если существуют эксперименты (а,Р) и (а,Р'), присущие S и S соответственно, где Р/Р'. Эксперимент, присущий автомату SeK, распознает автомат S в классе K, если он не присущ никакому автомату SeK для S ' /S.
Функция Шеннона для длины распознающего эксперимента вводится как
L(K)=max min /(а,Р)
SeK (а, Р) распознает S.
Ниже используются следующие обозначения. XN
- класс всех линейных автономных инициальных автоматов с размерностью состояния N; Х^,п - класс всех линейных инициальных автоматов с размерностью входного символа - k и состояния - n; pn(k) -класс всех инициальных автономных автоматов, порождающих н.п.п. с параметрами n и k. Известно, что |pn(k) I =(k!)m, где m=k" -1.
Теорема [31] (впервые в [32]). L(Xn)=2N.
Теорема [33]. 2n L(Xk,n) 2n+k(n+1).
Теорема [34] (впервые в [35]).
2" -2, если k=2 и n=2, 3, 4, kn -1 в остальных случаях.
Алгоритмы построения кратчайшего распознающе-го эксперимента для автоматов в pn(k) даны в [36,37].
Кратный эксперимент является конечным множеством простых экспериментов. Он присущ автомату S, если каждый простой эксперимент в нем присущ S. Его длина равна сумме длин простых экспериментов в нем, а высота - наибольшей из последних длин.
Он проверяет автомат S в классе K, если для любого автомата S’ в последнем, такого, что S' /S, в нем есть простой эксперимент с допустимой для S и S’ входной последовательностью, присущий S и не присущий S’.
В [38] решена задача синтеза конечного автомата с минимальным числом состояний, которому присущ заданный кратный эксперимент. Этот результат приведен также в [30.
С. 35-37]. В [39] через параметры произвольного частичного автомата описан класс всюду определенных автоматов, в котором кратный эксперимент фиксированной высоты проверяет этот автомат.
В [40] сформулированы необходимые и достаточные условия, при которых произвольный простой эксперимент проверяет инициальный автомат в классе автоматов с тем же или меньшим числом состояний.
Декомпозиция автоматов
Автоматы можно соединять в сеть каскадно, параллельно, последовательно, параллельно-последовательно и с обратными связями.
Поведение (статическое) автомата S=(X, Q, Y, ц, ф) это множество всех четверок (b,r s v), где beX, r, seQ, veYи s=^b,r), ?=фЬ, r).
Полугруппа автомата S - это полугруппа преобразований множества Q, порожденная отображениями цх: Q^Q для всех x в X, где ^x(q)=^(x,q).
Автомат сети определяется как соответствующая суперпозиция компонент сети. Автоматная сеть называется декомпозицией автомата S, если поведение последнего вкладывается в поведение автомата сети.
Тип декомпозиции (каскадная, параллельная и т.п.) определяется типом ее сети.
Пусть k 1, m2. Автомат S каскадно k-приводим по входам и каскадно m-приводим по состояниям, если существует каскадная декомпозиция этого автомата, в которой каждая компонента имеет k входных символов и m состояний соответственно.
Аналогично определяются другие типы приводимости по входам и состояниям - параллельная, последовательная и т.п.
Теорема. Пусть k2.
Автономный автомат кас-кадно k-приводим по входам и да-приводим по состояниям, если и только если mp, где p - наибольший простой делитель периода полугруппы автомата.
Теорема. Автономный автомат параллельно k-приводим по входам и да-приводим по состояниям, если и только если дашах(г, ра), где r - индекс полугруппы автомата и ра - наибольший сомножитель в каноническом разложении периода полугруппы автомата на простые множители.
Следствие. Проблемы каскадной и параллельной приводимости по входам и состояниям конечных автономных автоматов алгоритмически разрешимы.
Теорема. Автомат каскадно да-приводим по состояниям, если и только если каждый простой делитель его полугруппы изоморфен группе подстановок степени да.
Теорема. Автомат параллельно да-приводим по состояниям, если и только если его полугруппа делит прямое произведение полугрупп преобразований множества {1,..., да-1}, взятых в степенях, показатели которых не превосходят их порядков в степени nn
Следствие. Проблемы каскадной и параллельной приводимости по состояниям конечных автоматов алгоритмически разрешимы.
Автомат перестановочный, если каждый входной символ в нем вызывает перестановку состояний. Его полугруппа является группой.
3. Дискретные авт
Дискретная математика изначально служит математическим аппаратом для теории дискретных управляющих систем - дискретных автоматов. Ее функциональные средства являются удобным языком для адекватного описания статического (при фиксированном входном состоянии) поведения дискретного автомата, но, к сожалению, недостаточны для адекватного описания его динамического (вызываемого асинхронным изменением компонент входного состояния) поведения. Причина этого - в отсутствии в дискретной математике средств для выражения изменения дискретной величины, подобных дифференциалу и производной в непрерывной математике. В этих условиях в теории дискретных динамических систем идут на неестественное усложнение используемых математических моделей как в рамках дискретной математики (допустимые последовательности состояний Р. Миллера и А.Н.
Чеботарева, асинхронные процессы В.И. Варшавского, сети Петри, графы логических функций и переходов Э.А.
Якубай-тиса, дискретные процессы Ю.В. Капитоновой и А.А. Летичевского, булево дифференциальное исчисление Д Бохмана и Х. Постхофа), так и выходя за ее пределы в область непрерывного времени (В.Н. Рогинский, В.И.
Левин, З.Л. Рабинович, О.П.
Кузнецов, Y.C. Ho).
Несмотря на обилие попыток создания общих моделей для динамического поведения дискретной системы, ни одна из них не стала столь же общепринятой парадигмой, каковой в свое время стали дифференциальные уравнения для динамических систем с непрерывными переменными.
Теорема. Перестановочный автомат каскадно да-приводим по состояниям, если и только если каждый композиционный фактор его группы изоморфен группе подстановок степени да.
Теорема. Перестановочный автомат с полупростой группой G параллельно да-приводим по состояниям, если и только если в G существуют нормальные делители с единичным пересечением, фактор-группы по которым являются гомоморфными образами групп подстановок степени да.
Автомат перестановочно-возвратный (ПВ-авто-мат), если каждый входной символ в нем вызывает перестановку состояний или переход в одно и то же состояние. Всякий автомат допускает каскадную де-композицию на ПВ-автоматы (H.P.
Zeiger, 1965).
Пусть L(n) - функция Шеннона для числа компонент в каскадной декомпозиции автомата с n состояниями на ПВ-автоматы и LZn) - функция Шеннона для числа компонент такой же декомпозиции методом H.P. Zeiger.
Теорема. LZ(n)2n-1- 1 для n3.
Теорема. L(n)=n-1.
Результаты по декомпозиции автоматов находятся в книге [49], написанной по материалам статей [4148].
аты на полурешетках
Нами для теории дискретных автоматов предложен математический аппарат, основой которого служат конечные верхние полурешетки и полуре-шеточно упорядоченные алгебры. В любой такой алгебре, наряду с собственными алгебраическими операциями, задано еще и отношение частичного порядка, сохраняемого этими операциями, вместе с которым множество элементов алгебры является верхней полурешеткой, т.е. частично упорядоченным множеством, где для любой пары элементов существует точная верхняя грань, называемая их суммой.
В описании поведения дискретного автомата средствами полурешеточно упорядоченной алгебры отношение порядка интерпретируется как отношение сравнения состояний в нем по степени их неопределенности, обязанной явлению состязаний, которые возникают между компонентами состояния в процессе их асинхронного изменения, а сумма состояний моделирует это изменение как промежуточное (переходное) состояние. Например, асинхронное изменение состояния входов автомата с а на b моделируется в его описании промежуточным состоянием а+b. Именно а+b в предложенном аппарате рассматривается как выражение для изменения значения дискретной величины с а на b.
Далее, в дискретных функциональных системах с частично определенными функциями, такими, как частичные конечнозначные функции, частично-рекурсивные функции, частичные конечно-автоматные функции и т.п., неопределенность значения переменной (аргумента, функции) трактуется обычно одним способом - как любое из всех возможных определенных значений этой переменной. В приложениях к дискретным автоматам такая трактовка ведет нередко к снижению точности используемых моделей со всеми вытекающими отсюда неприятными последствиями: в синтезе - затрудняются формализация исходных функций и их декомпозиция, в анализе - теряется необходимая информация.
Наш аппарат лишен и этого недостатка традиционной дискретной математики, допуская введение в область значений каждой переменной значения разной степени неопределенности, трактуемые как любые из некоторых определенных значений и образующие в совокупности верхнюю полурешетку подмножеств определенных значений.
Важнейшими характеристиками любой математической модели являются ее адекватность и степень точности. В случае дискретных моделей первая понимается как безошибочность в том смысле, что результат адекватного моделирования всегда содержит в себе истинное значение моделируемой величины, а вторая - как степень неопределенности этого результата. Формализовать эти понятия традиционными средствами дискретной математики не удается. Аппарат же теории полурешеток позволяет сделать это через определение адекватной модели полурешетки как множества из наибольших элементов всех смежных классов последней по некоторой конгруэнции на ней, которая, в свою очередь, представляет собой степень точности этой модели.
В результате утверждения об адекватности и точности дискретных моделей впервые становятся теоремами.
Рассматривая функции и автоматы как определенные на полурешетках, можно дать (впервые) точное определение их физической реализуемости. Это понятие оказывается равносильным математическому понятию квазимонотонности, ибо квазимонотонные функции и автоматы на полурешетках и только они допускают схемную реализацию на современной микроэлектронной базе.
Таким образом, изучая дискретные автоматы на по-лурешетках, можно определить такие важные атрибуты дискретной управляющей системы, как динамическое поведение, адекватная модель и ее точность и физическая реализуемость, и сделать утверждения о них доказательными. Все традиционные задачи проектирования дискретных автоматов, включая задачи эквивалентных преобразований, минимизации, декомпозиции, кодирования, моделирования, анализа, синтеза и др., удается теперь поставить и решить в новой, более общей постановке, отражающей динамику поведения автомата, его физическую реализуемость и адекватность моделирования с любой наперед заданной точностью.
Результаты этих исследований, фактически открывающие новое научное направление на стыке дискретной математики, математической кибернетики и алгебры, изложены в монографии [52] и частично в ряде предшествующих работ, включая статьи [53-57] и монографию [58]. На их основе построена теория асинхронных интегральных схем логического управления, содержащая полуреше-точную модель динамического поведения и методы анализа и синтеза таких схем.
В следующем разделе кратко сообщается об этой теории.
В [60] показана возможность моделирования параллельных вычислений на конечной верхней полу-решетке конечным автоматом на полурешетках и приведены результаты из [52], относящиеся к синтезу, минимизации и декомпозиции таких автоматов. В [62] указаны канонические формы и построены примеры полных систем элементарных функций для представления и реализации формулами произвольных квазимонотонных функций на полурешетке подмножеств конечного множества.
В [63] сформулированы основные свойства и методы построения с заданной точностью адекватных моделей для полурешеток, функций и конечных автоматов на полурешетках, собранные из разных глав книги [52].
Полурешеточная теория интегральных схем
Каждая компонента интегральной схемы (диод, транзистор, логический вентиль, триггер, ключ, базовая ячейка и т.п.) представляется как переключательный элемент - многополюсник, в котором проводимости между полюсами являются функциями от состояний полюсов, а интегральная схема - как совокупность соединенных должным образом переключательных элементов.
