WWW.KNIGI.KONFLIB.RU

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

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

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

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

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

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

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

• частичные функции с данной величиной области определения, • функции с данным числом единиц, • функции с ограниченной энтропией, • ненулевые инвариантные классы С. В. Яблонского, • классы Поста, не содержащиеся в D3, L1, S6 и P6 (обозначения Основным результатом относительно топологических функциональных сетей является теорема о дублях. В процессе доказательства этой теоремы им предложен метод одновременной реализации многих экземпляров частичной функции и ее отрицания со сложностью, асимптотически не превосходящей сложности самой функции (то есть величины ее области определения). Теорема о дублях позволяет переносить на топологические функциональные сети многие конструкции принципа локального кодирования О. Б. Лупанова. Эта возможность иллюстрируется на примерах следующих классов операторов:

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

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

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

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

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

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

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

Формализуем изложенное. Пусть P множество всех частичных функций алгебры логики и M множество операций на P. Если операция F из M применима к набору (f 1, f2,..., fk ) функций из P, где k арность этой операции, то выражение называется функциональной сетью. Через [S] обозначается функция (оператор) разложением которой является функциональная сеть S.

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

Функциональная сеть S реализует функцию f (оператор) где f g, если g есть доопределение f. Сеть S корректирует неисправностей (a единичных и b нулевых) если любая функциональная сеть, которую можно получить из S произвольной заменой не более функций в наборе (f 1, f2,..., fk ) (не более a функций на тождественную единицу и одновременно не более b на тождественный ноль) также реализует f.

S, {,, (a, b)}, означают одно и то же.

Вводим три класса операций:

Операция из класса СЛ задается ориентированным ациклическим графом. В графе выделены вершины, называемые полюсами, они занумерованы числами 1, 2,..., k, где k число полюсов. В полюса ребра не входят, а во все остальные вершины входят ровно по два ребра. Каждая вершина не являющаяся полюсом, помечена либо символом &, либо. Выделены выходные вершины и занумерованы числами 1, 2,..., S, где S их число. Операция F, задаваемая такой логической сетью, имеет арность k и ее результатом является S-компонентный оператор [F(f1, f2,..., fk )], определяемый следующим образом. Пусть функции f1, f2,..., fk полностью определенные. Полюсу с номером i приписываем функцию f i, i = 1, 2,..., k, а каждой вершине, не являющейся полюсом приписываем функции так, что функция, приписанная данной вершине является конъюнкцией или дизъюнкцией (в соответствии с тем символом & или, которым помечена вершина) функций, приписанных вершинам, из которых в данную входят ребра. Компонентами оператора [F(f 1, f2,..., fk )] являются функции, приписанные выходным вершинам в соответствии с нумерацией последних. В общем случае, для определения оператора [F(f1, f2,..., fk )] рассматриваются всевозможные наборы g1, g2,..., gk такие, что gi полное доопределение fi, зависящее от тех же переменных. Если на данном наборе значений переменных в i-ой выходной вершине при любом таком полном доопределении реализуется одно и то же значение, то оно является значением i-ой компоненты результата операции на данном наборе значений переменных, в противном случае это значение равно.

Операция из класса Т задается конечным неориентированным графом без петель (кратные ребра допустимы) с выделенными вершинами, которые называются полюсами, то есть сетью. Ребра графов занумерованы натуральными числами от 1 до k, где k число полюсов. Арность операции k, она применима к любому набору из k функций. Ее результат при применении к набору (f 1, f2,..., fk ) является оператором с Cp компонентами. Ребру с номером i приписывается функция fi. Компонента результата с номером C j1 + i, значений переменных она равна 0, если нет цепей между i-ым и j-ым полюсами, либо, если в любой цепи между ними существует ребро помеченное функцией, обращающейся на выбранном наборе значений переменных в 0; равна 1, если существует цепь между рассматриваемыми полюсами такая, что все приписанные ее ребрам функции обращаются на выделенном наборе переменных в 1; в остальных случаях значение равно.

Пусть П подкласс класса Т, соответствующий двухполюсным параллельно последовательным сетям. Он совпадает с подклассом класса СЛ, порождаемым бесповторными (то есть древовидными) логическими сетями.

Полагаем, что LСЛ (F) наименьшее возможное число вершин в логической сети, задающей операцию F из СЛ. Функционалы L Т и LП являются ограничениями функционала L СЛ на множества операций Т и, соответственно, П.

Функционалы сложности функциональных сетей задаются:

• функционалом LM сложности операций;

• неотрицательным функционалом на P, характеризующим априорную сложность компонент;

• нормировочной функцией Ш, определенной, неотрицательной, монотонной и неограниченной на [0, );

• весовой функцией операции, определенной, неотрицательной Набор называется сигнатурой. Для функциональной сети полагаем где n число переменных задействованных в функциональной сети Определенная величина называется сложностью функциональной сети S в сигнатуре с весовой функцией.

Если f функция из P (оператор), то {,, (a, b)}, сложность реализации f функциональными сетями в сигнатуре с весовой функцией (корректирующими неисправностей, a единичных и b ненулевых неисправностей).

Если A класс функций или операторов, то {,, (a, b)}, соответствующая функция Шеннона.

В качестве основных функционалов характеризации априорной сложности компонент рассматриваются:

m(f ) число точек, на которых функция принимает значения ноль и один, 2N (f ) число всевозможных наборов значений переменных функции, в качестве вспомогательного H(f ) энтропия f, то есть двоичный логарифм (log) числа сочетаний из m(f ) по m1 (f ) числу единичных точек функции f. В качестве нормировочных функций рассматриваются:

где Если соотношение выполнено при всех таких, что то записываем а если при всех таких, что log log (n) = o(log log (n)), то записываем Если соотношение выполнено хотя бы для одной такой, что то записываем а если хотя бы для одной такой, что log log (n) = o(log log (n)), то записываем Для сигнатур 1, 2 записываем 1 2, если при всех допустимых при любых допустимых и Ш.

Пусть Показано, что при любых допустимых M и.

Для мощностных нижних оценок функции Шеннона имеет место утверждение.

Теорема 3.1 ([35]). Если log n = o(log H(A n )), то а если log log n = o(log log H(An )), то где 1 = СЛ, LСЛ, m, log x, а H(An ) энтропия класса An, то есть двоичный логарифм минимально возможной мощности множества булевых функций (операторов), содержащего доопределения всех f из An.

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

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

Теорема 3.2 ([35]). Если A класс булевых функций или операторов, M {П, Т, СЛ}, (n) {, (n), (a(n), b(n))}, log2 n = o(log (n)), то где 1 = M, LM, H, logx, 2 = M, LM, m, logx Через Qr обозначается множество всех таких f из P, что (r неотрицательная последовательность, N (f ) число переменных f ), а через 1,r всех таких f, что (r натуральная последовательность). Из теоремы 3.1 и 3.2 вытекает следующий результат.

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

Важно получение оценок сложности реализации частичных функций с данной величиной области определения функциональными сетями в сигнатуре = П, LП, 2N, log x.

Через r обозначается множество всех таких f из P, что m(f ) r(N (f )), где r натуральная последовательность. Имеет место следующее утверждение.

Теорема 3.4 ([35]). Если log log n = o(log log r(n)), то С помощью этой теоремы устанавливается такой факт.

Теорема 3.5 ([35]). Если A P, (n) {, (n), (a(n), b(n))}, log log n = o(log log (n)), то где имеет тот же смысл, что и в предыдущей теореме, а 0 = Рассматриваются ненулевые инвариантные классы С. В. Яблонского. Пусть R некоторый ненулевой инвариантный класс такой, что Тогда справедлива теорема.

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

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

Рассматриваются также классы Поста. Установлен следующий результат.



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


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

«Ю. С. Грачев В Иродовой бездне Воспоминания о пережитом Книга четвертая Оглавление  Часть 7. СВЕТ ПЕРЕД ЛЮДЬМИ (1945) Глава 1. Дорогие минуты нам Бог даровал Глава 2. Самый дорогой подарок Глава 3. Молитва Глава 4. Негоден Глава 5. Блаженны кроткие Глава 6. Восстановители Глава 7. Огонь с небес священный Глава 8. Семафор открыт Глава 9. Предвесеннее Глава 10. Униженные и оскорбленные Глава 11. Искушение Глава 12. Изгнанный Глава 13. Господь печется Глава 14. К ним все желание мое Глава 15. Не...»

«Грани Агни Йоги 1957 год Грани Агни Йоги. 1957 г. Записи Бориса Николаевича Абрамова, ближайшего ученика Н.К. Рериха, полученные из Высокого Источника, о чем имеется подтверждение Е.И. Рерих. – Новосибирск: Предприятие Алгим. 2008 г. – 560 с. Составитель Б.А. ДАНИЛОВ В книгу вошли ранее не публиковавшиеся Записи Бориса Николаевича Абрамова 1957 года. Б.Н. Абрамов (1897проживший многие годы (1917-1959) за рубежом, в Харбине, был ближайшим учеником Николая Константиновича Рериха. Источник Записей...»

«О чём эта книга и как её читать Чтобы меньше работать, надо, хотя бы, читать о том, как это делается! Сначала - для кого эта книга. Если уж вы взяли её в руки, она определённо для вас. Для вас, если вы умеете резать деревья. Для вас, если режете и думаете, что умеете резать. Для вас, если вы не умеете, но режете. И особенно для вас, если вы не умеете, не хотите и никогда не этого не делаете! Вам будет полезно узнать, что существует идеальная дачная форма* дерева, подходящая почти для всех пород...»

«Влияние через социальные сети: под общей ред. Е.Г. Алексеевой. – М.: Фонд ФОКУС-МЕДИА, 2010. – 200 с. В книге рассказывается о возможностях использования популярных социальных сетей для продвижения, поиска сторонников, влияния некоммерческих и коммерческих организаций. Корректор Валентина Главчева Оформление и верстка Денис Копейкин Книга издана Фондом ФОКУС-МЕДИА в рамках проекта Развитие местных сообществ Чечни, Ингушетии, Дагестана и Северной Осетии, при финансовой поддержке UNDEF. Тираж 1...»

«Международные перспективы образования взрослых Целью публикуемых в данной серии отчетов, исследований и материалов является развитие в деятельности народных университетов (VHS) теории и практики, связанных с международными аспектами образования взрослых и наоборот. Мы надеемся, что обеспечив доступ к информации и наладив каналы для диалога, данная серия изданий послужит повышению уровня знаний, углублению восприятия и налаживанию сотрудничества на международном уровне в области образования...»

«ЭТУ КНИГУ ПРЕДСТАВИЛ ДЛЯ ВАС {FIO} http://www.{URL} Copyright © 2006 Как начать зарабатывать 20 долларов в день, участвуя в программе Google AdSense ОГЛАВЛЕНИЕ ЧТО ТАКОЕ GOOGLE ADSENSE 6 ШАГОВ К ДОМИНИРОВАНИЮ В ADSENSE КАК ИЗБЕЖАТЬ ОТКАЗА В РЕГИСТРАЦИИ В GOOGLE ADSENSE УВЕЛИЧИВАЕМ НАШ ДОХОД В GOOGLE ADSENSE 5 САМЫХ РАСПРОСТРАНЕННЫХ ОШИБОК, СОВЕРШАЕМЫХ В ADSENSE, КОТОРЫХ ВАМ НАДО ИЗБЕГАТЬ ЧАСТО ЗАДАВАЕМЫЕ ВОПРОСЫ ЧТО ТАКОЕ GOOGLE ADSENSE? СКОЛЬКО СТОИТ УЧАСТИЕ В ПРОГРАММЕ СКОЛЬКО Я БУДУ...»

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

«Бьерн Андерсен Том Фагерхоуд ASQ Quality Press Милуоки, Висконсин 2 Root Cause Analysis - Simplified Tools and Techniques Введение Вам нравится Ваша работа? Задайте этот вопрос любому человеку и большинство людей ответит делая акцент не на положительных сторонах своей работы, а на желаемых улучшениях. Говоря в общем смысле, люди принимают как должное то, что работает хорошо и хотят улучшить то, что работает плохо. Таково же отношение (и это справедливо!) тех, кто занимается улучшением качества....»

«сц го и со о О. о сц и Іп ргоГипёит СААЕТЕЕШ ИСТОРИЧЕСКАЯ КНИГА Ася Пекуровская Герметический М И Л И м м ан у и л а ^ с щ г д а По ту сторону зрения и слуха Санкт-Петербург АЛЕТЕЙЯ 2010 УДК 141.3+929Кант ББК 87.3 П24 П екуровская А. П24 Герметический мир Иммануила Канта: По ту сторону зрения и слуха / Ася Пекуровская. — СПб. : Алетейя, 2010. — 568 с. — (Серия Тела мысли). І5ВЫ 978-5-91419-308-6 Как и обо всех культовых фигурах, о Канте известно, кажется, всё и очень немногое. А то, что...»

«Организаторы: • ФГБУ Научный центр акушерства, гинекологии и перинатологии им. В.И. Кулакова Минздрава России • Российское общество акушеров-гинекологов • Российское общество по контрацепции • Ассоциация по патологии шейки матки и кольпоскопии • Конгресс-оператор: ООО МЕДИ Экспо Место проведения: Москва, ул. Академика Опарина, д.4 ФГБУ Научный центр акушерства, гинекологии и перинатологии им. В.И. Кулакова Минздрава России Дата проведения: 12–15 марта 2013 года V Всероссийский...»






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

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