Методы и алгоритмы разработки вычислительных систем, устойчивых к отказам элементов, без проверки на изоморфизм тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Камил Ихаб Абдулджаббар Камил

• Камил Ихаб Абдулджаббар Камил
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Камил Ихаб Абдулджаббар Камил

Введение

1 Расширения графов и отказоустойчивость

1.1 Основные определения теории графов

1.2 Подграфы, суперграфы, расширения и отказоустойчивость

1.3 Базовый алгоритм построения расширений

2 Базовый алгоритм построения вершинных расширений

2.1 Анализ задач базового алгоритма и способов их решений

2.1.1 Перебор кандидатов

2.1.2 Проверка на расширение

2.1.3 Исключение изоморфизма

2.1.4 Параллельные вычисления

2.2 Метод канонических представителей и его варианты

2.3 Канонический М-код и его свойства

2.3.1 М-код и его свойства

2.3.2 Дерево канонических представителей

3 Алгоритмы построения вершинных расширений на основе исключения изоморфизма

3.1 Метод Рида-Фараджева

3.2 Перебор сочетаний с ограничениями

3.3 Алгоритмы ПСО

3.4 Алгоритм построения вершинных ^-расширений путём обхода дерева канонических представителей

3.5 Программа и инструментарий

3.6 Анализ влияния формы графа на эффективность построения МВ-£-Р

3.7 Исследование алгоритма ОДКП

3.8 Исследования влияния модификаций алгоритмов

4 Вычислительные эксперименты и экспериментальные результаты

4.1 Вычислительные эксперименты

4.2 Анализ результатов вычислительных экспериментов

4.3 Статистические характеристики алгоритмов

4.4 Статистические данные

4.5 Расширения некоторых графов

Заключение

Список условных обозначений и сокращений

Список литературы

Приложение А (справочное) Свидетельство о государственной регистрации

программы для ЭВМ

Приложение Б (справочное) Акт о внедрении результатов диссертационной

работы

Приложение В (справочное) Акт об использовании результатов работы в учебном процессе

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы разработки вычислительных систем, устойчивых к отказам элементов, без проверки на изоморфизм»

Введение

Актуальность темы исследования и степень её разработанности. В

современном мире огромное количество сложных вычислительных устройств, которые оказывают большое влияние на всех нас. В некоторых случаях наше здоровье, да и жизнь могут зависеть от работы этих устройств, поэтому необходимо, чтобы такие устройства были очень надёжными. Автор работы является сотрудником Министерства науки и технологий Ирака, где занимается вопросами, связанными с разработкой и использованием SCADA-систем, особенно в области электроэнергетики. Тема отказоустойчивости в этой области является чрезвычайно важной [2, 24, 28, 20, 53, 87-90].

Одна из первых работ по отказоустойчивости принадлежит Джону фон Нейману [109], и в ней он рассматривает вопрос построения надёжной системы из ненадёжных элементов. С одной стороны, необходимо повышать надёжность элементов, с другой стороны, хотелось бы иметь возможность сохранить работу системы даже при выходе из строя надёжного элемента. ENIAC, одно из первых электронных вычислительных устройств, использовал около 18000 вакуумных ламп со средним временем наработки на отказ около 2500 часов. Среднее время наработки на отказ ENIAC составляло 7 минут [5, 67]. В современных компьютерах используются существенно более надёжные компоненты, однако и сами устройства стали более сложными. Так, например, в июне 2020 года самым мощным общественно известным вычислительным устройством мира стал японский суперкомпьютер Фугаку, в котором установлено 158 976 процессоров Fujitsu A64FX [103, 107] с общим числом 7 299 072 ядер.

В 1971 году A. Avizienis [57] рассмотрел два подхода для повышения надёжности вычислительных систем: предотвращение ошибок и отказоустойчивость. Первое направление связано с уменьшением вероятности возникновения ошибки, оно состоит в разработке высоконадёжных компонентов системы и не будет рассматриваться в данной работе. Во втором направлении

используется введение в систему избыточных структур для придания ей свойств отказоустойчивости [9, 5]. В более поздних работах отказоустойчивость стала рассматриваться как одно из средств достижения гарантоспособности системы [58].

Понятие отказоустойчивости было введено A. Avizienis [56] как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Он рассмотрел два уровня отказоустойчивости:

1) при полной отказоустойчивости система продолжает работать в присутствии ошибок без существенной потери функциональных свойств;

2) при амортизации отказов система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

В 1976 году John Hayes в работе [83] предложил модель для исследования полной отказоустойчивости технических систем, основанную на графах. Системе Е сопоставляется помеченный граф О(Е), вершины которого соответствуют элементам системы Е, рёбра - связям между элементами, а метки указывают тип элементов [9, 5]. Если связи не являются симметричными, то можно рассматривать ориентированные графы. В данной работе будут рассматриваться неориентированные графы. Под отказом элемента системы Е понимается удаление соответствующей ему вершины из графа системы G(E) и всех связанных с ней ребер. Система Е* называется k-отказоустойчивой реализацией системы Е, если отказ любых k элементов системы Е* приводит к графу, в который можно вложить граф системы Е с учетом меток вершин. Построение k-отказоустойчивой реализации системы Е можно представить себе как введение в неё определенного числа избыточных элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры [5, 83]. Есть и другая интерпретация отказа, при которой сам элемент перестаёт функционировать, но через него могут передаваться сигналы [29, 32]. На языке

теории графов ^-отказоустойчивую реализацию системы Е мы будем называть вершинным ^-расширением (В-k-P) её графа G(E).

Если в системе Е встречается p различных типов элементов, то любая её k-отказоустойчивая реализация должна содержать не менее k дополнительных элементов каждого типа. Такого числа дополнительных элементов достаточно для построения k-отказоустойчивой реализации системы Е. Добавим k элементов каждого типа и соединим их все между собой и с элементами системы Е. Тогда любой отказавший элемент можно будет заменить одним из добавленных элементов соответствующего типа. Построенную k-отказоустойчивую реализацию будем называть тривиальной [9, 5]. Её можно использовать для оценки числа дополнительных вершин и рёбер произвольной k-отказоустойчивой реализации. Таким образом, известно минимально возможное число дополнительных элементов для построения k-отказоустойчивой реализации системы, далее добавим условие минимальности числа дополнительных связей.

Если элементы технической системы однотипны, то метки элементов опускаются, и в качестве графа системы рассматривается граф без меток. В этом случае оптимальная k-отказоустойчивая реализация будет содержать в точности k дополнительных элементов. На практике такая ситуация встречается достаточно часто. Например, массивно-параллельные вычислительные системы состоят из однородных узлов. Каждый узел состоит из одного или нескольких процессоров, локальной памяти и некоторых других компонент [75]. В данной работе мы будем рассматривать графы без меток, то есть когда все элементы системы являются одинаковыми.

k-отказоустойчивая реализация Е* системы Е называется оптимальной, если система Е* отличается от системы Е на k элементов, и среди всех k-отказоустойчивых реализаций с тем же числом элементов система Е* имеет наименьшее число связей [9, 5]. На языке теории графов оптимальную k-отказоустойчивую реализацию системы Е мы будем называть минимальным вершинным k-расширением (МВ-k-P) её графа С(Е). Позднее F. Harary и J. Hayes

[81] расширили модель на случай отказов связей. В данной работе мы будем рассматривать только отказы элементов, то есть только вершинные расширения графов. Заметим, что вместо минимальности числа связей могут рассматриваться и другие ограничения, которые по той или иной причине предпочтительны, например, наличие определённой группы автоморфизмов [74].

В своей первой работе J. Hayes [83] предложил схемы построения минимальных вершинных 1-расширений для цепей и циклов, а также для частного случая помеченного дерева. Большое количество теоретических исследований посвящено аналитическому построению минимальных вершинных ^-расширений для различных классов графов: А.В. Киреева [33], М.Ф. Каравай [29-32], М.А. Кабанов [19], М.Б. Абросимов [5], С.Г. Курносова [34, 35], А.А. Долгов [18, 17], О.В. Моденова [3, 13], А.В. Гавриков [15], J. Hayes [81-83], A.A. Farrag [78] и ряд других работ, из которых упомянем [66, 68, 69, 84, 106].

Позднее было доказано, что задача является вычислительно сложной. А именно, задача проверки того, что граф является вершинным ^-расширением заданного графа, является NP-полной [11]. В работах [7, 5] предлагается переборный алгоритм построения минимальных вершинных ^-расширений графов. С помощью программы, реализованной на его основе, были получены некоторые экспериментальные данные о минимальных вершинных k-расширениях: проанализированы минимальные вершинные 1 -расширения всех неориентированных графов с числом вершин до 7 [7]. Описанный алгоритм является переборным и сложен для распараллеливания, так как в нём необходимо поддерживать список всех найденных расширений. Программная реализация на основе этого алгоритма была использована для построения всех минимальных вершинных 1 -расширений графов с числом вершин до 7, а также для некоторых отдельных графов с большим числом вершин. Для генерации сложных комбинаторных структур, в том числе графов, хорошо показывают себя методы без непосредственной проверки на изоморфизм. В основе таких методов лежит каноническая форма структуры или её канонический код. Основная идея состоит в

оставлении структуры только в том случае, если её форма является канонической. Отметим некоторые известные работы и генераторы: И.А. Фараджев [49, 77], С.А. Сухов [47], R.C. Read [105, 70, 71], B. McKay [97, 98, 100], G. Brinkmann [6165], M. Meringer [102], R. Grund [79]. Алгоритмы генерации без проверки на изоморфизм хорошо подходят для распараллеливания, так как нет необходимости в хранении построенных ранее объектов, чтобы определить, нужно ли оставлять очередного кандидата.

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

Это определяет актуальность настоящей работы, а также соответствующие цели и задачи.

Цели и задачи. Цели данной работы состоят в разработке и исследовании математической модели отказоустойчивой системы для решения оптимизационной задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов, а также построения всех неизоморфных минимальных вершинных ^-расширений заданного графа системы без проверки на изоморфизм с последующей реализацией в виде программного продукта. Задачи работы:

1. Разработать математическую модель отказоустойчивой системы с целью решения оптимизационной задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов.

2. Разработать алгоритмы определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов

элементов, и построения всех минимальных вершинных ^-расширений, а также оценить адекватность математической модели комбинаторной оптимизации.

3. Провести исследование разработанных алгоритмов, оценить возможность их распараллеливания и эффективность.

4. Разработать программный комплекс, реализующий алгоритмы определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов, и построения всех минимальных вершинных ^-расширений.

5. Провести вычислительные эксперименты по построению минимальных вершинных ^-расширений графов с заданным числом вершин, а также некоторых интересных с практической точки зрения графов: торов и решёток.

Объектом исследования является граф, представляющий модель вычислительной системы.

Предметом исследования являются модели и алгоритмы, позволяющие строить для заданного графа все неизоморфные минимальные вершинные Ъ-расширения.

Научная новизна работы заключается в следующем:

1. Предложен подход к исследованию математической модели отказоустойчивой системы для решения оптимизационной задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов с использованием метода канонических представителей, а также построения всех её отказоустойчивых реализаций, что позволяет разрабатывать методы решения этой задачи с существенным сокращением области поиска решений.

2. Разработаны новые численные методы решения задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов, которые позволяют существенно сокращать область поиска решений.

3. Разработаны новые алгоритмы построения всех неизоморфных минимальных вершинных ^-расширений заданной графом системы, отличающиеся от известных ранее алгоритмов тем, что в них используется техника исключения изоморфных копий, что обеспечивает возможность разработки более эффективных параллельных алгоритмов и лучшее использование памяти.

4. Реализованы и исследованы параллельные версии всех разработанных алгоритмов для построения минимальных вершинных ^-расширений заданного графа, которые показали увеличение скорости работы в 10 и более раз по сравнению с известными аналогами.

5. Создан программный комплекс, реализующий разработанные алгоритмы, позволяющий определять минимальное число дополнительных связей системы, устойчивой к заданному числу отказов элементов, и строить все неизоморфные минимальные вершинные ^-расширения для заданного графа системы.

6. Построены минимальные вершинные 1-расширения всех неориентированных графов с числом вершин до 9 и минимальные вершинные 2-расширения всех неориентированных графов с числом вершин до 8.

7. Построены минимальные вершинные 1-расширения для решёток и торов с числом вершин до 12.

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

Положения и результаты, выносимые на защиту:

1. Предложен подход к исследованию математической модели отказоустойчивой системы для решения оптимизационной задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов с использованием метода канонических представителей.

2. Разработаны численные методы решения задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов.

3. Разработаны вычислительные алгоритмы построения всех неизоморфных минимальных вершинных ^расширений заданной графом системы без непосредственной проверки на изоморфизм.

4. Реализован комплекс программ, реализующий разработанные алгоритмы, позволяющий определять минимальное число дополнительных связей системы, устойчивой к заданному числу отказов элементов, и строить все неизоморфные минимальные вершинные ^расширения для заданного графа системы.

5. Построены минимальные вершинные 1-расширения всех неориентированных графов с числом вершин до 9, решётки и торы с числом вершин до 12, минимальные вершинные 2-расширения всех неориентированных графов с числом вершин до 8.

Теоретическая значимость работы. Предложен новый подход к исследованию математической модели отказоустойчивой системы для решения оптимизационной задачи определения минимального числа дополнительных связей системы, устойчивой к заданному числу отказов элементов, с использованием метода канонических представителей. Разработаны 4 алгоритма для построения всех неизоморфных минимальных вершинных ^расширений заданного графа. Алгоритмы хорошо подходят для их параллельной реализации. Исследование вносит вклад в теорию построения отказоустойчивых систем и теорию графов, в частности в теорию минимальных расширений графов и в разработку алгоритмов генерации графов без проверки на изоморфизм. Теоретическая значимость работы подтверждается прилагаемым актом внедрения её результатов в учебный процесс Саратовского национального исследовательского государственного университета имени Н.Г. Чернышевского.

Практическая значимость работы обусловлена созданием программного комплекса для построения минимальных вершинных расширений заданного графа

на основе разработанных в работе алгоритмов. Реализованный программный комплекс может быть использован на этапе анализа и разработки вычислительных архитектур или иных систем, для которых необходимо предусмотреть отказоустойчивость. С помощью разработанного программного комплекса были построены все минимальные вершинные 1 -расширения для графов с числом вершин до 9 и выложены в открытый доступ в онлайн-энциклопедии «Мир графов». Практическая значимость работы подтверждается прилагаемым актом использования её результатов и свидетельством о государственной регистрации программного комплекса.

Личный вклад автора. Все основные результаты, выносимые на защиту, получены автором лично. Автор участвовал в определении цели работы и постановке задач. Автор самостоятельно разрабатывал все программные части совместного программного комплекса, которые относятся к задаче построения вершинных расширений. Все основные алгоритмы из работы были реализованы как отдельное приложение, а также как часть программного комплекса FTConstructor, который позволяет для заданного графа строить как вершинные, так и рёберные расширения. Вклад автора в FTConstructor - все программные модули для построения вершинных расширений. В остальных совместных работах автору также принадлежит ведущая роль в тех вопросах, которые связаны с темой данной диссертации, а именно, с вершинными расширениями графов. Результаты данной работы докладывались автором на различных конференциях и семинарах.

Степень достоверности результатов исследования. Полученные результаты согласуются с результатами вычислительных экспериментов, проведённых ранее, а также с известными аналитическими результатами.

Апробация результатов исследования. Основные результаты работы докладывались и обсуждались на следующих семинарах и конференциях:

• научный семинар кафедры теоретических основ компьютерной безопасности и криптографии Саратовского национального исследовательского

государственного университета имени Н.Г. Чернышевского (Саратов, 2017, 2018, 2019, 2020);

• международная научная конференция «International Conference on Computing, Communication, Control and Automation» (ICCUBEA-2017) (Пуна, Республика Индия, 2017);

• VIII Международная научная конференция «Компьютерные науки и информационные технологии» памяти А.М. Богомолова (Саратов, 2018);

• всероссийская конференция «XVIII Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» -SIBECRYPT'19» (Томск, 2019);

• XV, XVI, XVII, XVIII Белорусско-российская научно-техническая конференция «Технические средства защиты информации» (Минск, Республика Беларусь, 2017, 2018, 2019, 2020);

• XXVII Международная конференция студентов, аспирантов и молодых учёных «Ломоносов» (Москва, 2020).

Соответствие содержания диссертации паспорту специальности.

Результаты работы соответствуют пунктам 1, 3, 4 и 5 паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ по областям исследования:

п. 1. Разработка новых математических методов моделирования объектов и явлений;

п. 3. Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий;

п. 4. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента;

п. 5. Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.

Публикации. По теме диссертации опубликовано 17 работ, в том числе 6 статей в журналах, включенных в Перечень рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук (из них 2 статьи в российских научных журналах, входящих в Web of Science), 1 статья в сборнике материалов конференции, представленном в издании, входящем в Scopus; получено 1 свидетельство о государственной регистрации программы для ЭВМ.

Структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка сокращений и условных обозначений, списка использованной литературы из 109 наименований, трёх приложений. Работа содержит 113 страниц, включая 27 рисунков и 24 таблицы.

Благодарность. Автор выражает глубокую признательность своему научному руководителю доктору физико-математических наук, доценту Михаилу Борисовичу Абросимову за предложенную тему исследования, помощь в постановке задач, а также за всестороннюю помощь и поддержку при подготовке диссертационной работы.

1 Расширения графов и отказоустойчивость

1.1 Основные определения теории графов

Дадим основные необходимые определения по теории графов в соответствии с работами [5, 14].

Неориентированным графом (везде далее просто графом) называется пара О = (V, а), где а - симметричное и антирефлексивное отношение на множестве вершин V. Графы в указанном смысле иногда называются простыми (нет петель и кратных ребер). Если (и,V) £а, то говорят, что вершины и и V смежны и эти вершины соединены ребром (и, V). При этом (и, V) и (V, и) - это одно и то же ребро, которое обозначают {и, V}. Говорят, что ребро {и, V} инцидентно каждой из вершин и и V. Далее для графа О = (V, а) число вершин будем иногда обозначать через п(О) или п, а число рёбер - через т(О) или т. В работе будут рассматриваться преимущественно неориентированные графы, хотя все рассмотренные методы и алгоритмы могут быть перенесены и на ориентированные графы.

Граф, любые две вершины которого смежны, называется полным и обозначается Куу. По определению, К|у| = С(У, V х V - А), где через А обозначено

тождественное отношение на множестве V. Граф без ребер, то есть с пустым отношением смежности а, называется вполне несвязным и обозначается Оуу|.

Степенью вершины V в неориентированном графе О будем называть количество вершин в О, смежных с V, и обозначать через Вектор,

составленный из степеней вершин графа О в порядке убывания, называется его вектором степеней.

