Специальность ВАК:
01.01.09 (дискретная математика и математическая кибернетика)
Ключевые слова: синтез; схема; сложность; булева функция; оценки; нижние оценки; ветвящаяся программа.
Коды УДК: 519.174.2, 519.175.3, 519.714, 519.714.4, 519.725, 519.95
Коды MSC: 68-XX, 94-XX, 05-XX
Основные темы научной работы:
Основные научные интересы лежат в области синтеза и сложности управляющих систем. Получен ряд результатов по нижним оценкам сложности реализации булевых функций различными типами схем. Рассматривается реализация монотонных булевых функций формулами в полном базисе $(\vee,\&,\neg)$ и в монотонном базисе $(\vee,\&). Показано, что использование отрицаний может существенно упростить реализацию монотонных булевых функций формулами. Предложен метод получения нижних оценок сложности реализации булевых функций ветвящимися программами. Получены нелинейные нижние оценки для сложности реализации характеристических функций кодов Рида–Маллера и БЧХ кодов в классе недетерминированных и детерминированных ветвящихся программ. При этом при получении нижних оценок сложности для схем без ограничений существенно использовались нижние оценки сложности для схем с ограничениями на структуру. Получен ряд результатов по сложности реализации булевых функций схемами с ограничениями. Введено понятие монотонного расширения функции. Показано, что операция геометрического проектирования и операция монотонного расширения булевых функций могут приводить к существенному усложнению реализаций булевых функций в ряде классов схем. Установлена связь между этими операциями.
Основные публикации:
Окольнишникова Е. А. О роли отрицаний при реализации монотонных булевых функций формулами в базисе (V,&,-) // Методы дискретного анализа в решении экстремальных задач: Сб. науч. тр. Вып. 33. - Новосибирск: Ин-т математики СО АН СССР, 1979. - С. 68–76.
Okol'nishnikova E. A. Lower bounds on branching programs // Siberian Adv. Math. - 1993. - V. 3, N 1. - P. 152–166.
Окольнишникова E. A. Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами // Дискрет. анализ и исслед. операций. Серия 1. - 2001. - Т. 8, № 4. - С. 76–102.
Okol'nishnikova E. A. On the hierarchy of nondeterministic branching $k$-programs // Fundamentals of computation theory. 11th International symposium, FCT 97 (Krakow, September 1–3, 1997). - Proc. Berlin: Springer, 1997. - P. 376–387 (Lecture Notes in Computer Science. - V. 1279).
Okol'nishnikova E. A. On some bounds on the size of branching programs (a survey) // 3rd Symposium on Stochastic Algorithms, Foundations and Applications, SAGA2005) (Moscou, October 20–22, 2005). - Proc. Berlin: Springer, 2005. (Lecture Notes in Computer Science. - V. 3777. - P. 107–115).
