Введение к работе
Актуальность проблемы. Известно, что для дискретных объектов (графов, булевских функций, цифровых автоматов, многогранников) важными являются задачи построения полной совокупности симметрии, реализации в естественных, например евклидовых пространствах, оценки информационной сложности и т.п. Такие задачи играют важную роль при исследованиях многих вопросов в области автоматизации проектирования вычислительных систем, как оптимальной укладки схем, размещения модулей, минимизации микропрограмм, тестов и т.д.; в области распознавания образов -минимизации описания исходных объектов, ранжировании и выделении информативных признаков и др.
При обычном кодировании дискретных объектов во многих случаях решение вышеперечисленных задач весьма затруднено (например, при стандартном, естественном представлении графов). Поэтому актуальной является проблема построения специального кодирования дискретных объектов, обладающего следующими свойствами: а) переход к специальному кодированию от естественного является достаточно нетрудоемким; б) специальное кодирование позволяет сравнительно просто решать задачи полного описания симглетрии дискретных объектов, оценивать их информационную сложность и реализовать эти объекты в естественных пространствах.
Диссертация посвящена разработке математических методов такого специального кодирования и применению их в научных исследованиях по автоматизации проектирования вычислительных систем, кристаллографии и других областях. Это определяет ее актуальность.
Цель работы. Разработать математические методы специального кодирования дискретных объектов - графов, многогранников,
булевских функций, связанных с их минимальными представлениями, обработкой и преобразованием. Показать, что булевское и арифметическое кодирование графов наделяет их теоретико-групповыми свойствами, отличающимися от классических свойств, и является ис точником формирования новых конечных групп и групповых композиций. Установить, что параметризация графов, осуществляемая предложенным методом кодирования порождает множества подстановок, укладывающихся в новые группы с ранее неизвестными свойствами, и обеспечивает реализуемость этих графов в евклидовых пространствах. Показать, что арифметическое кодирование графов является перспективным научным направлением в области применения математических методов и ЭВМ в научных исследованиях. Обосновать концепцию кодирования дискретных объектов как наиболее общего объединяющего начала, играющего важную роль в различных процессах и явлениях природа. Применить информационные, статистические и геометрические свойства дискретных объектов к решению некоторых задач по автоматизации проектирования вычислительных систем.
Научная новизна. В работе впервые делается попытка разработать основы специального кодирования объектов дискретной природа - булевских функций, графов, многогранников, приводящего к новым понятиям и постановкам задач в теории дизъюнктивных нормальных форм, теории конечных групп, теории графов и их приложений. Предложенное кодирование ставит на одну рснову вопросы полного описания симметрии, реализуемость и информационную сложность дискретных объектов.
Целесообразность и естественность предложенного направления обосновывается обнаружением у графов, представленных в определен ной системе кодирования, комплекса свойств, играющих важную роль в различных областях научных исследований, связанных с математи-
ческим моделированием сложных систем.
Вводятся новые понятия, как булевские графы, булевские автоморфизмы и группы, арифметические графа, арифметические автоморфизмы и группы, принципиально отличающиеся от классических. Для некоторых из этих классов графов достаточно просто решаются задачи гамильтоновости, связности, нахождения компоненты связности и другие вопросы, трудно решаемые в классической постановке. Впервые построена группа 66 (р) арифметических автоморфизмов простых циклов с числом вершин 2.р ( р - простое число) с новыми свойствами.
На основе предложенного метода кодирования графов вводится понятие арифметического многогранника, ставится задача математического синтеза этих тел и вопросы их реализуемости в трехмерном евклидовом пространстве.
На основе интерпретации изучаемых дискретных объектов как структуры и введения понятий "прямая" и "обратная" информационная сложность получены ноше критерии оценки сложности этих объектов и способы их применения к задаче минимального покрытия.
На основе геометрических свойств арифметических графов, а также многовариантности представления одного и того же графа в определенной системе кодирования впервые исследованы статистические свойства графов на примере задачи по определению наиболее вероятной '"длины графа".
Проведенные теоретико-числовые, алгебраические и геометрические исследования над графами, представленными в определенной системе, характеризуются единством взаимосвязанных свойств, объединяющей основой которых является концепция кодирования дискретных объектов как нового направления в области применения математических методов и ЭВМ в научных исследованиях по автома-
- 4 -тизации проектирования вычислительных' систем, кристаллографии и др.
Теоретическая и практическая значимость. Разработанные в работе методы специального кодирования дискретных объектов - булевских функций, графов, многогранников и др. создали основу для получения новых понятий и результатов в области теории дизъюнктивных нормальных форм (д.н.ф.), теории графов, теории групп, информатики и их приложений.
В области теории д.н.ф. сформулировано новое понятие графа, являющегося отображением сокращенной дизъюнктивной нормальной формы на обычный неориентированный граф, называемый булевским графом. Для булевских графов определено понятие автоморфизма и показано, что множество всевозможных таких автоморфизмов образует группу, отличающуюся от классических групп автоморфизмов графов. Характерная отличительная особенность этой группы заключается в том, что она отражает симметрии не одного графа, как в классическом случае, а семейства графов. Указанное говорит об универсальности этих групп и наличии в природе принципиально новых симметрии глобального характера. -
В области теоретико-числового описания неориентированных графов впервые введено понятие арифметического графа и изучены основные его свойства. Показано, что всякий неориентированный граф может быть представлен в виде арифметического графа (универсальность) . Ддна классификация графов на натуральные и ненатуральные арифметические графы.
По аналогии с булевскими автоморфизмами определяется понятие арифметического автоморфизма и группы арифметического графа, отличающейся от классической группы автоморфизмов графов. Подробно изучена группа GG(p) арифметических автоморфизмов простых
циклов.
Для целей практического применения некоммутативной группы G& (р) в области кристаллографии, квантовой механики и др. полностью решена задача представления этой группы. Указан метод получения всех неприводимых представлений и таблиц характеров этой группы для любого простого р .
Показано, что арифметические многогранники, как новые геометрические тела, обладают противоположными качествами: в трехмерном евклидовом пространстве они абсолютно асимметричны, в - [ 2 ) -мерном линейном пространстве они симметричны. В итоге на примере арифметических многогранников показано, что категории симметрии и асимметрии носят относительный характер. С физической, химической, биологической точек зрения установленные свойства арифметических многогранников предопределяют существование в природе определенных веществ, структуры которых являются носителями этих качеств.
Информационные, статистические и геометрические свойства д.н.ф., арифметических графов, многогранников нашли практическое применение при решении задач оценки сложности дискретных объектов, минимального покрытия, оценки качества размещения модулей и др. в области автоматизации проектирования вычислительных систем,, разрабатываемых в Ереванском НИИ математических машин (ЕрНИИММ).
Проведенный комплекс исследований, связанных с арифметическим представлением графов, подтверждает правильность наших предположений о роли концепции кодирования как важной основы для постановки и изучения новых задач из области дискретной матема-
тики и ее приложений к различным областям естествознания.
-
Апробация работы. Результаты диссертации докладывались с 1975-1989 гг. на семинарах в городах Ереване (ЕрГУ, ВЦ АН АрмССР, ЕрНИИММ, Армянский НИИ энергетики), Москве (ВЦ АН СССР, Институт кристаллографии АН СССР), Киеве (Институт кибернетики АН УССР), на Федоровской сессии (Ленинград, 1984) , на второй Всесоюзной конференции "Математические методы распознавания образов" (Дили-жан, АрмССР, 1985 ), на второй Всесоюзной конференции "ИНФОРМА-ТИКА-8?" (Ереван, 1987), на Советско-Германском семинаре по дискретной математике (Ереван, 1989).
-
Публикации. По теме диссертации имеется 14 публикаций.
-
Объем работы. Диссертация состоит из введения, пяти глав, заключения, двух приложений и библиографии из 40 наименований. Работа изложена на 183 страницах машинописаного текста. Иллюстрационный материал представлен.II таблицами и 18 рисунками.
