|
Эта публикация цитируется в 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{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/umn9459https://doi.org/10.4213/rm9459 http://mi.mathnet.ru/rus/umn/v67/i1/p97
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Замечания
Эта публикация цитируется в следующих статьяx:
-
Ю. В. Максимов, “Реализация булевых функций с ограниченным числом нулей в классе дизъюнктивных нормальных форм”, Ж. вычисл. матем. и матем. физ., 53:9 (2013), 1569–1588
; 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 -
Chikalov I., Hussain Sh., Moshkov M., “Totally optimal decision trees for Boolean functions”, Discrete Appl. Math., 215 (2016), 1–13
-
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
|
Просмотров: |
Эта страница: | 1358 | Полный текст: | 451 | Литература: | 119 | Первая стр.: | 76 |
|