WWW.KNIGI.KONFLIB.RU

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

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

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |

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

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

Теорема 3.7. Для любого замкнутого класса A функций алгебры логики, не содержащегося полностью ни в одном из классов D3, L1, S6, P6 имеет место где = П, LП, m, logx.

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

Наряду с реализацией функций и операторов рассматривается реализация и топологических функциональных сетей. При этом сеть S реализует сеть S1, записываем S1 S2, если множества их полюсов совпадают и компонента [S2 ], отвечающая данной паре полюсов, является доопределением соответствующей компоненты [S 1 ].

Если S = F(F ) топологическая функциональная сеть, то полагаем, что:

Hпр (S) минимально возможная суммарная энтропия такого набора функций, что любая компонента F или ее отрицание является компонентой этого набора, L (S) арность F, N (S) число переменных, задействованных в S. Если r 1, r2 положительные последовательности, то через Т 1, r2 обозначаем множеr ство всех таких топологических функциональных сетей S, что Имеет место следующее утверждение.

Теорема 3.8 ([35]). Если 1 r1 (n) = r2 (n)o(1), log3 n = o(log r2 (n)), r2 (n) 2cn, то где c константа, а = Т, LТ, m, logx.

Эта теорема позволяет переносить на топологические функциональные сети многие конструкции принципа локального кодирования О. Б. Лупанова.

Она может быть проиллюстрирована так. Рассматриваются инвариантные классы операторов. Они определяются аналогично инвариантным классам С. В. Яблонского. При этом число компонент у всех операторов из одного класса одинаково. Следуя С. В. Яблонскому, инвариантный класс A операторов называется ненулевым, если При помощи конструкции принципа локального кодирования О. Б. Лупанова для инвариантных классов и теоремы 3.8 получается следующий результат.

Теорема 3.9 ([35]). Если A ненулевой инвариантный класс операторов, то где = Т, LТ, m, logx.

Здесь через F, где F = (f1, f2,..., fS ), обозначается топологическая функциональная сеть вида Рассматривается класс монотонных операторов. Для булевого набора a = (a1, a2,..., an ) полагаем Класс MH состоит из всех таких операторов F, у которых число компонент равно числу переменных и С использованием конструкции О. Б. Лупанова для этого класса и теоремы 3.8 получается следующий результат.

Теорема 3.10 ([35]).

где = Т, LТ, m, logx.

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

Если f P n, то через f +k обозначается такая функция из При помощи конструкции О. Б. Лупанова и теоремы 3.8 получается следующий результат.

Теорема 3.11 ([35]). Если 1 t(n) где = Т, LТ, m, logx.

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

Теорема 3.12 ([35]). Если A P, log 2 n = o(log (n)), где = П, LП, m, logx.

Изучается самокорректирование в топологических функциональx ных сетях, предполагается, что = Т, L Т, m, logx. Основными результатами здесь являются следующие теоремы.

Теорема 3.13 ([35]). Если A класс функций или операторов и log3 n = o(log (n)), 1 log (n) = o(log (n)), то Теорема 3.14 ([35]). Если A класс функций или операторов и log3 n = o(log (n)), (n) 2cn, то где c константа.

Исследованы вопросы моделирования функциональных сетей.

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

Рассматриваются формулы в полном базисе Б, который состоит из надежной и ненадежной частей. При этом надежная часть базиса Бн полна. Формула, реализующая f корректирует неисправностей, если при замене в ней не более любых вхождений ненадежных функциональных символов на любые другие той же арности, получающаяся формула также реализует f. Через L (f ) обозначается сложность реализации f формулами в базисе Б н, корректирующими неисправностей. Через (Б) обозначается минимальный приведенный вес базиса Б.

Пусть семейство N1 состоит из следующих классов функций из 1) r = {f | m(f ) r(N (f ))}, где r любая натуральная монотонная последовательность;

2) 1,r = {f | m1 (f ) = r(N (f ))}, где r любая натуральная последовательность;

