Алгебраические байесовские сети: система анализа и синтеза вторичной структуры

Левенец Даниил Григорьевич

Алгебраические байесовские сети: система анализа и синтеза вторичной структуры

В выпускной квалификационной работе рассмотрена задача инкрементального и декрементального синтеза вторичной структуры алгебраических байесовских сетей. Для ее решения разработаны три алгоритма, доказаны шесть теорем, формализующих указанные алгоритмы. Кроме того, алгоритмы реализованы в комплексе программ для осуществления такого синтеза.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36465f1be77c40d58b4a

UUID: 03484175-a305-4ce1-8ea6-24dea70a0822

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 7

Левенец Даниил Григорьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 790920 bytes

Поделиться работой

Санкт-Петербургский государственный университет Кафедра информатики Фундаментальная информатика и информационные технологии Левенец Даниил Григорьевич АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ Бакалаврская работа Научный руководитель: проф. каф. инф., д.ф.-м.н., доц. Тулупьев А.Л. Рецензент: доцент НИУ ВШЭ СПб., к.ф.-м.н. Сироткин А.В. Санкт-Петербург 2016

Saint-Petersburg State University Computer Science Department Fundamental Informatics and Information Technology Daniel Levenets ALGEBRAIC BAYESIAN NETWORKS: SYSTEM FOR ANALYSIS AND SYNTHESIS OF SECONDARY STRUCTURE Bachelor’s Thesis Scientific supervisor: doctor. of Sc., associate professor Alexander Tulupyev Reviewer: associate professor NRU HSE, PhD Alexander Sirotkin Saint-Petersburg 2016

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 3 Содержание Введение 5 1 Обзор существующих алгоритмов синтеза вторичной структуры АБС 7 1.1 Существующие решения . . . . . . . . . . . . . . . . . . . . . 7 1.2 Актуальность работы . . . . . . . . . . . . . . . . . . . . . . 8 2 Определения и обозначения 9 2.1 Теоретическая часть . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Технологическая часть . . . . . . . . . . . . . . . . . . . . . . 11 3 Инкрементальный алгоритм добавления вершины в минимальный граф смежности 12 3.1 Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Корректность алгоритма . . . . . . . . . . . . . . . . . . . . 15 4 Улучшенный инкрементальный алгоритм добавления вершины в минимальный граф смежности 19 4.1 Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Корректность алгоритма . . . . . . . . . . . . . . . . . . . . 24 5 Декрементальный алгоритм удаления вершины 26 5.1 Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . 26 5.2 Корректность алгоритма . . . . . . . . . . . . . . . . . . . . 28 6 Система анализа и синтеза 29 6.1 Общие интерфейсы . . . . . . . . . . . . . . . . . . . . . . . . 30 6.2 Визуализация графа . . . . . . . . . . . . . . . . . . . . . . . 31 6.3 Графический пользовательский интерфейс . . . . . . . . . . 33

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 4 Заключение 43 Список литературы 44

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 5 Введение Графы смежности интенсивно используются в алгебраических байесовских сетях (далее АБС) в качестве вторичной структуры [9, 11, 16, 30, 33]. Такой объект оказался необходим потому, что ряд алгоритмов локального и глобального вывода, использующие рекуррентный подход, требуют, чтобы вторичной структурой был ациклический минимальный граф смежности [1, 8, 10, 12–14]. Однако предложенная стуктура сложна в построении, что заметно усложняет работу с динамически изменяющимися данными. Инкрементальный, а также использующий подобные методы декрементальный алгоритмы, рассматриваемые в данной работе, применяются для перестроения вторичной структуры АБС, что позволяет динамически изменять структуру графа смежности, не прибегая к полному перестроению графа. Это существенно сказывается на времени работы подобных алгоритмов вывода [2,5]. Кроме того, минимальный граф смежности легче визуализировать, равно как и легче выявлять скрытые закономерности, им представленные. При сложившейся практике обмена данными [15, 32] между программным компонентом, реализующим графический пользовательский интерфейс, и «блоком вычислений» — программным компонентом, обеспечивающим построение сложной системы из заданных составляющих, — типичный сценарий работы предполагает формирование набора составляющих, отправку набора в блок вычислений, формирование сложной системы, отправку данных в графический пользовательский интерфейс для визуального представления сформированной системы. Особенно это справедливо для клиент-серверных систем с так называемым «тонким» клиентом. Однако этот типичный сценарий ведёт ко всё более длительному ожиданию оператора, когда набор составляющих растёт, поскольку зачастую вычислительная сложность алгоритмов синтеза экспоненциально зависит

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 6 от объема исходных данных или оказывается ещё большей. Одним из возможных путей решения или, по крайней мере, смягчения обозначенной проблемы является инкрементализация и дектрементализация алгоритмов, которая нацелена на использование того, что было построено на предшествующих шагах работы с программой. Иначе говоря, на практике при работе с большим набором данных, в котором имеются связи, зависимости и отношения, часто ставится задача изменения подобного набора данных таким образом, чтобы имеющиеся ранее связи, зависимости и отношения либо сохранялись прежними, либо время, затрачиваемое на их перестроение, было бы близким к минимальному [24, 31, 34, 35, 37]. Трудозатраты на выполнение таких операций играют важную, а порой и критическую роль, когда речь идет о real-time-системах или о системах, для которых важна высокая степень доступности. Таким образом, возникает вопрос, как избежать полного перестроения системы после каждого небольшого изменения исходного набора данных. В рассматриваемом случае — примере минимального графа смежности как сложной системы — осуществляется попытка использовать уже построенный минимальный граф смежности и либо дополнить его новой вершиной, либо обеднить одной из существующих вершин с соблюдением требований структуры, подробно описанных во 2-м разделе. Таким образом, теоретической целью данной работы является разработка инкрементальных и декрементальных алгоритмов, ускоряющих построение глобальных структур алгебраических байесовских сетей при работе с динамически изменяющимися данными. Таже в данной работе есть технологическая цель: создание системы анализа и синтеза вторичной структуры алгебраических байесовских сетей в виде комплекса программ, который позволял бы пользователям наглядно изучать поведение глобальных структур АБС при поступлении в сеть новых данных, а также проводить различного рода вычисления, важные

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 7 в контексте вероятностных графических моделей. Такая система могла бы пригодиться при изучении и преподавании теории алгебраических байесовских сетей. Пользователи системы получат возможность быстро и удобно работать с такой сложной структурой, как граф смежности, и для этого им не понадобится изучать особенности программной реализации подобных алгебраических структур. Также необходимо отметить, что настоящая выпускная квалификационная работа бакалавра является проектной, то есть выполняется совместно с коллегами (Романовым Артемом Витальевичем, Березиным Алексеем Ивановичем), кроме того, тесно связана с выпускной квалификационной работой бакалавра Мальчевской Екатерины Андреевны. Для удобства изложения сначала раскрывается теоретическая часть данной работы (главы 3–5), а затем практическая (глава 6), при этом все используемые определения вынесены в главу 2. 1 Обзор существующих алгоритмов синтеза вторичной структуры АБС В данной главе проводится обзор существующих решений, касающихся синтеза вторичной структуры АБС. Обосновывается актуальность выбранной для работы темы. 1.1 Существующие решения В работах В.В.Опарина и А.А.Фильченкова были предложены два классических алгоритма синтеза вторичной структуры АБС — прямой и жадный [6, 7, 20, 22]. Оба алгоритма генерируют вторичную струткуру по полному набору данных, однако обладают серьезным недостатком — при малейшем изменении входного набора данных они полностью перестраивают

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 8 сгенерированную ранее структуру, то есть не учитывают текущее состояние сети и строят ее с нуля [2, 5]. Такой подход может быть полезен при синтезе начального состояния вторичной структуры, однако для дальнейших ее изменений не подходит. 1.2 Актуальность работы Обратимся к более детальному рассмотрению существующего положения вещей и средств его улучшения. Для того, чтобы граф являлся графом смежности, необходимо поддерживать выполнение определённых условий (см. определение из раздела 2), результат проверки которых зависит от текущего набора данных; также, чтобы граф смежности являлся минимальным графом смежности, необходимо поддерживать выполнение других условий, которые, в свою очередь, также зависят от текущего набора данных. В отношении предложенных ранее жадного и прямого алгоритмов синтеза минимального графа смежности были построены теоретические оценки сложности, а также проведён статистический анализ сложности этих двух конкурирующих алгоритмов [3,4,29]. Результаты статистического анализа отношений скорости работы двух алгоритмов позволили выделить три поддиапазона мощности наборов вершин графов смежности: в поддиапазоне 5–35 жадный алгоритм работает существенно быстрее прямого, в поддиапазоне 60–105 прямой алгоритм работает существенно быстрее жадного алгоритма, а в поддиапазоне 35–60 выигрыш в скорости зависит от конкретного набора исходных данных. Кроме того, было установлено, что в диапазоне 5–60 имеется некоторое число статистических выбросов, сигнализирующих об особенностях в соответствующих наборах исходных данных. Наконец, следует учесть, что на достаточно большом множестве наборов нагрузок, а именно, когда мощность набора превышает некоторый уровень, оба алгоритма работают долго, в частности, и с субъективной

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 9 точки зрения пользователя тоже. Именно поэтому особенно актуальной задачей представляется добавление новой вершины 𝑣 в уже в существующий минимальный граф смежности 𝐺 = ⟨𝑉, 𝐸⟩ таким образом, чтобы граф 𝐺′ = ⟨𝑉 ∪ {𝑣}, 𝐸 ′ ⟩ также оказался бы минимальным графом смежности, а время, затраченное на построение множества 𝐸 ′ , было бы минимальным, либо хотя бы приемлемым с точки зрения пользователя или решаемых задач машинного обучения. 2 Определения и обозначения В данной главе описываются основные понятия и определения из теории алгебраических байесовских сетей, используемые в дальнейшем в работе, а также технологии, применяемые при разработке комплекса программ. 2.1 Теоретическая часть Воспользуемся системой терминов и обозначений, сложившихся в ранее опубликованных работах по данной тематике [6, 9, 13, 14, 16]. Пусть задан конечный алфавит символов , а непустые множества символов (без повторов) — слова — рассматриваются как возможные значения нагрузок вершин графов (в основном, графов смежности) и их ребер. В контексте настоящей работы вершины и их нагрузки соотносятся взаимооднозначно, поэтому мы будем использовать соответствующие им обозначения 𝑣 и 𝑊𝑣 взаимозаменяемо. Определение 1. Нагрузка вершины является допустимой, если она не совпадает с нагрузкой никакой другой вершины, не поглощается нагрузками и не поглощает нагрузки никаких других вершин. Определение 2. Назовем неориентированный граф 𝐺 = ⟨𝑉, 𝐸⟩ графом смежности, если он удовлетворяет следующим условиям:

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 10 1. Магистральность: ∀𝑢, 𝑣 ∈ 𝑉 таких, что 𝑊𝑢 ∩ 𝑊𝑣 ̸= ∅, существует некоторый путь 𝑃 в графе 𝐺 такой, что для каждой вершины 𝑠 ∈ 𝑃 справедливо утверждение 𝑊𝑢 ∩ 𝑊𝑣 ⊆ 𝑊𝑠 ; 2. ∀{𝑢, 𝑣} ∈ 𝐸 𝑊𝑢 ∩ 𝑊𝑣 ̸= ∅. При этом множество вершин такого графа будем называть его первичной структурой. Граф смежности с минимальным и максимальным числом ребер мы будем называть минимальным графом смежности и максимальным графом смежности соответственно. Определение 3. Пересечение нагрузок двух вершин 𝑊𝑢 ∩ 𝑊𝑣 будем называть сепаратором. Элементами сепаратора являются нагрузки. Введём ряд дополнительных обозначений, которые понадобятся нам при описании алгоритмов. PathExists(𝐺, edge, nodeBegin, nodeEnd) — функция, которая определяет, связаны ли магистрально вершины nodeBegin и nodeEnd графе 𝐺′ = ⟨𝑉, 𝐸 ′ ⟩, причем, 𝐺 = ⟨𝑉, 𝐸⟩, и 𝐸 ′ = {{𝑝, 𝑞} : {𝑝, 𝑞} ∈ 𝐸 & {𝑝, 𝑞} = ̸ edge}. edge.First, edge.Second — вершины ребра edge. edge.RemoveAllowed — метка, которая показывает, возможно ли удаление ребра edge или нет. Изначальное значение — TRUE. Пусть задан конечный алфавит символов 𝐴, а непустые множества символов (без повторов) — слова — рассматриваются как возможные значения нагрузок вершин графов (в основном, графов смежности) и их рёбер. Пусть имеется набор вершин 𝑉 = {𝑣1 , 𝑣2 , . . . , 𝑣𝑛 } и такие нагрузки 𝑊 = {𝑊1 , 𝑊2 , . . . , 𝑊𝑛 }, причем ∀𝑢 ∈ 𝑉 𝑊𝑢 является нагрузкой для вершины 𝑢.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 2.2 11 Технологическая часть Windows Presentation Foundation (WPF) [40] — система для построения клиентских приложений с визуально привлекательными возможностями взаимодействия с пользователем [43], графическая (презентационная) подсистема в составе .NET Framework [45] (начиная с версии 3.0), использующая расширяемый язык разметки XAML [44]. Model-View-ViewModel (MVVM) [39] — шаблон проектирования архитектуры приложения [42], ориентированный на современные платформы разработки, такие как Windows Presentation Foundation, Silverlight [38] от компании Microsoft [27]. Шаблон MVVM делится на три части: ∙ Модель (англ. Model), так же, как в классической MVC (Model-ViewController) — представляет собой фундаментальные данные, необходимые для работы приложения. ∙ Представление (англ. View) — это графический интерфейс, то есть окно, кнопки и так далее. Представление является подписчиком на событие изменения значений свойств или команд, предоставляемых Моделью представления. В случае, если в Модели представления изменилось какое-либо свойство, то она оповещает всех подписчиков об этом, и Представление, в свою очередь, запрашивает обновленное значение свойства из Модели представления. В случае, если пользователь воздействует на какой-либо элемент интерфейса, Представление вызывает соответствующую команду, предоставленную Моделью представления. ∙ Модель представления (англ. ViewModel) — является, с одной стороны, абстракцией Представления, а с другой, предоставляет обёртку данных из Модели, которые подлежат связыванию. То есть она содержит Модель, которая преобразована к Представлению, а также содержит

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 12 в себе команды, которыми может пользоваться Представление, чтобы влиять на Модель. 3 Инкрементальный алгоритм добавления вершины в минимальный граф смежности Задан минимальный граф смежности 𝐺, на вход алгоритму поступает указанный граф и новая вершина. Требуется построить новый минимальный граф смежности — такой, что множество вершин состоит из объединения множества вершин 𝑉 графа 𝐺 и новой вершины. При этом для простоты изложения, предполагаем, что набор нагрузок остается корректным: нагрузка новой вершины допустима, то есть её нагрузка и нагрузка любой вершины из множества 𝑉 не совпадают, а также нагрузка новой вершины не поглощает полностью нагрузку любой вершины из множества 𝑉 и не поглощается такими нагрузками. Используя формальные обозначения, то же самое запишем следующим образом. 𝐺 = ⟨𝑉, 𝐸⟩ — граф, подаваемый на вход алгоритму. 𝑣 — новая вершина, подаваемая на вход алгоритму. 𝐺′ = ⟨𝑉 ∪{𝑣}, 𝐸 ′ ⟩, где 𝐸 ′ — множество ребер минимального графа смежности 𝐺′ . Как отмечалось ранее, инкрементальный алгоритм берёт за основу построения минимального графа смежности 𝐺′ множество рёбер 𝐸 — благодаря такому подходу предполагается, что инкрементальный алгоритм будет работать быстрее жадного (прямого) алгоритма, так как большая или даже большая часть связей (рёбер) останется без изменений. Напомним, что в контексте данной работы обозначения вершины и её нагрузки совпадают. Такой подход будет удобен для чтения и понимания графиков, представленных ниже, а также в разделе о корректности алгоритма.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 3.1 13 Описание алгоритма На листинге 1 приведен псевдокод инкрементального алгоритма добавления новой вершины в минимальный граф смежности. Приведённый алгоритм добавляет новую вершину в существующий минимальный граф смежности 𝐺, а на выходе выдаёт минимальный граф смежности 𝐺′ с добавленной новой вершиной. Представленный алгоритм состоит из двух частей. В первой части алгоритма (строки 2–7) во вторичную структуру алгебраической байесовской сети добавляются все допустимые рёбра. Во второй (строки 8–19) части алгоритма происходит удаление тех ребер, отсутствие которых не приведёт к нарушению магистральной связности вершин графа, другими словами — синтезируется минимальный граф смежности. Рассмотрим алгоритм более подробно. В строке 3 в множество вершин 𝑉 ′ , состоящее в точности из вершин 𝑉 исходного графа 𝐺, добавляется новая вершина 𝑣. В строке 4 для каждой вершины из множества 𝑉 и новой вершины 𝑣 проверяется наличие непустого сепаратора. Если такой сепаратор есть, то в множество 𝐸 ′ добавляется соответствующее ребро. После добавления новой вершины и новых ребер формируется граф 𝐺′ . Затем из него необходимо удалить те ребра, отсутствие которых не приведёт к нарушению магистральных связей (строки 8–19). В результате такого преобразования граф 𝐺′ станет минимальным графом смежности. Отметим, что ребра удаляются с помощью жадного алгоритма, описанного в статьях [4, 6, 7]. Приведённый алгоритм позволяет добавлять новую вершину 𝑣 в уже существующий минимальный граф смежности 𝐺. Отметим, что в указанном алгоритме для добавления новой вершины не требуется заново синтезировать множество рёбер искомого графа смежности, так как инкрементальный алгоритм учитывает и дополняет полученные ранее результаты.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ Algorithm 1 Инкрементальный алгоритм добавления новой вершины в минимальный граф смежности. input: 𝐺 = ⟨𝑉, 𝐸⟩, 𝑣 output: 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ 1: function SimpleIncremental 2: 𝐸′ = 𝐸 3: 𝑉 ′ = 𝑉 ∪ {𝑣} 4: foreach (𝑢 in 𝑉 ) 5: if ((𝑊𝑢 ∩ 𝑊𝑣 ) ̸= ∅) then 6: 𝐸 ′ = 𝐸 ′ ∪ {𝑢, 𝑣} 7: 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ 8: while (TRUE) 9: 10: edge = ∅ foreach(𝑒 in 𝐸 ′ ) if (𝑒.RemoveAllowed) then 11: 12: edge = 𝑒 13: break foreach //Выход из foreach 14: if (edge == ∅) then break while //Выход из while 15: 16: if (PathExists(𝐺′ , edge, edge.First, edge.Second)) then 𝐸 ′ = 𝐸 ′ ∖ {edge} 17: 18: 19: 20: else edge.RemoveAllowed = FALSE return 𝐺′ 14

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 15 Отметим, что в инкрементальном алгоритме были использованы результаты и объекты, построенные на предыдущих шагах. В данном случае это — минимальный граф смежности, который предстоит дополнить новой вершиной, то есть, собственно основной результат предшествующего запуска алгоритма синтеза. В других случаях могут оказаться доступны и вспомогательные конструкции или объекты, которые использовались при построении основного результата. Например, такое можно ожидать в случае, когда стоит задача построить не один минимальный граф смежности, а все возможные минимальные графы смежности [17–21, 23]. Кроме того, учтём, что потребовалось строить не весь набор ребер максимального графа смежности, а лишь те рёбра, которые исходят из новой вершины. При этом экономия в числе операций может возникнуть, и, исключая особые, специально подобранные случаи, как правило, возникает, за счёт двух моментов. Во-первых, требуется построить меньшее число ребер. Во-вторых, последующий перебор для исключения избыточных рёбер идёт по меньшему их числу. Наконец, экономия может проявится и за счёт того, что из пользовательского интерфейса пересылаются сведения об одной новой вершине, а не о всей их совокупности. Конечно, в случае нагрузок графа смежности в той форме, в которой они описаны выше, эффект экономии не будет так заметен. Но если вершина в свою очередь определяется сложным объемным набором данных, оператор почувствует ускорение в обработке его команды. 3.2 3.2.1 Корректность алгоритма Алгоритм синтезирует граф смежности При добавлении сразу всех допустимых ребрер, исходящих из новой вершины 𝑣, в граф смежности, получается новый граф смежности; следовательно, после выполнения первой части алгоритма (строки 2–6), граф

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 16 𝐺′ также будет графом смежности, при этом допустимость этих рёбер обуславливается проверкой, осуществляемой в строке 5. Проанализируем корректность этой части алгоритма более подробно. Теорема 1. Пусть 𝐺 = ⟨𝑉, 𝐸⟩ — минимальный граф смежности, 𝑣 — добавляемая (новая) вершина, 𝑉 ′ = 𝑉 ∪ {𝑣}, а 𝐸 ′ = 𝐸 ∪ {{𝑣, 𝑤} : 𝑤 ∈ 𝑉 & 𝑊𝑣 ∩ 𝑊𝑤 ̸= ∅}, тогда 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ — граф смежности. Доказательство: Возьмём любые две вершины 𝑠 и 𝑟 ∈ 𝐺′ . Рассмотрим два случая. Сепаратор 𝑠 и 𝑟 ̸= ∅. Тогда докажем, что в графе 𝐺′ существует путь между заданными вершинами. Предположим, что обе данные вершины принадлежат исходному графу (𝑠 и 𝑟 ∈ 𝐺), тогда, по определению графа смежности, между данными вершинами существует некоторый путь. Если же одна из данных вершин не принадлежит исходному графу, то она совпадает с вершиной 𝑣 (𝑠 = 𝑣 или 𝑟 = 𝑣), следовательно, по определению множества 𝐸 ′ = 𝐸 ∪ {{𝑣, 𝑤} : 𝑤 ∈ 𝑉 & 𝑊𝑣 ∩ 𝑊𝑤 ̸= ∅} — между этими вершинами существует ребро, которое и является путём с нужными свойствами, то есть магистралью. Сепаратор 𝑠 и 𝑟 равен ∅. Тогда докажем, что в графе 𝐺′ не существует магистрали между этими вершинами. Предположим, что обе вершины принадлежат исходному графу(𝑠 и 𝑟 ∈ 𝐺), тогда, по определению графа смежности, между данными вершинами не существует ребра. Если же одна из вершин не принадлежит исходному графу, то она совпадает с вершиной 𝑣 (𝑠 = 𝑣 или 𝑟 = 𝑣), следовательно, по определению множества 𝐸 ′ = 𝐸 ∪ {{𝑣, 𝑤} : 𝑤 ∈ 𝑉 & 𝑊𝑣 ∩ 𝑊𝑤 ̸= ∅} — между данными вершинами не существует ребра. Таким образом, любая пара вершин, пересечение нагрузок которых непусто, соединены магистралью, а вершины, нагрузки которых не пересекаются, не соединены ребром. Граф, обладающий таким свойством, является графом смежности. Также следует отметить, что полученный на пер-

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 17 вом шаге граф не обязательно является минимальным графом смежности. Приведём пример. В минимальный граф смежности 𝐺 (рис. 1a) добавляется новая вершина 𝑣 с нагрузкой {𝑓, 𝑞} (рис. 1b). На первом шаге инкрементального алгоритма в граф добавляются несколько рёбер с нагрузками {𝑞} и {𝑓 } (рис. 1c). Заметим, что полученный граф 𝐺′ не является минимальным графом смежности, так как удаление ребра {𝑎𝑞, 𝑓 𝑞} или любого другого ребра с нагрузкой {𝑞} не приводит к нарушению свойств графа смежности (рис. 1d). 3.2.2 Алгоритм синтезирует минимальный граф смежности Теорема 2. Алгоритм (листинг 1) синтезирует минимальный граф смежности. Доказательство. Удаление ребра при сохранении магистральности есть не что иное, как переход от одного графа смежности к другому с уменьшением числа ребер. В статьях [6, 7] было доказано, что множество графов смежности формирует матроид. По свойствам матроида, последовательность допустимых удалений рёбер в графе смежности сходится, а полученный в результате завершившейся последовательности допустимых удалений граф окажется минимальным графом смежности. Действительно, как было показано ранее, после выполнения первой части алгоритма, граф 𝐺′ является графом смежности, а во второй части алгоритма происходят удаления допустимых рёбер. Таким образом, по свойствам матроида, алгоритм из листинга 1 на выходе формирует минимальный граф смежности, включающий новую вершину 𝑣, что и требовалось доказать.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 18 (a) Исходный граф (b) Новая вершина (c) Новые ребра (d) Новый минимальный граф смежности Рис. 1: Интеграция новой вершины в граф смежности с сохранением его минимальности.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 4 19 Улучшенный инкрементальный алгоритм добавления вершины в минимальный граф смежности Формальная постановка задачи эквивалентна задаче из раздела 3. За- дан минимальный граф смежности 𝐺, на вход алгоритму поступает указанный граф и новая вершина. Требуется построить новый минимальный граф смежности — такой, что множество его вершин состоит из объединения множества вершин 𝑉 графа 𝐺 и новой вершины. При этом для простоты изложения предполагаем, что набор нагрузок остается корректным: нагрузка новой вершины допустима, то есть её нагрузка и нагрузка любой вершины из множества вершин 𝑉 не совпадают, а также нагрузка новой вершины не поглощает полностью нагрузку любой вершины из множества 𝑉 и не поглощается такими нагрузками. Однако по сравнению с предыдущим алгоритмом, приведённый в данном разделе алгоритм дополнительно улучшен тем, что производится отбор кандидатов в новые рёбра: при построении связей из новой вершины берётся не вся возможная совокупность исходящих из неё ребер в вершины, нагрузки которых имеют попарно непустые пересечения с нагрузкой новой, а лишь те из них, сепаратор на которых отвечает определённым условиям. 4.1 Описание алгоритма На первом шаге пополнения уже построенного минимального графа смежности 𝐺 новой вершиной 𝑣 требуется провести в нём новые рёбра, исходящие из 𝑣 в другие вершины графа, причём, с одной стороны, пополненный граф должен остаться графом смежности, то есть сохранить свойство магистральной связности, а с другой стороны, среди новых рёбер не должно оказаться заведомо избыточных, то есть легко отсеиваемых

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 20 по некоторому критерию рёбер. Для построения такого набора рёбер введем функцию GetVerticesToConnect(𝐺, 𝑢), программная реализация которой приведена на листинге 2. Algorithm 2 Алгоритм вычисления множества «необходимых» вершин. input: 𝐺 = ⟨𝑉, 𝐸⟩, 𝑣 output: 𝑉 ′ 1: function GetVerticesToConnect 2: 𝑆′ = ∅ 3: 𝑉′ =∅ 4: 𝐻 =< {𝑉 ′ , 𝑆} > 5: foreach (𝑢 in 𝑉 ) 6: 𝑠𝑒𝑝 = 𝑊𝑢 ∩ 𝑊𝑣 7: if (𝑠𝑒𝑝 == ∅) then 8: continue foreach 9: 𝐴𝑑𝑑𝐴𝑙𝑙𝑜𝑤𝑒𝑑 = TRUE 10: 11: foreach (ℎ in 𝐻) if (𝑠𝑒𝑝 ⊆ ℎ.𝑆) then 12: 𝐴𝑑𝑑𝐴𝑙𝑙𝑜𝑤𝑒𝑑 = FALSE 13: breake foreach 14: if (𝑠𝑒𝑝 ⊃ ℎ.𝑆) then 𝐻 = 𝐻 {𝑣, ℎ.𝑆} 15: 16: 17: 18: if (𝐴𝑑𝑑𝐴𝑙𝑙𝑜𝑤𝑒𝑑) then 𝐻 = 𝐻 ∪ {(ℎ.𝑆, 𝑠𝑒𝑝)} return 𝐻.𝑉 ′ На первом шаге алгоритма вводится дополнительное множество 𝐻 (строка 4) — множество упорядоченных пар «вершина–сепаратор», которое будет содержать текущий набор «нужных» вершин и их сепараторы с вершиной 𝑣. Такая реализация позволяет не вычислять каждый раз сепаратор заново. Необходимо уточнить, что под удалением вершины из множества 𝐻 подразумевается удаление упорядоченной пары, включающей данную

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 21 вершину (строка 15). Далее, для всех вершин 𝑢 из множества вершин входного графа (строка 5), сепаратор с вершиной 𝑣 которых непуст (строка 7), объявляется флаг AddAllowed (строка 9), который указывает на уникальность вершины и соответствующего данной вершине сепаратора. Изначально он принимает значение TRUE. После этого вычисленный в строке 6 сепаратор сравнивается со всеми сепараторами ℎ.𝑆 из 𝐻. При этом возможны 3 случая: 1. Сепаратор является подмножеством сепаратора 𝑠 или равен ему (строка 11). Это означает, что вершины, имеющие сепаратор 𝑠, уже связаны с 𝑣, и добавление ещё одного ребра с такой же нагрузкой избыточно (строка 12). Более того, при добавлении этого ребра произойдет образование в графе 𝐺 цикла с нагрузкой 𝑠 (см. пример на рис.2). Рис. 2: Цикл с нагрузкой ⟨ а ⟩. 2. 𝑠 является подможеством сепаратора (строка 14). В этом случае новое ребро покроет собой все вершины, которые покрывались ребром с нагрузкой 𝑠 и, возможно, ещё некоторые из них. Это означает что, после добавления нового ребра, ребро с нагрузкой 𝑠 станет избыточно, и его нужно удалить из 𝐻 (строка 15) (см. пример на рис.3) 3. Все остальные случаи. Тогда сепараторы либо не пересекаются, либо пересекаются частично, а значит, каждый из них покрывает своё уникальное множество вершин и не может быть поглощён другим. Следует отметить, что если пересечение сепараторов не пусто, то в граф может

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 22 Рис. 3: Ребро ⟨ а ⟩ поглощается ⟨ аb ⟩. добавиться неэлиминируемый (неустранимый) цикл с нагрузкой, равной пересечению данных сепараторов (если нагрузка ребра не между вершинами 𝐺 не является подмножеством нового ребра). Рис. 4: Элиминируемый цикл с нагрузкой ⟨ а ⟩. Рис. 5: Неэлиминируемый цикл с нагрузкой ⟨ а ⟩. Если после описанных выше проверок значение флага AddAllowed осталось истинным, то множество 𝐻 дополняется новой упорядоченной парой (𝑢, 𝑊𝑢 ∩ 𝑊𝑣 ), и, после завершения цикла/обхода всех вершин 𝑢 графа 𝐺, будет состоять из минимального по мощности множества вершин и их сепараторов, добавление ребра к которым необходимо для сохранения свойств магистральности графа 𝐺. Описанные выше результаты использованы в алгоритме на листинге 3. Этот алгоритм инкрементальный, он добавляет новую вершину в минимальный граф смежности. Ему на вход поступают уже существующий

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ Algorithm 3 Улучшенный инкрементальный алгоритм добавления новой вершины в минимальный граф смежности. input: 𝐺 = ⟨𝑉, 𝐸⟩, 𝑣 output: 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ 1: function SmartIncremental 2: 𝐸′ = 𝐸 3: 𝑉 ′ = 𝑉 ∪ {𝑣} 4: foreach (𝑢 in GetVerticesToConnect(G, v)) 𝐸 ′ = 𝐸 ′ ∪ {𝑢, 𝑣} 5: 6: 𝐺′ =< 𝑉 ′ , 𝐸 ′ > 7: while (TRUE) 8: edge = ∅ 9: foreach(𝑒 in 𝐸 ′ ) if (𝑒.RemoveAllowed) then 10: 11: edge = 𝑒 12: break foreach //Выход из foreach 13: if (edge == ∅) then break while //Выход из while 14: 15: if (PathExists(𝐺′ , edge, edge.First, edge.Second)) then 𝐸 ′ = 𝐸 ′ ∖ {edge} 16: 17: 18: 19: else edge.RemoveAllowed = FALSE return 𝐺′ 23

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 24 минимальный граф смежности 𝐺 и новая вершина, а алгоритм в свою очередь возвращает минимальный граф смежности 𝐺′ с добавленной новой вершиной. Алгоритм улучшен в части предварительного отбора новых рёбер. Код алгоритма делится на две части. В первой части (строки 2–6) для исходного графа 𝐺 вычисляется минимальное по мощности множество вершин, проведение рёбер от которых в новую вершину обеспечит магистральность графа 𝐺′ , то есть сделает его графом смежности, и для каждой такой вершины в граф добавляется соответствующее ребро. Во второй части (строки 7–18) из графа удаляются все ребра, отсутствие которых не нарушает магистральную связность графа. 4.2 4.2.1 Корректность алгоритма Алгоритм синтезирует граф смежности Теорема 3. Пусть 𝐺 = ⟨𝑉, 𝐸⟩ — минимальный граф смежности, 𝑣 — добавляемая в него вершина, 𝑉 ′ = 𝑉 ∪ {𝑣}, 𝐻 = {ℎ : ℎ ∈ 𝑉, 𝑊ℎ ∩ 𝑊𝑣 ̸= ∅, ∀ℎ′ ∈ 𝐻 : ℎ′ ̸= ℎ, ℎ ∈ / ℎ′ }, а 𝐸 ′ = 𝐸 ∪{{𝑢, 𝑤} : 𝑤 ∈ 𝐻}, тогда 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ — граф смежности. Доказательство. Возьмем любые две вершины 𝑠, 𝑟 ∈ 𝐺′ . Возможны два случая. Первый — сепаратор 𝑠 и 𝑟 ̸= ∅, тогда докажем, что в 𝐺′ вершины 𝑠 и 𝑟 магистрально связаны. Предположим, что обе вершины принадлежат исходному графу, тогда, по определению графа смежности, между ними существует магистраль. Если же одна из вершин не принадлежит исходному графу, то она совпадает с вершиной 𝑣, а значит, по определению множества 𝐸 ′ = 𝐸 ∪ {{𝑢, 𝑤} : 𝑤 ∈ 𝐻} и построению множества 𝐻, между ними существует магистраль. Второй — сепаратор 𝑠 и 𝑟 = ∅, тогда докажем, что в 𝐺 не существует

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 25 ребра между этими вершинами. Предположим, что обе вершины принадлежат исходному графу, тогда, по определению графа смежности, между ними не существует ребра. Если же одна из вершин не принадлежит исходному графу, то она совпадает с вершиной 𝑣(𝑠 = 𝑣 или 𝑟 = 𝑣), а значит, по определению множества 𝐸 ′ = 𝐸 ∪ {{𝑢, 𝑤} : 𝑤 ∈ 𝐻} и по построению множества 𝐻, в графе 𝐺′ между ними не существует ребра. Таким образом, любая пара вершин, пересечение нагрузок которых непустое, соединены магистралью, а вершины, нагрузки которых не пересекаются, не соединены ребром. Граф, обладающий таким свойством, является графом смежности, но не обязательно минимальным. 4.2.2 Алгоритм синтезирует минимальный граф смежности Теорема 4. Алгоритм (листинг 3) синтезирует минимальный граф смежности. Доказательство. Рассмотрим вторую часть алгоритма подробнее. Сначала в множество вершин 𝐺′ добавляются новая вершина 𝑣 и все вершины исходного графа 𝐺 (строка 3). Далее формируется минимальное множество вершин, добавление ребра к которым необходимо для сохранения свойств смежности, и для каждой такой вершины 𝑢 (строка 4) в множество ребер 𝐸 ′ добавляется соответствующее ребро {𝑣, 𝑢} (строка 5). После добавления новой вершины и новых ребер формируется граф смежности 𝐺′ . Далее, из графа 𝐺′ необходимо удалить все те рёбра, отсутствие которых не приведёт к нарушению магистральных связей (строки 7–18). Данное преобразование описано, а также улучшено в [3, 4, 6, 21]. В его результате граф 𝐺′ станет минимальным графом смежности.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 5 26 Декрементальный алгоритм удаления вершины Задан минимальный граф смежности 𝐺 и одна из его вершин 𝑣; граф 𝐺 и вершина 𝑣 подаются на вход алгоритму. Требуется построить новый минимальный граф смежности — такой, что множество вершин состоит из разности множества вершин 𝑉 графа 𝐺 и выбранной вершины. Используя формальные обозначения, то же самое запишем следующим образом. 𝐺 = ⟨𝑉, 𝐸⟩ — граф, подаваемый на вход алгоритму. 𝑣 ∈ 𝑉 — вершина, которую нужно удалить. 𝐺′ = ⟨𝑉 ∖{𝑣}, 𝐸 ′ ⟩, где 𝐸 ′ — множество ребер минимального графа смежности 𝐺′ . Декрементальный алгоритм берёт за основу построения минимального графа смежности 𝐺′ множество ребер 𝐸 — благодаря такому подходу предполагается, что декрементальный алгоритм будет работать быстрее жадного (прямого) алгоритма, так как большая или даже большая часть связей (рёбер) останется без изменений. Напомним, что в контексте настоящей работы обозначения вершины и её нагрузки совпадают. Такой подход будет удобен для чтения и понимания графиков, представленных ниже, а также в разделе о корректности алгоритма. 5.1 Описание алгоритма На листинге 4 приведён псевдокод декрементального алгоритма удаленя вершины из минимального графа смежности. Алгоритм состоит из двух частей. В первой части (строки 2–19) формируется граф смежности, с множеством вершин 𝑉 ∖ 𝑣 и множеством рёбер, состяещем из множества рёбер исходного графа без рёбер, инцидентных вершине 𝑣, а также из всех возможных рёбер между вершинами таких рёбер (без 𝑣). Во второй части из вышеописанной вторичной структуры

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ Algorithm 4 Декрементальный алгоритм удаления вершины из минимального графа смежности. input: 𝐺 = ⟨𝑉, 𝐸⟩, 𝑣 ∈ 𝑉 output: 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ 1: function DeleteIncremental 2: 𝐸′ = 𝐸 3: 𝑉′ =𝑉 4: 𝐸 ′′ = ∅ 5: 𝑉 ′′ = ∅ 6: foreach (𝑒 in 𝐸) 7: if (𝑒.𝐹 𝑖𝑟𝑠𝑡 == 𝑣) then 8: 𝑉 ′′ = 𝑉 ′′ ∪ {𝑒.𝑆𝑒𝑐𝑜𝑛𝑑} 9: 𝐸 ′′ = 𝐸 ′′ ∪ {𝑒} 10: if (𝑒.𝑆𝑒𝑐𝑜𝑛𝑑 == 𝑣) then 11: 𝑉 ′′ = 𝑉 ′′ ∪ {𝑒.𝐹 𝑖𝑟𝑠𝑡} 12: 𝐸 ′′ = 𝐸 ′′ ∪ {𝑒} 13: 14: foreach (𝑥 in 𝑉 ′′ ) foreach (𝑦 in 𝑉 ′′ ) 15: if ((𝑊𝑥 ∩ 𝑊𝑦 ) ̸= ∅) then 16: 𝐸 ′ = 𝐸 ′ ∪ {𝑥, 𝑦} 17: 𝐸 ′ = 𝐸 ′ ∖ 𝐸 ′′ 18: 𝑉 ′ = 𝑉 ′ ∖ {𝑣} 19: 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ 20: while (TRUE) 21: 𝑒𝑑𝑔𝑒 = ∅ 22: foreach(𝑒 in 𝐸 ′ ) if (𝑒.𝑅𝑒𝑚𝑜𝑣𝑒𝐴𝑙𝑙𝑜𝑤𝑒𝑑) then 23: 24: 𝑒𝑑𝑔𝑒 = 𝑒 25: break foreach //Выход из foreach 26: if (𝑒𝑑𝑔𝑒 == ∅) then break while //Выход из while 27: 28: if (PathExists(𝐺′ , 𝑒𝑑𝑔𝑒, 𝑒𝑑𝑔𝑒.𝐹 𝑖𝑟𝑠𝑡, 𝑒𝑑𝑔𝑒.𝑆𝑒𝑐𝑜𝑛𝑑)) then 𝐸 ′ = 𝐸 ′ ∖ {𝑒𝑑𝑔𝑒} 29: 30: 31: 32: else 𝑒𝑑𝑔𝑒.𝑅𝑒𝑚𝑜𝑣𝑒𝐴𝑙𝑙𝑜𝑤𝑒𝑑 = FALSE return 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ 27

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 28 алгебраической байесовской сети удаляются рёбра, отсутствие которых не приведёт к нарушению магистральных связей (строки 20–31). Рассмотрим алгоритм более подробно. В строках 4–12 формируется множество 𝐸 ′′ , состоящее из рёбер, инцидентных вершине 𝑣 (строки 9, 12), а также множество вершин 𝑉 ′′ , состоящее из вершин рёбер 𝐸 ′′ , но не включающее в себя вершину 𝑣 (строки 8, 11). Далее в множество 𝐸 ′ добавляются всевозможные рёбра между вершинами из множества 𝑉 ′′ (строка 16), пересечение нагрузок которых не пусто (строка 15). После этого формируется граф 𝐺′ = ⟨𝑉 ′ , 𝐸 ′ ⟩ (строка 19). Из данного графа необходимо удалить те ребра, отсутствие которых не приведёт к нарушению магистральных связей (строки 19–30). В результате такого преобразования граф 𝐺′ станет минимальным графом смежности. Отметим, что рёбра удаляются с помощью жадного алгоритма, описанного в статье. 5.2 5.2.1 Корректность алгоритма Алгоритм синтезирует граф смежности Теорема 5. Вышеописанный алгоритм синтезирует граф смежности. Доказательство. При добавлении допустимого ребра в минимальный граф смежности получается новый граф смежности, а удаление вершины и инцидентных ей рёбер с последущим добавлением допустимой клики на её место — переход от одного графа смежности к другому, с мешьшим числом вершин. Следовательно, после выполнения первой части алгоритма, граф 𝐺′ будет графом смежности, при этом допустимость этих ребер обслувливается проверкой, осуществляемой в строке 15.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 5.2.2 29 Алгоритм синтезирует минимальный граф смежности Теорема 6. Алгоритм (листинг 4) синтезирует минимальный граф смежности. Доказательство. Удаление ребра при сохранении магистральности есть не что иное, как переход от одного графа смежности к другому с уменьшением числа рёбер. В статьях было доказано, что множество графов смежности формирует матроид. По свойствам матроида, последовательность допустимых удалений рёбер в графе смежности сходится, а полученный в результате завершившейся последовательности допустимых удалений граф будет минимальным графом смежности. Действительно, как было показано ранее, после выполнения первой части алгоритма, граф 𝐺′ является графом смежности, а во второй части алгоритма происходит допустимое удаление рёбер. Таким образом, по свойствам матроида, алгоритм из листинга 4 на выходе формирует минимальный граф смежности, не включающий вершину 𝑣, что и требовалось доказать. 6 Система анализа и синтеза Представленная в данной выпускной квалификационной работе систе- ма позволяет пользователям проводить анализ и синтез различых структур АБС, наглядно изучать поведение структур АБС при поступлении в сеть новых данных, а также проводить различного рода вычисления, важные в контексте вероятностных графических моделей. Разработанная платформа могла бы быть полезна для сотрудников математических кафедр университетов, занимающихся изучением АБС, как в качестве наглядного пособия, так и в качестве базовой библиотеки для дальнейших разработок. Также следует отметить, что данная система является результатом совместной разработки с Романовым Артемом Витальевичем и Березиным Алексеем

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 30 Ивановичем, однако в данной главе описан только мой вклад в данный комплекс программ. В качестве языка программирования для реализации системы был выбран язык С# [26], поскольку на конечную систему налагался ряд требований, а именно: расширяемость и масштабируемость системы, высокая скорость работы технологии. Платформой для разработки была выбрана Microsoft Visual Studio 2015 [25]. Также использовался BitBucket [28], в качестве общего репозитория для совместной разработки системы. 6.1 Общие интерфейсы Для совместной разработки системы были разработаны следующие интерфейсы: 𝐼𝐷𝑎𝑡𝑎 и 𝐼𝑆𝑒𝑝𝑎𝑟𝑎𝑏𝑙𝑒, которые будут рассмотрены подробнее в следующих разделах. В качестве базового интерфеса графа был выбран интерфейс 𝐼𝐵𝑖𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛𝑎𝑙𝐺𝑟𝑎𝑝ℎ < 𝑇 𝑉 𝑒𝑟𝑡𝑒𝑥, 𝑇 𝐸𝑑𝑔𝑒 >, реализованный в библиотеке с открытым исходным кодом QuickGraph [41]. Отмечу, что в контексте данной системы данный интерфейс, налагаемый на граф вторичной структуры выглядит так — 𝐼𝐵𝑖𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛𝑎𝑙𝐺𝑟𝑎𝑝ℎ < 𝐼𝑆𝑒𝑝𝑎𝑟𝑎𝑏𝑙𝑒 < 𝐼𝐷𝑎𝑡𝑎 >, 𝐼𝐸𝑑𝑔𝑒 < 𝐼𝑆𝑒𝑝𝑎𝑟𝑎𝑏𝑙𝑒 < 𝐼𝐷𝑎𝑡𝑎 >>>, где 𝐼𝐸𝑑𝑔𝑒 — интерфейс, также реализованный в библиотеке QuickGraph. 6.1.1 IData Основной задачей данного интерфейса является обеспечение взаимодействия алгоритмов, отвечающих за генерацию и хранение вторичной структры и алгоритмов локального и глобального вывода. Также данный интерфейс позволяет абстрагироваться от конкретных типов данных, позволяя в дальнейшем работать с различными представлениями коньюнктов.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 31 Листинг 1: Интерфейс IData. p u b l i c i n t e r f a c e IData : IComparable , IComparable<IData >, IEquatable <IData> { s t r i n g Data ( ) ; } 6.1.2 ISeparable Данный интерфейс представляет собой вершину графа. Листинг 2: Интерфейс ISeparable<T>. p u b l i c i n t e r f a c e I S e p a r a b l e <T> : IComparable , IComparable<I S e p a r a b l e <T>>, IEquatable <I S e p a r a b l e <IData>> where T: IData { IEnumerable<T> ListOfData ( ) ; i n t IntData ( ) ; I S e p a r a b l e <T> G e t S e p a r a t o r ( I S e p a r a b l e <T> s e p a r a t o r ) ; I S e p a r a b l e <T> G e t S e p a r a t o r ( IEnumerable<T> i t e r a t i o n ) ; b o o l I s S u b s e t O f ( I S e p a r a b l e <T> o t h e r ) ; b o o l I s S u b s e t O f ( IEnumerable<T> o t h e r ) ; } 6.2 Визуализация графа Одной из подзадач данной работы является визуализация графа, поскольку все структуры АБС могут быть наглядно представлены в виде графа. Например: вторичная структура АБС сама по себе является графом, а вот первичная структура может быть представлена в виде максимального графа смежности, то есть графа смежности, с максимальным числом ребер.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 32 В качестве основного инструмента визуализации графа, был выбран фреймворк с открытым исходным кодом Graph# [36], основанный на библиотеке QuickGraph [41]. Данный фреймворк включает в себя весь необходимый в контексте данной работы набор форм для отрисовки графа, однако не содержит никакой доступной докуметации, что существенно сказывается на времени освоения данной техологии. Чтобы продемонстрировать всю простоту визуализации графа с помощью данного фреймворка, приведём пример кода: Листинг 3: Визуализация графа. 1 : <zoom : ZoomControl Mode=" O r i g i n a l " Grid . RowSpan="2" Grid . ColumnSpan="4"> 2: <graph : GraphLayout 3: Graph="{ Binding GraphToVisuale , Mode=OneWay}" 4: LayoutAlgorithmType="{ Binding S e l e c t e d I t e m }" 5: OverlapRemovalAlgorithmType="FSA" 6: H i g h l i g h t A l g o r i t h m T y p e=" Simple " 7: > 8: </graph : GraphLayout> 9 : </zoom : ZoomControl> На листинге 3 приведен отрывок XAML-кода, взятого из проекта, который используется для отображения графа. Рассмотрим подробнее: в строках 1–2 создаются два объекта — ZoomControl, который позволяет менять масштаб дочерних компонентов, и GraphLayout, отображающий граф. При этом, в строках 3–6 указываются параметры отображаемого графа, например: алгоритм расположения вершин на форме, макет графа и т.п. Конкретнее: в строке 3 граф, которой должен отображаться в форме graph (View часть паттерна MVVM), связывается (binding) с его представлением из ViewModel, также как и макет графа в строке 4.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 6.3 33 Графический пользовательский интерфейс Графический пользовательский интерфейс представляет собой набор диалоговых окон. Основой интерфейса является главное окно, представленное на рисунке 6. Рис. 6: Главное окно. В главном окне располагаются несколько групп элементов, таких как «Панель для работы с файлами» или «Панель для работы с АБС», которые детально рассмотрены в следующих разделах.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 6.3.1 34 Панель для работы с файлами Рис. 7: Панель для работы с файлами. Панель для работы с файлами представляет собой три кнопки со следующей функциональностью: 1) создание нового файла с пустой АБС; 2) загрузкой АБС из файла; 3) сохранением АБС в файл. Иконки к кнопкам выбраны максимально похожие на соответствующие иконки из операционной системы Windows, чтобы пользователь интуитивно понимал их функциональность. Рассмотрим реализацию этих функциональностей подробнее, на примере кнопки сохранения: Сохранение АБС в файл: Поскольку MVVM-паттерн требует разделения модели и её представления — ниже приведен XAML-код кнопки сохранения АБС в файл, а также отрывок кода из ViewModel, реализующий её функциональность. Листинг 4: SaveButton <Button Grid . Column="2" Command="{ Binding SaveCommand}" Height=" 90 "> <S t a ckPanel H o r i z o n t a l A l i g n m e n t=" Center " V e r t i c a l A l i g n m e n t=" Center "> <Image Source=" images \ SaveImg . png" MinHeight=" 50 " MinWidth=" 50 " Height=" 64 " Width=" 60 "/>

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ <TextBlock Text="{x : S t a t i c p : GraphResource . S a v e S t r i n g }" H o r i z o n t a l A l i g n m e n t=" Center " V e r t i c a l A l i g n m e n t="Top" MinHeight=" 20 "/> </StackPanel> </Button> Листинг 5: SaveCommand p u b l i c v o i d SaveCommandAction ( ) { _stopSaving = f a l s e ; var d l g = new M i c r o s o f t . Win32 . S a v e F i l e D i a l o g { FileName = "Graph" , D e f a u l t E x t = " . xml" , F i l t e r = "Xml documents ( . xml ) | * . xml" }; var r e s u l t = d l g . ShowDialog ( ) ; i f ( r e s u l t != t r u e ) { _stopSaving = t r u e ; r e t u r n ; } var f i l e n a m e = d l g . FileName ; try { XmlTools . WriteToXml ( f i l e n a m e , _abnData ) ; _isDataDirty = f a l s e ; } catch { MessageBox . Show ( " E r r o r s a v i n g " ) ; } } Листинг 6: Класс XmlTools // / <summary> 35

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ // / C l a s s XmlTools . // / </summary> p u b l i c s t a t i c c l a s s XmlTools { // / <summary> // / Convets t o abn i n XML. // / </summary> // / <param name="abn">The abn.</param> // / <r e t u r n s >AbnInXml.</ r e t u r n s > p r i v a t e s t a t i c AbnInXml ConvetToAbnInXml ( AbnData abn ) { var nodes = abn . S e c o n d a r y S t r u c t u r e . V e r t i c e s . S e l e c t ( node => node . ListOfData . S e l e c t ( data => data . GetData ( ) ) . ToList ( ) ) . S e l e c t ( l i s t O f D a t a => new VertexInXml {Data = listOfData }) . ToList ( ) ; r e t u r n new AbnInXml { V e r t i c e s = nodes } ; } // / <summary> // / Convets t o abn . // / </summary> // / <param name="o v e r v i e w">The o v e r v i e w .</param> // / <r e t u r n s >AbnData.</ r e t u r n s > p r i v a t e s t a t i c AbnData ConvetToAbn ( AbnInXml o v e r v i e w ) { var l i s t = o v e r v i e w . V e r t i c e s . S e l e c t ( v e r t => v e r t . Data . S e l e c t ( data => new S t r i n g D a t a ( data ) ) . Cast<IData >() . ToList ( ) ) . S e l e c t ( vertData => new VertexData<IData >( vertData ) ) . Cast<I S e p a r a b l e <IData >>() . ToList ( ) ; r e t u r n new AbnData ( l i s t ) ; } 36

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ // / <summary> // / Reads from XML. // / </summary> // / <param name="path">The path .</param> // / <r e t u r n s >AbnData.</ r e t u r n s > p u b l i c s t a t i c AbnData ReadFromXml ( s t r i n g path ) { var r e a d e r = new System . Xml . S e r i a l i z a t i o n . X m l S e r i a l i z e r ( t y p e o f ( AbnInXml ) ) ; u s i n g ( var f i l e = new System . IO . StreamReader ( path ) ) { var o v e r v i e w = ( AbnInXml ) r e a d e r . D e s e r i a l i z e ( f i l e ) ; r e t u r n ConvetToAbn ( o v e r v i e w ) ; } } // / <summary> // / Writes t o XML. // / </summary> // / <param name="path">The path .</param> // / <param name="abn">The abn.</param> p u b l i c s t a t i c v o i d WriteToXml ( s t r i n g path , AbnData abn ) { var w r i t e r = new System . Xml . S e r i a l i z a t i o n . X m l S e r i a l i z e r ( t y p e o f ( AbnInXml ) ) ; u s i n g ( var w f i l e = new System . IO . StreamWriter ( path ) ) { w r i t e r . S e r i a l i z e ( w f i l e , ConvetToAbnInXml ( abn ) ) ; } } } 37

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 6.3.2 38 Панель для работы с АБС Рис. 8: Панель для работы с АБС. Панель для работы с АБС также представлена тремя кнопками с функциональностью: 1) очищение АБС до пустой; 2) создание случайной АБС; 3) перестроение АБС. Также как и в случае с кнопками из предыдущей панели, их функциональность будет рассмотрена подробнее: Функциональность кнопки «Случайный»: иногда для проверки работоспособности или демонстрации системы требуется создать АБС и добавить в нее некоторое колличество вершин, однако в таких случаях удобнее машинно генерировать слуйчайную АБС, что и позвоялет делать эта кнопка. Функциональность кнопки «Перестроить»: поскольку отображаемые графы не являются статическими, и пользователь может проводить с ними некоторые манипуляции (перемещение вершин, изменение масштаба и так далее), иногда может потребоваться получить их начальный вид и структуру, что и позволяет сделать данная кнопка.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 6.3.3 39 Панель для работы с графом Рис. 9: Панель для работы с графом. Панель для работы с графом содержит информацию о количестве вершин и ребер отображаемого графа, кнопки «Добавить вершину» и «Удалить вершину», а также соответствующие им поля ввода. Кроме этого панель содержит ComboBox, позволяющий пользователю выбирать стиль отображения графа, например: Circular или Tree. 6.3.4 Панель структур АБС Рис. 10: Панель структур АБС.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 40 Панель структур АБС: состоит из набора вкладок (tab items) для каждой глобальной структуры АБС, на которых отоброжается информация о соответствующей структуре АБС: Рис. 11: Вкладка «Первичная структура». Рис. 12: Вкладка «Вторичная структура».

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ Рис. 13: Вкладка «Третичная структура». Рис. 14: Вкладка «Четвертичная структура». 41

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 42 Рис. 15: Вкладка «Множество минимальных графов смежности». 1. Вкладка «Первичная структура» (рис. 11). 2. Вкладка «Вторичная структура» (рис. 12). 3. Вкладка «Третичная структура» (рис. 13). 4. Вкладка «Четвертичная структура» (рис. 14). 5. Вкладка «Множество минимальных графов смежности» (рис. 15). Вкладка «Первичная структура» состоит из GraphLayout-а, отображающего первичную структуру АБС в виде максимального графа смежности, а также ZoomControl-а, позволяющего менять масштаб этого графа. Такой нестандартный способ отображения первичной структуры был выбран изза большей наглядности по сравнению с традиционным представлением первичной структуры в виде списка вершин. Вкладка «Вторичная структура» также содержит GraphLayout и ZoomControl, отвечающие за отображение вторичной структуры АБС — минимального графа смежности. Отметим, что множество минимальных

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 43 графов смежности [18, 23], зачастую, имеет мощность больше еденицы, и выбор одного из таких графов не является принципиальным. Однако алгоритмы локального и глобального вывода могут работать быстрее или медленнее на разных элементах такого множества, но явная зависимость от конкретных характеристик вторичной структуры пока не выявлена, и нуждается в дальнейшем изучении, не входящем в рамки текущей работы. Вкладка «Третичная структура» отличается от предыдущей вкладки лишь тем, что GraphLayout отображает третичную структуру АБС, используя алгоритм отображения графа «Tree». Вкладка «Четвертичная структура» состоит из списка графов, именнованых по их сепаратору, а также GraphLayout-а, отображающего выбранный граф. Вкладка «Множество минимальных графов смежности» также состоит из списка графов и GraphLayout-а, отображающего выбранный граф. Заключение В данной работе рассмотрены три алгоритма, существенно ускоряющие синтез [2,5] нового минимального графа смежности при изменении первичной структуры исходного минимального графа смежности. Вышеуказанные алгоритмы особенно удобны для интерактивных программных систем, когда минимальный граф смежности строится в диалоге с пользователем. Последний ожидает от системы достаточного быстродействия, полагая, что небольшое изменение в данных, в частности, при добавлении или удалении вершины, влечет умеренное изменение минимального графа смежности. Разработана система анализа и синтеза вторичной структуры АБС, реализующая все предъевленные к ней требования. Все задачи выполнены. Все цели достигнуты.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 44 Список литературы [1] Золотин А.А., Тулупьев А.Л., Сироткин А.В. Матрично-векторные алгоритмы нормировки для локального апостериорного вывода в алгебраических байесовских сетях // Научно-технический вестник информационных технологий, механики и оптики. 2015. Том 15. № 1. С. 78–85. [2] Зотов М.А., Левенец Д.Г., Тулупьев А.Л., Золотин А.А. Синтез вторичной структуры алгебраических байесовских сетей: инкрементальный алгоритм и статистическая оценка его сложности // Научнотехнический вестник информационных технологий, механики и оптики. 2016. № 1. С. 122–132. [3] Зотов М.А., Тулупьев А. Л. Синтез вторичной структуры алгебраических байесовских сетей. // Компьютерные инструменты в образовании(2015. Выпуск 1). [4] Зотов М.А., Тулупьев А.Л., Сироткин А.Л. Статистические оценки сложности прямого и жадного алгоритмов синтеза вторичной структуры алгебраических байесовских сетей // Нечеткие системы и мягкие вычисления. 2015. Т. 10. №1. С. 75–91 [5] Левенец Д.Г., Зотов М.А., Тулупьев А.Л. Инкрементальный алгоритм синтеза минимального графа смежности. // Компьютерные инструменты в образовании. 2015. № 6. С. 3–18. [6] Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности. // Тр. СПИИРАН. 2009. №11. C. 142–157. [7] Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 45 государственного университета информационных технологий, механики и оптики. 2010. №4(68). С. 73–76. [8] Тулупьев А.Л. Автоматическое обучение фрагментов знаний в алгебраических байесовских сетях // Интегрированные модели и мягкие вычисления в искусственном интеллекте. V-я Международная научнопрактическая конференция. Сборник научных трудов. В 2-х т. Т. 1. С. 163–176. [9] Тулупьев А.Л. Алгебраические байесовские сети: глобальный логиковероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. С. 40. (Сер. Элементы мягких вычислений). [10] Тулупьев А.Л. Алгебраические байесовские сети: локальный логиковероятностный вывод: // Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. С. 80. (Сер. Элементы мягких вычислений) [11] Тулупьев А.Л. Алгебраические байесовские сети: открытые вопросы локального автоматического обучения // СПИСОК-2014: Материалы всероссийской научной конференции по проблемам информатики. Санкт-Петербург, 2014. С. 569–577. [12] Тулупьев А.Л. Вероятностная логика и вероятностные графические модели в базах фрагментов знаний с неопределенностью // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов (Коломна, 26–27 мая 2009 г.). Научные доклады. В 2-х т. Т. 1. М.: Физматлит, 2009. С. 26–46.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 46 [13] Тулупьев А.Л. Дерево смежности с идеалами конъюнктов как ациклическая алгебраическая байесовская сеть // Тр. СПИИРАН. Вып. 3, т. 1. СПб.: Наука, 2006. С. 198–227. [14] Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. С. 607. [15] Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальнойструктуры алгебраической байесовской сети в Javaприложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99. [16] Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009. С. 400. [17] Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей. Дисс.... к-та физ.-мат. н. Самара, 2013. С. 339. (Самарск. гос. аэрокосм. ун-т им. ак. С.П. Королева (нац. исслед.)) [18] Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза минимального графа смежности // Тр. СПИИРАН. 2013. Вып. 2(35). С. 221–234. ун-т. [19] Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Тр. СПИИРАН. 2011. №17. С. 151–173. [20] Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Тр. СПИИРАН. 2009. №11. C. 104–129. [21] Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные графы смежности алгебраической байесовской сети: нормализация основ

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 47 синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления. 2011. Т. 6. № 2. С. 145-163. [22] Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. № 1 (12). С. 97-118. (цит. 24, ИФ РИНЦ) [23] Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система синтеза подмножеств минимальных графов смежности // Тр. СПИИРАН. 2013. Вып. 4(27). С. 200–244. [24] Шинкаренко В.И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширования // Математические машины и системы. 2007. №2. С. 43–55. [25] Обзор продуктов Visual Studio 2015 [Электронный ресурс]. Режим доступа: URL: https://www.visualstudio.com/ru-ru/products/vs2015-product-editions.aspx (дата обращения 07.05.2016). [26] Руководство по программированию на C# [Электронный ресурс]. Режим доступа: URL: https://msdn.microsoft.com/ru- ru/library/67ef8sbd.aspx (дата обращения 07.05.2016). [27] Сайт компании Microsoft [Электронный ресурс]. Режим доступа: URL: https://www.microsoft.com/ru-ru/ (дата обращения 07.05.2016). [28] Сайт проекта BitBucket [Электронный ресурс]. Режим доступа: URL: https://bitbucket.org/ (дата обращения 07.05.2016). [29] Barrett C., Marathe A., Marathe M., Cook D., Hicks G., Faber V., Srinivasan A., Sussmann Y., Thornquist H. Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry. Journal of Graph Algorithms and Applications (JGAA). 2003. Vol. 7. P. 3–31.

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 48 [30] Jaynes E.T. Bayesian Methods: General Background // Maximum-Entropy and Bayesian Methods in Applied Statistics, by J. H. Justice (ed.). Cambridge: Cambridge Univ. Press, 1986. P. 1–19. [31] Kas M., Wachs M., Carley K.M., Carley.L.R. Incremental Algorithm for Updating Betweenness Centrality in Dynamically Growing Networks. // Ozyer, T and Carrington, P, editor,2013 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), p.39–46, 345 E 47TH ST, Newyork, NY 10017 USA, 2013. IEEE. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Niagara Falls, Canada, aug. 25–28, 2013. [32] Maier D. Theory of Relational Databases. // Rockville, MD: Computer Science Press, 1983. P. 637 [33] Pearl J. Causality: Models, Reasoning, and Inference. Cambridge: Cambridge University Press, 2000. P. 400. [34] Respondek J. S. Dynamic data structures in the incremental algorithms operating on a certain class of special matrices //Computational Science and Its Applications–ICCSA 2014. – Springer International Publishing, 2014. – С. 171-185. [35] Song X., Yu L., Sun H. An Incremental Query Algorithm for Optimal Path Queries Under Traffic Jams. // Yu, F and Chen, W and Chen, Z and Yuan, J, editor, ISCSCT 2008: International Symposiumon Computer Science and Computational Technology, Proceedings, p.472–475, 10662 Los Vaqueros Circle, PO BOX3014, Los Alamitos, CA 90720-1264 USA, 2008. IEEE Computer SOC. International Symposium on Computer Science and Computational Technology, Shanghai, Peoples R China, dec.20–22, 2008. [36] Graph# [Электронный ресурс]. Режим доступа: https://graphsharp.codeplex.com/ (дата обращения 07.05.2016). URL:

