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

n ef 1Л

Л-LLjk^

Рязанская государственная радиотехническая академия

На правах рукописи

УДК 681.324:519.2:519.83:519.977.5

Цветков Игорь Анатольевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДЛЯ КОНТРОЛЯ КАЧЕСТВА КОМПОНЕНТОВ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ

НА ОСНОВЕ ТЕОРИИ СТАТИСТИЧЕСКИХ СЕЛЕКЦИОННЫХ ПРОЦЕДУР, ИГР С ГИПЕРОТНОШЕНИЯМИ И МОДИФИКАЦИЙ ЦЕПЕЙ МАРКОВА

Специальность 05.13.11 -«Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей»

Диссертация на соискание ученой степени доктора технических наук

Научный консультант доктор технических наук, профессор, Заслуженный деятель науки и техники Российской Федерации Коричнев Л.П.

Рязань - 1998

_2_

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ................................................................................... 27

Глава 1. ОБЩАЯ ТЕОРИЯ СТАТИСТИЧЕСКИХ

СЕЛЕКЦИОННЫХ ПРОЦЕДУР ..................................... 56

1.1. Необходимость разработки общей теории статистических селекционных процедур .......................... 56

Ш. Статистические селекционные процедуры:

современное состояние.............................................................................................56

1.1.2. Необходимость разработки общей теории статистических селекционных процедур

на основе теоретико-множественной модели теории вероятностей..............60

1.1.3. Структура главы............................................................................................................61

1.2. Постановка двух задач статистической селекции ............ 63

1.3. Достаточные статистики в задачах

статистической селекции ................................................... 69

1.4. Синхронные и поочередные статистические селекционные процедуры .................................................. 72

1.5. Модели статистических селекционных процедур

с фиксированными объемами выборок ............................ 75

1.6. Выводы ................................................................................ 81

Глава 2. ЕДИНАЯ ФОРМАЛЬНАЯ МОДЕЛЬ

ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК

СТАТИСТИЧЕСКИХ СЕЛЕКЦИОННЫХ ПРОЦЕДУР ...... 84

2.1. Необходимость разработки единой формальной модели вероятностных характеристик

статистических селекционных процедур .......................... 84

_3_

2.1.1. Нерешенные задачи о вероятностных характеристиках

статистических селекционных процедур...............................................................84

2.1.2. Структура главы..........................................................................................................86

2.2. Исходные определения единой формальной модели вероятностных характеристик

статистических селекционных процедур .......................... 89

2.3. Исходные определения подмодели

функционала вероятности правильного решения............ 92

2.4. Функционал вероятности правильного решения синхронных статистических селекционных процедур..... 95

2.5. Функционал вероятности правильного решения поочередных статистических селекционных процедур....... 128

2.6. Примеры расчета значений функционала

вероятности правильного решения .................................. 143

2.6.1. Расчет значений функционала вероятности правильного решения статистической селекционной процедуры

для двух гауссовских случайных величин........................................................... 143

2.6.2. Расчет значений функционала вероятности правильного решения статистической селекционной процедуры

для двух случайных величин с гамма-распределением.................................... 154

2.6.3. Расчет значений 1-частного функционала вероятности правильного решения статистической селекционной процедуры

для двух гауссовских случайных величин........................................................... 159

2.6.4. Ускоренный расчет значений функционала вероятности правильного решения статистической селекционной процедуры

для двух случайных величин с гамма-распределением....................................167

2.7. Выводы ............................................................................... 171

_4_

Глава 3. КРИТЕРИИ ОПТИМАЛЬНОСТИ

И МЕТОДЫ АДАПТАЦИИ

СТАТИСТИЧЕСКИХ СЕЛЕКЦИОННЫХ ПРОЦЕДУР ..... 175

3.1. Необходимость разработки критериев оптимальности и методов адаптации статистических

селекционных процедур .................................................... 175

3.1.1. Нерешенные задачи об оптимальных и адаптивных

статистических селекционных процедурах........................................................ 175

