4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
Строка 9: | Строка 9: | ||
== Нотация == | == Нотация == | ||
Термины «почти наверняка» и «с высокой вероятностью» будут использоваться в их обычном значении при описании свойств случайных графов. Свойство, определенное для случайного графа, выполняется «почти наверняка», если его вероятность стремится к 1 по мере того, как значение независимой переменной (обычно такой переменной является число вершин графа) стремится к бесконечности. Выражение «с высокой вероятностью» означает, что вероятность выполнения свойства случайного графа (или вероятность успешного завершения рандомизированного алгоритма) равна по меньшей мере 1 | Термины «почти наверняка» и «с высокой вероятностью» будут использоваться в их обычном значении при описании свойств случайных графов. Свойство, определенное для случайного графа, выполняется «почти наверняка», если его вероятность стремится к 1 по мере того, как значение независимой переменной (обычно такой переменной является число вершин графа) стремится к бесконечности. Выражение «с высокой вероятностью» означает, что вероятность выполнения свойства случайного графа (или вероятность успешного завершения рандомизированного алгоритма) равна по меньшей мере <math>1 - \; n^{- \alpha\ }</math>, где <math>\alpha\ > 0</math> – константа, а n – число вершин графа. | ||
В [ ] приводится великолепное изложение вероятностного метода и вариантов его применения, [2] является классическим учебником по случайным графам, а [6] представляет собой превосходное пособие по конструированию и анализу рандомизированных алгоритмов. | В [1] приводится великолепное изложение вероятностного метода и вариантов его применения, [2] является классическим учебником по случайным графам, а [6] представляет собой превосходное пособие по конструированию и анализу рандомизированных алгоритмов. | ||
== Основные результаты == | == Основные результаты == |
правка