Два графа О1 = (VI, а1) и О2 = (Р2, а2) называются изоморфными, если можно установить взаимно однозначное соответствие /: У1 ^ У2, сохраняющее отношение смежности: (и, V) е а1 ^ (Ди),/(V)) е аг, для любых и, V е V],.

Граф, вершинам которого приписаны метки, называется помеченным. Непомеченным или абстрактным графом называется класс изоморфных графов.

Изоморфное отображение графа на себя называется автоморфизмом. Тождественное отображение А: V ^ V является автоморфизмом для любого графа. Автоморфизмы графа образуют группу.

Инвариантом графа G называется набор его характеристик, одинаковых для всех изоморфных ему графов. Инвариантами графа являются, например, число вершин графа, количество дуг или рёбер. Полным инвариантом называется такой инвариант, который определяет граф однозначно с точностью до изоморфизма. Одним из известных числовых инвариантов является максимальный (минимальный) матричный код графа [5, 101].

Матрица отношения смежности графа называется его матрицей смежности. Пусть G = (V, а) - п-вершинный граф. Тогда его матрица смежности А = М(а) имеет размерность п х п, а на позиции (/,у) стоит 1, если есть дуга (у, у), и 0 в противном случае:

/" л

Хл

А =

Х1,1 Х1,2

Х2,1 Х2,2

V Хп,1 Хп,2

х1,п

Х

2 п

Х

п,п у

Если выписать элементы матрицы смежности по строкам, то получится двоичное число, код графа:

-^1,1, •^1,2, • • • х1^ x2,1, x2,2, • • • x2,и, • • xи,1, xи,2, • • • хп,п .

Само по себе это число не является инвариантом, так как матрицы смежности у изоморфных графов могут различаться, однако если среди всех изоморфных графов выбрать матрицу смежности с максимальным (максимальный код) или минимальным (минимальный код) значением кода, то получится инвариант, причем полный. Очевидно, что для и-вершинного графа размер кода будет п2 бит. Для некоторых классов графов, например, для неориентированных графов, достаточно хранить только часть матрицы смежности, расположенную

над главной диагональю. В этом случае размер кода будет составлять n(n - 1)/2 бит. В данной работе будет предложен еще один полный инвариант на основе матричного кода.

Однородным или регулярным n-вершинным графом Rn,p порядка p называют граф, в котором все степени вершин равны p. Однородный граф порядка 3 называется кубическим.

Цепью Pn называется граф G = (V, а), где V = (v1s v2, ..., vn}, и а = {(vb vj): \i -j\ = 1}, а циклом Cn - граф G = (V, а), где V = {vi, V2, ..., Vn}, и а= {(vb vj): \i -j\ = 1} U {(v1, vn), (vn, v1)}. Обычно считают, что циклы определены для числа вершин 3 и более, но иногда в приложениях считают, что цикл C2 изоморфен цепи P2. В частности, такое допущение используют при обозначении торов.

Дадим определения основных алгебраических операций над графами.