3.1.2. Структура главы........................................................................................................179

3.2. Критерии оптимальности

статистических селекционных процедур ......................... 182

3.2.1 Особенности критериев оптимальности

статистических селекционных процедур.............................................................182

3.2.2. Подклассы статистических селекционных процедур......................................186

3.2.3. Максиминный критерий оптимальности

статистических селекционных процедур.............................................................188

3.2.4. Зона безразличия по отношению к вероятности правильного решения........190

3.2.5. Состоятельные синхронные статистические селекционные процедуры..........196

3.2.6. Максиминные синхронные статистические селекционные процедуры.............199

3.2.7. Состоятельные поочередные статистические селекционные процедуры.........200

3.3. Оптимизация статистической

селекционной процедуры Собела—Хьюетта ....................204

3.3.1. Расчет функционала вероятности правильного решения статистической селекционной процедуры Собела-Хьюетта..........................204

3.3.2. Оптимальные максиминные и байесовские

статистические селекционные процедуры Собела-Хьюетта......................... 208

_5_

3.4. Оптимальные поочередные

статистические селекционные процедуры

для бернуллиевских случайных последовательностей ........217

3.4.1. Общие сведения........................................................................................................ 217

3.4.2. Вывод соотношения

для функционала вероятности правильного решения....................................219

3.4.3. Вывод соотношений для вероятностных характеристик

объемов выборок..................................................................................................... 226

3.4.4. Результаты расчетов по полученным соотношениям..................................... 229

3.4.5. Оптимальное значение суммарного объема выборок.....................................243

3.4.6. Сравнение оптимальных максиминных синхронной и поочередной статистических селекционных процедур

для бернуллиевских случайных последовательностей...................................244

3.5. Оптимальные статистические селекционные процедуры Собела-Хьюетта при марковском воздействии ...............248

3.5.1. Общие сведения........................................................................................................248

3.5.2. Марковское воздействие

на бернуллиевские случайные последовательности....................................... 250

3.5.3. Вывод соотношения

для функционала вероятности правильного решения................................... 252

3.5.4. Результаты расчетов по полученным соотношениям......................................259

3.5.5. Оптимальное значение объема выборок............................................................264

3.5.6. Сравнение оптимальных максиминных статистических селекционных процедур Собела-Хьюетта

при отсутствии и наличии марковского воздействия.....................................266

3.6. Адаптивные статистические

селекционные процедуры .................................................268

3.6.1. Постановка задачи.................................................................................................. 268

_6_

3.6.2. Статистические селекционные процедуры

с параметрической и непараметрической адаптацией..................................274

3.7. Выводы ............................................................................... 277

Глава 4. СТАТИСТИЧЕСКАЯ СЕЛЕКЦИЯ

СЛУЧАЙНЫХ ПОТОКОВ ............................................. 281

4.1. Необходимость разработки статистических потоковых селекционных процедур ....................................................281

4.1.1. Нерешенные задачи о статистической селекции случайных потоков..........281

4.1.2. Структура главы....................................................................................................... 283

4.2. Особенности статистической селекции

случайных потоков ............................................................286

4.3. Модели статистических потоковых

селекционных процедур ....................................................293

4.4. Вероятностные характеристики

статистических потоковых селекционных процедур ......303

4.5. Статистическая селекция

простейших случайных потоков .......................................307

4.5.1. Общие положения.....................................................................................................307

4.5.2. Фиксированное время наблюдений

для двух простейших случайных потоков...........................................................307

4.5.3. Фиксированный объем выборок для двух и более простейших потоков.........312

4.6. Примеры расчетов вероятностных характеристик

статистических потоковых селекционных процедур .........323

4.6.1. Расчет вероятностных характеристик потоковой

селекционной процедуры для простейших случайных потоков

при фиксированном объеме выборки................................................................. 323

4.6.2. Расчет вероятностных характеристик потоковой селекционной процедуры для случайных потоков Эрланга

при фиксированном времени наблюдений..........................................................325

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

