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

Національна академія наук України

Інститут кібернетики імені В. М. Глушкова

 

УДК 519. 2+519. 7

 

Автореферат дисертації на здобуття наукового ступеня доктора фізико-математичних наук

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

 

01. 05. 01 – теоретичні основи інформатики та кібернетики

 

Савчук Михайло Миколайович

 

Київ 1999

 

 

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

Перші ймовірнісні задачі виникли на основі комбінаторних схем. Елементарна теорія ймовірностей, становлення якої пов'язано з іменами Б. Паскаля, П. Ферма, Я. Бернуллі, Л. Ейлера, фактично встановила тотожність комбінаторних задач і задач із класичними ймовірностями. У самостійну математичну дисципліну теорія ймовірностей оформилася остаточно у ХХ столітті після побудови А. Н. Колмогоровим аксіоматичної основи теорії. Ймовірнісні методи, що спираються на багатий апарат математичного аналізу, дали можливість розв'язати ряд складних комбінаторних задач. Одними з перших фундаментальних робіт, у яких систематично і послідовно застосовуються ймовірнісні методи в комбінаториці, стали монографії П. Ердеша «Ймовірнісні методи в комбінаториці» (1976), В. Ф. Колчина, Б. О. Севастьянова, В. П. Чистякова «Випадкові розміщення» (1976), В. Н. Сачкова «Комбінаторні методи дискретної математики» (1976) і «Ймовірнісні методи в комбінаторному аналізі» (1978), В. Ф. Колчина «Випадкові відображення» (1984), І. Н. Коваленка, А. О. Левітської, М. М. Савчука «Вибрані задачі ймовірнісної комбінаторики» (1986). Всі ці монографії видано російською мовою.

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

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

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

- провести асимптотичне дослідження різноманітних схем розміщення частинок, вивчити асимптотичну поведінку мішаних моментів випадкових величин, розподілів випадкових величин, сумісних розподілів тощо;

- розробити загальну методику асимптотичного дослідження векторних випадкових процесів у задачах розміщення та доведення слабкої збіжності векторних випадкових процесів, побудованих за різними схемами розміщення частинок (з двома типами спрямованості часу), до гауссівских дифузійних процесів;

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

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

Загальна