|
Эта публикация цитируется в 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}$.
Статья поступила: 10.07.2008
Образец цитирования:
А. В. Шаповалов, “Совместность и алгоритм распознавания несовместности реализаций случайных систем дискретных уравнений с двузначными неизвестными”, Дискрет. матем., 20:3 (2008), 28–39; Discrete Math. Appl., 18:4 (2008), 351–362
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1010https://doi.org/10.4213/dm1010 https://www.mathnet.ru/rus/dm/v20/i3/p28
|
Статистика просмотров: |
Страница аннотации: | 600 | PDF полного текста: | 230 | Список литературы: | 86 | Первая страница: | 9 |
|