49 АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ [37] Incremental algoritms [Электронный ресурс]. Режим доступа: URL: http://c2.com/cgi/wiki? IncrementalAlgorithms (дата обращения 01.11.2015). [38] Microsoft Silverlight [Электронный ресурс]. Режим доступа: URL: https://www.microsoft.com/silverlight/ (дата обращения 07.05.2016). [39] Introduction WPF apps to Model/View/ViewModel [Электронный ресурс]. pattern Режим for building доступа: URL: https://blogs.msdn.microsoft.com/johngossman/2005/10/08/introductionto-modelviewviewmodel-pattern-for-building-wpf-apps/ (дата обращения 07.05.2016). [40] MSDN: Windows Presentation Foundation [Электронный ресурс]. Режим доступа: URL: https://msdn.microsoft.com/ru-ru/library/ms754130.aspx (дата обращения 07.05.2016). [41] QuickGraph, Graph Data Structures And Algorithms for .NET [Электронный ресурс]. Режим доступа: URL: https://quickgraph.codeplex.com/ (дата обращения 07.05.2016). [42] Wikipedia: Model-View-ViewModel [Электронный ресурс]. Режим доступа: URL: https://ru.wikipedia.org/wiki/Model-View-ViewModel (дата обращения 07.05.2016). [43] Wikipedia: [Электронный Windows ресурс]. Presentation Режим доступа: Foundation URL: https://ru.wikipedia.org/wiki/Windows_Presentation_Foundation (дата обращения 07.05.2016). [44] Wikipedia: XAML [Электронный ресурс]. Режим доступа: URL: https://ru.wikipedia.org/wiki/XAML (дата обращения 07.05.2016).

АБС: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ 50 [45] .NET Framework [Электронный ресурс]. Режим доступа: URL: https://www.microsoft.com/net/default.aspx 07.05.2016). (дата обращения

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв