Модели просеивания случайных множеств тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИМ ОРДЕНА ЛЕНИНА ОРДЕНА 0КТЯ0?ЬСК01^ РЕВОЛЮЦИИ У. ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ км. М. В. ЛОМОНОСОВА

йеханшсо-натепзтический факультет

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

ГАЛЬЦОВ Максим Вениаминович

УДК Я9.21.

«ОДЕЛИ ПРОСЕИВАНИЯ СЛУЧАЙНЫХ МНОЖЕСТВ ОТ.01.05 - теория вероятностей и иатематическая статистика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1992

Работа выполнена на кафедре теории" вероятностей механико-зтематического факультета Московского Государственного шверситета имени Ы.В-Ломоносова.

Научный руководитель-- доктор ' физико-математических наук,

-профессор А.Д.Соловьев.

Официальные оппоненты: доктор ' физико-математических наук,

профессор В.М.Круглов, кандидат физико-математических наук» доцент. А.В.Павлов.

Ведущая организация - Московский Институт Электронного

Машиностроения.

Защита диссертации состоится "/¿2" ¿¿^¿с-и*_ 1952 г. в

? час. 05 мин. на заседании специализированного совета 053.05.04 при Московском Государственном Университете 1. М.В.Ломоносова по адресу: 119899, ГСП, Москва, .Левиасккг >ры, [ЛГУ, механико-математический факультет, аудитория 16-24, I С диссертацией можно ознакомиться в библиотеке мэхшшко-гематического факультета МГУ (14 этаж).

Автореферат разослан "/<эп ^._ 1992 г.

Ученый секретарь специализированна« совета Д.053.05.04 при МГУ, доцент

Т. П Лукашенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТ-1

Актуальность темы. В настоящее время большинство ело; технических и организациошго-теянйческпх систем имеют час компьютерные подсистем, неотъемлемой частью которых являе ирограг.мюе обеспечение (software). Поскольку сбой в подос системе влечет за собой серьезные экономические потери, мс стать причглсй аварии, экологической катастрофы и даже гас людей, то требования, предъявляемые к надежности таких сисз как правило, весьма велики. Входящая в состав системы аппарат (hardware), наде:кность которой оценивается хорошо известа способами т; основном удовлетворяет этим требованиям. Однг как показывает практика, очень часто причиной отказа сиса является не сбой аппаратур«, а ошибка в програшном обеспечен К сожалению, сложность современного программного обзспече такова, что, по всей видаюсти, не существует технолс создания програмуноЯ продукции без единого дефекта, поэтом: одна фирма-разработчик не мокет гарантировать абсолю надежности, созданных ею программ. Более того, в настоящее в невозможно дать даже какую-либо оценку надежности по пру отсутствия способов определения таковой.

Сама по себе эта проблема не является новой. Первые мо надегжости программного обеспечения были созданы угсе в на семидесятых годов, и на сегодняшний день их имеется уке б 400. Однако все они либо не являются математически корректив либо включавт условия, которые не выполняются ни для одно' реально существующих прографи.

В этой ситуации весьма ва-.кной и актуальной оказывав проблема -создания ^""^оектного математического аппарата

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

Цель работы. Построение моделей надежности программного ¡еспечения и исследование связанных с ними случайных процессов.

Научная новизна. Все основные результаты диссертации ¡ляются новыми. ' .

1. Построены новые модели продеивания случайных множеств •ермин "просеивание" введен автором).