монотонная последовательность;

4) всех ненулевых инвариантных классов С. В. Яблонского;

5) всех классов Поста, не содержащихся полностью в D 3, L1, S6, P6.

Пусть семейство N1 состоит из всех классов A семейства N 1 таn ) log n, а также классов и Q таких, что log log n = o(log log r(n)).

для любого базиса Б с полной надежной частью Это утверждение вытекает из изложенных выше результатов и результатов О. Б. Лупанова [28], в которой получена асимптотика функции Шеннона для формул.

Рассматриваются контактные схемы. Через L k (F ) обозначается сложность реализации F обычными контактными схемами, а через L (F ) и Lk (F ) корректирующими любых неисправностей конk тактов и, соответственно, a замыканий и b размыканий контактов одновременно. Получена верхняя оценка сложности реализации контактными схемами частичных функций с данной величиной области определения, которая необходима для асимптотически оптимального моделирования топологических функциональных сетей.

Теорема 3.17 ([35]). Если f P n, то Пусть семейство N2 состоит из следующих классов операторов:

1) всех ненулевых инвариантных классов операторов;

2) класса MH монотонных операторов;

3) {(f, f +1,..., f +r(N (f )) ) | f P }, где r такая натуральная последовательность, что 1 r(n) = 2o(n) ;

4) {(f, f, f, f,..., f, f ) | f P }, где r такая натуральная последоr(N (f )) вательность, что Если A класс операторов, то полагаем A = { F | F A}.

Полагаем N Считается, что контактная схема реализует функциональную сеть S, если она реализует [S].

Изложенные результаты опубликованы в [29]–[34].

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

Особую роль здесь играют схемы из функциональных элементов, по отношению к которым до 80-х годов не удавалось привести примеров булевых функций с нелинейной сложностью.

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

4. Минимизация булевых функций Важное место в теории управляющих систем занимает теория дизъюнктивных нормальных форм. Булева функция f (x 1,..., xn ), описывающая функционирование управляющей системы, может быть реализована с помощью дизъюнктивной нормальной формы (д. н. ф.), которая в этом случае опишет схему соответствующей управляющей системы. Важная задача теории управляющих систем нахождение оптимальной схемы с наименьшей затратой оборудования выражается в теории д. н. ф. как задача нахождения среди всех д. н. ф., реализующих данную функцию, кратчайших или минимальных д. н. ф. Существует тривиальное решение указанной задачи: упорядочиваются все д. н. ф. над переменными {x 1,..., xn } (их число 23 ) по порядку неубывания рассматриваемой сложности и выбирается первая д. н. ф., которая реализует данную функцию.

Это решение с точки зрения практики слишком громоздко. Известно [44, 48], что кратчайшее д. н. ф. (к. д. н. ф.) и минимальное д. н. ф.

(м. д. н. ф.) можно получить из сокращенной д. н. ф. (с. д. н. ф.) заданной функции путем удаления некоторых конъюнкций. Установлен достаточно эффективный критерий, позволяющий осуществлять это удаление (так называемый критерий поглощения) [41, 44]. Однако и при таком подходе решение задачи минимизации булевых функций встречает ряд серьезных препятствий. Последние были указаны в работах по алгоритмическим трудностям синтеза минимальных схем и в работах Ю. Л. Васильева и В. В. Глаголева [37, 38, 44]. Эти трудности проявляются прежде всего в том, что, переходя последовательно посредством упрощения от одной д. н. ф. для данной функции к другой с помощью критерия поглощения, приходят к далее неупрощаемой тупиковой д. н. ф. (т. д. н. ф.), которая может являться к. д. н. ф. или м. д. н. ф., а может и не быть таковой. Приходится снова проводить процесс упрощения с. д. н. ф., удаляя другие конъюнкции до тех пор, пока не будут получены все т. д. н. ф. и среди них выбрано искомое решение.

Подчеркивая большую трудоемкость процедур такого рода, Ю. И. Журавлев указывал на необходимость предварительного изучения свойств удаляемых конъюнкций и предложил в связи с этим подход, названный им локальными алгоритмами [41, 42, 43]. Главным достоинством таких алгоритмов является то, что, не прибегая к просмотру всех т. д. н. ф. и ограничиваясь лишь информацией о конъюнкциях, близких к рассматриваемой конъюнкции, они позволяют иногда определить, входит или не входит последняя в некоторые (или во все) к. д. н. ф (м. д. н. ф.) данной функции. Однако, в общем случае утвердительного ответа на такой вопрос локальные алгоритмы дать не могут [43, 44]. Поэтому можно считать, что локальные алгоритмы играют лишь промежуточную роль в общей теории минимизации булевых функций. Характерная трудность изучаемой задачи заключается в том, что, с одной стороны, процедуры минимизации булевых функций не могут быть осуществлены без перебора [37], а, с другой стороны, мощность областей перебора обычно очень велика.

Как отмечено в [38, 44], максимальное число т. д. н. ф. функции от n переменных имеет порядок, больший, чем 2 2.

В работе Нгуен Ким Ань [50] изучаются качественные и количественные вопросы, связанные с алгоритмами минимизации булевых функций.

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

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

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

Изучается процесс построения всех т. д. н. ф. булевой функции в геометрическом плане и исследуется поведение указанных функций Шеннона. Граф интервалов был введен А. А. Сапоженко [46]. Здесь исследуются новые качественные и количественные проблемы, связанные с этим графом. Описаны алгоритмы нахождения к. д. н. ф. и м. д. н. ф. для класса булевых функций, так называемый упрощенный граф интервалов каждой из которых является деревом. Сложность построенных алгоритмов оказалась линейно зависящей от числа вершин-конъюнкций в исходном графе.

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



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |
 


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

«УДК 64] ББК 36.996 Л63 Иллюстрации автора Лисси Мусса Л63 Моя фортуна—Лакомка, или ОК'сЮМОРон и 3000 способов угостить Удачу / Лисси Мусса; ил. автора. — М.: ACT: ACT МОСКВА: ХРАНИТЕЛЬ, 2006.-287, [1] с: ил. ISBN 5-17-036895-Х (ооо Издательство аст) ISBN 5-9713-2521-3 (ооо аст москва) ISBN 5-9762-0128-8 (ооо хранитель) Это не просто Волшебная Кулинария — это сенсация! Вам случалось находить рецепт блюда, резко повышающего самооценку или усиливающего телепатическую и интернетсвязь? А готовить...»

«Жизнь индейцев – это непрерывная цепь горьких и трагических событий. Жозеф Диксон, Исчезающий народ ПРЕДИСЛОВИЕ В предлагаемых вниманию читателя мемуарах индейского вождя Мато Нажина Мой народ cиу показана трагедия одного из североамериканских индейских племен, раздавленного колонизаторами. События, описанные в мемуарах, относятся ко второй половине XIX века. До прихода бледнолицых племя cиу жило охотой на бизонов, которые бесчисленными стадами паслись у них на родине, в прериях Дикого Запада...»

«ГОсуДаРсТвО и цЕРкОвЬ ТОм II мОсква институт русской цивилизации 2011 УДК 347 ББК 66.1(2)5 П-41 Победоносцев...»

«Пансион Святой Маргарет Элен Бронтэ 2 Книга Элен Бронтэ. Пансион Святой Маргарет скачана с jokibook.ru заходите, у нас всегда много свежих книг! 3 Книга Элен Бронтэ. Пансион Святой Маргарет скачана с jokibook.ru заходите, у нас всегда много свежих книг! 4 Книга Элен Бронтэ. Пансион Святой Маргарет скачана с jokibook.ru заходите, у нас всегда много свежих книг! Элен Бронте Пансион Святой Маргарет 5 Книга Элен Бронтэ. Пансион Святой Маргарет скачана с jokibook.ru заходите, у нас всегда много...»