Соединением двух графов Gx = (V, а{) и G2 = (V2, а2), не имеющих общих вершин, называется граф

G + G2 := (V и V, а иа2 и V х V2 и V2 х V).

Объединением двух графов Gx = (V, ах) и G2 = (V2, а2) называется граф G1 и G2 := (V и V2, ах и а2). Далее будем считать, что множества V1 и V2 не пересекаются.

Декартовым или прямым произведением двух графов G1 = (V1, а1) и G2 = (V2, а2) называется граф G1 х G2 с множеством вершин V1 х V2, в котором вершины (u1, u2) и (v1, v2) смежны тогда и только тогда, когда либо u1 = v1, а u2 смежна с v2, либо u2 = v2, а u1 смежна с v1.

n-мерной решёткой (mesh, lattice graph или grid graph) называется граф, являющийся декартовым произведением n цепей Ртг X ... X Ртп. n-мерным тором называется граф, являющийся декартовым произведением n циклов Стг X ... X Стп. Решётки и торы представляют большой интерес с точки зрения архитектуры компьютера [21, 93].

Будем считать, что каждая вершина достижима из самой себя. Тогда отношение достижимости является отношением эквивалентности на множестве вершин графа. Классы этого отношения называются компонентами связности графа. Граф с универсальным отношением достижимости называется связным. Связный граф без циклов называется деревом. В связном графе расстояние й(и, у) между вершинами и и у есть длина кратчайшей цепи, соединяющей эти вершины [9, 5, 14].

1.2 Подграфы, суперграфы, расширения и отказоустойчивость

Подграфом графа О = (V, а) называется пара О' = (V, а), где V' с V и а= (VXV)Па. Подграф графа О называется максимальным, если он получается из О удалением одной вершины и всех связанных с ней рёбер. Будем обозначать через О - у максимальный подграф, получающийся из графа О удалением вершины у. Через О - ¥, где F с V, будем обозначать подграф, получающийся из графа О удалением всех вершин из F [9, 5].

Список литературы диссертационного исследования кандидат наук Камил Ихаб Абдулджаббар Камил, 2021 год

Список литературы

1. Абросимов М.Б. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей / М.Б. Абросимов, И.А.К. Камил, А.А. Лобов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. - 2019. - Т. 19, вып. 4. - С. 479-485.

2. Абросимов М.Б. Разработка системы предотвращения вторжений с использованием параллельного программирования и системы отказоустойчивости / М. Б. Абросимов, И. А. К. Камил // Безопасность информационных технологий. 2018. - Т. 25, № 1. - С. 65-73.

3. Абросимов М.Б. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1 -расширения / М. Б. Абросимов, О. В. Моденова // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. - 2013. - Т. 13., вып. 2, ч. 2. - С. 3-9.

4. Абросимов М.Б. О количестве оптимальных 1-гамильтоновых графов с числом вершин до 26 и 28 / М. Б. Абросимов, С. А. Сухов // Прикладная дискретная математика. Приложение. - 2016. - № 9. - С. 103-105.

5. Абросимов М.Б. Графовые модели отказоустойчивости. - Саратов: Издательство Саратовского университета. - 2012. - 192 с.

6. Абросимов М.Б. Минимальные ^-расширения предполных графов // Известия ВУЗов: Математика. - 2003. - № 6(493). - С. 3-11.

7. Абросимов М.Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных графов. - Саратов гос. ун-т. - Саратов, 2000. - 26с.; Деп. в ВИНИТИ 06.09.2000, № 2352-В00.

8. Абросимов М.Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур: докл. Третьей Всерос. конф. с междунар. участием. - Томск, 2000. - С. 59-64.

9. Абросимов М.Б. Минимальные расширения графов: дис. ... канд. физ.-мат. наук. Саратовский гос. университет. - Саратов, 2001. - 169 с.

10. Абросимов М.Б. Минимальные расширения циклов с числом вершин не более одиннадцати. - Саратов: СГУ, 2001. - 17с.; Деп. в ВИНИТИ 14.08.2001, №1869-В2001.

11. Абросимов М.Б. О сложности некоторых задач, связанных с расширениями графов // Математические заметки. - 2010. - № 88:5. - С. 643-650.

12. Абросимов М.Б. Параллельный алгоритм построения минимальных вершинных и реберных 1-расширений графов / М. Б. Абросимов, Д. А. Зайцев // XII Белорусская математическая конференция: материалы междунар. науч. конф. Минск, Республика Беларусь, 05-10 сентября 2016 г. - Минск, 2016. - Ч. 4. - С. 46-47.

13. Абросимов М.Б. Характеризация орграфов с тремя дополнительными дугами в минимальном вершинном 1 -расширении / М. Б. Абросимов, О. В. Моденова // Прикладная дискретная математика. - 2013. -№ 3. - С. 68-75.

14. Богомолов А.М. Алгебраические основы теории дискретных систем / А. М. Богомолов, В. Н. Салий. - М.: Наука, 1997. - 368 с.

15. Гавриков А.В. Т-неприводимые расширения объединений некоторых типов орграфов // Прикладная дискретная математика. - № 4 (22). - 2013. - С. 4756.

16. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.

17. Долгов А.А. Семейство точных 2-расширений турниров // Прикладная дискретная математика. - 2010. - № 9. - С. 96-99.

18. Долгов А.А. О семействах точных вершинных ^-расширений графов при k > 1 // Материалы Международного молодежного научного форума «Ломоносов-2010». - М.: МАКС Пресс, 2010. - С. 30-32.

19. Кабанов M.A. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. - Саратов: Изд-во Сарат. унта, 1997. - Вып. 1. - С. 50-5B.

20. Камил ИА.К. Безопасность системы и система отказоустойчивости / И. A. К. Камил, M. Б. Aбросимов // Технические средства защиты информации: Тезисы докладов XVII Белорусско-российской научно-технической конференции, Mинск, Республика Беларусь, 11 июня 2019 г. - Mинск: БГУИР, 2019. - С. 6B.

21. Камил ИА.К. Вычислительный эксперимент по построению отказоустойчивых реализаций графов с числом вершин до 9 // International Journal of Open Information Technologies. - 2020. - Vol. B, № 9. - P. 43-47.

22. Камил ИА.К. К вопросу о параллельных алгоритмах построения минимальных вершинных и рёберных 1-расширений графов / И. A. К. Камил, Х. Х. К. Судани, M. Б. Aбросимов // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. - Саратов : Издат. центр «Наука», 201B. - С. 173-176.

23. Камил ИА.К. О разработке параллельного алгоритма построения оптимальных вершинно-отказоустойчивых расширений графов без проверки на изоморфизм // Mатериалы Mеждународного молодежного научного форума «ЛОMОНОСОВ-2020» [Электронный ресурс] / Отв.ред. ИА. Aлешковский, A.ß. Aндриянов, E.A. Aнтипов. - Электрон. текстовые дан. (1500 M6.) - M.: MARE Пресс, 2020. - Режим доступа: https://lomonosov-msu.ru/archive/Lomonosov_2020/index.htm, свободный - Mатериалы Mеждународного молодежного научного форума «ЛОMОНОСОВ-2020».

24. Камил ИА.К. Обеспечение отказоустойчивости высокопроизводительного узла параллельных вычислений с интерфейсом передачи сообщений (MPI) // Современная наука: актуальные проблемы теории и практики: Серия «Естественные и Технические науки». - 201B. - № 4. - С. 57-59.

25. Камил И.А.К. Построение всех неизоморфных суперграфов без проверки на изоморфизм / И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. - 2020. - № 48. - С.82-92.

26. Камил И.А.К. Построение минимальных вершинных расширений графа методом Рида-Фараджева / И. А. К. Камил, М. Б. Абросимов, А. А. Лобов // International Journal of Open Information Technologies. - 2020. - Vol. 8, № 4. - Р. 5458.

27. Камил И.А.К. Построение минимальных расширений графа методом канонических представителей / И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. Приложение. - 2019. - № 12. - С. 179-182.

28. Камил И.А.К. Разработка системы предотвращения вторжений с использованием параллельного программирования и технологий отказоустойчивости / И. А. К. Камил, М. Б. Абросимов // Технические средства защиты информации: Тезисы докладов XVI Белорусско-российской научно-технической конференции. Минск, Республика Беларусь, 05 июня 2018 г. - Минск. Минск: БГУИР, 2018. - С. 44.

29. Каравай М.Ф. Инвариантно-групповой подход к исследованию А-отказо-устойчивых структур // Автоматика и телемеханика. - 2000. - № 1. - С. 144-156.

30. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры // Автоматика и телемеханика. - 2004. - № 12. - С. 159-177.

31. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и k-отказоустойчивость // Автоматика и телемеханика. - 2005. - № 2. -С. 175-189.

32. Каравай М.Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. - 1996. - № 6. - С. 159— 173.

33. Киреева А.В. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. - Саратов : Изд-во Сарат. ун-та, 1995. -Вып. 11. - С. 32-38.

34. Курносова С.Г. Т-неприводимые расширения объединений полных графов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. -2005. - Т. 5, вып. 1. - С. 107-115.

35. Курносова С.Г. Т-неприводимые расширения полных бинарных деревьев // Вестн. Томск. гос. ун-та. Приложение. - 2005. - № 14. - С. 158-160.

36. Лобов А.А. О вершинном 1-расширении гиперкуба / А. А. Лобов, М. Б. Абросимов // Компьютерные науки и информационные технологии. Материалы Международной научной конференции. - 2018. - С. 249-251.

37. Официальный сайт Поволжского Регионального Центра Новых Информационных Технологий [Электронный ресурс]. - URL: http://prcnit.sgu.ru (дата обращения: 01.08.2020).

38. Розенфельд М.З. О построении и свойствах некоторых классов сильно регулярных графов // УМН. - 1973. - Т. 28, вып. 3 (171). - С. 197-198.

39. Салий В.Н. Минимальные примитивные расширения ориентированных графов // ПДМ. - 2008. - № 1(1). - С.116-119.

40. Салий В.Н. Оптимальные реконструкции графов // Современные проблемы дифференциальной геометрии и общей алгебры. - Саратов : Изд-во Сарат. ун-та, 2008. - С. 59-65.

41. Салий В.Н. Функциональная отказоустойчивость и оптимальные реконструкции графовых систем по заданным параметрам // Вестник ТГУ. Приложение. - 2007. - № 23. - С. 253-256.

42. Свидетельство о государственной регистрации программы для ЭВМ № 2010616497. Исследование минимальных вершинных и реберных 1-расширений цепей с вершинами двух типов / Абросимов М. Б. ^и), Бондаренко П. П. ^и); правообладатель: Государственное образовательной учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» ^и). Заявка № 2010614677; заявл. - 2 августа 2010 г.; дата государственной регистрации в Реестре программ для ЭВМ - 30 сентября 2010 г.

