Позначимо щільність розподілу моменту часу надходження заявки (вимоги) на півпрямій ;  – щільність розподілу часу закінчення обслуговування вимоги за умови надходження його в момент часу ;  – ймовірність того, що вимога, яка надійшла, буде повністю обслужена (ймовірність виконання задачі). Тоді , де нестаціонарний коефіцієнт готовності  – ймовірність того, що система буде працездатна в момент часу ,  – ймовірність того, що система не відкаже на проміжку за умови, що вона була працездатна в момент . За допомогою останньої формули та отриманих аналітичних співвідношень для нестаціонарного коефіцієнта готовності знайдені аналітичні вирази для ймовірності повного обслуговування вимоги різними типами систем обслуговування для двох випадків щодо часу надходження вимоги: щільність розподілу моменту часу надходження вимоги має вигляд (з деяким параметром ) або надходження вимоги рівноймовірно на проміжку , .

Параграф 5.5 присвячено вивченню схеми розміщення комплектів частинок різного типу методом статистичного моделювання схеми на ЕОМ. Для різних схем розміщення частинок отримано багато теоретичних, в основному асимптотичних, тверджень про ймовірнісні характеристики випадкових величин і процесів, побудованих за допомогою цих схем. Однак асимптотичний характер результатів часто утруднює їх застосування при не дуже великих значеннях параметрів. До того ж в багатьох теоретичних роботах відсутні добрі оцінки збіжності з явно виписаними константами. Широке коло питань в різних схемах розміщення ще потребує вивчення. Моделювання таких схем на ЕОМ дало б можливість знаходити значення ймовірнісних характеристик статистично з необхідною точністю. При цьому різні схеми можуть моделюватися одноманітно, а за одне моделювання можна одночасно отримувати значення ймовірнісних характеристик ряду різних випадкових величин, заданих на цих схемах.

Нехай в ячейках, занумерованих числами , випадковим чином розміщується незалежно один від одного комплекти частинок обсягу , кожний з яких містить частинок -го типу, , . Окремий комплект розміщується таким чином, що в кожну ячейку попадає не більше однієї частинки та всі можливих розміщень рівноймовірні. Така схема розміщення раніше не вивчалася. В даному параграфі моделювання цієї схеми використовується для одночасного визначення математичного сподівання та дисперсії часу (мінімальне число комплектів) до заповнення фіксованих множин ячейок комплектами різного обсягу. За допомогою запропонованого алгоритму моделювання були досліджені на ЕОМ декілька десятків схем розміщення і отримані оцінки вказаних характеристик часу сподівання.

У останньому §5.6 пропонуються методи статистичного визначення спеціальних властивостей багатовимірних бульових функцій. Позначимо множину бульових -векторів, тобто двійкових векторів розмірністю . Нехай мається векторнозначна бульова функція з параметром, де вхід , параметр , вихід , тобто та є бульовими векторами вимірності та відповідно. За допомогою таких функцій може описуватись функціонування вузлів дискретних пристроїв, систем керування, скінченних автоматів тощо. Наприклад, блочний шифратор з входом , ключем і виходом у режимі електронної кодової книги реалізує такі бульові функції.

Позначимо булів -вектор, на -й позиції (координаті) якого стоїть одиниця, а на решті – нулі (); через  – значення -ї координати вектора . Припустимо, що на множинах та задані рівноймовірні розподіли. Функція має лавинний ефект по входу, якщо для довільних () ймовірність . Аналогічно означається лавинний ефект функції по параметру . При великих і перевірити наявність лавинного ефекту у функції згідно з наведеним, а також іншими означеннями, не можливо через надто великий обсяг обчислень. У п. 5.6.1 §5.6 за допомогою статистичного моделювання будується статистичний критерій для перевірки присутності у функції лавинного ефекту по входу і по параметру.

При програмній або апаратній реалізації складних бульових функцій від багатьох змінних виникає проблема перевірки правильності реалізації, тобто тотожності бульового перетворення деякій еталонній функції. Здійснити таку перевірку при великому числі змінних перебором за усіма можливими входами – задача, що не під силу навіть сучасній обчислювальній техніці. У пункті 5.6.2 §5.6 пропонуються та обґрунтовуються ймовірнісні тести, що установлюють із заданими значеннями вірогідності та ризику методом Монте-Карло тотожність або неоднаковість векторнозначних бульових функцій і багатьох змінних з параметрами.

