WWW.KNIGI.KONFLIB.RU

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

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |

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

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

О сложности алгоритмов

В. Б. Кудрявцев, А. Е. Андреев

Излагаются некоторые результаты по теории сложности

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

Введение

Алгоритмы применяются к двум основным объектам конечным

и бесконечным множествам.

В первом случае имеют дело со схемными вычислениями, во втором с тьюринговыми или программными вычислениями.

Схемные вычисления оперируют с функциями k-значной логики.

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

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

Здесь мы опишем результаты А. Е. Андреева по схемным вычислениям и результаты Нгуен Ким Ань, Т. М. Игамбердыева и А. Е. Андреева по минимизации булевых функций и решению булевых уравнений.

Работа поддерживалась грантом РФФИ № 06-01-00240.

696 В. Б. Кудрявцев, А. Е. Андреев 1. Более чем квадратичные эффективные нижние оценки сложности -схем Здесь на основе обобщения метода Б. А. Субботовской (1961, [110]) и с использованием идеи универсальной функции Э. И. Нечипорука (1966, [111]) построен пример функции, имеющий в классе -схем сложность реализации по порядку не менее, чем n5/, (log n)3/2 log log n где n число переменных. Самые высокие из известных ранее нижние оценки сложности реализации -схемами индивидуальных функций имели рост n2 (В. М. Храпченко, 1971, [112]).

Пусть x1 = (x1,..., x1 ), x2 (x2,..., x2 ),..., xk (xk,..., xk ) 1 1 l l l попарно не пересекающиеся наборы различных переменных. Через k,l Xs обозначим множество всех таких наборов = (j1,1,..., j1,s,..., jk,1,..., jk,s, 1,1,..., 1,s,..., k,1,..., k,s ) что 1 ji,1 ji,2... ji,s l, i = 1, 2,..., k;

i,t {0, 1}, i = 1, 2,..., k, t = 1, 2,..., s.

Если f (1, x2,..., xk ), то через f обозначим функцию, которая поx лучается из f подстановкой вместо переменных x i i,t констант i,t j i = 1, 2,..., k, t = 1, 2,..., s. Пусть L(F ) сложность реализации функции f посредством -схем.

Лемма 1.1 ([114]). Если k 1, l 5, то для любой булевой функции k,l f (1, x2,..., xk ) такой, что L(f ) 2, существует из X 1, такое, x что L(f ) L(f ), l где 3 (x) = 1 x + x2.

2 О сложности алгоритмов Лемма 1.2 ([114]). Существует такая положительная константа c0, что если k 4, то для любой булевой функции 1, l r k,l f (1, x2,..., xk ) существует из Xlr, такое, что x l L(f ) c0 L(f ).

r Лемма 1.3 ([114]). Если k 1, l r 4, функции g 1 (1 ),..., gk (k ) x x не обращаются в константу ни на каком интервале размерности r и f = g(g1 (1 ),..., gk (k )), то x x 1 l L(f ) L(g).

c0 r натуральное, k 3 и l = 2k /k, n = 2k + k · l. Пусть Пусть k набор y состоит из 2k различных переменных y1,...,k, 1,..., k {0, 1}, не входящих в x1,..., xk. Полагаем k i xi... x i Теорема 1.1 ([114]). Имеет место где C положительная константа.

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

До недавнего времени имелись лишь методы, которые позволяли получать относительно числа переменных только полиномиальные оценки(А. А. Марков [95], Э. И. Нечипорук [96, 97], M. S. Paterson [98], V. R. Pratt [99], N. Pipenger [100], Z. Galil [101], K. Mehlohrn [101, 102], I. Vegener [103], Е. А. Окольнишникова [104]).

В 1984 году А. Е. Андреев предложил метод позволяющий получать почти экспоненциальные нижние оценки монотонной сложности (2n 3, где n число переменных).

Одновременно А. А. Разборов [107, 108] предложил метод, позволивший получить оценку вида 2O(log n).

В работе [109] А. Е. Андреев предложил усовершенствованный вариант своего метода. Основным результатом является общая оценка сложности монотонной булевой функции через некоторые ее комбинаторные характеристики. Приведен пример последовательности функций, для которых полученная оценка имеет рост 2 n 3, где число переменных. Эта оценка остается самой высокой и в наn стоящее время.

2.1. Метрический критерий сложности A-схем Если A P, где P множество всех булевых функций, то A-схемой называем схему в базисе {&, }, входным полюсам которой приписаны функции из множества A. Через L A (f ) обозначаем наименьшее число функциональных элементов, достаточное для реализации A-схемой функции f. Ясно, что и если A содержит константы 0, 1 и все переменные монотонной функции f, то где Lc (f ) сложность реализации f схемами из функциональных элементов в базисе B.

Неотрицательная функция (x, y) называется псевдометрикой, если она удовлетворяет соотношениям:

Далее мы будем рассматривать псевдометрики на P n, где An множество всех булевых функций из A, зависящих от первых n переменных алфавита {u1, u2,..., un,...}. Псевдометрику на P n будем называть монотонной, если Очевидно, что для любой монотонной псевдометрики справедливо неравенство Полагаем Последовательность функций f1, f2,..., fk называем правильной, если для любого i из {1, 2,..., k 1} либо f i fi+1, либо fi fi+1.

Полагаем Записываем если существует такая правильная последовательность f 1,..., fk, что Если B1, B2 P n и для любой f из B1 существует g из B2 такая, что [1, 2 ](f, g) (a1, a2 ), то записываем Через A обозначим класс функций, которые представимы в виде f1 &f2 или f1 f2, где f1, f2 A.

Лемма 2.1 ([109]). Если и для монотонных псевдометрик 1, 2 выполнено то существует g из P n такая, что Теорема 2.1 ([109]). Если и для монотонных псевдометрик 1, 2 выполнено 2.2. Лемма о системе конечных множеств Лемма 2.2 ([109]). Если R система непустых попарно невложимых множеств мощности не более s и то существуют такие различные V1, V2,..., Vr из R и множество V0 (быть может пустое), что V0 V1 V2 и множества V1 \ V0,..., Vr \ V0 попарно не пересекаются.

2.3. Аппроксимация функций из некоторых специальных классов торое каждому подмножеству w множества W ставит в соответствие некоторое подмножество F(w) множества переменных U n = {u1, u2,..., un }, причем Через Kw обозначим конъюнкцию всех переменных из F(w), а если w =, то Kw = 1. Через F обозначим такой набор из E n, где E n n-мерный бинарный куб, у которого единичными являются все компоненты, соответствующие переменным из F(w), а остальные компоненты нулевые.

Через M обозначаем множество всех монотонных функций алгебмножество таких f из M n, что f ры логики, а через M (F) либо константа, либо любая ее простая импликанта есть K w для некоторого w W.

Если f M n, то множество w W называется простым для f, если не существует такого w1, что w1 w и Kw1 импликанта f, F является импликантой f. Через всех простых для f множеств. Ясно, что для всех f из M (F) верно (пустая дизъюнкция считается равной 0).

Через ls обозначаем число непустых множеств из F мощности не более s, а через RF (f ) максимальную мощность множеств из Через M (F, w, k, r) обозначаем множество всех таких f из M (F), что все множества из F содержат w и выполнено Через l(f ) обозначаем число простых импликант f, а через R(f ) их максимальную длину. Через Бr,k обозначаем множество всех бесповторных f из M таких, что Здесь f мы называем бесповторной, если ее простые импликанты не имеют общих переменных. Полагаем Лемма 2.3 ([109]). Если 2, |w| k, то для любой f из M (F, w, k) \ M (F, w, k, r) сущеr ствует g из M (F, w, k) такая, что Лемма 2.4 ([109]). Если ствует такая g из M (F, w, k, r), что Псевдометрика на M n называется F-правильной, если (f1, f2 ) = 0, как только для всех w, содержащихся в W, выполнено Полагаем Лемма 2.5 ([109]). Если 1, 2 монотонные псевдометрики на M n, 1 F-правильная, r 2, k 1, то где Теорема 2.2 ([109]). Если 1, 2 монотонные псевдометрики на то для любого где 2.4. Оценки в случае специальных псевдометрик Полагаем, что F (f ) минимально возможное число множеств из F таких, что их пересечение содержит не менее s элементов. Через R (f ) обозначаем минимальную длину импликант f. Полагаем Теорема 2.3 ([109]). Если p (0, 1), |W | k 1, r 2, f M (F), LA (f ) 0, F (f ) 1, t(F, k) 1, A = M(F, k, r), то Через s (f ) обозначаем максимально возможное число простых импликант f, имеющих не менее s общих переменных.

R (f ) k + 1, Б = {&,, 0, 1}, то Через Ak обозначаем декартово произведение k экземпляров множества A.

c1, c2 GF (q), неприводимый над GF (q) многочлен. Рассмотрим расширение GF (q), порождаемое присоединением корней p(x). В этом случае операции на GF (q)2 = GF (q) GF (q) определяются следующим образом:

Данное расширение является, как известно, полем Галуа GF (q 2 ). При этом множество всех пар вида (a, 0) образует подполе GF (q) и выполнено Рассмотрим следующую систему функций на GF (q) 2 со значениями в GF (q):

то есть мы индексировали тройками из GF (q) 3 все переменные из Un.

Полагаем Следствие 2.1 ([109]). Если m четное, то для любого полного монотонного базиса Б выполнено где CБ константа, зависящая только от базиса.

Максимальный рост этих оценок достигается при В этом случае Пусть W некоторое множество мощности n 0, w1, w2,..., wn все его подмножества мощности µ. Если w W, i {1, 2,..., n}, то полагаем, что Полагаем Эти функции называем µ-симметрическими.

