RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
 
Окольнишникова Елизавета Антоновна

В базах данных Math-Net.Ru
Публикаций: 8
Научных статей: 8

Статистика просмотров:
Эта страница:284
Страницы публикаций:2555
Полные тексты:982
Списки литературы:120
кандидат физико-математических наук (1982)
Специальность ВАК: 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,\&). Показано, что использование отрицаний может существенно упростить реализацию монотонных булевых функций формулами. Предложен метод получения нижних оценок сложности реализации булевых функций ветвящимися программами. Получены нелинейные нижние оценки для сложности реализации характеристических функций кодов Рида–Маллера и БЧХ кодов в классе недетерминированных и детерминированных ветвящихся программ. При этом при получении нижних оценок сложности для схем без ограничений существенно использовались нижние оценки сложности для схем с ограничениями на структуру. Получен ряд результатов по сложности реализации булевых функций схемами с ограничениями. Введено понятие монотонного расширения функции. Показано, что операция геометрического проектирования и операция монотонного расширения булевых функций могут приводить к существенному усложнению реализаций булевых функций в ряде классов схем. Установлена связь между этими операциями.

Научная биография:

Окончила механико-математический факультет Новосибирского государственного университета в 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).

http://www.mathnet.ru/rus/person17580
Список публикаций на Google Scholar
Список публикаций на ZentralBlatt
https://mathscinet.ams.org/mathscinet/MRAuthorID/194064

Публикации в базе данных Math-Net.Ru
2011
1. Е. А. Окольнишникова, “О распределённых схемах”, Дискретн. анализ и исслед. опер., 18:6 (2011),  71–81  mathnet  mathscinet  zmath
2009
2. Е. А. Окольнишникова, “Нижняя оценка сложности вычисления характеристических функций БЧХ-кодов ветвящимися программами”, Дискретн. анализ и исслед. опер., 16:5 (2009),  69–77  mathnet  mathscinet  zmath; E. A. Okolnishnikova, “Lower bound for the computation complexity of BCH-codes for branching programs”, J. Appl. Industr. Math., 4:2 (2010), 231–235  scopus
2005
3. Е. А. Окольнишникова, “О числе гамильтоновых циклов в гамильтоновых плотных графах”, Матем. тр., 8:2 (2005),  199–206  mathnet  mathscinet; 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  mathnet  mathscinet
2001
5. Е. А. Окольнишникова, “Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами”, Дискретн. анализ и исслед. опер., сер. 1, 8:4 (2001),  76–102  mathnet  mathscinet  zmath
2000
6. Е. А. Окольнишникова, “О двух операциях над булевыми функциями”, Дискретн. анализ и исслед. опер., сер. 1, 7:1 (2000),  79–93  mathnet  mathscinet  zmath
1999
7. Е. А. Окольнишникова, “О сравнении сложностей недетерминированных ветвящихся $k$-программ”, Дискретн. анализ и исслед. опер., сер. 1, 6:1 (1999),  65–85  mathnet  mathscinet  zmath
1995
8. Е. А. Окольнишникова, “О сравнении сложностей бинарных $k$-программ”, Дискретн. анализ и исслед. опер., 2:4 (1995),  54–73  mathnet  mathscinet  zmath

Организации
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020