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

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

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



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






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


Дискретн. анализ и исслед. опер., 1995, том 2, номер 3, страницы 18–23 (Mi da465)  

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

Расшифровка пороговых функций $k$-значной логики

Н. Ю. Золотых, В. Н. Шевченко

Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: Рассматривается класс пороговых функций $k$-значной логики от $n$ переменных. Под расшифровкой функции из этого класса понимается процедура из последовательности вопросов о значении функции в точке, после завершения которой функция восстанавливается в остальных точках. Доказано, что при любом фиксированном $n$ существует алгоритм расшифровки любой пороговой функции $k$-значной логики, который использует не более $C_n\log^n(k+1)$ вопросов о значении функции в точке, где $C_n$ – константа, зависящая только от $n$.
Библиогр. 15

Полный текст: PDF файл (608 kB)

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

Образец цитирования: Н. Ю. Золотых, В. Н. Шевченко, “Расшифровка пороговых функций $k$-значной логики”, Дискретн. анализ и исслед. опер., 2:3 (1995), 18–23

Цитирование в формате AMSBIB
\RBibitem{ZolShe95}
\by Н.~Ю.~Золотых, В.~Н.~Шевченко
\paper Расшифровка пороговых функций $k$-значной логики
\jour Дискретн. анализ и исслед. опер.
\yr 1995
\vol 2
\issue 3
\pages 18--23
\mathnet{http://mi.mathnet.ru/da465}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1388658}
\zmath{https://zbmath.org/?q=an:0860.94036|0856.94038}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da465
  • http://mi.mathnet.ru/rus/da/v2/i3/p18

    ОТПРАВИТЬ: 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. Shevchenko V.N., Zolotykh N.Y., “Lower bounds for the complexity of learning half-spaces with membership queries”, Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence, 1501, 1998, 61–71  mathscinet  zmath  isi
    2. Shevchenko V.M., Zolotykh N.Y., “On complexity of deciphering of threshold functions of k-valued logic”, Dokl Akad Nauk, 362:5 (1998), 606–608  mathnet  mathscinet  zmath  isi
    3. Н. Ю. Золотых, В. Н. Шевченко, “Об оценке сложности расшифровки пороговых функций $k$-значной логики”, Ж. вычисл. матем. и матем. физ., 39:2 (1999), 346–352  mathnet  mathscinet  zmath; N. Yu. Zolotykh, V. N. Shevchenko, “Estimating the complexity of deciphering a threshold functions in a $k$-valued logic”, Comput. Math. Math. Phys., 39:2 (1999), 328–334
    4. Н. Ю. Золотых, “О сложности решения одного класса задач целочисленного линейного программирования”, Дискретн. анализ и исслед. опер., сер. 2, сер. 2, 10:1 (2003), 3–10  mathnet  mathscinet  zmath
    5. Н. Ю. Золотых, А. Ю. Чирков, “О верхней оценке мощности минимального разрешающего множества пороговой функции”, Дискретн. анализ и исслед. опер., 19:5 (2012), 35–46  mathnet  mathscinet
    6. Золотых Н.Ю., “Расшифровка пороговой функции, заданной расширенным оракулом”, Вестник нижегородского университета им. Н.И. Лобачевского, 2012, 175–178  elib
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:327
    Полный текст:125
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020