WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |

«Излагаются некоторые результаты по теории сложности схемных и тьюринговых алгоритмов, полученные А. Е. Андреевым, Нгуен Ким Ань и Т. М. Игамбердыевым. Введение Алгоритмы ...»

-- [ Страница 6 ] --

Общеизвестные понятия, не определяемые здесь, можно найти в [116]. Через lC, lT, lQ, lkp, lkp, lko и lA обозначим число элементарных конъюнкций соответственно в д. н. ф.: сокращенной, объединение и пересечение тупиковых, Квайна, кратчайшей, кратчайшей из корректирующих s отбрасываний элементарных конъюнкций, получающихся в результате применения к сокращенной д. н. ф. кольцевого алгоритма ранга 2 и A-алгоритма; а через l min число букв в минимальной д. н. ф. Пусть протяженность, Y разброс, число тупиковых д. н. ф. Через lC обозначим число интервалов размерности k в сокращенной д. н. ф. Пусть P n множество всех булевых функций, определенных на {0, 1}n ; P n соответствующее множество чаВ. Б. Кудрявцев, А. Е. Андреев стичных булевых функций; P,m множество всех булевых функций n, принимающих значение на m наборах; P n частичных булевых функций, определенных на m наборах из {0, 1} n ;

множество всех частичных (n, t)-операторов, определенных на m наборах из {0, 1}n ; Pm1,m2 множество всех частичных булевых функций из Pm1 +m2, принимающих значение 1 на m2 наборах.

Во всех рассматриваемых далее асимптотических отношениях предполагается, что n ; это же относится к термину для почти всех.

Теорема 4.7 ([115]). Для почти всех булевых функций а из P 0,m имеет место если 1 = o(m), m Асимптотика получена также для классов Pm1,m2 при всех возможных соотношениях между n, m1 и m2. Ранее была известна лишь асимптотика логарифма lC [117].

Теорема 4.8 ([115]). Для почти всех булевых функций f из P 0,m верно:

если n log m = o(n), 2n = O(2n m);

При m 2n1 отсюда следует результат А. А. Сапоженко [118].

Теорема 4.9 ([115]). Для почти всех булевых функций f из P m1,m верно, что В ряде случаев можно получить явную асимптотику, например, для почти всех булевых функций из P n, если s, а n специального вида. При m1 m2 2n1, s log log n из этой теоремы вытекает результат Н. Н. Кузюрина [119].

Теорема 4.10 ([115]). Для почти всех операторов F из P m выполнено:

Рассмотрим задачу минимизации д. н. ф. с помощью машины Тьюринга. При работе с булевыми функциями из P n элементарные конъюнкции кодируются стандартным образом наборами длины n, код д. н. ф. составляется из кодов ее элементарных конъюнкций, код булевой функции из кодов совершенной д. н. ф. и совершенной д. н. ф. ее отрицания. Пусть T (f ) время работы машины T на коде булевой функций f.

Положим Теорема 4.11 ([115]). Можно указать машины T min и Tkp, вычисляющие по коду булевой функции f код ее минимальной и, соответственно, кратчайшей д. н. ф., и константу c такие, что:

Сравнение полученных оценок с оценками для числа тупиковых д. н. ф. (см. [116]) показывает, что последнее, как правило, растет существенно быстрее. Следовательно, алгоритмы, включающие перебор тупиковых д. н. ф., нельзя рассматривать в качестве универсального метода минимизации. Из этих оценок также легко извлекается ряд случаев полиномиальности задачи минимизации, например, при условии, что m1 + m2 = O(log n). Однако в этих же условиях рост числа тупиковых д. н. ф. не является полиномиальным.

Как обычно, задачи A и B назовем полиномиально эквивалентными, если для любой машины TA, решающей задачу A, найдется машина TB, решающая задачу B, и константа c такие, что T B (n) 2cn TA (n), и наоборот.

Теорема 4.12 ([115]). Следующие задачи полиномиально эквивалентны:

1) по частичной булевой функции f найти некоторую ее минимальную д. н. ф.;

2) по частичной булевой функции f найти некоторую элементарную конъюнкцию, входящую в д. н. ф. сумма минимальных ;

3) по частичной булевой функции f и ее элементарной конъюнкции K вычислить значение предиката элементарная конъюнкция принадлежит д. н. ф. сумма минимальных ;

