Автореферат (Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности), страница 3

Как и в предыдущей главе, заключительный параграф третьей главы посвящен тестированию программной реализации разработанного алгоритма. Представлены результаты сравнения работы алгоритма MaxIS c алгоритмом Робсона, а также методом полного перебора,несколько модифицированным для нахождения одного наибольшего независимого множества.Тестирование работы алгоритмов MaxIS и Робсона проводилось на одинаковом наборе графов с различными значениями плотности ребер. Экспериментальные результаты показали (Рисунки 3, 4), что при значении плотностибольше 70% оба алгоритма имеют практически одинаковый порядок роставремени работы, не превышающий O(2 0.276n ).Практическое применение разработанных алгоритмов продемонстрировано в четвертой главе на примере решения некоторых задач из биоинформатики.

В первом параграфе рассматривается задача поиска максимальнойобщей подструктуры органических соединений. Строится модель угольнойкислоты и глицина в виде молекулярных графов, для которых ищется подграф, изоморфный исследуемым графам. Проблема изоморфного вхождениясводится к задаче поиска наибольшей клики вспомогательного графа, для14Рис. 3: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри фиксированной плотности p = 70%.а)б)Рис. 4: Зависимость времени работы алгоритмов Робcона и MaxIS от размерности графовпри значении плотности p = 85% (a) и p = 95% (б).решения которой используется алгоритм M axIS.

Второй параграф посвященпроблеме определения потенциальных структур РНК, моделирование которых проводится с использованием неориентированного графа. В полученномграфе с помощью программной реализации алгоритма AllIS организуетсяпоиск всех клик, которые и соответствуют искомым структурам.В заключении диссертации представлены основные результаты, полученные в ходе исследования.15Список публикаций по теме диссертации1. Фирюлина О. С., Олемской И. В., Нечипорук А. А.

Алгоритм нахождения наибольшего независимого множества // Процессы управления и устойчивость: Труды 40-й межд.научн. конф. аспирантов и студентов/ Под ред. Н.В. Смирнова, Г. Ш. Тамасяна - СПб.:Издат. Дом С.-Петерб. гос. ун-та, 2009. C. 73–78.2. Фирюлина О. С. Метод построения максимальных независимых множеств // Процессы управления и устойчивость: Труды 41-й межд. научн. конф. аспирантов и студентов/ Под ред. Н.

В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2010.С. 68–72.3. Фирюлина О. С., Олемской И. В. Алгоритм решения задачи о наибольшем независимом множестве // Устойчивость и процессы управления: Всероссийская конф., посвящ.80-летию со дня рождения В. И. Зубова. Санкт-Петербург, 1-2 июля 2010 г.

– С.-Петербург:ВВМ, 2010. С. 212.4. Фирюлина О. С. Вычисление неплотности квадратных (0,1)-матриц // Процессыуправления и устойчивость: Труды 43-й межд. научн. конф. аспирантов и студентов /Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб.

гос. ун-та, 2012. С.55–60.5. Олемской И. В., Фирюлина О. С. Алгоритм вычисления наибольшего независимогомножества // Обозрение прикладной и промышленной математики. 2012. Т. 19, Вып. 3.С. 10.6. Фирюлина О. С. Нахождение всех максимальных независимых множеств неориентированного графа // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2013. Вып. 1. С. 63–69.7. Олемской И. В., Фирюлина О.

С. Решение задачи о поиске максимальной общейподструктуры в молекулярных графах // Процессы управления и устойчивость: Труды44-й международной научной конференции аспирантов и студентов / Под ред. Н. В.Смирнова, Т. Е. Смирновой. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2013. С. 355–360.8.

Олемской И. В., Фирюлина О. С. Алгоритм поиска наибольшего независимогомножества // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика,процессы управления. 2014. Вып. 1. С. 81–91.16.