Портал освітньо-інформаційних послуг «Студентська консультація»

  
Телефон +3 8(066) 185-39-18
Телефон +3 8(093) 202-63-01
 (093) 202-63-01
 studscon@gmail.com
 facebook.com/studcons

<script>

  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){

  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),

  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)

  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

 

  ga('create', 'UA-53007750-1', 'auto');

  ga('send', 'pageview');

 

</script>

Асимптотичні методи в задачах імовірнісної комбінаторики

Предмет: 
Тип роботи: 
Автореферат
К-сть сторінок: 
45
Мова: 
Українська
Оцінка: 

ймовірнісної міри розподілена на перших   векторах. Якщо   так, що   та  , то вся міра асимптотично зосереджена на цих векторах.

Далі, у §4. 4 досліджуються варіаційні ряди ймовірностей у поліноміальних схемах з одним виділеним менш ймовірним наслідком, з лінійно спадними ймовірностями  , з «швидко» або «повільно» спадними  , з двома різними значеннями для ймовірностей  ,  . Знаходяться оцінки для величини  .
У §4. 5 четвертого розділу розглядається послідовність незалежних у сукупності бульових випадкових величин  ,   таких, що  ,  ,   та побудована за допомогою   послідовність бульових випадкових величин  ,  , де довільні натуральні числа  ,  , такі, що   та  ;  , якщо   парне і   при непарному  ;   при  .
Такий метод побудови нових послідовностей використовується, зокрема, у генераторах випадкових чисел. У §4. 5 знаходяться ймовірнісні характеристики вихідної послідовності  , такі, як  ,  ,  , коефіцієнт кореляції   та інші. Досліджуються також статистичні характеристики вихідної послідовності для більш загального випадку, коли   може бути представлена у вигляді  ,  , де   – невипадкова функція від   зі значеннями в  ,  ,  .
У §4. 6 четвертого розділу вирішуються деякі питання знаходження скінченних формул та асимптотичних оцінок для моментів максимуму двох і трьох незалежних гауссівських випадкових величин. Наведемо деякі результати, які отримані методами комбінаторики та теорії рядів. Будемо позначати   –  -й початковий момент максимуму випадкових величин  .
Теорема 4. 6. 1. Якщо   та   – незалежні гауссівські випадкові величини з параметрами   та   відповідно, то при  :
Теорема 4. 6. 2. Якщо  ,  ,   – незалежні гауссівські випадкові величини з нульовими математичними сподіваннями та дисперсіями   то при    , де   визначаються за теоремою 4. 6. 1.
Розділ 5. Розробка та аналіз комбінаторно-ймовірнісних моделей та алгоритмів. Розділ присвячено побудові та дослідженню ймовірнісно-комбінаторних алгоритмів, за допомогою яких розв'язується ряд актуальних прикладних задач у галузі математичних методів захисту інформації, теорії надійності, оптимізації.
Починається розділ з побудови та аналізу в §5. 1 деяких статистичних алгоритмів декодування спотворених кодів. Відомо, що декодування лінійних кодів загального вигляду NP-повна задача. Пошук алгоритмів декодування, що мають порівняно з методом максимуму правдоподібності меншу складність та ефективні в практичному застосуванні, становить значний інтерес, особливо для методів захисту інформації та криптоаналізу.
Розглянемо лінійний код над   з породною матрицею  , який перетворює інформаційне слово   у кодове слово  , що передається по двійковому симетричному каналу без пам'яті з ймовірністю безпомилкової передачі  -го символу   та дає прийняте слово  :  ,  ,  ;  ,  .
Опишемо основні положення алгоритму декодування цього лінійного коду, який по прийнятому слову   та наперед невідомої породної матриці відновлює інформаційне слово  . Позначимо   розширену матрицю, яка утворена додаванням до породної матриці прийнятого слова як останнього стовпця:  ,  ,  , де при   елементи   матриці   дорівнюють відповідним елементам породної матриці  ;  ,  . Впорядковуємо рядки матриці   (чи необхідну їх частину) таким чином, щоб ймовірність безпомилкової передачі  -го символу   не зростала з номером рядка. Тобто, можна вважати, що всі   розташовані по незростанню  .
Оберемо  перших рядків розширеної матриці   та для деякого   складемо   всіляких комбінацій   рядків з  . Для кожної комбінації знаходимо бульову покоординатну суму всіх   рядків з обраними номерами  . Серед усіх утворених   нових рядків виділяємо ті, для яких виконується умова
 
Розглянемо статистику  , де підсумовування провадиться за всіма можливими невпорядкованими наборами  ; індикатор  , якщо виконується вище зазначена умова на виділені рядки та   в інших випадках;   – вагова функція. Показано, що асимптотично оптимальною є вагова функція  .
Значення першого символу   інформаційного слова   визначимо за допомогою критерію:  .
Складність визначення решти символів інформаційного слова має менший порядок.
Описаний алгоритм застосовується для декодування серії   лінійних кодів над   з однією породною матрицею для всіх кодів серії та різними інформаційними словами, які перетворюються в кодові слова і передаються по двійковому симетричному каналу без пам'яті з ймовірністю безпомилкової передачі  ,  ,  , що залежить від номерів коду та символу.
Для обох методів проводиться асимптотичний аналіз, відшукуються асимптотичні оцінки складності алгоритмів при незалежних в сукупності елементах породної матриці, таких, що  ,  ,  , та сильних перетвореннях:  ,  ,  ,  ,  . Описані алгоритми особливо ефективні при розріджених породних матрицях та недостатньої при сильних спотвореннях для інших методів вимірності кодового слова.
У §5. 2 розглядається бернулліївська послідовність, у якої в ряді випадкових моментів часу відбуваються зміни ймовірнісних характеристик послідовності. При цьому математичне сподівання послідовності може приймати тільки два значення   і  ,  ,  . На відміну від класичної задачі про «розладку» відбувається не один, а ряд моментів зміни характеристик. Задача полягає у виявленні та оцінці всіх цих моментів «переключення». У §5. 2 запропоновано алгоритм, що використовує специфічні можливості розглянутої бернуллівської послідовності та дозволяє будувати необхідні надійні інтервали для цих випадкових моментів переключення з мінімальними обмеженнями на
Фото Капча