4) по частичной булевой функции f найти длину ее минимальной Эта теорема объясняет обнаруженное Ю. И. Журавлевым [116] отсутствие локального критерия распознавания предиката вхождение в сумму минимальных. Поскольку указанное распознавание по сложности фактически совпадает с решением задачи минимизации, применение локальных алгоритмов, базирующихся на этом предикате, в общем случае либо почти не понижает сложности перебора, либо сводится к нему же. Следующее утверждение достаточно хорошо иллюстрирует эту закономерность.

Теорема 4.13 ([115]).

а) Для почти всех булевых функций f из P n имеет место:

в) Если m 2n, [1/2, 1) то для почти всех булевых функций f из P0,m имеет место:

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

Ранее полученные результаты [116] следуют из п. а) Теоремы 4.13.

Отметим, что при m 2n, [1/2, 2/3], мы получаем из P0,m примеn ры массивных классов плотных булевых функций, причем существенно более простые, чем у Ю. Л. Васильева [120, 121]. Для этих классов простейшие локальные алгоритмы имеют почти всегда нулевой эффект, а анализ не более чем 2n частичных функций из кольца ранга 2 приводит к построению минимальной д. н. ф. Однако реализация кольцевого алгоритма требует анализа существенно большего числа частичных булевых функций. Следовательно, в этом случае трудоемкость кольцевого алгоритма неприемлема. В то же время алгоритм наискорейшего спуска является для этих классов асимптотически оптимальным по порядку.

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

Пусть LB сложность реализации схемами из функциональных элементов в базисе B, а (B) минимальный приведенный вес элементов этого базиса.

Теорема 4.14 ([115]). Для почти всех булевых функций f из P m выполнено:

если log n m Отметим, что при m = O(log n) задача вырождается, так как в этом случае сложность соответствующих схем ограничена константой. В совокупности с результатами Л. А. Шоломова [122] эта теорема дает окончательное решение задачи о зависимости сложности булевой функции от величины области определения. В рассматриваемом нами случае наблюдается лишь незначительное отличие схем от д. н. ф., однако оно есть.

Теорема 4.15 ([115]). Для почти всех булевых функций f из P m выполнено для некоторой константы 1 C(m, n) 2, если log n m Константа может быть вычислена эффективно.

Пусть (g) хроматическое число графа g.

Теорема 4.16 ([115]). Для почти всех графов g с n вершинами и m ребрами верно:

При 1 из этой теоремы следует результат А. Д. Коршунова [123].

Пусть L сложность реализации контактными схемами, не имеющими цепей с нулевой проводимостью.

Теорема 4.17 ([115]). Для почти всех булевых функций f из P n имеет место:

Эта оценка совпадает по порядку с полученной С. Е. Кузнецовым [124] нижней оценкой.

5. Булевые уравнения Многие задачи теории управляющих систем, дискретной оптимизации, распознавания образов, технической диагностики и др. [53, 63] естественно сводятся к решению систем булевых уравнений. При этом требуется найти или все решения системы, или часть их со специальными свойствами, или хотя бы одно решение. Как правило, уравнения в возникающих системах имеют достаточно регулярную структуру.

Чаще всего они имеют вид D = 1, где D дизъюнктивная нормальная форма (д. н. ф.) Так, например, задача построения тупиковых тестов приводит к исследованию систем булевых уравнений вида Проверка разрешимости системы булевых уравнений является одной из N P -полных проблем, причем N P -полнота сохраняется даже в случае, если каждое уравнение является дизъюнкцией трех членов, каждый из которых есть переменная или отрицание переменной.

Поэтому разработка методов решения, исследование систем булевых уравнений представляет интерес не только в связи с конкретными приложениями, но и для изучения N P -полных проблем.

В работах [64]–[67] исследовались вопросы классификации систем булевых уравнений, существования и единственности их решений, представления решений в параметрическом виде. Однако весьма актуальной остается задача разработки эффективных алгоритмов решения систем булевых уравнений.

Как и многие другие дискретные проблемы, задача нахождения решений булевых уравнений может быть решена тривиальной проверкой всех комбинаций значений переменных, однако это требует большого перебора. Все существующие универсальные методы решения систем булевых уравнений [57, 63, 68]–[78] не позволяют элиминировать этот перебор. Причем остается открытым вопрос о принципиальной возможности такой элиминации.

