О прикладной дискретной математике в ТГУ (1970-1999 гг.) | Вестн. Том. гос. ун-та. 2000. № 271.

О прикладной дискретной математике в ТГУ (1970-1999 гг.)

Дается краткий обзор результатов научных исследований по прикладной дискретной математике в ТГУ за 1970-1999 гг.

Discrete applied mathematics at TSU (1970-1999).pdf Термин «дискретная математика» начал входить в научный обиход на рубеже 50-х и 60-х гг. XX в. для обозначения системы новых математических дисциплин, таких, как теория булевых функций, теория конечных автоматов, теория графов, теория кодирования и др. Иногда в него вкладывают и более широкий смысл, полагая, что если в основе математики лежит понятие множества, то в основе дискретной математики лежит понятие дискретного множества. В этом смысле к дискретной математике относят и теорию чисел, и математическую логику, и всю конечную алгебру, и некоторые другие «ласеичеекне разделы математики. Мы этого де-> лать не будем и под дискретной математикой далее будем подразумевать именно современную дискретную математику. Ее основоположником следует считать, по-видимому, Клода Шеннона - американского математика и инженера, опубликовавшего в 1938 г. первые теоремы о свойствах булевых функций и переключательных схем. Справедливости ради следует заметить, что тремя годами раньше некоторые схожие результаты получил В.И. Шеста-ков, доцент физфака МГУ, но смог опубликовать их лишь в 1941 г., т.к. эти результаты обосновывали применимость логики в технике, чего не могло быть по меркам тогдашней отечественной идеологии. Позднее (1949 г.) К. Шеннон ввел в рассмотрение функцию, получившую в науке его имя, - функцию Шеннона, ставшую на все последующие годы предметом многочисленных исследований (в том числе и наших) в разных областях дискретной математики. В наиболее общем виде она определяется следующим образом. Пусть имеются два множества - А и В и бинарное отношение рсАхВ. Пусть также каждый элемент Ь в В характеризуется положительным числом 1(b) - сложностью Ь. Тогда функция Шеннона есть L(A)=шах min 1(Ь)\ аеЛ (beВ, 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 докладов на международных и отечественных научных конференциях. Часть этих публикаций отражена в прилагаемом списке литературы. 1. Компьютерная дискретная математика 1. Автоматизация синтеза дискретных автоматов В ТГУ исследования по дискретной математике были начаты в конце 50-х гг. тогдашним аспирантом РФФ Аркадием Дмитриевичем Закревским. Тот факт, что эти исследования зародились на РФФ, а не на ММФ, наложило определенный отпечаток на их характер. Изначально они велись как прикладные, т.е. вызывались не потребностями самой математики, но ее применениями главным образом к синтезу дискретных автоматов (тогда - релейных схем управления). Прикладной характер исследований выразился и в том, что их результатами должны были стать алгоритмы решения задач дискретной математики, аттестованные в эксперименте на вычислительной машине (ЭВМ). Фактически уже тогда речь шла о создании нового направления в математике - компьютерной дискретной математики. А.Д. Закревский заложил первые «кирпичи» в фундамент этой науки. Чтобы правильно понять и оценить действительное значение этого вклада, надо обратить внимание на то, что в дискретной математике мало имеют дело с числами, все больше - с подмножествами множеств нечисловой природы. Это значит, что классические математические средства вычислений, включая базовые -сложение, умножение, дифференцирование и т.п., в компьютерной дискретной математике мало полезны. Здесь нужны другие математические операции, и А.Д. Закревский их создал [1]. Для этого он сначала предложил представлять системы подмножеств конечных множеств при помощи булевых и так называемых троичных матриц, а затем разработал иерархическую систему математических операций над такими матрицами и эффективные алгоритмы их выполнения. Система охватывает широкий спектр операций: от простейших (нахождение минимального столбца и максимальной строки) до предельно сложных (кратчайшее покрытие булевой матрицы или минимальное разбиение множества ее столбцов на совместимые подмножества, например). Фундаментальное и прикладное значение этой системы состоит в том, что через операции в ней легко выражаются алгоритмы решения многих задач как в самой дискретной математике, так и в ее приложениях, и не только к синтезу дискретных автоматов. К числу таких задач относятся: минимизация и функциональная разделимость булевых функций, минимизация конечных автоматов и кодирование их состояний, логический синтез схем и тестов для них, раскраска графов, градостроительные задачи размещения, трассировки и многие другие. Полезность этой разработки вскоре была доказана на практике, когда на ЛЯПАСе - «русском» языке программирования, разработанном под руководством А.Д. Закревского [2], - был создан ряд систем автоматического синтеза и диагностики дискретных автоматов, основу математического обеспечения в которых составила именно данная система операций (см., например, [3-6]). В 70-80-е гг. эти автоматические системы широко применялись на предприятиях МЭП и МРП. А.Д. Закревский одним из первых (если не самым первым) в мировой науке предложил и осуществил на практике технологию статистического исследования алгоритмов в эксперименте на ЭВМ, ставшую отличительной особенностью и обязательным элементом деятельности его научной школы, в том числе и в ТГУ в рассматриваемый период. За малым исключением, все публикации в списке литературы, содержащие оригинальные алгоритмы, содержат и результаты такого исследования последних. Примером этого могут служить работы [7,8]. 1.2. Технология решения задач дискретной математики Многие оптимизационные задачи дискретной математики формулируются как следующая задача о кратчайшем допустимом разбиении (ЗКДР): даны конечное множество X и ограничения Р на его подмножества; требуется найти разбиение X на подмножества (блоки), удовлетворяющие Р (допустимое разбиение), с наименьшим количеством блоков (кратчайшее разбиение). Примеры: минимальная раскраска графа, кратчайшее разбиение системы чисел на подсистемы с ограниченной суммой, кратчайшее разбиение сети на подсети ограниченной сложности или структуры, кратчайшее покрытие булевой матрицы, кратчайшее разбиение системы формул на подсистемы с ограниченными количественными характеристиками, кратчайшее покрытие схем свободными модулями и др. Конкретные (с конкретными X и Р) ЗКДР, как правило, не допускают иных методов решения, кроме переборных. К числу последних относится и метод сокращенного обхода дерева поиска [9,10], разработанный нами для решения всевозможных ЗКДР. Вершины и ребра дерева поиска в нем сопоставляются подмножествам в разбиваемом множестве X, причем ребра - допустимым подмножествам, корень дерева - множеству X, его листья - пустому множеству, и разность множеств, соответствующих концам ребра, соответствует ребру. Таким образом, всякий путь от корня дерева к листу сопоставлен допустимому разбиению множества X, а всякий кратчайший такой путь - решению задачи. Метод сокращенного обхода дерева поиска принадлежит к точным методам последовательных приближений и представляет собой общий алгоритм поиска с возвращением и сохранением «лучшего» приближения. Он содержит средства сокращения поиска - алгоритм начального приближения, алгоритм перечисления, операцию сокращения и функцию нижней оценки. Алгоритм начального приближения - это эвристический алгоритм, позволяющий быстро построить некоторое допустимое, но не обязательно кратчайшее разбиение, принимаемое за начальное. Алгоритм перечисления и операция сокращения обеспечивают процесс ветвления в каждой вершине дерева поиска. Первый порождает некоторую достаточную совокупность очередных альтернативных элементов искомого решения, а вторая выбрасывает из нее «лишние» элементы. С их помощью для каждой достигаемой вершины дерева поиска порождается некоторая такая часть его ребер, исходящих из этой вершины, в которой есть хотя бы одно ребро, которое принадлежит хотя бы одному кратчайшему пути, проходящему через данную вершину и соединяющему корень с листом дерева. С помощью функции нижней оценки производится отсечение каждого такого поддерева дерева поиска, для которого сумма длины пути от корня дерева к корню поддерева и значения функции нижней оценки для длины кратчайшего пути в последнем не меньше длины известного на данный момент наиболее короткого допустимого разбиения. Эти средства сокращения входят в метод как его параметры. Для решения конкретной ЗКДР надо подобрать их подходящими данной задаче и подставить в формулировку метода. Результатом и будет алгоритм решения этой ЗКДР. Его эффективность определяется сокращающими способностями подобранных параметров, т.е. степенью близости начального разбиения к кратчайшему, степенью точности нижней оценки и степенью ветвления вершин дерева. Пользуясь данной технологией, нам удалось построить наиболее эффективные (на момент их создания) решающие алгоритмы для многих оптимизационных задач дискретной математики и ее приложений, в том числе для разбиения системы чисел, для раскраски графа, для покрытия схем свободными модулями, для разбиения схем на подсхемы ограниченной сложности, для синтеза схем в различных программируемых базисах - ПМВ, ППЗУ, ПЛМ, ПМЛ, для распределения элементов схем по ячейкам компоновочного пространства и др. Эти результаты отражены в монографии [10], статьях [9, 11-29] и в докладах на конференциях. 2.1. Эксперименты с автоматами Конечный автомат определяется пятеркой S=(X, Q, Y, у/, 2 и л£1 - это периодическая последовательность р=у(1М2)- с периодом А", составленная из чисел множества {0, 1,..., £-1}, в которой все слова y{i")y{H-l)...y(H-n-1) для /'=1, 2,..., А" различны. Она порождается автономным автоматом с А" состояниями. Эксперимент (простой) - это любая пара слов (а,Р) в некоторых алфавитах. Его длина /(а,Р) - это длина слова а. Эксперимент (а,р) присущ инициальному автомату S, если a - входная последовательность для S и Р - реакция на нее автомата S. Автоматы S и S' различимы (S*S), если существуют эксперименты (а,Р) и (а,Р'), присущие S и S соответственно, где Р*Р'. Эксперимент, присущий автомату SeK, распознает автомат S в классе К, если он не присущ никакому автомату S"eK для S'*S. Функция Шеннона для длины распознающего эксперимента вводится как Ь{К)=тгх min /(a,P) SeK (a, P) распознает S. Ниже используются следующие обозначения: kN - класс всех линейных автономных инициальных автоматов с размерностью состояния класс всех линейных инициальных автоматов с размерностью входного символа - А и состояния - и; р„(к) -класс всех инициальных автономных автоматов, порождающих н.п.п. с параметрами пик. Известно, что |рЛ*)1 =(*!)", где/п^"'. Теорема [31] (впервые в [32]). L(Xn)=2N. Теорема [33]. 2п ) - это множество всех четверок {b,г s v), где ЬеХ, г, seQ, veYns=y4.b,r), v=Q для всех х в X, где y/x(q)=ty(x,q). Автомат сети определяется как соответствующая суперпозиция компонент сети. Автоматная сеть называется декомпозицией автомата S, если поведение последнего вкладывается в поведение автомата сети. Тип декомпозиции (каскадная, параллельная и т.п.) определяется типом ее сети. Пусть А> 1, т>2. Автомат S каскадно к-приводим по входам и каскадно т-приводим по состояниям, если существует каскадная декомпозиция этого автомата, в которой каждая компонента имеет р, где р - наибольший простой делитель периода полугруппы автомата. Теорема. Автономный автомат параллельно к-приводим по входам и /и-приводим по состояниям, если и только если m>max(r, р"), где г - индекс полугруппы автомата и р" - наибольший сомножитель в каноническом разложении периода полугруппы автомата на простые множители. Следствие. Проблемы каскадной и параллельной приводимости по входам и состояниям конечных автономных автоматов алгоритмически разрешимы. Теорема. Автомат каскадно m-приводим по состояниям, если и только если каждый простой делитель его полугруппы изоморфен группе подстановок степени

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Агибалов Геннадий ПетровичТомский государственный университетпрофессор, доктор технических наук, заведующий кафедрой защиты информации и криптографии факультета прикладной математики и кибернетикиagibalov@fpmk.tsu.ru
Всего: 1

Ссылки

Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.
Логический язык для представления алгоритмов синтеза релейных устройств / Под ред. М.А. Гаврилова. М.: Наука, 1966. 342 с.
Синтез асинхронных автоматов на ЭВМ / Под общ. ред. А.Д. Закревского. Минск: Наука и техника, 1975. 184 с.
Автоматизированное проектирование цифровых устройств / Под ред. С.С. Бадулина М.: Радио и связь, 1981. 240 с.
Панкратова И.А., Быкова С.В., Николаева Л.A., Оранов A.M. Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф // Управляющие системы и машины. 1991. № 1. С. 3-9.
Агибалов Г.П., Иволга В.П., Комаров Ю.М., Кутугина Е.С. Система логического моделирования схем во времени//Обмен опытом в радиопромышленности. 1983. Вып. 4. С. 13-16.
Быкова С.В. Система алгоритмов кратчайшего покрытия // Труды Сибирского физ.-техн. ин-та. Проблемы кибернетики. Томск: Изд-во Том. ун-та, 1973. Вып. 64. С. 3-11.
Быкова С.В., Иволга В.П. Оценка эффективности некоторых алгоритмов минимального разбиения // Вычислительная техника в машиностроении. Минск: ИТК АН БССР, июнь 1974. С. 79-86.
Агибалов Г.П., Беляев В.А. Метод сокращенного обхода дерева поиска и его применение в синтезе интегральных схем // Управляющие системы и машины. 1977. № 6. С. 99-103.
Агибалов Г.П., Беляев В.А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска Томск: Изд-во Том. ун-та, 1981. 12S с.
Агибалов Г.П. Об одном подходе к размещению аппаратуры //Автоматика и вычислительная техника, 1971. № 1. С. 56-61.
Беляев В.А. Томашев В.Ф. Об одной комбинаторно-логической задаче, связанной с оптимальным размещением аппаратуры по линейно-упорядоченным отсекам // Труды Сибирскою физ.-тех. ин-та. Проблемы кибернетики. Томск: Изд-во Том. ун-та, 1971. Вып. 62. С.49-57.
Агибалов Г.П., Беляев В.А., Оранов A.M. Некоторые алгоритмы разбиения, покрытия и размещения логических схем // Управляющие системы и машины. 1974. № 5. С. 86-92.
Агибалов Г.П., Беляев В.А., Янковская А.Е. Алгоритм компоновки схем в модули ограниченной вместимости // Управляющие системы и машины. 1976. № 1. С. 84-89.
Беляев В.А. Усовершенствованный алгоритм минимального разбиения системы чисел// Прикладная математика и кибернетика. Томск: Изд-во Том. ун-та, 1976. Вып. 1. С. 17-22.
Агибалов Г.П., Оранов A.M. Алгоритм покрытия схем свободными модулями // Автоматика и вычислительная техника. 1977. № 4. С. 15-16
Агибалов Г.П., Оранов A.M. О покрытии схем модулями // Вопросы автоматизации проектирования интегральных схем. Киев: ИК АН УССР, 1978. С. 46-57.
Агибалов Г.П. Задача выбора и декомпозиция схем с размещением и трассировкой в компоновочном пространстве // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1987. Вып. 2. С. 134-153.
Беляев В.А. Алгоритм раскраски графа методом сокращенного обхода дерева поиска // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1987. Вып. 2. С. 165-172.
Агибалов Г.П., Оранов A.M. Покрытие логических схем модулями некоторых серийных систем // Кибернетика. 1986. № 2. С. 34-38, 43.
Оранов A.M., Андреева ЛИ. Алгоритм минимального разбиения системы множеств // Автоматика и вычислительная техника. 1992. № 2. С. 37-44.
Оранов A.M., Андреева Л.Н. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах // Автоматика и вычислительная техника. 1992. № 5. С. 57-63.
Оранов A.M., Андреева Л.Н. Алгоритм минимального разбиения некоторого набора объектов // Автоматика и вычислительная техника. 1993. № 2. С. 27-35.
Оранов A.M. К синтезу комбинационных схем в базисе ПЛИС // Автоматика и вычислительная техника. 1996. № 1. С. 27-35.
Андреева Л.Н., Оранов A.M. О сложности некоторых задач разбиения //Известия РАН. Теория и системы управления. 1997. № 2. С. 114-116.
Оранов A.M. Алгоритм построения кратчайших монотонно-допустимых разбиений конечных множеств // Автоматизация проектирования дискретных систем. Материалы 2-й Международной конференции. Т. 3. Минск: ИТК АН Беларуси, 1997. С. 221-227.
Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения // Автоматизация проектирования дискретных систем. Материалы 2-й Международной конференции. Т. 3. Минск: ИТК АН Беларуси, 1997. С. 228-231.
Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения // Известия РАН. Теория и системы управления. 1999. № 1. С. 89-93.
Оранов A.M. Кратчайшие допустимые разбиения в синтезе и компоновке схем на современной элементной базе // The third international symposium «Application of the conversion research results for international cooperation» (Sibconvers'99). Proceedings. Tomsk: Tomsk state university of control systems and radioelectronics. 1999. C. 192-194.
Агибалов Г.П., Оранов A.M. Лекции по теории конечных автоматов. Томск: Изд-во Том. ун-та, 1984. 185 с.
Агибалов Г.П. Распознавание операторов, реализуемых в линейных автономных автоматах // Известия АН СССР. Техническая кибернетика. 1970. № 3. С. 99-108.
Агибалов Г.П. Распознавание операторов, реализуемых в автономных автоматах // Конференция по теории автоматов и искусственному интеллекту: Аннотации докладов и программа. М.: ВЦ АН СССР, 1968.
Агибалов Г.П., Юфит Я.Г. О простых экспериментах для линейных инициальных автоматов // Автоматика и вычислительная техника. 1972. № 2. С. 17-19.
Агибалов Г.П., Ванина Н.В. Точная верхняя оценка степени различимости произвольной нормальной периодической последовательности // Известия АН СССР. Техническая кибернетика. 1973. № 1. С. 131-136.
Агибалов Г.П., Ванина Н.В. О кодовых свойствах нормальных периодических последовательностей // V конференция по теории кодирования и передачи информации. 11 Теория кодирования. Москва-Горький, 1972. С. 5-6.
Агибалов Г.П. Отождествление нормальных периодических последовательностей начальными отрезками // Труды Сибирского физ.-тех. ин-та. Проблемы кибернетики. Томск: Изд-во Том. ун-та, 1970. Вып. 49. С. 20-37.
Агибалов Г.П. Распознавание операторов, вычисляющих нормальные периодические последовательности // Известия АН СССР. Техническая кибернетика. 1971. № 6. С. 165-173.
Агибалов Г.П. Синтез автоматов по конечно-определенным словарным функциям // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1979. С. 160-164.
Евтушенко Н.В, Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и вычислительная техника 1989. №3. С. 9-14.
Евтушенко Н.В. О принадлежности последовательности множеству контрольных последовательностей автомата // Алгоритмы решения задач дискретной математики. Томск: Изд-во Том. ун-та, 1987. Вып. 2. С. 130-133.
 О прикладной дискретной математике в ТГУ (1970-1999 гг.) | Вестн. Том. гос. ун-та. 2000. № 271.

О прикладной дискретной математике в ТГУ (1970-1999 гг.) | Вестн. Том. гос. ун-та. 2000. № 271.

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