Введение 3
Постановка задачи 4
Обзор литературы 5
Глава 1. Теоретические результаты 6
1.1. Алгебраическая теория 6
1.2. Переход от неотрицательных матриц к графам 7
1.3. Транзитивное замыкание 10
1.4. Построение нормальной формы 12
Глава 2. Практическое приложение 16
Заключение 18
Список литературы 19
Приложение
В современном развивающемся мире в абсолютно различных отраслях необходима работа с большими массивами данных. Например, в экономике, производственной или научной деятельности. Иногда эти данные необходимо упорядочить, и тогда разумно разделить их на кластеры, то есть группы, связанные между собой по какому-либо признаку.
Отдельный интерес представляет кластеризация матриц с неотрицательными элементами. Такие матрицы встречаются в различных разделах математики. Например, в теории вероятностей при исследовании цепей Маркова (стохастические матрицы) или в теории малых колебаний упругих систем (осцилляционные матрицы) [1]. Существует математический аппарат работы с неотрицательными матрицами, но не всегда известные алгоритмы возможно точно реализовать программно. Одним из таких алгоритмов является алгоритм проверки разложимости матрицы, то есть приведение матрицы к определенному виду с помощью перестановок строк и столбцов. Кроме того, известные алгоритмы, которые являются эффективными в случае матриц небольших размерностей, оказывается неприменимыми для больших матриц. Поэтому возникает необходимость разработки новых методов и алгоритмов, которые могут использоваться для решения практических задач, связанных с обработкой больших массивов данных, порождающих матрицы больших порядков.
Теория графов позволяет упростить и оптимизировать работу с неотрицательными матрицами, в том числе и вышеупомянутый алгоритм.
В работе была рассмотрена задача построения канонической матри¬цы для неотрицательной матрицы большого порядка. Уже существующий алгоритм решения задачи был улучшен: ранее при проверке матрицы на разложимость могло возникнуть переполнение в случае больших значе¬ний в оригинальной матрице либо, наоборот, в случае значений, близких к нулю. В новом алгоритме этой проблемы нет, поскольку проверяется инди¬каторная матрица, и используются только матрицы, состоящие из нулей и единиц.
Недостаток метода заключается в том, что его можно применять только к квадратным матрицам.
Помимо этого была решена задача выявления несвязанных вершин в графе. Применение результата алгоритма было рассмотрено во второй главе для решения оптимизационной задачи рекламы в социальных сетях.