Для обхода этих трудностей существует два традиционных пути. Первый из них заключается в разработке алгоритмов, ориентированных на достаточно узкие классы систем. Это направление активно развивается разными авторами [61, 63, 79]–[84]. Второй путь элиминации перебора состоит в построении алгоритмов малой трудоемкости, находящих приближенное решение задачи. Возможности алгоритмов второго типа применительно к задаче решения систем булевых уравнений остались мало исследованными. Разработке этого подхода посвящены исследования Т. А. Игамбердыева, которые излагаются здесь.

Представляется также актуальным оценить, насколько эффективен каждый конкретный алгоритм. Такие попытки предпринимались, например в [85].

Очевидно, что естественной нижней оценкой сложности любого алгоритма может служить число решений. Такой подход был применен, например, в работах [86]–[89] при решении задачи поиска всех тупиковых тестов, где были разработаны алгоритмы, имеющие сложО сложности алгоритмов ность, асимптотически равную числу тупиковых тестов для почти всех таблиц.

С точки зрения такого подхода применительно к рассматриваемой задаче целесообразно вести работу в направлении поиска асимптотически оптимальных алгоритмов, число шагов которых эквивалентных числу решений системы булевых уравнений.

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

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

В работах [90, 91] исследовался вопрос о типичном значении числа решений таких систем булевых уравнений, где каждому уравнению соответствует случайная булева функция, без учета того, в каком виде она задана.

Целью исследований Т. И. Игамбердыева является исследование систем булевых уравнений заданных в конкретных базисах, получение для них точных и асимптотических оценок числа решений и построение на основе этих оценок приближенных алгоритмов решения систем булевых уравнений.

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

Рассматривается класс систем булевых уравнений, заданных в виде суммы по модулю 2 элементарных конъюнкций. Получена точная формула для среднего числа решений систем из заданного класса и асимптотическая оценка числа решений для почти всех систем с заданным ростом параметров.

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

Описываются конкретные алгоритмы аппроксимации булевых функций и их применение при решении систем булевых уравнений.

Определим ряд понятий, необходимых для изложения основных результатов.

некоторое множество. Через |M | обозначим число его элементов, называемое мощностью множества M.



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |
 


Похожие работы:

«Сканировал и создал книгу - vmakhankov БЕСПОЩАДНАЯ ТОЛЕРАНТНОСТЬ КИРИЛЛ БЕНЕДИКТОВ ВЛАДИМИР БЕРЕЗИН ЮРИЙ БУРНОСОВ ДМИТРИЙ ВОЛОДИХИН ЕВГЕНИЙ ГАРКУШЕВ ОЛЕГ ДИВОВ ЛЕО КАГАНОВ ТИМ СКОРЕНКО СЕРГЕЙ ЧЕКМАЕВ И ДРУГИЕ БЕСПОЩАДНАЯ ТОЛЕРАНТНОСТЬ 5 ЭКСМО МОСКВА УДК 82-312.9 ББК 84(2Рос-Рус)6-4 Б 53 Составитель сборника С. Чекмаев Оформление серии Е. Савченко Серия основана в 2003 году Иллюстрация на переплете А. Дубовика Беспощадная толерантность: Сборник социальных анти­ Б 53 утопий / сост. С. Чекмаев. —...»

