Автореферат (1137128), страница 4
Текст из файла (страница 4)
Лес покрывает всеТГС4 до 30 вершин включительно (289 графов), то есть в нём 289 вершин. Бесконечные семейства образуют подграф из 194 вершин. Остальные вершиныобозначают конечные семейства. Интересно, что некоторые графы малого размера не попали в основной лес бесконечных семейств. Например, из двух графов на 8 вершинах один входит в дерево с корнем в клике на 5 вершинах, а второй расположен отдельно. Это обусловлено требованием безызбыточности семейств.
Сам лес семейств реализован в виде интерактивной графовой модели.Проведён анализ спектральной сложности бесконечных семейств ТГС4.Показано, что ISSC в различных базисах различным образом коррелирует с характеристиками симметрии, что важно при выборе необходимого семействапри синтезе структуры реальной системы с заданными характеристиками.В четвёртой главе описываются программные разработки автора, рассматриваются вопросы повышения эффективности решения задач структурногоспектрального анализа, обсуждаются практические вопросы реализации программных средств, взаимодействия с пользователем и проведения вычислительных экспериментов. Большинство программных разработок позволяют интегрировать их в АСНИ «Graph Model Workshop» (далее – GMW).
GMW (авторыКохов В.А., Ткаченко С.В., Незнанов А.А.) предназначена для проведения научных исследований, объектом которых являются графовые модели систем,включая подготовку исходных данных, автоматическое проведение вычислительных экспериментов и обработку их результатов (рис. 4).На базе GMW создаются программные средства для решения прикладныхзадач и программные средства учебного назначения. GMW является открытой15системой с многоуровневым интерфейсом для подключения программных расширений, которые могут повышать функциональность всех операций, выполняемых в АСНИ.
Реализованные автором программные средства можно разделить на два класса: анализа структурной сложности орграфов и синтеза графов.Разработки автора также используются с целью расширения доступных отношений сходства структур в экспериментах по анализу сходства графов на основе структурно-характеристического подхода.Рис. 4. Главное окно АСНИ «Graph Model Workshop»(окно редактирования графа содержит лес семейств ТГС4)Программные средства реализованы в основном в среде Embarcadero RADStudio (Delphi) для ОС Microsoft Windows и представляют собой набор динамически компонуемых библиотек (таблица 4) и отдельных средств организацииинтерфейса с пользователем.№123Таблица 4.
Параметры программных библиотек, содержащих расширения GMWКоличествоОбъёмКоличество Объёмэкспорти- авторского компилимашинБиблиотекаруемыхисходногоруемыхногофункцийкода, КБ строк кода кода, КБОбщие модули87Синтез транзитивных топологий3114987422145Вычисление моделей сложности993624512602орграфовВспомогательные программы1036973514216В части анализа структурной сложности орграфов наиболее интересны алгоритмы вычисления индексов, вектор-индексов и построение b-моделей сложности в базисах ОЦФ. Данный базис, являясь уникальным именно для орграфов, позволяет эффективно вычислять изоморфные вложения фрагментов ограниченного размера и даёт многообразие оценок сложности с высокой дискриминирующей способностью.Система анализа спектральной сложности орграфов включает редактор базисов ОЦФ.
На рис. 5 представлен внешний вид редактора. Он позволяет задавать элементы базиса различной длины, их индексы структурной сложности, атакже загружать/сохранять базисы в собственном формате. Основной сценарийиспользования системы – выбор и сохранение базиса, построение и сохранениеb-моделей для базы ГМС, использование сохранённых моделей сложности дляанализа сходства или решения других задач.
Для подтверждения корректностии оценки временной вычислительной сложности алгоритмов генерацииISC(G/DP) в базисе путей, ISC(G/DC) в базисе контуров, ISC(G/DCF) в базисеОЦФ и построения b-моделей в базисе путей, контуров и ОЦФ были проведеныобъемные вычислительные эксперименты на семействах одно-, двух-, трехсвязных орграфов различной сложности. Особенностью вычислений является последовательное наращивание длины путей и ОЦФ (длина ≤ 10) при вычислениииндексов структурной сложности и построении b-моделей для каждого семейства.Рис. 5.
Диалог создания базиса структурных дескрипторов(ориентированных цепных фрагментов)Для применения при решении прикладных задач реализован учёт произвольных весов вершин и дуг орграфов. В таком виде средства анализа структурной сложности использовались в проектах по анализу данных (graph mining)17для анализа сходства понятийных структур (conceptual graphs) и компьютернойлингвистике для выявления схожих цепочек в структурных моделях текстов.Приведены результаты объёмных вычислительных экспериментов (обработано более 1 000 000 обыкновенных графов и 4 000 000 орграфов). Исследовались: симметрия расположения вершин и более сложных фрагментов графовразличных классов; связь симметрии графа с его сложностью; отношения эквивалентности графов на основе индексов спектральной сложности и b-моделей(большинство данных вынесено в приложение).Автором также реализована система для линейной по вычислительнойсложности генерации транзитивных графов степени 4 и их симметричных диаграмм с размещением вершин по нескольким окружностям, проверена полнотаи безызбыточность генерации базы связных транзитивных графов степени 4 до30 вершины включительно.
Основное окно генератора приведёно на рис. 6.Рис. 6. Интерфейс подсистемы TransGen (каталог семейств и параметры генерации)Система может быть легко расширена для синтеза других семейств путёмдобавления в базу семейств новых скриптов генерации. Именно это позволилоприменить генератор при решении задач оптимизации систем управления, когда потребовалась генерация семейств транзитивных графов степени 3 и 5.Наиболее востребованным оказалась возможность выбора семейства с заданнойдлиной минимальных циклов, которые выступали в роли проектных групп, в товремя как рёбра, не входящие в минимальные циклы, соответствовали передачерезультатов деятельности проектных групп.Также система активно используется в исследовательской работе при подготовке исходных данных для вычислительных экспериментов.На базе разработок автора созданы программные средства учебного назначения, внедрённые в учебный процесс НИУ МЭИ и НИУ ВШЭ по дисциплинам«Теория графов и комбинаторика», «Прикладная теория графов», «Практикумна ЭВМ» и снабжённые методической поддержкой.В заключении приведены основные результаты работы и открытые проблемы.181.2.3.4.5.6.7.8.Основные результаты работыРассмотрена проблема определения структурной сложности систем изадачи анализа структурной сложности, проанализированы подходы ких решению.Развита методология анализа структурной сложности орграфов в базисах ориентированных цепных фрагментов (ОЦФ).
Предложены системы базисов ОЦФ и реализованы алгоритмы:1) эффективного поиска вложений элементов базиса ОЦФ в исследуемый орграф;2) построения и анализа моделей структурной сложности (индексов ивектор-индексов спектральной сложности, b-моделей) для орграфовобщего вида.Это позволило повысить качество и эффективность решения задач различения и анализа сходства орграфов.На основе результатов, полученных ранее при изучении конечныхгрупп и конструктивного перечисления транзитивных графов, предложена оригинальная классификация связных транзитивных графов степени 4 (ТГС4) с выделением конечных и бесконечных семейств, причём критериями выделения, наряду с классическими параметрами, являлись также характеристики стабильности симметрии, структурнойсложности и варианты прорисовки диаграмм.Предложенная классификация позволила создать каталог семействТГС4 (59 бесконечных и 72 конечных семейства), причём представители семейств безызбыточно покрывают все ТГС4 до 30 вершин.Созданы программные средства структурного анализа (среди них«Сложность орграфов в цепных базисах», «TransGen – система синтезатранзитивных топологий»).
Программные разработки содержат более400 КБ авторского исходного кода и более 6 МБ исполняемого кода.Большинство программных разработок способны интегрироваться вАСНИ «Graph Model Workshop».Программные разработки применены при решении задач анализа понятийных структур и текстовых коллекций, представленных орграфами сразличными весами на вершинах.На базе программных разработок созданы программные средства учебного назначения для поддержки дисциплин «Теория графов и комбинаторика», «Практикум на ЭВМ», «Прикладная теория графов».Проведены объёмные вычислительные эксперименты с использованием GMW и авторских программных разработок с целью исследования:1) характеристик симметрии и сложности ТГС4, что позволило подтвердить корректность классификации и построить симметричные диаграммы представителей семейств ТГС4 (более 120 экспериментов, более 1,5 лет машинного времени);2) структурной сложности семейств ТГС4 из каталога (см.
пункт 4) вразличных базисах (12 базисов, более 60 экспериментов, более недели19машинного времени), что позволило дополнительно классифицироватьсемейства и расширить множество параметров генерации семейств;3) числовых и структурных инвариантов орграфов и их подклассов(например, планарных орграфов) на основе g- и b-моделей В.А.
Коховав различных базисах (более 30 базисов, более 200 экспериментов, более года машинного времени), что позволило, например, уточнить различия в дискриминирующей способности базисов ОЦФ и базисов путей, полупутей, контуров.ВыводыВ работе исследуются базовые задачи анализа структурной сложности исимметрии ГМС. Актуальность решения этих задач непрерывно повышается,так как на их решении основано сопоставление структур систем, необходимоепри построении топологий вычислительных систем и сред, распознавании образов, анализе сходства химических соединений, сравнении моделей текстов вкомпьютерной лингвистике и решении других задач.Методы построения различных моделей сложности орграфов реализованыв авторских программных средствах, способных работать как независимо, так ив составе АСНИ «Graph Model Workshop».
Результаты объёмных вычислительных экспериментов свидетельствуют, что при анализе спектральной сложностиорграфов выбор базиса приобретает ещё большее значение, чем в случае обыкновенных графов. При исследовании орграфов получены результаты по количественному анализу индексов структурной спектральной сложности орграфовразличных классов в базисах ориентированных цепных фрагментов и показанэффект повышения различающей способности от выбора базиса ОЦФ определённого вида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
