Аннотация:Дипломная работа Ильи Александровича Берелехиса на тему
<<О схемной сложности некоторых предполных замкнутых классов в базисах, содержащих элементы
с нулевыми весами>> относится к
одному из разделов дискретной математики и математической кибернетики~---
синтезу и сложности управляющих систем.
В дипломной работе исследуется задача
о сложности реализации булевых функций схемами из функциональных элементов в базисах, состоящих из элементов двух типов, одному типу элементов приписан нулевой вес, а другому типу~--- единичный; такие базисы иногда называют вырожденными.
Ранее отдельные частные случаи этой очень общей задачи рассматривали А.\,А.\;Марков, Э.\,И.\;Нечипорук, А.\,Б.\;Угольников и некоторые другие авторы. И.\,А.\;Берелехисом изучается два подкласса задач указанного вида: либо
в качестве множеств элементов первого типа
берутся различные предполные замкнутые классы булевых функций (или, что то же самое, порождающие множества в этих классах), а в качестве множества элементов второго типа берется одна или несколько функций, не лежащих в соответствующем предполном замкнутом классе; либо
в качестве множеств элементов первого типа
берутся различные <<предпредполные>> (т.\,е. предполные для данного предполного класса) замкнутые классы булевых функций, а в качестве множества элементов второго типа берется одна или несколько функций, не лежащих в соответствующем предпредполном замкнутом классе и, следовательно, дополняющихя этот предпредполный класс до предполного.
Для первого подкласса задач с использованием известных результатов найдено точное решение исходной задачи в самой общей постановке (кроме случая, когда нулевой вес имеют функции из класса $L$).
Для отдельных пар из предполного и препредполного классов булевых функций найдены новые точные значения соответствующих функций Шеннона, для других~--- доказаны нетривиальные оценки функций Шеннона.