Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств

Научная новизна определяется следующими результатами: 1. Доказана трудноразрешимость задач, связанных с вычислением классического минимального базиса импликаций. 2. Предложена новая модель приближенного базиса импликаций формального контекста, алгоритм его вычисления и эффективная программнаяреализация. 3. Доказана трудноразрешимость вычисления минимальных гипотез встандартной постановке 4. Предложена и экспериментально проверена модель распределенногообучения гипотезам – импликативным зависимостям для задачи машинного обучения. 5. Предложен линейный по времени алгоритм поиска всех гипотез по распределенной обучающей выборке и его программная реализация. 6. Предложена и экспериментально проверена модель оценивания гипотези формальных понятий – вероятностный индекс устойчивости. 7. Теоретически и экспериментально исследована сложность вычисления вероятностного индекса устойчивости, предложен эффективный алгоритм и его программная реализация. 8. Решены давно сформулированные и остававшиеся открытыми задачи создания эффективных алгоритмов и оценки вычислительной сложности распознавания псевдосодержаний и существенных содержаний. 9. Показана полиномиальная эквивалентность задачи перечисления мини-мальных гипотез и задачи дуализации монотонной булевой функции нарешетке. 10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделении прикладной математики и информатики НИУ ВШЭ комплекс программ. Объект исследования: модели импликативных зависимостей в данных и их эффективная алгоритмическая реализация. Цель: разработка моделей импликативных зависимостей в данных, для которых существуют более быстрые алгоритмы, а также решение связанных с ними вычислительных задач и разработка комплекса программ, реализующего предложенные алгоритмы.