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

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

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



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






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


Дискретн. анализ и исслед. опер., 2009, том 16, номер 5, страницы 78–87 (Mi da589)  

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

О сложности обобщённых контактных схем

К. Л. Рычков

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

Аннотация: Рассматриваются обобщения понятий контактной и параллельно-последовательной контактной схем на случай, когда переменные, приписанные контактам, могут принимать не два, как в булевом случае, а большее число значений. При этом проводимость контакта по-прежнему остаётся двузначной (контакт либо замкнут, либо разомкнут). Получены оценки сложности таких схем, реализующих функцию $f\colon\{0,1,…,q-1\}^n\to\{0,1\}$, которая принимает значение 1 на наборе $(\delta_1,…,\delta_n)\in\{0,1,…,q-1\}^n$, если $\delta_1+…+\delta_n\neq0\pmod q$. Библиогр. 9.

Ключевые слова: булева функция, контактная схема, сложность схем.

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

Реферативные базы данных:
УДК: 519.174
Статья поступила: 05.06.2009

Образец цитирования: К. Л. Рычков, “О сложности обобщённых контактных схем”, Дискретн. анализ и исслед. опер., 16:5 (2009), 78–87

Цитирование в формате AMSBIB
\RBibitem{Ryc09}
\by К.~Л.~Рычков
\paper О сложности обобщённых контактных схем
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 5
\pages 78--87
\mathnet{http://mi.mathnet.ru/da589}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2590757}
\zmath{https://zbmath.org/?q=an:1249.94083}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da589
  • http://mi.mathnet.ru/rus/da/v16/i5/p78

    ОТПРАВИТЬ: 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. К. Л. Рычков, “Нижняя оценка сложности реализации в классе $\pi$-схем $q$-ичного счётчика кратности $q$”, Дискретн. анализ и исслед. опер., 17:6 (2010), 68–76  mathnet  mathscinet  zmath
    2. С. В. Августинович, Ю. Л. Васильев, К. Л. Рычков, “Формульная сложность тернарной линейной функции”, Дискретн. анализ и исслед. опер., 19:3 (2012), 3–12  mathnet  mathscinet; S. V. Avgustinovich, Yu. L. Vasil'ev, K. L. Rychkov, “The computation complexity in the class of formulas”, J. Appl. Industr. Math., 6:4 (2012), 403–409  crossref
    3. Ю. Л. Васильев, К. Л. Рычков, “Нижняя оценка формульной сложности тернарной линейной функции”, Дискретн. анализ и исслед. опер., 20:4 (2013), 15–26  mathnet  mathscinet; Yu. L. Vasil'ev, K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, J. Appl. Industr. Math., 7:4 (2013), 588–596  crossref
    4. Jukna S., “Limitations of Incremental Dynamic Programming”, Algorithmica, 69:2 (2014), 461–492  crossref  mathscinet  zmath  isi  elib  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:321
    Полный текст:79
    Литература:34
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020