Алгоритм фрагментации и дефрагментации формальных контекстов
Аннотация
Дата поступления статьи: 13.10.2023Рассматривается комбинаторная задача – задача нахождения множества всех формальных понятий формального понятий. Вычислительная сложность задачи состоит в том, что число формальных понятий экспоненциально зависит от размера исходного формального контекста. В статье для решения данной задачи приводится алгоритм фрагментации и дефрагментации формального контекста, основанный на методе декомпозиции формального контекста на фрагменты. Суть метода заключается в том, что исходный формальный контекст разделяется на различные фрагменты. Фрагменты имеют разные размеры и непустое пересечение. Каждый фрагмент в дальнейшем рассматривается как формальный контекст и вновь может подвергаться к декомпозицию. В итоге формируется конечное множество фрагментов. Затем в каждом фрагменте находятся формальные понятия и объединяются, образуя искомое множество всех формальных понятий формального контекста. Метод является «неискажающим»: при разделении контекста на фрагменты не образуются новые формальные понятия и не теряются искомые понятия. Приводятся результаты вычислительных экспериментов, показывающие эффективность разработанного алгоритма.
Ключевые слова: анализ формальных понятий, алгоритм фрагментации, формальный контекст, объектно-признаковая таблица, комбинаторная задача, задача нахождения множества всех формальных понятий
1.2.2 - Математическое моделирование, численные методы и комплексы программ
.