то для любого полного монотонного базиса Б выполнено 3. Сложность схемных алгоритмов При проектировании управляющих систем, одной из основных задач является минимизация их параметров, обуславливающих стоимость, размеры и материалоемкость. Пусть, например, перед конструктором стоит задача разработки блока ЭВМ для умножения чисел заданных в двоичной записи. В целях обеспечения быстродействия и надежности желательно, чтобы этот блок состоял из одной микросхемы. Однако число транзисторов и других функциональных узлов, которое можно разместить на одном кристалле, ограничено, вследствие причин технологического и физического характера. Кроме того производство микросхем с меньшим числом функциональных узлов обходится дешевле. Поэтому разработчик блока стремится уменьшить число транзисторов и других элементов в проектируемой схеме для умножения чисел.

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

Основная задача этой теории состоит в следующем. Задано множество схем U и оператор F, сопоставляющий каждой схеме u U, реализуемую ею булеву функцию F(u) (или оператор). В приведенном примере U это множество микросхем, а F(u) преобразование входных наборов импульсов в выходные, осуществляемое микросхемой u. Задан неотрицательный, определенный на U функционал L U сложности схем. Это может быть, например, число транзисторов в микросхеме или площадь кристалла, на котором она расположена.

Схема u реализует функцию f (или оператор), если f = F(u). Требуется для каждой функции (оператора) f найти реализующую ее схему u минимально возможной сложности L U (u), которая обозначается через LU (f ) и называется сложностью реализации f, схема же u называется минимальной. Эта задача называется задачей синтеза.



Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |
 


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

«Конференция Сторон Комитет по науке и технике Одиннадцатая сессия Виндхук, Намибия, 1720 сентября 2013 года Пункт 5 a), b) и c) предварительной повестки дня Реорганизация деятельности Комитета по науке и технике в соответствии со Стратегией: обзор итогов второй Научной конференции КБОООН Оценка организации второй Научной конференции КБОООН Оценка научных конференций КБОООН Обзор предварительных итогов второй Научной конференции КБОООН и оценка научных конференций КБОООН Доклад Бюро Комитета по...»

«Xperia™ V LT25i Содержание Xperia™ V Руководство по эксплуатации Начало работы Информация о руководстве по эксплуатации Android™ — что и почему? Основные элементы телефона Детали устройства Включение и выключение телефона Блокировка и разблокировка экрана Руководство по настройке Учетные записи и услуги Знакомство с основными функциями устройства Использование клавиш Использование сенсорного экрана Аккумулятор Экран блокировки Начальный экран Создание снимка экрана Доступ и работа с...»

«А. В. Домрин, А. Г. Сергеев Лекции по комплексному анализу Второе полугодие Москва 2004 УДК 517.5 ББК (В)22.16 Д66 Домрин А. В., Сергеев А. Г. Д66 Лекции по комплексному анализу : В 2 частях. / А. В. Домрин, А. Г. Сергеев. — М.: МИАН, 2004. ISBN 5-98419-006-0 Часть II : Второе полугодие. — 2004. — 136 с. ISBN 5-98419-008-7 Издание осуществлено при поддержке Российского фонда фундаментальных исследований (грант № 04-01-14126). c Домрин А. В., Сергеев А. Г., 2004 ISBN 5-98419-008-7 (ч. II) c...»

«Министерство образования и науки Российской Федерации Федеральное агенство по образованию Утверждаю: _ 200 г. Примерная основная образовательная программа высшего профессионального образования подготовки бакалавров Направление подготовки 210600 Нанотехнология Профиль подготовки Композитные наноматериалы Квалификация выпускника - бакалавр техники и технологии Санкт-Петербург - 2008 1. Общие положения 1.1. Примерная основная образовательная программа высшего профессионального образования (ПООП...»

«ДИКИЙ ДОН Предисловие В прессе давно и бурно спорят: кто написал Тихий Дон? Между тем куда по лезнее вспомнить, про что, собственно, Тихий Дон. И тогда эта книга, подроб ный и кровавый отчет о банкротстве русского национального характера, очень многое объяснила бы нам про нас сегодняшних. Зеев Бар Селл (Владимир Назаров) написал книгу о подлинных авторах шо лоховского наследия — Вениамине Краснушкине, Константине Каргине и Анд рее Платонове. Краснушкин (более известный под псевдонимом Виктор...»

«Книга подготовлена во время проекта Диет нет, на блоге Иры Бонэр (январь, 2012) Цель проекта — не только похудеть, но и научиться правильно питаться, а также оздоровить свой организм. Подробное меню на каждый день составлялось во время проекта. Все рецепты подобраны специально, с учётом полезных для женского здоровья продуктов. Рецепты рассчитаны на две порции. В рецептах указано количество калорий каждого блюда и время приготовления. Все блюда просты в приготовлении и не занимают много...»






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

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