43. Свидетельство о государственной регистрации программы для ЭВМ № 2011610846. Построитель минимальных вершинных и реберных 1-расширений графов / Абросимов М. Б. ^и); правообладатель: Государственное образовательной учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» ^и). Заявка № 2010615111; заявл. - 20 августа 2010 г.; дата государственной регистрации в Реестре программ для ЭВМ - 19 января 2011 г.

44. Свидетельство о государственной регистрации программы для ЭВМ № 2012661394. Поиск минимальных реберных и вершинных 1-расширений графов / Абросимов М. Б. ^и), Комаров Д. Д. ^и); правообладатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского» ^и). Заявка № 2012619258; заявл. - 29 октября 2012 г.; дата государственной регистрации в Реестре программ для ЭВМ - 13 декабря 2012 г.

45. Свидетельство о государственной регистрации программы для ЭВМ № 2012612065. Исследование минимальных вершинных 1-расширений орграфов / Абросимов М. Б. ^и), Моденова О. В. ^и); правообладатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный университет

имени Н.Г. Чернышевского» (RU). Заявка № 2011660130; заявл. - 27 декабря 2011 г.; дата государственной регистрации в Реестре программ для ЭВМ -22 февраля 2012 г.

46. Свидетельство о государственной регистрации программы для ЭВМ № 2020614773. Построение оптимальных отказоустойчивых реализаций графов FTConstructor / Абросимов М. Б. (RU), Камил И. А. К. (RU), Судани Х. Х. К. (RU), Лобов А. А. Заявка № 2020612581; заявл. - 27 марта 2020 г.; дата государственной регистрации в Реестре программ для ЭВМ - 24 апреля 2020 г.

47. Свидетельство о государственной регистрации программы для ЭВМ № 2016610073. DSR Generator / Сухов С.А. (RU). Заявка № 2015660808; заявл. 10 ноября 2015 г.; дата государственной регистрации в Реестре программ для ЭВМ -11 января 2016 г.

48. Теслер Г.С. Решение проблемы гарантоспособности компьютерных систем в аспекте базисов компьютерной науки // Математичш машини i системи. -

2008. - № 4. - С. 171-188.

49. Фараджев И.А. (ред) Алгоритмические исследования в комбинаторике. -М.: Наука, 1978. - 190 с.

50. Харченко В.С. Гарантоспособность и гарантоспособные системы : элементы методологии // Радюелектронш i комп'ютерш системи. - 2006. - № 5 -С. 7-19.

51. Харченко В.С. Парадигмы и принципы гарантоспособных вычислений : состояние и перспективы развития // Радюелектронш i комп'ютерш системи. -

2009. - № 2(36). - С. 91-100.

52. Энциклопедия «Мир графов» [Электронный ресурс]. -URL:http://graphworld.ru (дата обращения: 01.08.2020).

53. Abrosimov M. Increasing SCADA System Availability by Fault Tolerance Techniques / M. Abrosimov, I. A. Kamil, H. Mahajan // 2017 International Conference

on Computing, Communication, Control and Automation (ICCUBEA), PUNE, India, 2017. - P. 461-466.

54. Ajima Y. Tofu: A 6D Mesh/Torus Interconnect for Exascale Computers / Y Ajima, S. Sumimoto, T. Shimizu // IEEE Computer. - 2009. - Vol. 42, № 11. - P. 3640.

55. Ajima Y The Tofu interconnect D / Y Ajima, T. Kawashima, T. Okamoto, N. Shida, K. Hirai, T. Shimizu // 2018 IEEE International Conference on Cluster Computing (CLUSTER). - 2018. - P. 646-654.

56. Avizienis A. Design of fault-tolerant computers // AFIPS'67 Conf. Proc. -New York: ACM, 1967. - P. 733-743.

57. Avizienis A. Fault-Tolerant Computing: An Overview // IEEE Computer. -1971. - Vol. 4, № 1. - P. 5-8.

58. Avizienis A. Basic Concepts and Taxonomy of Dependable and Secure Computing / A. Avizienis, J.-C. Laprie, B. Randell, C. Landwehr // IEEE Transactions on Dependable and Secure Computing. - 2004. - № 1. - P. 11-33.

59. Babai L. The Graph Isomorphism Problem (Dagstuhl Seminar 15511) / L. Babai, A. Dawar, P. Schweitzer, J. Toran // Dagstuhl Reports, 2016. - Vol. 5, is. 12. -P. 1-17. - DOI: 10.4230/DagRep.5.12.1.

60. Bonnici V. A subgraph isomorphism algorithm and its application to biochemical data / V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha // BMC Bioinformatics. - 2014. - Vol. 14, S13. - P. 1-13. - DOI: 10.1186/1471-2105-14-S7-S13.

61. Brinkmann G. Fast generation of cubic graphs // J. Graph Theory. - 1996. -Vol. 23, № 2. - P. 139-149.

62. Brinkmann G. Isomorphism rejection in structure generation programs // Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. - 2000. - Vol. 51. - P. 25-38.

63. Brinkmann G. Generation of cubic graphs and snarks with large girth / G. Brinkmann, J. Goedgebeur // Journal of Graph Theory. - 2017. - Vol. 86, № 2. - P. 255-272.

