|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Расшифровка булевых функций из замкнутых классов Постадипломная работа (Магистр)
- Научный руководитель: Гасанов Э.Э.
- Автор: Быстрыгова Анастасия Викторовна
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2018
- Аннотация: В работе Анастасии Быстрыговой рассматривается задача параметро-эффективной расшифровки булевых функций запросами на значение. В работе имеется обзор, в котором содержатся все ранее известные результаты по расшифровке замкнутых классов Поста. При этом оказалось, что для большого количества классов Поста задача расшифровки не решена. Анастасии удалось закрыть этот пробел и получить результаты для каждого из классов Поста. Часть результатов являются простыми следствиями известных результатов, но для расшифровки некоторых классов, в частности, для самодвойственных функций и функций, удовлетворяющих условию <α_i>, пришлось приложить изрядные усилия и смекалку. Все результаты разделились на 4 класса: точные значения сложности расшифровки, асимптотические оценки, оценки по порядку и оценки, асимптотические эквивалентные размерам минимальных покрывающих матриц (binary covering array). Последний класс оценок можно назвать условным, поскольку ни асимптотика, ни даже порядок для размеров минимальных покрывающих матриц не известны.
- Добавил в систему: Гасанов Эльяр Эльдарович