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

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

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


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




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

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

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

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

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

Аннотация: Булевы функции являются одним из основных объектов дискретной математики, в особенности тех ее разделов, которые входят в математическую логику и математическую кибернетику. Язык булевых функций удобен для описания функционирования многих дискретных систем, например, контактных схем, булевых схем, ветвящихся программ и некоторых других. Важным параметром таких дискретных систем является их сложность. Эта характеристика активно изучается, начиная с работ К. Шеннона. Опубликовано много научных статей, в которых содержится большое число результатов. Цель обзора – изложение основных результатов по сложности вычислений (реализации) булевых функций контактными схемами, булевыми схемами и булевыми схемами без ветвлений, которые получены за последние шестьдесят лет.
Библиография: 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{http://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{http://elibrary.ru/item.asp?id=17985109}
\scopus{http://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
    		• Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:1117
    Полный текст:318
    Литература:115
    Первая стр.:76
     
    Обратная связь:
    		  Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020