64. Brinkmann G. Generation and properties of Snarks / G. Brinkmann, J. Goedgebeur, J. Hagglund, K. Markstrom // Journal of Combinatorial Theory, Series B. - 2013. - Vol. 103, № 4. - P. 468-488.

65. Brinkmann G. Generation of cubic graphs / G. Brinkmann, J. Goedgebeur,

B. D. McKay // Discrete Math. Theor. Comput. Sci. - 2011. - Vol. 13, № 2. - P. 69-80.

66. Bruck J. Fault-tolerant meshes with small degree / J. Bruck, R. Cypher,

C. Ho // SIAM J. Comput. - 1997. - Vol. 26, № 6. - P. 1764-1784.

67. Carter W.C. A Survey of Fault Tolerant Computer Architecture and its Evaluation / W. C. Carter, W. G. Bouricius // IEEE Computer. - 1971. - Vol. 4, № 1. - P. 9-16.

68. Chou R.S. 1-edge fault-tolerant designs for meshes / R. S. Chou, L. H. Hsu // Parallel Process. Lett. - 1994. - Vol. 4, № 4. - P. 385-389.

69. Choudum S. A. Optimal fault-tolerant networks with a server / S. A. Choudum, S. Sivagurunathan // Networks. - 2000. - Vol. 35, № 2. - P. 157-160.

70. Colburn C.J. Orderly algorithms for generating restricted classes of graphs / C. J. Colburn, R. C. Read // Journal of Graph Theory. - 1979. - Vol. 3. - P. 187-195.

71. Colburn C.J. Orderly algorithms for graph generation / C. J. Colburn, R. C. Read // Intern. J. Computer Math. - 1979, Sec.A.7. - P. 167-172.

72. Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd ACM Symposium on Theory of Computing. - 1971. - P. 151-158.

73. Darga P.T. Exploiting structure in symmetry detection for CNF / P. T. Darga, M. H. Liffiton, K. A. Sakallah, I. L. Markov // Proceedings of the 41st Design Automation Conference, 2004. - P. 530-534.

74. Dutt S. Designing fault-tolerant systems using graph automorphisms / S. Dutt, J. P. Hayes // Journal of Parallel and Distributed Computing. - 1991. - Vol. 12. - P. 249-268.

75. Encyclopedia of Parallel Computing / ed. D. A. Padua. - New York : Springer, 2011. - 2195 p.

76. Fan W. Reconfigurable Fault-tolerance mapping of ternary N-cubes onto chips / W. Fan, J. He, Z. Han, P. Li, R. Wang // Concurrency and Computation: Practice and Experience. - 2020. - Vol. 32, is. 11. - Article number e5659. -https://doi.org/10.1002/cpe.5659.

77. Faradzev I.A. Constructive enumeration of combinatorial objects // Colloques internationaux C.N.R.S. - № 260 : Problemes Combinatoires et Theorie des Graphes. -Orsay, 1976 - P. 131-135.

78. Farrag A.A. Designing optimal fault-tolerant star networks / A. A. Farrag, R. J. Dawson // Networks. - 1989. - Vol. 19. - P. 707-716.

79. Grund R. Konstruktion schlichter Graphen mit gegebener Gradpartition // Bayreuther Mathematische Schriften. - 1993. - Vol. 44. - P. 73-104.

80. Gurevich Y. From invariants to canonization // Bulletin of the European Association of Theoretical Computer Science. - 1997. - Vol. 63. - P. 115-119.

81. Harary F. Edge fault tolerance in graphs / F. Harary, J. P. Hayes // Networks. -1993. - Vol. 23. - P. 135-142.

82. Harary F. Node fault tolerance in graphs / F. Harary, J. P. Hayes // Networks. -1996. - Vol. 27. - P. 19-23.

83. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers, 1976. - Vol. C-25, iss. 9. - P. 875-884.

84. Hsu L.H. Graph Theory and Interconnection Networks / L. H. Hsu, C. K. Lin. - New York: CRC Press, 2009. - 720 p.

85. Junttila T. Engineering an efficient canonical labeling tool for large and sparse graphs / T. Junttila, P. Kaski // Proceedings of the 9th Workshop on Algorithm

Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, 2007. - P. 135-149.

86. Junttila T. Conflict Propagation and Component Recursion for Canonical Labeling / T. Junttila, P. Kaski // Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms, 2011. - P. 151-162.

87. Kamil I.A.K. Information security for SCADA systems / I. A. K. Kamil, N. Nasonova // Технические средства защиты информации: Тезисы докладов XIII Белорусско-российской научно-технической конференции. Минск, Республика Беларусь, 04-05 июня 2015 г. - Минск: БГУИР, 2015. - С. 22.

88. Kamil I.A.K. SCADA systems security / I. A. K. Kamil, N. Nasonova // Технические средства защиты информации: Тезисы докладов XVI Белорусско-российской научно-технической конференции. Минск, Республика Беларусь, 2526 мая 2016 г. - Минск: БГУИР, 2016. - С. 20.

89. Kamil I.A.K. Design and development complex safety SCADA systems / I. A. K. Kamil, M. B. Abrosimov // Технические средства защиты информации: Тезисы докладов XV Белорусско-российской научно-технической конференции. Минск, Республика Беларусь, 06 июня 2017 г. - Минск: БГУИР, 2017. - С. 77.

90. Kamil I.A.K. Development reliability node fault-tolerant computing systems by parallel technics / I. A. K. Kamil, M. B. Abrosimov // Технические средства защиты информации: тезисы докладов XVIII Белорусско-российской научно-технической конференции. Минск, Республика Беларусь, 09 июня 2020 г. - Минск: БГУИР, 2020. - С. 9-10.

91. Kozielski S. Development of High Performance Computing Systems / S. Kozielski, D. Mrozek // Gaj P., Guminski W., Kwiecien A. (eds) Computer Networks. CN 2020. Communications in Computer and Information Science. - Springer, Cham, 2020. - Vol. 1231. - P. 52-63.

92. Land A.H. An automatic method of solving discrete programming problems / A. H. Land, A. G. Doig // Econometrica. - 1960. - Vol. 28, № 3. - P. 497-520.

93. Leighton F.T. Introduction to Parallel Algorithms and Architecture: Arrays,Trees,Hypercubes. - San Mateo, Morgan Kaufmann, 1992. - 852 p.

94. Lopez-Presa J.L. Fast algorithm for graph isomorphism testing / J. L. Lopez-Presa, Anta A. Fernandez // Proceedings of the 8th International Symposium on Experimental Algorithms, 2009. - P. 221-232.

