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

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

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



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Дискретн. анализ и исслед. опер., сер. 1, 2007, том 14, номер 1, страницы 110–139 (Mi da45)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

О сложности последовательной реализации частичных булевых функций схемами

Л. А. Шоломов

Институт системного анализа РАН

Аннотация: Пара $(f,g)$ частичных булевых функций характеризуется параметром $l_{\alpha,\beta}$ – числом наборов $\widetilde x$, на которых $(f(\widetilde x),g(\widetilde x))=(\alpha,\beta)$, где $\alpha$ и $\beta$ принимают значения 0, 1 и неопределённое. Рассматривается последовательная реализация системы $(f,g)$, когда сначала строится схема $S_f$ для $f$, которая затем достраивается до схемы $S_{f,g}$. Показано, что если область определения $D(f)$ включает $D(g)$, то можно последовательно реализовать $f$ и $g$ так, чтобы схемы $S_f$ и $S_{f,g}$ были одновременно асимптотически минимальными (т.е. удовлетворяли асимптотически наилучшим оценкам сложности для соответствующих классов), и что эти функции, вообще говоря, нельзя последовательно реализовать в порядке $g$$f$, чтобы асимптотически минимальными были $S_g$ и $S_{f,g}$. Получена достижимая нижняя оценка сложности схем $S_{f,g}$ при последовательной реализации. Существенную роль играют информационные свойства частично определённых данных, изучение которых начато в предшествующих работах автора и продолжено здесь.
Библ. 12.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2008, 2:2, 270–289

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


Образец цитирования: Л. А. Шоломов, “О сложности последовательной реализации частичных булевых функций схемами”, Дискретн. анализ и исслед. опер., сер. 1, 14:1 (2007), 110–139; J. Appl. Industr. Math., 2:2 (2008), 270–289

Цитирование в формате AMSBIB
\RBibitem{Sho07}
\by Л.~А.~Шоломов
\paper О сложности последовательной реализации частичных булевых функций схемами
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2007
\vol 14
\issue 1
\pages 110--139
\mathnet{http://mi.mathnet.ru/da45}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2328238}
\zmath{https://zbmath.org/?q=an:1249.94085}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 2
\pages 270--289
\crossref{https://doi.org/10.1134/S1990478908020117}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44849098608}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da45
  • http://mi.mathnet.ru/rus/da/v14/s1/i1/p110

    ОТПРАВИТЬ: 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. Л. А. Шоломов, “Элементы теории недоопределенной информации”, ПДМ, 2009, приложение № 2, 18–42  mathnet
    2. А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165  crossref  isi  elib
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:257
    Полный текст:93
    Литература:40
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020