WWW.KNIGI.KONFLIB.RU

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

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

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 8 |

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

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

Формализуем изложенное. Введем основные понятия и обознанекоторые множество. |A| чения, используемые далее. Пусть A его мощность, 2A множество всех его подмножеств и A n декартово произведение A... A. Если |A| = n, то A называем n-мноn раз жеством. Используем символ n для множества {1,..., n}, (n 1) и символ E = (1,..., n ), где i E2 для любого i n. При фиксированном n положим = (1,..., 1) и = (0,..., 0). Для точки из E2 обозначим через I (соответственно, I ) множество всех номеров i из n, таких, что i = 1 (соответственно i = 0). Нормой точки (обозначается | называется мощность множества I. Пусть, две точки из E2. Будем говорить, что не превосходит (обозначение не выполняется ни, ни.

Граф с множеством вершин V и множеством ребер U обозначается через = (V, U ).

Если V E2, то под V -графом будем понимать граф = (V, U ), где U состоит из всех пар вершин, из V, таких, что, отличаютn ся друг от друга ровно в одной координате. В частности, E 2 -графом является единичный n-мерный куб.

Через P2 обозначим множество всех булевых функций, то есть таких функций, у которых переменные и сами функции принимают значения из E2, а через P2 (n) множество всех булевых функций, зависящих от n переменных {x1,..., xn }. Элементарной конъюнкцией ранга r называется логическое произведение x 11... xrr, где xi = xi, если i = 1, и xi = xi, если i = 0, а все xij различны. Д. н. ф. есть логическая сумма D = K1... Km различных элементарных конъюнкций Kj. Для д. н. ф. D обозначим через M (D) множество всех ее элементарных конъюнкций. Если булева функция представляется в виде д. н. ф., то говорят, что последняя реализует данную функцию. К. д. н. ф. (соответственно м. д. н. ф) для функции f (x 1,..., xn ) являются те д. н. ф., которые реализуют f (x 1,..., xn ) и содержат наименьшее число элементарных конъюнкций (соответственно, наименьшее число вхождений символов переменных) по сравнению с другими реализующими f (x1,..., xn ) д. н. ф. Каждой булевой функции f (x1,..., xn ) сопоставим в соответствие подмножество N f множества E2 все точек таких, что f ( = 1. Для элементарной конъюнкции K r-го ранга множество NK E2 (n r) называется интервалом r-го ранга, а NK граф (n r)-мерной гранью единичного n-мерного куба. Элементарная конъюнкция K называется простой, а соответствующий интервал максимальным для функции f (x 1,..., xn ), если имеет место NK Nf и не существует конъюнкции K, такой, что NK NK Nf. Дизъюнкция всех простых конъюнкций функции f (x1,..., xn ) называется с. д. н. ф. для данной функции и обозначается через DC (f ). Любая дизъюнкция D простых конъюнкций функции f называется т. д. н. ф., если D реализует f и не существует другой реализующей f дизъюнкции D, такой, что M (D ) M (D).

Логическую сумму всех т. д. н. ф. функции обозначаем через D T (f ), а логическую сумму всех простых конъюнкций функции f, каждая из которых входит во все т. д. н. ф. через D T (f ). Множество M (DT (f )) называется множеством ядровых конъюнкций, а множество M (DC (f )) \ M (DT (f )) множеством неядровых конъюнкций функции f. Две функции f (x1,..., xn ) и g(x1,..., xn ) считаются равными, если Nf = Ng, а две д. н. ф. D1, D2 конъюнктивно равными (обозначаем D1 = D2 ), если M (D1 ) = M (D2 ).

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

Пусть C = (X1,..., Xs ) некоторое семейство подмножеств множества X и пусть Y X. Будем говорить, что Y покрывает семейство C (или Y является покрытием для C), если для любого X i из C имеет место Xi Y =. Покрытие Y называется приведенным для C, если любое его собственное подмножество не является покрытием для C. Множество всех приведенных покрытий для C обозначается через P(C).

Изучается алгоритм минимизации булевых функций, в основе которого лежит процедура сравнения на поглощаемость одного набора конъюнкций другими [40, 48]. Предполагается, что булева функция задается с помощью с. д. н. ф. Тогда этот алгоритм состоит в последовательном получении наследственных д. н. ф., реализующих заданную функцию и получающихся друг из друга с помощью удаления дизъюнктивных членов. Эта процедура удобно представляется в виде так называемого графа перебора, вершинами которого является д. н. ф., состоящие из простых конъюнкций и реализующие заданную функцию, а ребрами пары указанных д. н. ф., отличающихся друг от друга ровно одним дизъюнктивным членом.

Назовем поликубом любой П(l, k) граф, где П(l, k) состоит из некоторых k попарно несравнимых точек 1,..., k из E2 удовлетвоl ряющих условию | I 0 i | = l, и из всех точек из E l таких, что имеет место для некоторых I из k. Число l называется размерностью поликуба, а число k числом подкубов поликуба. Установлено, что если булева функция имеет l неядровых конъюнкций и k т. д. н. ф., то ее граф перебора изоморфен некоторому поликубу П(l, k). Наоборот, показывается, что для любого поликуба размерности l, существует булева функция от l + 2 переменных, граф перебора для которой изоморфен данному поликубу.

Обозначим через {1,..., k } k попарно-несравнимых точек из E2, которые определяют поликуб П(l, k). Положим J (П(l, k)) = {I1,..., Ik }. Пусть : l M некоторое отображение множества l в множество конъюнкций M, = {i1,..., is }, (s l) произвольное подмножество множества l. Положим & () = (i1 )&... &(is ), () = (i1 )... (is ). Множество всех булевых функций с графом перебора, изоморфным поликубу П(l, k), обозначается через F(П(l, k)). Справедливо утверждение.

Теорема 4.1. Булева функция f содержится в F(П(l, k)) тогда и только тогда, когда выполняются следующие условия:

конъюнкций функции f ;

2) Существует взаимно однозначное отображение f : l M (DT (f )), такое, что для из P(F(П(l, k))) справедливо соотношение:

причем для всех других множеств ( l ), не являющихся покрытием для F(П(l, k)), это соотношение не выполняется.

Пусть l, l,k и s соответственно есть множество всех подкубов размерности l, всех поликубов размерности l с k подкубами и всех поликубов размерности l с s подкубами максимальной размерности.

Пусть n(П) наименьшее число переменных у всех таких функций, граф перебора для которых изоморфен поликубу П. Положим n(l) = max n(П); n(l) = min n(П); n(l, k) = max n(П); ns (l) = max n(П).

Показывается, что для любого l 1 имеет место n(l) = l + 2, что n(l) имеет порядок log 3 l, и что l + 1 l + 2 при всех l, s, удовлетворяющих соотношениям l 1, 1 s C l 2.

Теорема 4.2. Справедливы следующие оценки:

Как вытекает из этой теоремы, величина n(l, k) не более чем на 2 отличается от l при k l, и есть o(l) при k, достаточно малых по сравнению с l.

Обозначим через s множество всех поликубов из l,k, каждый вие 1 s k Cl 2 является необходимым для непустоты s.

Очевидно, что существует тройка (l, k, s), удовлетворяющая необходимому условию, но не являющаяся набором соответствующих параметров некоторого поликуба. Однако, как показывает следующая теорема, число таких исключительных случаев сравнительно мало при росте l.

Фиксируем l, s, где 1 s Cl 2, и обозначим через K(l, s) максиl] мальную разность k s по всем числам k таким, что s k C l 2 и Теорема 4.3. l () равномерно сходится к 1 при l, стремящемся к бесконечности.

На языке булевых функций непустота s означает, что существует функция, которая имеет l неядровых конъюнкций и k т. д. н. ф., среди которых ровно s к. д. н. ф. При оценке функции n s (l, k), где ns (l, k) = max n(П), также выяснено, что при всех k, больших некоl,k торой величины (l, s), имеет место l + 1 ns (l, k) l + 2.

Изучаются некоторые метрические свойства графа перебора такие, как высота, ширина, объем.

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

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

Пусть T m (соответственно Gm ) множество всех графов (соответственно, деревьев) с m вершинами без петель и кратных ребер.

Положим n(T m ) = max n(); n(T m ) = min n(); n(Gm ) = max n();

n(Gm ) = min n(), n() минимальное число переменных у всех булевых функций, граф интервалов у которых изоморфен графу.

Установлены следующие оценки этих величин:

Теорема 4.4. Справедлива оценка n(T m ) log 3 m.

Теорема 4.5. Для любого m Теорема 4.6. Для любого m 2 справедливы следующие оценки:

1) ] log 2 (m + 1)[+2 n(Gm ) (log 2 m)2 + c1 log 2 m + c2, где c1 = 16, 2) log2 (m + 1) n(Gm ) ] log 2 (m 1)[+2.

В ряде специальных случаев возможен переход от известных локальных процедур [40, 41, 42] к улучшающим их нелокальным, но логически простым процедурам минимизации булевых функций. Приy водится пример реализации этой идеи для класса F G всех булевых функций таких, что упрощенный граф интервалов для каждой из них, полученный из графа интервалов после удаления некоторых специальных конъюнкций, является лесом, то есть графом, каждая компонента связности которого является деревом. Особенностью построенных алгоритмов нахождения т. д. н. ф. и м. д. н. ф. является то, что благодаря специфике выбранного класса булевых функций они работают лишь с информацией о рангах конъюнкций, связанной с вершинами упрощенного графа интервалов. Сложность описанных алгоритмов линейно зависит от числа вершин в упрощенном графе интервалов для исходной функции.

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

долгое время оставались открытыми.

Здесь излагаются результаты А. Е. Андреева, в которых изучается эволюция ряда свойств, характеризующих проблему минимизации д. н. ф., в зависимости от мощностных характеристик булевых функций, причем описывается в основном типичное поведение соответствующих параметров. В этой постановке получены окончательные или близкие к окончательным результаты по следующим вопросам:

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



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 8 |
 


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

«Дама с собачкой Антон Чехов 2 Книга Антон Чехов. Дама с собачкой скачана с jokibook.ru заходите, у нас всегда много свежих книг! 3 Книга Антон Чехов. Дама с собачкой скачана с jokibook.ru заходите, у нас всегда много свежих книг! Антон Чехов Дама с собачкой 4 Книга Антон Чехов. Дама с собачкой скачана с jokibook.ru заходите, у нас всегда много свежих книг! I Говорили, что на набережной появилось новое лицо: дама с собачкой. Дмитрий Дмитрич Гуров, проживший в Ялте уже две недели и привыкший тут,...»

«Доклад Национального разведывательного совета США КОНТУРЫ МИРОВОГО БУДУЩЕГО Александр Шубин РОССИЯ-2020: БУДУЩЕЕ СТРАНЫ В УСЛОВИЯХ ГЛОБАЛЬНЫХ ПЕРЕМЕН Москва Издательство Европа 2005 УДК 327.8 ББК (Т)63.3(2)6 Р 76 Серия Мировой порядок РОССИЯ И МИР В 2020 ГОДУ Доклад Национального разведывательного совета США Контуры мирового будущего А. Шубин Россия-2020: будущее страны в условиях глобальных перемен Перевод с английского Ш. Хаграса Охраняется законом РФ об авторском праве. Воспроизведение всей...»

«НЕМЕЦКИЙ ЯЗЫК Серия Академический школьный учебник. классы 2–11 классы 8 Линия УМК Вундеркинды О. А. Радченко. Линия УМК Немецкий язык И. Л. Бим и др. Серия Академический 5–9 классы школьный учебник 2–4 классы 11 Линия УМК Контакты Г. И. Ворониной и др. 10–11 классы с. 2 с. 8 12 Линия УМК Мозаика Н. Д. Гальсковой и...»

«Януш Леон Вишневский НА ФЕЙСБУКЕ С СЫНОМ Лица, места и события, о которых говорится на страниц этой книги, выдуманы автором, а их возможное совпадение фактами, местами или реально существующими лицами но случайный характер. Правда, время от времени такое как раз и происходит. Ирена Вишневская (1914–†1977) 20 апреля 2011 года Мой день рождения У нас в аду, сыночек, нынче рождение Гитлера отмечали. А и то сказать, сыночек, — событие-то для нас немаловажное. Мало кто заслугами сво так...»

«Дорогие Друзья, Вы держите в руках пятый выпуск каталога 100 новых книг. К своему полуюбилейному возрасту наш ребенок повзрослел: мы старались отдавать предпочтение книгам для школьников, для подростков — и надо сказать, нам было, из чего выбрать. Правда, подростковых текстовых книг опять оказалось меньше, чем книжек-картинок. Зато наконец можно сказать: благодаря нашим совместным усилиям в России стала развиваться книжкакартинка! В условиях конкуренции печатной книги с мультимедийным продуктом...»

«Благодарим за покупку цифровой гибридной IP-ATC Panasonic. Внимательно прочтите это Руководство перед использованием изделия и сохраните его для будущего использования. Установку и программирование системы должен выполнять Авторизованный Установщик. KX-TDA100D: программный файл PDMPR версии 5.1000 или выше Основные функции Основные функции Удобное управление Связь по IP Использование телефона Panasonic, оборудованного Эта УАТС поддерживает связь по IP с помощью кнопкой навигации и дисплеем,...»

«Д Московского ОСНОВНЫМ И ЕДИНСТВЕННО РАДИКАЛЬНЫМ МЕТОДОМ ЛЕЧЕНИЯ ВНЕОРГАННЫХ ЗАБРЮШИННЫХ ОПУХОЛЕЙ Онкологического ЯВЛЯЕТСЯ ХИРУРГИЧЕСКИЙ – БОЛЬШИНСТВО ЭТИХ НОВООБРАЗОВАНИЙ МАЛОЧУВСТВИТЕЛЬНЫ К ЛУЧЕВОМУ Общества ВОЗДЕЙСТВИЮ И ЛЕКАРСТВЕННОМУ ЛЕЧЕНИЮ Энциклопедия клинической онкологии, 2004. ) Интернет: www. ronc.ru //www.oncology.ru //www.elibrary.ru //www.oncodome.narod.ru №4 2013 ИНФОРМАЦИОННЫЙ БЮЛЛЕТЕНЬ МОСКОВСКОГО ОНКОЛОГИЧЕСКОГО ОБЩЕСТВА. ИЗДАЕТСЯ С 1994 г. АПРЕЛЬ ОБЩЕСТВО ОСНОВАНО В 1954 г....»

«Редакционная коллегия: А. с б у ш м и н, в я КИРПОТИН. С. А. МАКАШИН (главный редактор), Е И. ПОКУСАЕВ, К. И. тюныдан Издание осуществляется совместно с Институтом русской литературы (Пушкинский дом) Академии наук СССР ИЗДАТЕЛЬСТВО ХУДОЖЕСТВЕННАЯ ЛИТЕРАТУРА МОСКВА 1977 М.Е. м д т ы к о в - щ в д я н СОБРАНИЕ СОЧИНЕНИЙ Том двадцатый * ПИСЬМА (1884-1889) ИЗДАТЕЛЬСТВО ХУДОЖЕСТВЕННАЯ ЛИТЕРАТУРА МОСКВА 1977 PI C16 Подготовка текста и примечания В. H Баскакова При участии С. А. Макашина (письма к А....»






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

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