Успехи математических наук
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


УМН:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

УМН, 2012, том 67, выпуск 1(403), страницы 97–168 (Mi umn9459)  
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Сложность вычислений булевых функций

А. Д. Коршунов

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Булевы функции являются одним из основных объектов дискретной математики, в особенности тех ее разделов, которые входят в математическую логику и математическую кибернетику. Язык булевых функций удобен для описания функционирования многих дискретных систем, например, контактных схем, булевых схем, ветвящихся программ и некоторых других. Важным параметром таких дискретных систем является их сложность. Эта характеристика активно изучается, начиная с работ К. Шеннона. Опубликовано много научных статей, в которых содержится большое число результатов. Цель обзора – изложение основных результатов по сложности вычислений (реализации) булевых функций контактными схемами, булевыми схемами и булевыми схемами без ветвлений, которые получены за последние шестьдесят лет.
Библиография: 165 названий.

Ключевые слова: базис, булевы схемы, булева функция, глубина и задержка булевой схемы, дизъюнктивная нормальная форма, инвариантные классы булевых функций, клеточная схема, контактная схема без нулевых цепей, логическая формула, нижние оценки сложности схем, параллельно-последовательная контактная схема, симметрическая булева функция, сложность схемы, частичная булева функция

DOI: https://doi.org/10.4213/rm9459

Полный текст: PDF файл (1086 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Russian Mathematical Surveys, 2012, 67:1, 93–165

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.95+519.7
MSC: Primary 06E30, 68Q30, 94C10; Secondary 06E99
Поступила в редакцию: 04.10.2011

Образец цитирования: А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168; Russian Math. Surveys, 67:1 (2012), 93–165

Цитирование в формате AMSBIB
\RBibitem{Kor12}
\by А.~Д.~Коршунов
\paper Сложность вычислений булевых функций
\jour УМН
\yr 2012
\vol 67
\issue 1(403)
\pages 97--168
\mathnet{http://mi.mathnet.ru/umn9459}
\crossref{https://doi.org/10.4213/rm9459}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2961468}
\zmath{https://zbmath.org/?q=an:1257.94041}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2012RuMaS..67...93K}
\elib{https://elibrary.ru/item.asp?id=20423434}
\transl
\jour Russian Math. Surveys
\yr 2012
\vol 67
\issue 1
\pages 93--165
\crossref{https://doi.org/10.1070/RM2012v067n01ABEH004777}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000303447100002}
\elib{https://elibrary.ru/item.asp?id=17985109}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84860872148}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn9459
  • https://doi.org/10.4213/rm9459
  • http://mi.mathnet.ru/rus/umn/v67/i1/p97

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Замечания

    Эта публикация цитируется в следующих статьяx:
    1. Ю. В. Максимов, “Реализация булевых функций с ограниченным числом нулей в классе дизъюнктивных нормальных форм”, Ж. вычисл. матем. и матем. физ., 53:9 (2013), 1569–1588  mathnet  crossref  elib; Yu. V. Maximov, “Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms”, Comput. Math. Math. Phys., 53:9 (2013), 1391–1409  crossref  isi  elib
    2. Chikalov I., Hussain Sh., Moshkov M., “Totally optimal decision trees for Boolean functions”, Discrete Appl. Math., 215 (2016), 1–13  crossref  mathscinet  zmath  isi  elib  scopus
    3. AbouEisha H., Amin T., Chikalov I., Hussain Sh., Moshkov M., “Multi-Stage Optimization of Decision Trees With Some Applications”: AbouEisha, H Amin, T Chikalov, I Hussain, S Moshkov, M, Extensions of Dynamic Programming For Combinatorial Optimization and Data Mining, Intelligent Systems Reference Library, 146, Springer-Verlag Berlin, 2019, 49–71  crossref  mathscinet  isi  scopus
    4. К. А. Попков, “О реализации булевых функций контактными схемами равномерной ширины 3”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162, № 3, Изд-во Казанского ун-та, Казань, 2020, 350–358  mathnet  crossref
    5. К. А. Попков, “О реализации булевых функций контактными схемами минимальной равномерной ширины”, Дискрет. матем., 33:4 (2021), 94–109  mathnet  crossref
    		• Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:1461
    Полный текст:1057
    Литература:120
    Первая стр.:76
     
    Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021