Основные научные интересы лежат в области синтеза и сложности управляющих систем. Получен ряд результатов по нижним оценкам сложности реализации булевых функций различными типами схем. Рассматривается реализация монотонных булевых функций формулами в полном базисе $(\vee,\&,\neg)$ и в монотонном базисе $(\vee,\&). Показано, что использование отрицаний может существенно упростить реализацию монотонных булевых функций формулами. Предложен метод получения нижних оценок сложности реализации булевых функций ветвящимися программами. Получены нелинейные нижние оценки для сложности реализации характеристических функций кодов Рида–Маллера и БЧХ кодов в классе недетерминированных и детерминированных ветвящихся программ. При этом при получении нижних оценок сложности для схем без ограничений существенно использовались нижние оценки сложности для схем с ограничениями на структуру. Получен ряд результатов по сложности реализации булевых функций схемами с ограничениями. Введено понятие монотонного расширения функции. Показано, что операция геометрического проектирования и операция монотонного расширения булевых функций могут приводить к существенному усложнению реализаций булевых функций в ряде классов схем. Установлена связь между этими операциями.
Научная биография:
Окончила механико-математический факультет Новосибирского государственного университета в 1970 г. (кафедра теоретической кибернетики). Кандидатская диссертация — 1982 г. Имею свыше 30 публикаций.
Основные публикации:
Окольнишникова Е. А. О роли отрицаний при реализации монотонных булевых функций формулами в базисе (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).
Е. А. Окольнишникова, “О распределённых схемах”, Дискретн. анализ и исслед. опер., 18:6 (2011), 71–81
2009
2.
Е. А. Окольнишникова, “Нижняя оценка сложности вычисления характеристических функций БЧХ-кодов ветвящимися программами”, Дискретн. анализ и исслед. опер., 16:5 (2009), 69–77; E. A. Okolnishnikova, “Lower bound for the computation complexity of BCH-codes for branching programs”, J. Appl. Industr. Math., 4:2 (2010), 231–235
Е. А. Окольнишникова, “О числе гамильтоновых циклов в гамильтоновых плотных графах”, Матем. тр., 8:2 (2005), 199–206; E. A. Okolnishnikova, “On the Number of Hamiltonian Cycles in Hamiltonian Dense Graphs”, Siberian Adv. Math., 16:4 (2006), 79–85
2003
4.
Е. А. Окольнишникова, “О сложности недетерминированных ветвящихся программ, реализующих характеристические функции кодов Рида–Маллера.”, Дискретн. анализ и исслед. опер., сер. 1, 10:3 (2003), 67–81
Е. А. Окольнишникова, “Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами”, Дискретн. анализ и исслед. опер., сер. 1, 8:4 (2001), 76–102
Е. А. Окольнишникова, “О двух операциях над булевыми функциями”, Дискретн. анализ и исслед. опер., сер. 1, 7:1 (2000), 79–93
1999
7.
Е. А. Окольнишникова, “О сравнении сложностей недетерминированных ветвящихся $k$-программ”, Дискретн. анализ и исслед. опер., сер. 1, 6:1 (1999), 65–85
1995
8.
Е. А. Окольнишникова, “О сравнении сложностей бинарных $k$-программ”, Дискретн. анализ и исслед. опер., 2:4 (1995), 54–73
Обратная связь: