О вероятностях значений случайных булевых выражений

• Автор: Яшунский, Алексей Дмитриевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 108 с.

Глава 1 Нахождение функции вероятности
1.1 Основные понятия и определения
1.2 Элементарные примеры
1.3 Языки и производящие функции
1.4 Функция вероятносги на интервале (0,1)
1.5 Функция вероятности в граничных точках
1.6 Связь с другими вероятностными пространствами
1.7 Функции вероятности базисов первого порядка
Глава 2 Некоторые свойства функций вероятности
2.1 Примеры функций вероятности
2 2 Непрерывность функции вероятности на интервале (0,1)
2.3 Непрерывность функции вероятносги в граничных точках
2.4 Задача восстановления вероятности
Глава 3 Постоянство функции вероятности
3.1 Векторное пространство многочленов
3 2 Постоянство функции вероятности однородных базисов
3 3 Постоянство функции вероятности неоднородных базисов
Глава 4 Приближение непрерывных функций функциями вероятности
4.1 Равномерное приближение многочленов
4 2 Равномерное приближение непрерывных функций
4 3 Преобразование аппроксимирующих базисов
Глава 5 Функции вероятности формул
5.1 Постановка задачи
5.2 Некоторые примеры
5.3 Всюду плотные множества значений
Литература

Современное понимание термина „вычисление” столь широко, чгю давать определение этого понятия представляется довольно затруднительным. Неформально можно говорить, что вычислением называется процесс преобразования исходных данных (чагце всего числовых или текстовых), согласно некоторой процедуре (алгоритму) Формализация понятия „вычисление” приводит к математическим моделям, таким как машины Тьюринга, конечные автоматы, логические схемы, и многие другие.
Эти модели, как правило, являются детерминированными, но могут быть модифицированы таким образом, что выполняемые ими действия приобретут случайный характер: элементы случайности могут быть внесены в исходные данные вычисления или же в саму процедуру. Результатом таких модификаций будет некоторая модель случайных вычислений.
Изученные к настоящему времени модели случайных вычислений можно условно разделить на две группы: к первой относятся модели, в которых случайность является „неотъемлемой” частью — в силу природы моделируемого обьекта, или же потому, что сама случайность является обьекюм изучения. Ко второй группе относятся модели, в которых случайность является „привнесённой извне”. При этом случайность может быть как инструментом построения более удобной вычислительной модели, так и инструментом изучения модели Такая классификация моделей, как уже отмечалось, достаточно условна, так как не всегда легко различить „врождённые” и „привнесенные” элементы случайности в вычислительной модели.
Приведём краткий обзор основных направлений исследований в области случайных вычислений. Хотя, строго говоря, большинство упомянутых в нём задач связаны с темой данной работы лишь косвенным образом, знакомство с ними позволяет лучше понять место и значение данной работы в общей картине исследований в области случайных вычислений. Сначала перечислим некоторые работы, рассматривающие модели, которые можно отнести к первой группе.
Одними из первых вычислительные системы с элементами случайности рассмотрели Дж. фон Нейман (J. von Neumann) [36], а также Е Мур (E. Moore) и К. Шеннон (C. Shannon) [35]. Эти работы посвящены построению надёжных вычислительных схем из ненадёжных элементов. Случайность в таких системах возникает из-за возможных неисправностей некоторых элементов схемы, т. е. у каждого элемента схемы существует ненуле-