из двух каналов передачи данных........................................................................334

4.7. Выводы ............................................................................... 336

Глава 5. МНОГОСВЯЗНЫЕ, НЕОДНОРОДНЫЕ, РЕЖИМНЫЕ, УПРАВЛЯЕМЫЕ И НЕНАБЛЮДАЕМЫЕ КОНЕЧНЫЕ ЦЕПИ МАРКОВА. СПОСОБЫ МАШИННОГО МОДЕЛИРОВАНИЯ ИХ РЕАЛИЗАЦИЙ....................... 339

5.1. Необходимость разработки новых моделей конечных цепей Маркова и способов

машинного моделирования их реализаций .....................339

5.1.1. Актуальные задачи развития моделей конечных цепей Маркова..................339

5.1.2. Структура главы........................................................................................................343

5.2. Минимаксные s-оптимальные критерии проверки нескольких сложных статистических гипотез о параметре многосвязной конечной цепи Маркова...........................345

5.2.1. Введение......................................................................................................................345

5.2.2. Исходные допущения .............................................................................................346

5.2.3. Вспомогательные положения................................................................................348

5.2.4. Основной результат.................................................................................................349

5.3. Ядерные оценки распределений вероятностей случайных элементов на ненаблюдаемой обобщенной односвязной однородной конечной цепи Маркова........351

5.3.1. Введение......................................................................................................................351

5.3.2. Исходные допущения и постановка задачи ......................................................352

5.3.3. Функционал ядра......................................................................................................355

5.3.4. Математическое ожидание функционала ядра.................................................357

5.3.5. Статистики.................................................................................................................358

5.3.6. Ядерные оценки........................................................................................................359

5.3.7. Процедура получения "гладких" оценок..............................................................361

5.4. Режимные многосвязные неоднородные конечные цепи

Маркова и машинное моделирование их реализаций

на основе раскрашенных взвешенных псевдоорграфов .....362

5.4.1. Введение..................................................................................................................... 362

....................... 366

5.4.2. Объект моделирования и модель для его представления.............................363

5.4.3. Способ моделирования..................................................................

5.4.4. Машинное представление объекта моделирования...............

5.4.5. Пример расчета эффективности предлагаемой модели.......

5.5. Режимные многосвязные управляемые однородные

конечные цепи Маркова и способ машинного моделирования их реализаций .........................................369

5.5.1. Введение......................................................................................................................369

5.5.2. Модель режимной многосвязной управляемой однородной

конечной цепи Маркова...........................................................................................370

5.5.3. Способ машинного моделирования реализаций режимной

многосвязной управляемой однородной конечной цепи Маркова...............371

5.5.4. Оптимизационная задача представления вероятностей переходов

и способ ее решения...............................................................................................372

5.5.5. Оптимизация длины кадра......................................................................................373

5.5.6. Машинное представлении модели режимной многосвязной

управляемой однородной конечной цепи Маркова..........................................374

_9_

5.5.7. Алгоритмы моделирования реализаций режимной многосвязной

управляемой однородной конечной цепи Маркова ........................................383

5.6. Способ расчета вероятностных характеристик односвязной однородной бинарной цепи Маркова........ 398

5.6.1. Введение......................................................................................................................398

5.6.2. Постановка задачи...................................................................................................399

5.6.3. Рекуррентная форма...............................................................................................401

5.6.4. Многочленная форма...............................................................................................403

5.6.5. Вычислительная эффективность предлагаемого способа............................404

5.7. Выводы ...............................................................................406

Глава 6. СТРАТЕГИИ ОПТИМАЛЬНОГО

НЕПАРАМЕТРИЧЕСКОГО АДАПТИВНОГО УПРАВЛЕНИЯ МНОГОСВЯЗНЫМИ УПРАВЛЯЕМЫМИ ОДНОРОДНЫМИ КОНЕЧНЫМИ ЦЕПЯМИ МАРКОВА .......................... 409

