Данная работа является обзором результатов некоторых направлений изучения сложности реализации булевых функций ветвящимися программами. Даны определения контактно-вентильной схемы, ориентированной и ациклической контактно-вентильной схем, как моделей управляющих систем наиболее близких к ветвящимся программам, определены недетерминированная и детерминированная ветвящиеся программы; определены меры сложности для этих классов схем. Приведен ряд соотношений для этих мер сложностей, и описано поведение функции Шеннона для этих классов схем. Приведены известные нижние оценки сложности для недетерминированных и детерминированных ветвящихся программ соответственно. Рассмотрены ветвящиеся программы с ограничениями на ширину, также рассмотрены ветвящиеся k-программы и приведены методы получения нижних оценок для этого класса схем. Описан метод использования нижних оценок сложности ветвящихся k-программ для получения нижних оценок сложности ветвящихся программ без ограничений. При подготовке обзора использовались доклады, прочитанные автором на школе-семинаре по синтезу и сложности управляющих систем, проходившей в 1998 г. в ННГУ и НИИ ПМК, г. Нижний Новгород, и доклады, прочитанные на школах молодых ученых, проходящих в рамках программы ¦Интеграция» в МГУ (г. Москва, 1997 г.) и в ННГУ (г. Нижний Новгород, 1998 г.)

ветвящиеся программы, сложность реализации булевых функций, вентильные схемы, нижние оценки сложности

Математические вопросы и теория численных методов