2. Подробно исследована одномерная модель просеивания (модель [учайных- интервалов), найдены ее основные характеристики, юведен'асимптотический анализ. "

3. Исследована модель просеивания случайных множеств в к2. Методы исследования. В работе используются различные методы

ории вероятностей, методы и терминология случайных множеств, имптотические методы. ¿^ ■

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

лись на научно-исследовательских семинарах механико-математи- -

ческого факультета и "фзкультета вычислительной математшси кибернетики.

Публикации. Основше результаты - диссертации опубликованы двух работах, список которых приведен - в конце автореферат Работа [I] является совместной статьей диссертанта А.Д.Соловьева. В данной статье А.Д.Соловьеву принадлек постановка задачи и идея основного результата.

Структура ^диссертации. Работа, состоит из введения, двух гла: разбитых на 8 параграфов, и списка литературы, содержащего наименований. Имеется два рисунка. Общий объем диссертации ' страниц.

Содержание работн,

I

Во введении дан краткий обзор изучаемой теш и соответств; зощей литературы, перечислены основше результаты работы, описш содержание диссертации по главам и параграфам. |

, Содержание главы I. На большом отрезке [0,Ш имеется попарно-непересекающихся интервалов 11,...,1 . Предполагаете что длины этих интервалов - 11,...,Х - являются независимы одинаково распределенными случаШшми величинам! •' с функци распределения ?(х) = РСХ, < х), а их сухарная длина - е много раз меньше длины отрезка.

Кроме того, тлеется последовательность независимых случайн величин ,£2,..Л, равномерно распределенных на отрезке [0,К

Изучаемым объектом является последовательность множеств (Ап (точнее некоторые связанные с ней случайные величины)-, „котор определяется следующим рекуррентным соотношением:

А0 = А V

I

• 2. А = А ,, если € ¿.А ,;

П П-1 * ^п ^ п-1

.3. А = А А I., если ^ € I, (I. с А , >.

п п-1 3 п 3 3 п-1

Иными словагж, случайные величины ...} соответствуют

:оследовательным бросаниям точки, производимым наугад в отрезок

О,К], согласно которым ' происходит динамическое изменение

нонества А. Бросания проводятся до тех пор, пока точка не

:опадет в один ..из интервалов » составляющих А, после

1 ' ч>

:его этот интервал удаляется из множества А, уменьшая тем самым го длину. Соответственна увеличивается длина дополнения А до О,К]. После этого бросания продолжаются, пока точка вновь не гападет.на один из оставшихся в А интервалов, и т.д. С течением ¡ремени множество А уменьшается, пока не становится пустым. Обозначим через Бк суммарную длину отрезков, составляющих

п

ножество А после (к-1)-го попадания (т.е. Б - т. X ; если 2 -

■ 1 1

эмер-интервала, на который произошло щрвое попадание, то 32 = - и т.д.). Поскольку Еелйчина Б., а следовательно и Б, , алы до сравнению с К, . го число - бросаний V от (к-1 )-го шадания до 'к-го , которое при фиксированном Бк имеет юметричёское распределение, мощю аппроксимировать показатель-ш распределением с параметром Бк/ N. Если нормировать теперь ь времени, рассмотрев величины = V / N. то окончательная одель выглядит так: интервал мекду (к-1 )-м и к-м попаданиями, , при условии, что фиксировано Б, , имеет показательное

АС

определение с параметром Б , т.е. .

Р(Ск £ « ■= Обозначим тк = £ +--.+ Ск-

Глава I посвщена изучению распределений величин тк, Ск и £ Глава. I состоит из 3 параграфов.

В 5 1.1 дано подробное описание модели и .введены основ!

случайные величины. ................ _„...:.

В § 1.2 найдены распределения случайных величин тк, и Основным результатом главы I является ■ Теорема 1.2.1. Совместное распределение случайных вели* г ,... ,т; совпадает с распределением вариационного ряд построенного по выборке объема п из распределения

го, г < о; •, .

ф( t) =

135

1 - J e_2CtdP(x), t > 0.

°

С помощью доказанной теоремы нетрудно найти распределен: величины Ск = хк - что и является содержат?

первого следствия из теоремы 1.2.1.

Следствие 1.2.2. Случайная величина Ск имеет следующее распре^

леые:

Р(Ск $ 2} =

тлггттг i^k"2(t)(1 - ®(t+z))n"k+1®' (t)dt.

~ штатшргтт J

о

Следующее следствие, используя метод теоремы I.2.1, дает фс

мулу для совместного распределения случайных величин s .....I

если существует плотность распределения Р(х)

СледстЕье 1.2.3. Если существует плотность распределен случайных величин X.....,Х - Г(х) = ?'(х), то случайный вект

1 п

S1,...,Sn также имеет плотность g(y1,...,У ), равную '

ш(y,-y2)(У2-У3)•••(yn_,-yn)í(ул-y2)•••r(yn)/ '}

8(у,.-.у») -—' g ¿ ;У1... y;

n-1

эсредоточенную на множестве о < yn < ... < у1 < а>.

В § 1.3 даны примеры применения теоремы I.2.I для исследова-ля различных характеристик модели.

В п.1 § 1.3 найдено распределение числа ошибок, обнаруженных э момента t - N(t). PÍN(t) = Ю = cj ®(t)k[1 - ®(t)]n_k. HN(t) = n®(t); DN(t) = пФ(г)[1 - ©(t)3.

В п.2 5 1.3 найдено ■'распределение времени момента t до Энаружения следущей ошибки - . .•

и

Так как общее число отказов ограничено и равно п, то величина . имеет несобственное распределение, дефект которого pd равен

= с»} = p{N(t) = п> = í»(tr. Поэтому найдено условное pac-je деление £ :

p(i+ > х ¡ N(t) < n) = [ФШ +1 -q>(win-<i>(t)n * 1 - ®(t)n

В п.З § 1.3 показано, что если (ггои n ->'со) к таково, что п -> А,, то величина т распределена ""асимптотически нормально

средним Ф~1 (А,) и дисперсией

- м

П[Ф' (Ф-1 (А,))]2

В п.4 § 1.3 исследован вопрос о принадлежности величины 1 юму из предельных типов. В частности, установлены следующие <ты:

1. Распределение величины тп при п -*■ « может принадлежать пь одному из двух типов:

№ (х) = е2р(-е~х) -со < х < +оо; Г о, X < О

^ I ехр(-х а), а >.0, х > 0.

2. Найдены необходимые и достаточные условия принадлежности

'•т ic типу'2'. Этот факт является содержанием леммы 1.3.1.

Лемма 1.3Л. Для того чтобы предельное распределение величина тп- Н_(х) - щдшадлежало второму типу, необходимо и достаточно» чтобы исходная функция распределения -?(х) • удовлетворяла следующему условию: .

F(x) = xa-L(x), при х -»■ 0, ■

где Ь(х) - некоторая медленно меняющаяся в нуле функция. : Основные результаты главы I опубликованы в [1]. Содержание главы II. Глава II посвящена исследованию некоторых проблем просеивания случайных множеств1 на плоскости.

Пусть Т есть система всех замкнутых, подмножеств кп. Рассмотрим множество , элементами которого являются шокества из 7, вида >

?к = (F € 7 / F П К = 0}, где К - некоторый компакт в Обозначим через g минимальную о-.алгебру, которая содержит все множества

Случайным замкнутым множеством (СЗ.М) называется случайный элемент 3 со значения?«! в [JF,^]. Это означает, что S есть (21,g) измеримое отображение пространства [П.Щ.Р] в

Примерами СЗ.М являются .случайные точки, шары со случайными радиусами, квадраты со случайными положениями и случайными длинами сторон.

Пусть в пространстве к11 задан точечный процесс Ф = = ix^,x2,...) и последовательность Е1,Ег,... одинаково распределенных СЗМ со свойством MV(En) < оз. Исходную случайную структуру Д0 мы определил как СЗМ следующего вида:

д0 = и (агп О Еп) = и в Е1) U (хг о Eg) U ... ' " хп е Ф ч

где знак © обозначает сложение по Минковско'му, т.е., если С -

= {с/с € т> = ш/а € к), то с © т> = (с+с£ /се е,а е V).

л

.Предположим также, что в полупространстве к к задан однородный пуассоновский процесс Ф интенсивности ц. Точечный процесс ¡Рг= {ул,уг,...}, г/к € к11, определив . как проекцию ® в к" [0,1;] на гиперплоскость к11 « (0>. Процесс £>, в дальнейшем будем называть просеивающим потоком.

Определение. Мы будем говорить, что случайной множество (или случайная структура) Д^. получается из исходной структуры Д0 в результате просеивания процессом ЧВ , если

А - АЛ { и и [(Е )/(Е

t О ,т, » п п п п' 11 . .

т.е. - совокупность тех СЗ,М из исходной структуры Д0, которые' не пересекаются с Ф .

Определение. Мы будем говорить, что Ф есть процесс просеянных ростков, если

* • *4 {„д £с7 (Е- •*»> ^ «}: ''

т.е. если ^ -.множество тех ростксв исходной структуры, которые остались к моменту 1; после просеивания , или, что то же самое, осли есть множество ростков процесса Л+ в момент времени X.

В работе исследован случай, когда Ф есть пуассоновский процесс интенсивности Я,, а Р(Еп с В(0,а)} ^ 1, где В(0,а) - шар центром в нуле радиуса а. Кроме того, все выводы сделаны для лучзя,_ когда хп <г к2!! Е ' с к2, однако это сделано лишь для ¡удобства изложения, а также чтобы избежать слишком громоздких выражений, и из контекста -ясно, что основные формулы (с зоответствующими поправками, конечно) справедливы для любой размерности размерности.

е

Объектами исследования является два связанных с At случай1: процесса:

1) A(t,R)= ~г Г Хд (x)dx « Y(S(0,R) П At), х = (x^xg),

R J t

S(0,R) ........ -............-".

где Хд - индикатор множества Д ; S(Q,H) - квадрат с центром начале координат и стороной длины R, а интеграл понимается в обычный интеграл Лебега по траекториям процесса At;

2) р- количество точек ирэцееоа ®t в борелевси множестве Л.

Глава II состоит из 5 параграфов.

3 §§ 1-3 проведено подробное описание модели и даны основв определения.

В § 4 проводится исследование процесса A(t,R).

*

Теорема 2.4.1. Математическое окидание A(t,R) равно: '

ИЛ(t,R) = 1 - Ифвхр^Шз J(1 - (z))dz],

Ê(O).

где X„ - индикатор множества равного 3. = о £ (Ê есть "t „ t t

множество центральносимметричное множеству Е, т.е., если Е ix}, то Ê - {-х}). Символ обозначает математическое отгадан

л ; •

по распределению СЗМ Е (усреднение по форме) при условии, ч множество Ф фиксировано, а М(Ъ математическое ожидание по ра пределению

Теорема 2.4.2. Дисперсия A(t,R) равна:

DA(t,R)= JJ [ïyT^

S(0,R)*2

1 ГГ Гм й-АИи(о(х.В)+а(у,11)-ф(Х,у,В))

R^

_ „ E),ç p-?lLxr{y.E)'

<Шу,

ч

1е .

а(и,Е)

[1 - ^ (в)]йа, Е(и)

ф(и,т,Е) = Г[1 - 5С, (2)]<1а.

л Л л

Е(и)П ЕМ *

¡к и ранее Х^, - хшдикатор множества 3^ равного Ф © Е,- Ё(и) = ё © и; символ '.1ц обозначает математическое ; ожидание по 1сцределению СЗМ Е (усреднение по форме) при условии, что кжество фиксировано, а математическое ожидание по расселению

Оценка дисперсии при. И «> содержится следствии I. Следствие 2.4.3. . При И со

Да _ ■ '

БЛ(г,Ю = ^ Г Гм _

и 1 «

о

Г

Обобщением теорем 2.4.1 и 2.4.2 является

Теорема 2.4.4. .Для ш-го-момента величины справедлива

[едущая формула:

ю (-1)кСк

1 П» V-1 ) и Г . г

'(г.Ю ]мфежр[-ЛМЕф1(х1,Е)-...-Х^ф1(х1,,Е) + ...+

Б(0,Е)х:к

(-1 )к НЕфк(х1,----х. !Е)1с121...сЬск,

-ю

ф2(х =' J [1 - Xz^yfzfldz

EU.) Л...Л E(s.)

31 -......; 3l_;____________ ___

Все остальные обозначения тагате же как-и в-теореме-2.4.2.

Следствие 2.4.5 Формула для преобразования Лапласа величин

A(t.R). " "*

S ..у---..-

v2 V1 jre-Aft,B)z _ Иезф£_?<м| j} (1_ eÊ(u-q))[l- П 0- e^Oj-^.z))]^

с 1-1 1-1 '

1

Здесь v1 и vz пуассонозские случайные величины, с параметра'.® z и |aiv(c )- соответственно; (f^) - случайные величины, равномерн распределенкке в Сг , а {17 } - случайте величины, /раЕномерн распределенные б S(0,R). Величины {г)±}, i>2, {£±) не зависти в совокупности. Через e^iu) обозначен индикатор СЗМ Ê. Матема тическое окндаше внутри скобок берется по распределению Ê, математическое. ожидание перед экспонентой (в правой части выражения) - по распределению Ф .

Следующая теорема описывает асимптотиче ское распределени A(t,R) при R <х).

Теорема 2.4.6. При R «

A(t.R) - MA(t.R) •/ DA(t,R)

2

1 Г - 5 —— s 2 di.

«iiTJ

-со

Выракения для ИЛ(г,Н) и 1)Л(1:,Н) найдены в теоремах 2.4.1 2.4.2 соответственно.

В 5 2.5 проводится исследование процесса р(1;,Л)Основны результатом 5того параграфа является

Теорема '2.5.1. Производящая функция случайной величин р(1;,Л) имеет следующий вид:

•л "

11

'.=>|^ез£р£м1-£)(Ьу5 4 (и)йи - лУ(УОУ].

~, Л' °

Как и ранее X, - индикатор множества Б., равного 2). ф Е; символ

"г ъ г

М£ обозначает математическое ожидание ио распределению СЗМ Е

(усреднение по форме) при.условии, что множество Ф. фиксировано,

а Мф математическое ожидание по распределению Ф .

Основные результаты главы II опубликованы в 12).

Автор ;выражает глубокую благодарность своему научному

руководителю, профессору Л.Д.Соловьеву за постоянное внимание к

работе.

Работы автора по теме диссертации.

I. Гальцов М.В., Соловьев А.Д. Одна простейшая модель тестирования слоп-шх программ. // Вестник Московского Университета. Сер Л. 'Математика. Механика. 1991. N5.

?■. Гальцов М.В. Задача о просеивании случайных шюжеств на плоскости. // Вестник Московского Университета. Сер Л. Математика. Механика. 1992. N2.