Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №10, Москва, 2001
Авторы: Окольнишникова Е.А.
О сложности ветвящихся программ
Аннотация:
Данная работа является обзором результатов некоторых направлений изучения сложности реализации булевых функций ветвящимися программами. Даны определения контактно-вентильной схемы, ориентированной и ациклической контактно-вентильной схем, как моделей управляющих систем наиболее близких к ветвящимся программам, определены недетерминированная и детерминированная ветвящиеся программы; определены меры сложности для этих классов схем. Приведен ряд соотношений для этих мер сложностей, и описано поведение функции Шеннона для этих классов схем. Приведены известные нижние оценки сложности для недетерминированных и детерминированных ветвящихся программ соответственно. Рассмотрены ветвящиеся программы с ограничениями на ширину, также рассмотрены ветвящиеся k-программы и приведены методы получения нижних оценок для этого класса схем. Описан метод использования нижних оценок сложности ветвящихся k-программ для получения нижних оценок сложности ветвящихся программ без ограничений. При подготовке обзора использовались доклады, прочитанные автором на школе-семинаре по синтезу и сложности управляющих систем, проходившей в 1998 г. в ННГУ и НИИ ПМК, г. Нижний Новгород, и доклады, прочитанные на школах молодых ученых, проходящих в рамках программы ¦Интеграция» в МГУ (г. Москва, 1997 г.) и в ННГУ (г. Нижний Новгород, 1998 г.)
Ключевые слова:
ветвящиеся программы, сложность реализации булевых функций, вентильные схемы, нижние оценки сложности
Язык публикации: русский, страниц: 14 (с. 69-82)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Окольнишникова Елизавета Антоновна,  Институт математики им. С.Л. Соболева СО РАН