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

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

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



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






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


Дискретная математика, 1994, том 6, выпуск 1, страницы 83–99 (Mi dm618)  

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

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

В. А. Ватутин
Аннотация: Для файла $\mathcal F$, содержащего $n$ записей, помеченных ключами $F_1,\ldots,F_n$, принадлежащими линейно упорядоченному множеству ключей
$$ \mathcal K_m=\{K_j, 1\le j\le m\colon\ K_1<K_2<\ldots<K_m\} $$
рассматривается перестановка (сортировка) записей $\sigma=\sigma(1)\ldots\sigma(n)$ такая, что
$$ F_{\sigma(1)}\leq F_{\sigma(2)}\le\ldots\le F_{\sigma(n)}, $$
и для любого $i=1,2,\ldots,n-1$ соотношение $F_{\sigma(i)}=F_{\sigma(i+1)}$ влечет неравенство $\sigma(i)<\sigma(i+1)$. В предположении, что ключ $F_i$ для $i$-й записи выбирается случайно и равновероятно из множества ключей $\mathcal K_m$, доказаны предельные теоремы о распределении числа отрезков возрастания в перестановке $\sigma$ при $n,m\to\infty$. Вид этих теорем зависит от асимптотического поведения величины $ne^{-n/m}$ при $n,m\to\infty$.
Статья поступила: 16.02.1993
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2
Образец цитирования: В. А. Ватутин, “Предельные теоремы для числа отрезков возрастания в случайных перестановках, порождаемых алгоритмами сортировки”, Дискрет. матем., 6:1 (1994), 83–99; Discrete Math. Appl., 4:1 (1994), 31–44
Цитирование в формате AMSBIB
\RBibitem{Vat94}
\by В.~А.~Ватутин
\paper Предельные теоремы для числа отрезков возрастания в~случайных перестановках, порождаемых алгоритмами сортировки
\jour Дискрет. матем.
\yr 1994
\vol 6
\issue 1
\pages 83--99
\mathnet{http://mi.mathnet.ru/dm618}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1273235}
\zmath{https://zbmath.org/?q=an:0801.60003}
\transl
\jour Discrete Math. Appl.
\yr 1994
\vol 4
\issue 1
\pages 31--44
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm618
  • https://www.mathnet.ru/rus/dm/v6/i1/p83
  • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Статистика просмотров:
    Страница аннотации:299
    PDF полного текста:117
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024