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

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

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


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




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

Успехи математических наук, 2012, том 67, выпуск 1(403), страницы 97–168
DOI: https://doi.org/10.4213/rm9459 (Mi rm9459) 		 
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)

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

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

Институт математики им. С. Л. Соболева СО РАН
PDF полного текста (1086 kB) PDF английской версии (978 kB) Список цитирования (7)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/rm9459
Аннотация: Булевы функции являются одним из основных объектов дискретной математики, в особенности тех ее разделов, которые входят в математическую логику и математическую кибернетику. Язык булевых функций удобен для описания функционирования многих дискретных систем, например, контактных схем, булевых схем, ветвящихся программ и некоторых других. Важным параметром таких дискретных систем является их сложность. Эта характеристика активно изучается, начиная с работ К. Шеннона. Опубликовано много научных статей, в которых содержится большое число результатов. Цель обзора – изложение основных результатов по сложности вычислений (реализации) булевых функций контактными схемами, булевыми схемами и булевыми схемами без ветвлений, которые получены за последние шестьдесят лет.
Библиография: 165 названий.
Ключевые слова: базис, булевы схемы, булева функция, глубина и задержка булевой схемы, дизъюнктивная нормальная форма, инвариантные классы булевых функций, клеточная схема, контактная схема без нулевых цепей, логическая формула, нижние оценки сложности схем, параллельно-последовательная контактная схема, симметрическая булева функция, сложность схемы, частичная булева функция.
Поступила в редакцию: 04.10.2011
Англоязычная версия:
Russian Mathematical Surveys, 2012, Volume 67, Issue 1, Pages 93–165
DOI: https://doi.org/10.1070/RM2012v067n01ABEH004777
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.95+519.7
MSC: Primary 06E30, 68Q30, 94C10; Secondary 06E99
Образец цитирования: А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 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/rm9459}
\crossref{https://doi.org/10.4213/rm9459}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2961468}
\zmath{https://zbmath.org/?q=an:1257.94041}
\adsnasa{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&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}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm9459
  • https://doi.org/10.4213/rm9459
  • https://www.mathnet.ru/rus/rm/v67/i1/p97
    Замечания
    Эта публикация цитируется в следующих 7 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:1787
    PDF русской версии:2347
    PDF английской версии:80
    Список литературы:148
    Первая страница:76
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024