6.1. Необходимость разработки стратегий оптимального непараметрического адаптивного управления многосвязными управляемыми однородными конечными цепями Маркова............................................409

6.1.1. Современное состояние вопроса и нерешенные задачи................................409

6.1.2. Структура главы........................................................................................................ 413

6.2. Стратегии непараметрического адаптивного управления многосвязными управляемыми однородными

конечными цепями Маркова..............................................415

6.2.1. Постановка задачи................................................................................................... 415

6.2.2. Свойства /'-связных управляемых однородных конечных цепей Маркова и стратегий непараметрического адаптивного управления

при целях управления 81, а\................................................................................... 418

_10_

6.2.3. Синтез стратегий непараметрического адаптивного управления

для ^-связных управляемых однородных конечных цепей Маркова

при целях управления 81( 4 б2.............................................................................420

6.3. Алгоритм стратегий непараметрического адаптивного управления многосвязными управляемыми однородными конечными

цепями Маркова ................................................................423

6.4. Результаты статистического моделирования ...................428

6.5. Применение предлагаемых стратегий непараметрического адаптивного управления многосвязными управляемыми однородными конечными цепями Маркова в протоколах информационно-вычислительных сетей.........................429

6.6. Выводы ...............................................................................432

Глава 7. МОДЕЛИ СТАТИСТИЧЕСКИХ

И БЕСКОАЛИЦИОННЫХ ИГР

С ГИПЕРОТНОШЕНИЯМИ ПРЕДПОЧТЕНИЯ .......... 435

7.1. Необходимость разработки моделей статистических и бескоалиционных игр с гиперотношениями предпочтения .....................................................................435

7,1.1. Анализ имеющихся результатов по моделям статистических

и бескоалиционных игр и нерешенные задачи..................................................435

7,1.2, Структура главы.........................................................................................................441

7.2. Модель статистической игры с гиперотношениями

предпочтения .....................................................................444

7.3. «Композиционный» принцип оптимальности в статистических играх с гиперотношениями предпочтения .....................................................................447

7.3.1. Общие условия реализуемости

"композиционного" принципа оптимальности

447

7.3.2. Условия реализуемости "композиционного" принципа оптимальности

в статистических играх с бинарными отношениями предпочтения.............450

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

7.4. «Конъюнктивный» принцип оптимальности в статистических играх с гиперотношениями предпочтения .....................................................................464

7.4.1. Общие условия реализуемости

"конъюнктивного" принципа оптимальности.......................................................464

7.4.2. Условия реализуемости "конъюнктивного" принципа оптимальности в статистических играх с бинарными отношениями предпочтения. Гомоморфность редуцирующего преобразования

7.5.1. Общие условия реализуемости

"дизъюнктивного" принципа оптимальности.......................................................473

7.5.2. Условия реализуемости "дизъюнктивного" принципа оптимальности в статистических играх с бинарными отношениями предпочтения. Гомоморфность редуцирующего преобразования

для "дизъюнктивного" принципа оптимальности...............................................474

7.5.3. Минимизация операторов решения

для "дизъюнктивного" принципа оптимальности...............................................482

для "конъюнктивного" принципа оптимальности.................

7.5. «Дизъюнктивный» принцип оптимальности в статистических играх с гиперотношениями предпочтения ...................................................

465

473

_12_

7.5.4, Гомоморфность редуцирующего преобразования

для "конъюнктивного" принципа оптимальности (продолжение)..................485

7.6. Модель обобщенной бескоалиционной игры

с гиперотношениями предпочтения ................................488

7.7. Выводы ...............................................................................492

Глава 8. РАЗРАБОТКА И ИССЛЕДОВАНИЕ

ДЕТЕРМИНИРОВАННЫХ ИЗОМОРФНЫХ УТОЧНЕНИЙ ПСЕВДОАЛГОРИТМОВ МОДЕЛИРОВАНИЯ РЕАЛИЗАЦИЙ СТОХАСТИЧЕСКИХ ОБЪЕКТОВ.....