«Книга Путешествий Часть 1 2011 год 1 Автор 2010 год 2 Моей любимой жене и неизменному редактору Наташе и сыновьям Ильюше и ещё раз Ильюше 3 Содержание первой части Предисловие Несколько слов о нашем поколении Часть 1. Широка страна моя родная Глава 1. Техникум. Опыт первых путешествий Глава 2. На шлюпках по Днепру из Киева в Канев (август 1963 года) Глава 3. Путешествия Автостопом Путешествие первое: Крым – Кавказ – Волга (август 1965 года) Путешествие второе: Кавказкие Горы – Крым (август 1967...»

«АФАНАСЬЕВ Николай Иванович ФРОНТ БЕЗ ТЫЛА Л.: Лениздат, 1983. Аннотация издательства: Автор книги — один из участников партизанского движения под Ленинградом, прошедший путь от командира батальона 6-го истребительного партизанского полка, сформированного в Ленинграде в июле 1941 года, до заместителя начальника Волховской опергруппы Ленинградского штаба партизанского движения. Богатый боевой опыт, хорошее знание обстановки в тылу врага, накопленный обширный фактический материал позволили автору...»

«Перед Вами каталог учебной литературы Издательского центра Академия на 2012 год, в котором содержится более 1 200 наименований учебников, учебных и методических пособий для среднего и начального профессионального образования, для профессиональной подготовки рабочих и служащих, а также изданий для широкого круга читателей. Каталог представляет собой аннотированный список литературы, распределенный по отраслям знаний и по уровням образования. Структура каталога ориентирована на новый...»

«Факты и мнения (Статьи и другие материалы, опубликованные в русскоязычной прессе США) Издание второе, дополненное Компьютерное обеспечение: Леонид Рыклянский. Корректировка: Лоренс Кулинский, Элла Кулинская, Леонид Рыклянский. Первое издание книги “Факты и мнения” на русском языке было опубликовано в 2004 году США – Калифорния – 2009 год Незабвенной и светлой памяти замечательной жены, друга, советчицы при написании многих моих публикаций и первой их читательницы Муси Рыклянской посвящаю эту...»

«Аннотация Третья стража – своего рода магический спецназ, цель которого – охранять город от возможных потусторонних опасностей. И вновь на бой с нечистью выходят Темные и Светлые маги. Содержание Глава 1 7 Глава 2 28 Глава 3 49 Глава 4 69 Глава 5 91 Глава 6 109 Глава 7 129 Глава 8 149 Глава 9 168 Глава 10 188 Глава 11 208 Глава 12 232 Глава 13 252 Глава 14 272 Глава 15 292 Глава 16 311 Глава 17 331 Глава 18 351 Глава 19 371 Глава 20 390 Глава 21 410 Глава 22 429 Глава 23 449 Глава 24 467 Глава...»

«В ПОИСКАХ АДРЕСАТА Санкт-Петербург – Foster City 2012 (Ред. от 18.02.2011 – 6.02.2012) А. Алексеев Б. Докторов В поисках Адресата ПЕРЕПИСКА ДВОИХ С ПОСТЕПЕННЫМ РАСШИРЕНИЕМ КРУГА ТЕМ И УЧАСТНИКОВ (февраль – октябрь 2006 г. ) Посвящается Алле Родионовой – молчаливому и заинтересованному со-участнику и почтальону этой переписки. 2 Содержание Вместо предисловия (1) А. Алексеев. От составителя - сегодня (2) А. Алексеев – Б. Докторову (3) Апология письма (из переписки с Р. Г. Баранцевым) (4) А....»

«ПЕРВОЕ ПРЕЖДЕ ВСЕГО УДК 159.9+17+316.6 ББК 88 К56 Перевод с английского Н. Гринева по изданию: FIRST THINGS FIRST by Stephen R. Covey.— N. Y.: Fireside, 1995. Охраняется законом об авторском праве. Нарушение ограничений, накладываемых им на воспроизведение всей этой книги или любой ее части, включая оформление, преследуется в судебном порядке. КовиС.Р. К56 Первое Прежде Всего /Пер. с англ. Н. Гринева; фирма Колибри, 2003.—284с.:ил. ISBN 966-9491-26-1. Человека, научившегося быстро решать...»

«Альманах КАДЕТСКИЙ ВЕСТНИК РОССИИ Январь — август 2008 года Выпуск №4 ПЕРИОДИЧЕСКОЕ ИЗДАНИЕ ОБЩЕРОССИЙСКОГО СОЮЗА КАДЕТСКИХ ОБЪЕДИНЕНИЙ ОТКРЫТОЕ СОДРУЖЕСТВО СУВОРОВЦЕВ, НАХИМОВЦЕВ И КАДЕТ РОССИИ Москва 2008 2 Вступительное слово Председателя Общероссийского союза кадетских объединений Открытое Содружество суворовцев, нахимовцев и кадет России генерал майора Александра Владимирова Уважаемые братья кадеты! Четвертый выпуск альманаха Кадетский вестник России является первым выпуском альманаха в...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.