Вероятностные модели комбинаторных схем

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

Ключевые слова

перечислительный метод; метод графов; вероятностные модели; задача нумерации; быстрое моделирование.

Литература

1. Риордан, Д. Введение в комбинаторный анализ / Д. Риордан. - М.: Иностранная литература, 1963.
2. Сачков, В.Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. - М.: МЦНМО, 1982.
3. Колчин, В.Ф. Случайные размещения / В.Ф. Колчин, Б.А. Севастьянов, В.П. Чистяков. - М.: Наука, 1976.
4. Кнут, Д. Искусство программирования на ЭВМ / Д. Кнут. - М.: Мир, 1976.
5. Энатская, Н.Ю. Анализ комбинаторных схем в доасимптотической области изменения параметров / Н.Ю. Энатская // Труды Карельского научного центра РАН. - 2018. - № 7. - C. 117-133.