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

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

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



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






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


Дискрет. матем., 2008, том 20, выпуск 3, страницы 28–39 (Mi dm1010)  

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

Совместность и алгоритм распознавания несовместности реализаций случайных систем дискретных уравнений с двузначными неизвестными

А. В. Шаповалов


Аннотация: Рассматривается случайная система дискретных уравнений относительно $n$ двузначных неизвестных, состоящая из $M=M(n)$ уравнений. Функции в уравнениях выбираются случайно из конечного множества функций и могут зависеть не более чем от $m$ переменных. Обоснован критерий наличия у случайной системы уравнений пороговой функции совместности, определяемой как функция $Q(n)$, для которой вероятность совместности случайной системы уравнений стремится к единице и к нулю при $n\to\infty$, $M(n)/Q(n)\to0$ и $M(n)/Q(n)\to\infty$. Показано, что пороговые функции совместности могут иметь только вид $n$ и $n^{1-1/r}$, $2\le r\le m+1$; построены критерии наличия у случайной системы уравнений таких пороговых функций. Для случайных систем уравнений с пороговыми функциями вида $n^{1-1/r}$, $2\le r\le m+1$, оценена вероятность совместности при $M\sim cn^{1-1/r}$, $n\to\infty$ (она убывает от единицы до нуля, принимая все промежуточные значения, с ростом $c$ от нуля до $\infty$) и построен алгоритм распознавания несовместности реализаций случайных систем уравнений. Этот алгоритм имеет такую же предельную вероятность определения несовместности систем уравнений, как и алгоритм полного перебора решений, но низкую трудоемкость – порядка $n^{1-1/r}$.

DOI: https://doi.org/10.4213/dm1010

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

Англоязычная версия:
Discrete Mathematics and Applications, 2008, 18:4, 351–362

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

УДК: 519.2
Статья поступила: 10.07.2008

Образец цитирования: А. В. Шаповалов, “Совместность и алгоритм распознавания несовместности реализаций случайных систем дискретных уравнений с двузначными неизвестными”, Дискрет. матем., 20:3 (2008), 28–39; Discrete Math. Appl., 18:4 (2008), 351–362

Цитирование в формате AMSBIB
\RBibitem{Sha08}
\by А.~В.~Шаповалов
\paper Совместность и~алгоритм распознавания несовместности реализаций случайных систем дискретных уравнений с~двузначными неизвестными
\jour Дискрет. матем.
\yr 2008
\vol 20
\issue 3
\pages 28--39
\mathnet{http://mi.mathnet.ru/dm1010}
\crossref{https://doi.org/10.4213/dm1010}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2467451}
\zmath{https://zbmath.org/?q=an:1181.93080}
\elib{http://elibrary.ru/item.asp?id=20730250}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 4
\pages 351--362
\crossref{https://doi.org/10.1515/DMA.2008.025}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-53349128537}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1010
  • https://doi.org/10.4213/dm1010
  • http://mi.mathnet.ru/rus/dm/v20/i3/p28

    ОТПРАВИТЬ: 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. А. В. Шаповалов, “Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных”, Матем. вопр. криптогр., 1:3 (2010), 93–117  mathnet  crossref
    2. А. В. Шаповалов, “Совместность случайных систем уравнений с неравновероятной выборкой двузначных неизвестных”, Матем. вопр. криптогр., 2:4 (2011), 109–146  mathnet  crossref
  • Дискретная математика
    Просмотров:
    Эта страница:372
    Полный текст:91
    Литература:57
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020