95. Lopez-Presa J.L., Fernandez Anta A., Nunez Chiroque L. Conauto-2.0: Fast isomorphism testing and automorphism group computation, 2011. [Электронный ресурс]. - URL: http://arxiv.org/abs/1108.1060 (дата обращения: 01.08.2020).

96. Lowler E.L. Branch-and-bound methods. A survey / E. L. Lowler, D. E. Wood // J. Op. Res. Soc. America, 1966. - Vol. 14. - P. 217-282.

97. McKay B.D. Practical graph isomorphism // Congr. Numer. - 1980. - Vol. 30. - P. 45-87.

98. McKay B.D. Isomorph-free exhaustive generation // Journal of Algorithms. -1998. - Vol. 26. - P. 306-324.

99. McKay B.D. Computing automorphisms and canonical labellings of graphs // Combinatorial Mathematics, Lecture Notes in Mathematics. - Berlin: Springer-Verlag, 2006. - Vol. 686. - P. 223-232.

100. McKay B.D. Practical Graph Isomorphism, II / B. D. McKay, A. Piperno // Journal of Symbolic Computation. - 2014. - Vol. 60. - P. 94-112.

101. McKay B.D. Description of graph6, sparse6 and digraph6 encodings [Электронный ресурс]. - URL: http://cs.anu.edu.au/people/bdm/data/formats.txt (дата обращения: 01.08.2020).

102. Meringer M. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. - 1999. - Vol. 30. - P. 137-146.

103. Outline of the Development of the Supercomputer Fugaku [Электронный ресурс] // RIKEN Center for Computational Science. - URL: https://www.r-ccs.riken.jp/en/fugaku/project/outline (дата обращения: 01.08.2020).

104. Read R.C. The graph isomorphism disease / R. C. Read, D. G. Corneil // J. Graph Theory1. - 1977. - P. 339-363.

105. Read R.C. Every one a winner // Annals of Discrete Mathematics 2. - 1978.

- P. 107-120.

106. Sung T.Y Optimal k-fault-tolerance network for token rings / T. Y. Sung, T. Y Ho, C. P. Chang, L. H. Hsu // J. Inform. Science and Engineering. - 2000. - № 16.

- P. 381-390.

107. T0P500 [Электронный ресурс] // T0P500. - URL: https://www.top500.org/ (дата обращения: 01.08.2020).

108. Ullmann J. An algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery. - 1976. - Vol. 23. - P. 31-42.

109. von Neumann J. Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components // Automata Studies, ser. Annals of Mathematics Studies. Princeton, NJ : Princeton University Press, 1956. - Vol. 34. -P. 43-98.

111

Приложение А

(справочное)

Свидетельство о государственной регистрации программы для ЭВМ

112

Приложение Б

(справочное)

Акт о внедрении результатов диссертационной работы

Камила Ихаба Абдулджаббара Камила «Методы и алгоритмы разработки вычислительных систем, устойчивых к отказам элементов, без проверки на

АО «ИНИУС» является разработчиком программ для ЭВМ БСАОА «КИРАС» (свидетельство об официальной регистрации программы для ЭВМ № 2003611900 от 15.06.2004 г.), ЭСАйА «КИРАС с функциями коммерческого учета ресурсов и диспетчерского управления» (свидетельство об официальной регистрации программы для ЭВМ № 2007611352 от 28.04.2007 г.), «Универсальный компьютерный тренажерный комплекс» (свидетельство об официальной регистрации программы для ЭВМ №2004612135 от 17.09.2004 г.) и «Универсальный тренажерный комплекс» (свидетельства о государственной регистрации программы для ЭВМ № 2008610432 от 23.01.2008 г., № 2011611763 от 25.02.2011 г., № 2012619028 от 05.10.2012, 2015611408 от 08.10.2014, № 2017614987 от 02.05.2017).

Настоящим актом подтверждаем, что отдельные результаты, содержащиеся в диссертационном исследовании Камила Ихаба Абдулждабара Камила. а также программный продукт РТСопэ^исЮг использовались для анализа надёжности вычислительных систем для функционирования тренажёрных комплексов, разрабатываемых АО «ИНИУС».

ИНфо рмационные

Юридический адрес: Россия. 41(1005, Саратов,

ул. Б. Садовая, 239, оф. 415

Почтовый адрес: 4)0005, г. Саратов, а/я 3668

Адрес для курьерской доставки:

41ШГ6, Саратов, ул. Верхняя, д.17

т/ф ([phone], 74-00-15

Сайт АО «ИНИУС»: http:/www.inius.ru

E-mail! iw»trn'inius.ru

АКТ О ВНЕДРЕНИИ

результатов диссертационного исследования

изоморфизм»

Ген. директор АО "ИНИУС

Гильман Е.А,

7 *

Ы *

113

Приложение В

(справочное)

Акт об использовании результатов работы в учебном процессе

внедрения в учебный процесс кафедры теоретических основ компьютерной безопасности и крнпннрафии результатов диссертации Камила Ихаба Абдулджаббара Камила «Методы и алгоритмы разработки вычислительных систем, устойчивых к отказам элементов, без проверки на изоморфизм»

Настоящим акгом удостоверяется, что результаты диссертационного исследования К.И.А. Камила на тему «Методы и алгоритмы разработки вычислительных систем, устойчивых к отказам цементов, без проверки на изоморфизм» внедрены в учебный процесс кафедры при разработке методических рекомендаций и курсов лекций, а именно: I ) теоретические результаты главы 2 и практические результаты главы 4 используются в курсе «Теория графов» для студентов, обучающихся по специальности 10.05.01 «Компьютерная безопасность» (специализация «Математические методы зашиты информации»);

2) теоретические результаты глав 2-3 используются в курсе «Теория построения отказоустойчивых систем» для студентов, обучающихся по направлению 09.04.01 «Информатика и вычислительная техника» (профиль подготовки «Сети ЭВМ и телекоммуникации»);

3 ) алгоритмы из глав 2-3 и разработанная на их основе программа используются в курсе «Методы оптимизации графовых систем» для студентов, обучающихся по специальности 10.05.01 «Компьютерная безопасность» (специализация «Математические методы защиты информации»).

Заведующий кафедрой ТОКБиК,

АКТ

д.ф.-м.н., доценг

М.Б. Абросимов