«Магистерская программа Программное обеспечение вычислительных сетей Магистерская диссертация ГЕО-КОНТЕКСТНЫЕ ПРИЛОЖЕНИЯ НА WINDOWS PHONE Работу выполнил: студент Юсуф-заде Гулам Эльчин оглы Научный руководитель: с.н.с. к.ф.-м.н. Намиот Дмитрий Евгеньевич Подпись научного руководителя: Москва 2013 Оглавление Аннотация 1 Введение 2 Постановка задачи 3 Обзор существующих решений 4 Цели и критерии сравнения 4.1 4.2 gMaps 4.3 Nokia Friends View 4.4 Social recommendation system 4.5 Google Now Выводы...»

«Авторы ответов: Василий Юнак, Петр Рыбачек, Игорь Иващенко, Максим Балаклицкий, Виктор Белоусов, Алексей Опарин, Лариса Сугай, Андриан Дмитрук, Иван Миненко, Александр Дулгер, Александра Ланц, Максим Гордиенко, Руслан Фазлеев. (c) 2000-2010, Твоя Библия www.bible.com.ua. Разрешается использование материалов в неизмененном виде, с упоминанием автора и с указанием точной ссылки на используемую статью. www.bible.com.ua Страница 1 из 90 Дорогие Братья и Сестры! Позвольте называть вас именно так,...»

«Постановление суда от 23 мая 1991 г. В деле “Обершлик (Oberschlick)”, Европейский суд по правам человека, принимая свое постановление на пленарном заседании во исполнение статьи 51 Регламента Суда, и составленный из следующих судей: г-н Р. Риссдал, Председатель, г-н Й. Кремона, г-н Тор Вильялмсон, г-жа Д. Биндшедлер-Роберт, г-н Ф. Гелчюклю, г-н Ф. Матчер, г-н Л. –Е. Петтити, г-н Б. Уолш, сэр Винсент Эванс, г-н Р. Макдональд, г-н К. Руссо, г-н Р. Бернхардт, г-н А. Шпильманн, г-н Й. Де Мейер, г-н...»

«Зарегистрировано в Минюсте РФ 30 декабря 2010 г. N 19452 МИНИСТЕРСТВО ФИНАНСОВ РОССИЙСКОЙ ФЕДЕРАЦИИ ПРИКАЗ от 1 декабря 2010 г. N 157н ОБ УТВЕРЖДЕНИИ ЕДИНОГО ПЛАНА СЧЕТОВ БУХГАЛТЕРСКОГО УЧЕТА ДЛЯ ОРГАНОВ ГОСУДАРСТВЕННОЙ ВЛАСТИ (ГОСУДАРСТВЕННЫХ ОРГАНОВ), ОРГАНОВ МЕСТНОГО САМОУПРАВЛЕНИЯ, ОРГАНОВ УПРАВЛЕНИЯ ГОСУДАРСТВЕННЫМИ ВНЕБЮДЖЕТНЫМИ ФОНДАМИ, ГОСУДАРСТВЕННЫХ АКАДЕМИЙ НАУК, ГОСУДАРСТВЕННЫХ (МУНИЦИПАЛЬНЫХ) УЧРЕЖДЕНИЙ И ИНСТРУКЦИИ ПО ЕГО ПРИМЕНЕНИЮ На основании статьи 165 Бюджетного кодекса...»

«Урок 2: Планеты. 20 стр. • Понятие планета. • Значение каждой планеты. • Классификация планет. • Направление движения планет. • Скорость движения планет. • Таблицы соответствий. • Планетные принципы в жизни. Урок 3: Знаки Зодиака. 43 стр. • Зодиак как единое целое. • Индивидуальность каждого знака. • Взаимосвязь планет и знаков Зодиака. • Понятие обители и изгнания планет. • Понятие экзальтации и падения планет в знаках Зодиака. • Классификация знаков Зодиака. • Расчет доминирующего элемента. •...»






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

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