• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

Соискатель:Бабин Михаил Александрович
Руководитель:Кузнецов Сергей Олегович (др. работы под рук-вом)
Оппоненты:Виноградов Дмитрий Вячеславович; Аншаков Олег Михайлович
Специальность: 05.13.18 Математическое моделирование, численные методы и комплексы программ
Дисс. совет:Д 212.048.09 - Совет по техническим и физико-математическим наукам
Дата защиты:29.10.2012


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

Диссертация [*.pdf, 22.36 Mb]
Автореферат [*.pdf, 366.47 Kb]



Ключевые слова: анализ формальных понятий, импликативные зависимости