Нахождение замыкания признаков как одна из наиболее часто возникающих задач во время построения базисов импликаций. Сравнительный анализ показателей времени работы трансверсального алгоритма при использовании различных методов минимизации базиса.
При низкой оригинальности работы "Разработка и сравнение алгоритмов построения канонического базиса импликаций", Вы можете повысить уникальность этой работы до 80-100%
Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики» Выполнил студент группы 123, 4 курса, Белов Павел ДмитриевичАнализ формальных понятий позволяет выявлять закономерности в данных и находить взаимоотношения между признаками объектов. Более формально, контекст K представляет собой тройку (G, M, I), где G - множество объектов, M - множество признаков, I GXM - бинарное отношение между объектами и признаками. Все признаки в данной модели бинарные, то есть ?обладает ли объект данным свойством?. Другими словами, данная запись означает следующее: ?Для всех объектов из множества выполняется, что если в объекте присутствуют все признаки из Однако, количество импликаций в данных может быть очень большим, поэтому появляется задача - найти множество, эквивалентное всем импликациям, выполняющимся в данном контексте.В ходе данной работы были реализованы и протестированы два алгоритма - Closure и LINCLOSURE. Основная идея Closure заключается в том, что мы проходим по базису и пытаемся расширить текущее множество с помощью каждой импликации. Теоретическая сложность данного алгоритма квадратичная, так как в худшем случае мы на каждом шаге будем использовать только одну импликацию. A Алгоритм LINCLOSURE обладает линейной от количества импликаций в базисе сложностью. 6 импликации мы храним количество ссылок, и расширяя постепенно на-ше множество, применяем новые импликации, который стали доступны после предыдущих.В самом деле, иногда можно быстро построить базис импликаций, но с большим числом импликаций, чем базис Дюкенна-Гига. В таком случае можно применить алгоритм минимизации базиса и получить базис Дюкенна-Гига. В алгоритме мы перебираем все импликации из L и каждую импликацию сначала стараемся расширить с помощью других импликаций из базиса, после чего удаляем из L импликации, не добавляющие новой информации. Данный алгоритм обладает сложностью O(JLJ3), так как он проходит один раз по всем импликациям из L и на каждом шаге вызывает Closure(), который обладает сложностью O(JLJ2). Алгоритм рассматривает импликации одну за одной и пробует построить контр-пример к каждой из них.Для ускорения работы алгоритмов было принято решение использовалать библиотеку Boost ([10]) и, в частности, контейнер Boost::dynamic bitset. По результатам профилирования удалось оптимизировать работу с памятью в алгоритмах и ускорить их засчет этого. Было проведено тестирование всех алгоритмов по скорости работы на реальных данных. 6.3: Время работы инкрементального алгоритма на различных наборах данных. трансверсалям в данном алгоритме, растет очень быстро с увеличением размера формального контекста. 6.6: Время работы трансверсального алгоритма на основе минимального покрытия при множественной минимизации. рования программы, реализующей данный алгоритм, выяснилось, что около 90% времени работы уходило на минимизацию базиса.В ходе выпускной квалификационной работы были исследованы различные алгоритмы для построения базиса импликаций Дюкенна-Гига и связанных с этим подзадач. На языке C мною были написаны эффективные реализации алгоритмов построения замыкания признаков, минимизации базиса и непосредственно построения базиса. Кроме того, были разработаны и проделаны многочисленные оптимизации как на техническом (работа с памятью, эффективное использование особенностей С ), так и на алгоритмическом уровнях. Babin, M.A., Kuznetsov, S.O.: Recognizing pseudo-intents is CONP-complete. Beeri, C., Bernstein, P.: Computational problems related to the design of normal form relational schemas.