При побудові першого тесту по перевірці тотожності і , коли зафіксовано деякий параметр , вводяться дві ймовірнісні характеристики алгоритму:  – ймовірність того, що у випадку підтвердження гіпотези тотожності ризик при використанні функції замість функції не перевищує (), де ризик – це ймовірність того, що при рівноймовірно вибраних входах обчислені значення функцій при фіксованому параметрі не співпадають: . Основна операція тестування полягає в порівнянні векторів-значень функцій, що розглядаються як "чорні ящики". Наводиться формула для числа таких операцій в залежності від довірчої ймовірності та ймовірності ризику .У пункті 5.6.2 описується також статистичний тест перевірки тотожності функцій і при не фіксованому параметрі .

У д о д а т к у до дисертаційної роботи наведено основні положення розробленого методу умовної оптимізації складних багатоекстремальних функцій від багатьох змінних, який був застосований до розв'язання задачі синтезу багатошарових інтерференційних оптичних покриттів з заданими властивостями. Однією з особливостей методу є вибір початкових наближень для застосування на різних етапах ієрархічного пошуку оптимуму спеціальних варіантів методів спуску зі штрафними функціями. Вибір початкових точок здійснювався за допомогою статистичного моделювання схем випадкового розміщення частинок по ячейках.

На основі описаного методу був знайдений цілий ряд різноманітних оптичних покриттів із заданими оптимальними характеристиками: з похідною , близькою до нуля, та високими коефіцієнтами відбиття; з мінімальною чутливістю до впливу температури або похибкам у нанесенні шарів, та високими коефіцієнтами відбиття; з близьким до та оптимізацією інших оптичних характеристик; для різних показників заломлення та товщин шарів діелектричних покриттів. Знайдені апроксимуючі формули, що дозволяють синтезувати інтерференційні покриття з оптимальними оптичними характеристиками при різних початкових даних.

ОСНСВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

Загальним результатом даного дослідження є розробка нових ймовірнісно-комбінаторних методів, алгоритмів і теоретичних положень, що використані для розв'язання широкого класу задач теорії випадкових розміщень, задач визначення ймовірнісних характеристик дискретних моделей. Розроблено математичний апарат для дослідження дискретних схем, комбінаторно-ймовірнісних алгоритмів та розв'язання прикладних задач, що використовують поняття та ідеологію теорії випадкових розміщень.

1.

1.

1.

1.

1.

Таким чином, в дисертації розв'язана актуальна науково-прикладна проблема в області асимптотичного дослідження широкого класу задач теорії випадкових розміщень та їх застосувань до вивчення комбінаторно-ймовірнісних моделей та алгоритмів.

Основні положення дисертації опубліковані в таких працях:

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

Савчук М.М. Асимптотичні методи в задачах ймовірнісної комбінаторики. – Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 1999.

Дисертаціійна робота присвячена дослідженню та розробці нових ймовірнісно-комбінаторних методів, алгоритмів та теоретичних положень, що використані для розв'язання широкого класу задач теорії випадкових розміщень, задач визначення ймовірнісних характеристик дискретних моделей.

Розроблено нові методи отримання багатовимірних гауссівських граничних теорем та функціональних граничних теорем в n-вимірному просторі функцій без розриву другого роду у схемах розміщення частинок. Запропоновано загальну чітку методику асимптотичного дослідження векторних випадкових процесів у задачах розміщення. Ця методика дала можливість довести цілий ряд функціональних граничних теорем у різноманітних схемах розміщення, а також гауссівські граничні теореми для розподілів. Отримані результати, а також теореми про збіжність розподілів випадкових величин у схемах розміщення до пуассонівських, складних пуассонівських, двічі експоненційніх та інших розподілів дають цілісну картину асимптотичної поведінки випадкових величин, процесів і методику їхнього вивчення для певних класів схем розміщення.

З використанням отриманих результатів розроблено ряд ймовірнісно-комбінаторних алгоритмів для дослідження методів декодування, комбінаторних схем, дискретних і неперервних моделей, оптимізації їхніх характеристик. Розроблені методи, алгоритми та отримані результати мають застосування в області криптографічного захисту інформації, методів визначення статистичних характеристик та оцінки якості дискретних пристроїв та керуючих систем, теорії надійності, статистичної фізики, оптиці.