вая вероятность сбоя. В указанных работах предложены методы построения схем высокой надёжности из элементов с ненулевой (но достаточно малой) вероятностью сбоя. Схемы из ненадёжных элементов рассматривались также С Г. Гиндикиным и А. А. Мучником: в [3] они исследовали проблему полноты базисов из ненадёжных элементов. Этой задачей занимались и многие другие авторы (см. обзор в [19]).
Другим примером вычислительных систем с элементами случайное!и могут служить вероятностные автоматы, т. е. авюматы, у которых переходам между состояниями и выходным значениям приписаны некоторые вероятности. Понятие вероятностного автомата было сформулировано в середине 60-х годов прошлого века, и с тех пор была построена достаточно обширная теория вероятностных автоматов, обзор результатов и проблем которой можно найти в книге Р. Г. Бухараева [2]. Одним из интересных результатов теории вероятностных автоматов является утверждение о возможности представления любого вероятностного автомата в виде последовательного соединения „источника вероятности”, порождающего случайным и независимым образом символы некоторого алфавита с заданными вероятностями, и детерминированного конечного автомата. Ввиду наличия подобного представления, особый интерес приобретает задача о синтезе такого „источника вероятности”.
Впервые задача порождения значений вероятности с помощью булевых преобразователей была, по-видимому, рассмотрена P. JI. Схиртладзе [14]. В его работе предложен метод получения всех двоично-рациональных значений вероятности путём комбинирования бернуллиевских случайных величин, имеющих вероятность обращения в 1 равную 1/2, с помощью контактных схем. В дальнейшем вопросы порождения значений вероятности также исследовались Ф И. Салимовым [11].
Наиболее широкое развитие эта проблематика получила в работах Р. М. Колпакова, который рассматривал различные постановки задачи порождения значений вероятности. В его работах (в частности, [9]) получены критерии, позволяющие по искомому значению и заданным исходным значениям вероятности определить, порождается ли искомое значение булевой комбинацией бернуллиевских случайных величин с вероятностями из заданного множества
В работе А. Бродского (A. Brodsky) и Н. Пипиенджера (N. Pippenger) [25] рассматривается модель случайного порождения булевых функций. Функции порождаются с помощью формул, состоящих из символов некоторой функции-связки и литералов из некоторого конечного множества. Для каждого п > 0 на множестве формул сложности п задаётся распределение вероятности, причём для тг — 0 оно произвольное, а для следующих значений п

бесгювторной формулы заданной сложности и случайной независимой подстановки констант 0 и 1 вместо её переменных. Все бесповторные формулы заданной сложности при этом подразумеваются равновероятными. Такое требование, на первый взгляд, делает распределение вероятности достаточно специфическим, однако, как будет показано далее, в действительности, оно позволяет смоделировать другие распределения вероятности на множестве формул.
Пусть однородный базис В представляет из себя мультимножество булевых функций /1 /т с кратностями вхождения, соответственно, к ктп. Покажем, что в определённом ранее вероятностном пространстве булевых выражений (при любом п) имеет место равенство Р{Ф начинается с символа /,} = кг/В.
Рассмотрим множество всех формул сложности п и разобьём его на подмножества формул такие, чтобы внутри каждого подмножества формулы различались лишь начальным символом. Очевидно, чю в каждом подмножестве будет В формул, из которых ровно кг начинаются с символа /г, и таких подмножеств будет ровно 5„/|5|. Как отмечалось ранее, вероятность множества выражений, порождённых одной и той же формулой, равна 1/.5п. Следовательно, вероятность множества выражений начинающихся с /г, порождённых формулами из некоторого заданного подмножества, равна кг/зп. Суммируя вероятности по всем подмножествам, на которые было разбито множество формул, получаем, что вероятность того, что выражение начинается с символа /, равна (кг/зп) • (б’п/|£?|) = кг/В, что и требовалось доказать. Аналогично показывается, что для данного базиса вероятность появления символа /, на любом наперёд заданном месте в выражении равна кг/В.
Таким образом, в случае однородных базисов предложенное ранее распределение вероятности позволяет моделировать неравномерные распределения вероятности на множестве выражений, с любыми наперед заданными рациональными вероятностями появления функциональных символов в выражении.
Перейдём к рассмотрению вероятностных пространств булевых выражений при других определениях сложности выражения. Кроме уже разобранного случая определения сложности как количества символов функций базиса в выражении, возможно также определение сложности как количества символов констант, и как суммарного количества символов констант и функций.
Рассмотрим случай, когда сложность определяется как количество символов конс1ант в выражении. Пусть базис В содержит функции одной переменной, например отрицание -|(ж). Допустим сначала, чгю в выражениях