519.1 К 705 Коршунов, А. Д. Сложность вычислений булевых функций [Текст] / А. Д. Коршунов // Успехи математических наук. - 2012. - Т. 67, вып. 1 (403). - С. 97-168 : ил. - Библиогр.: с. 159-168 (165 назв.) . - ISSN 0042-1316
Рубрики: Математика Комбинаторный анализ Математическая кибернетика Кл.слова (ненормированные): булевы функции -- сложность вычислений -- булевы схемы -- булевы схемы без ветвлений -- контактные схемы -- клеточные схемы -- частичные булевы функции -- логические формулы -- дискретная математика Аннотация: Булевы функции являются одним из основных объектов дискретной математики, в особенности тех ее разделов, которые входят в математическую логику и математическую кибернетику. Язык булевых функций удобен для описания функционирования многих дискретных систем, например, контактных схем, булевых схем, ветвящихся программ и некоторых других. Важным параметром таких дискретных систем является их сложность. Эта характеристика активно изучается, начиная с работ К. Шеннона. Опубликовано много научных статей, в которых содержится большое число результатов. Цель обзора - изложение основных результатов по сложности вычислений (реализации) булевых функций контактными схемами, булевыми схемами и булевыми схемами без ветвлений, которые получены за последние шестьдесят лет. |