Ключові слова: ймовірнісна комбінаторика, асимптотичні методи, випадкові розміщення, граничні теореми для розподілів, простір функцій без розривів другого роду, збіжність векторних випадкових процесів, ймовірнісно-комбінаторні алгоритми, декодування спотворених кодів, статистичні випробування, оцінка параметрів, перевірка гіпотез, оптимізація, багатошарові інтерференційні оптичні покриття, оптимізація.

Савчук М.Н. Асимптотические методы в задачах вероятностной комбинаторики. – Рукопись.

Диссертация на соискание научной степени доктора физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. – Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 1999.

Диссертационная работа посвящена исследованию и разработке новых вероятностно-комбинаторных методов, алгоритмов и теоретических положений, которые использованы для решения широкого класса задач теории случайных размещений, задач определения вероятностных характеристик дискретных моделей.

Проведено асимптотическое исследование различных схем размещения частиц, получены результаты об асимптотическом поведении смешанных моментов случайных величин, доказан ряд предельных теорем для распределений, совместных распределений.

Предложен единый подход к исследованию совместного распределения случайных величин в схемах размещения и доказательству функциональных предельных теорем. Разработаны новые методы получения многомерных гауссовских предельных теорем и функциональных предельных теорем в n-мерном пространстве функций без разрывов второго рода в схемах размещения частиц. Предложена общая четкая методика асимптотического исследования векторных случайных процессов в задачах размещения. Эта методика дала возможность доказать целый ряд функциональных предельных теорем в различных схемах размещения, а также гауссовские предельные теоремы для распределений.

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

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

Разработан ряд вероятностно-комбинаторных алгоритмов для исследования методов декодирования, комбинаторных схем, дискретных и непрерывных моделей, оптимизации их характеристик.

Разработанные методы, алгоритмы и полученные результаты имеют приложения в области криптографической защиты информации, методов определения статистических характеристик и оценки качества дискретных устройств и управляющих систем, теории надежности, статистической физике, оптике.

Ключевые слова: вероятностная комбинаторика, асимптотические методы, случайные размещения, предельные теоремы для распределений, пространство функций без разрывов второго рода, сходимость векторных случайных процессов, вероятностно-комбинаторные алгоритмы, декодирования искаженных кодов, статистические испытания, оценка параметров, проверка гипотез, оптимизация, многослойные интерференционные оптические покрытия.

Savchuk M.N. Asymptotic methods in problems of probability combinatorics. – Мanuscript.

Thesis submitted for the degree of doctor in Physics and Mathematics, specialization "Theoretical Foundation of Computer Science" (Mathematical Cybernetics). – V.M.Institute of Cybernetics of the Ukrainian National Academy of Science. Kiev, 1999.

The dissertation is devoted to investigation and development of new probabilistic combinatorial algorithms, methods and theoretical assertions used to solve a broad class of problems in the theory of random allocations and to evaluate probability characteristics of discrete models.

Methods are developed to derive multi-dimensional Gaussian limit theorems and functional limit theorems in -dimensional space of functions without discontinuities of the second kind for allocation problems. A general clear technique is proposed to asymptotically investigate vector random processes related to allocation problems. This technique permitted to prove a lot of functional limit theorems in various allocation schemes, as well as Gaussian limit theorems for distribution functions the results obtained as well as theorems on the convergence of distribution functions of random variables related to allocation problems to Poisson and Compound Poisson, twice exponential and other distributions provide a comprehensive understanding of the asymptotic behavior of random variables and processes related to certain classes of allocation problems and a technique to investigate them.

On the base of the obtained results a number of probabilistic combinatorial algorithms is developed used to analyze decoding algorithms, combinatorial schemes discrete and continuous models and to optimize their characteristics. The developed method, algorithms and the obtained results may be applied to cryptographic information protection techniques, evaluation of the performance of discrete and control devices, reliability theory, statistical physics, optics.

Key words: probabilistic combinatorics, asymptotic methods, random allocations, limit theorems for distribution functions, space of functions without discontinuities of the second kind, convergence of vector random processes, probabilistic combinatorial algorithm, decoding corrupted codes, statistical trials, estimation of parameters, hypotheses testing, optimization, multi-layer interference optical coatings.