WWW.KNIGI.KONFLIB.RU

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

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

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

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

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

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

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

В связи с этими трудностями в 1949 г. К. Э. Шенноном [1] был предложен подход, заключающийся в следующем видоизменении задачи синтеза. Полагаем, что где максимум берется по всем функциям от n переменных. Требуется получить возможно лучшие оценки для L U (n) (в настоящее время она называется функцией Шеннона) и предложить метод синтеза, то есть построения, который по каждой функции от n переменных строит реализующую ее схему сложности, близкой к L U (n).

В упомянутой работе К. Э. Шенноном был найден порядок функции LU (n) в случае контактных схем и предложен, соответственно, оптимальный по порядку, в указанном выше смысле, метод синтеза контактных схем.

Асимптотически оптимальные методы синтеза были разработаны О. Б. Лупановым [2, 5]. В этих работах получена и асимптотика функции Шеннона для многих классов управляющих систем. Из результатов О. Б. Лупанова вытекает, что почти все булевы функции от данного числа переменных являются асимптотически самыми сложными, причем эта сложность очень велика. Так, например, в случае умножения 100-разрядных чисел Шенноновская оценка составляет примерно 2200 элементов.

Возникает задача выделения классов функций, допускающих относительно простую реализацию, и разработки асимптотически оптимальных методов синтеза схем для функций из этих классов. То есть, если задан класс A булевых функций, то требуется для каждой функции из An (где An множество функций из A, зависящих от первых n переменных) построить реализующую ее схему, близкую по сложности к Последняя величина называется функцией Шеннона для сложности реализации функций из класса A.

Впервые этот вопрос был рассмотрен в упомянутой выше работе К. Э. Шеннона. Первый результат общего характера принадлежит С. В. Яблонскому [10, 11], который построил и изучил, в том числе с точки зрения сложности реализации, континуальное семейство классов булевых функций, инвариантных относительно переименования переменных и подстановок констант.

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

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

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

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

Первый результат в этом направлении был получен С. В. Яблонским и Ю. Г. Потаповым в упомянутой выше работе, где была доказана возможность асимптотически неизбыточного корректирования одного замыкания контакта для контактных схем. Аналогичный результат для размыканий впоследствии был получен Х. А. Мадатяном [15].

Наиболее глубокие результаты были достигнуты Э. И. Нечипоруком [16]–[19], который разработал метод асимптотически неизбыточного корректирования растущего числа обрывов в вентильных схемах. На его основе он установил возможность асимптотически неизlog n быточного корректирования растущего числа размыканий (o( log log n ), где n-число переменных) в контактных схемах, а также одновременно растущего числа размыканий и замыканий в контактно-вентильных и -схемах. Возможность асимптотически неизбыточного корректиlog n рования одновременно растущего числа размыканий (o( log log n )) и замыканий (o( log n )) в контактных схемах была затем установлена Н. П. Редькиным [20, 21] Д. Улигом [22] было показано, что при увеличении асимптотики функции Шеннона не более, чем в два раза, в контактных схемах возможно одновременное корректирование 2o( log n ) замыканий и размыканий.

Вопросы самокорректирования рассматривались и для схем из функциональных элементов (Г. И. Кириенко [23, 24], Улиг [25], С. И. Ортюков [26]), однако в этом случае возникает необходимость использования абсолютно надежных элементов.

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

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

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

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

Исследования, которые здесь излагаются, были проведены А. Е. Андреевым [30].

Разработка этих вопросов привела к необходимости • фактического выхода за пределы двузначной логики, а именно рассмотрения недоопределенных булевых функций, которые понимаются как принимающие на наборах из нулей и единиц три значения 0, 1 и в точках их неопределенности;

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

Функциональные сети становятся основным объектом изучения.

Функциональная сеть реализует частичную булеву функцию, если она является разложением некоторого доопределения этой функции (f доопределение g, если f и g совпадают в тех точках, где g определена). Сложность функциональной сети определяется, исходя из сложности порождающей операции и числа наборов, на которых определены компоненты (рассматриваются и другие характеризации сложности компонент). При этом сложность операции учитывается с очень большим весом (растущим с ростом числа задействованных переменных). Вес компонент растет с уменьшением мощности области определения. Затем по обычной схеме определяется сложность реализации функции как минимум сложности по всем реализующим ее функциональным сетям, и функция Шеннона для класса A как максимальная сложность функций из A n. В качестве неисправностей функциональных сетей рассматриваются замещения компонент либо произвольные, либо на нули и единицы. Классы неисправностей описываются ограничениями на допустимое число замещений.

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

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

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

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

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



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


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

«О законе области О бюджетном процессе в Вологодской области Законодательное Собрание области ПОСТАНОВЛЯЕТ: 1. Принять закон области О бюджетном процессе в Вологодской области. 2. Признать утратившими силу с 1 января 2008 года следующие постановления Законодательного Собрания области: от 20 марта 2002 года № 113 О законе области О бюджетном процессе в Вологодской области; от 10 сентября 2003 года № 519 О законе области О внесении изменения в закон области О бюджетном процессе в Вологодской...»

«www.kodges.ru www.kodges.ru ББК 28.6с 434 Чегодаев А. 434 ПАУКИ И СКОРПИОНЫ. Содержание. Разведение. — М.: АКВАРИУМ БУК, 2003. - 64 с, илл. ISBN 5-94838-062-9 Эта книга посвящена паукообразным. Несмотря на, мягко говоря, предубеждение против пауков и скорпионов, сегодня есть их защитники и любители. О жизни пауков, скорпионов и сольпуг в природе, о возможности их содержать и разводить в домашних условиях рассказывает в этой книге известный ученый. Б Б К 28.6с Охраняется Законом РФ об авторском...»

«Новосибирск Библиотека НГУ 2001 1 Список литературы составлен по материалам каталогов НБ НГУ, библиографических указателей, БД ИНИОН и ряда ретроспективных библиографических пособий на русском и иностранных языках. Описания книг из фонда НБ НГУ сопровождаются шифрами, указанием места хранения и количеством имеющихся экземпляров. Приведено краткое содержание сборников. Список включает материалы с 1931 по 2001 г. Электронная версия рекомендательного списка дополнена новыми материалами с 2002 –...»

«100 рецептов для разных знаков зодиака. Вкусно, полезно, душевно, целебно Анна Мудрова 2 Книга Анна Мудрова. 100 рецептов для разных знаков зодиака. Вкусно, полезно, душевно, целебно скачана с jokibook.ru заходите, у нас всегда много свежих книг! 3 Книга Анна Мудрова. 100 рецептов для разных знаков зодиака. Вкусно, полезно, душевно, целебно скачана с jokibook.ru заходите, у нас всегда много свежих книг! Анна Мудрова 100 рецептов для разных знаков зодиака. Вкусно, полезно, душевно, целебно 4...»

«руководстве Предупреждение — ситуации, которые могут привести к получению травмы вами или кем-либо из окружающих. Внимание — ситуации, которые могут Данное руководство пользователя привести к повреждению устройства или предназначено для ознакомления с функциями и другого оборудования. возможностями телефона. Чтобы сразу приступить Примечание — примечания, советы или к использованию телефона, смотрите разделы дополнительная информация. Знакомство с телефоном, Подготовка телефона к работе См. —...»

«стиля С пробуждением весны мы стряхиваем с себя зимнюю сонливость, становимся более жизнерадостными и энергичными. Мы всегда с нетерпением ожидаем этого времени года и стремимся меняться вместе с природой: блеснуть, удивить себя и других новыми сочетаниями цветов, обновиться и продемонстрировать всем, что солнцем и светом наполняются и наши сердца. Это необычайно просто, когда осознаешь, что вокруг – огромное количество источников вдохновения, помогающих создать неповторимый стиль и каждому...»

«Нефритовое Кружевница Черепаха Салат с пекинской капустой и кольцо ветчиной Полянка Тигровая Праздничный салат Фортепиано с копченой колбасой бухта и плавленым сыром Фантазия Любовница Пчелки Слоеный салат Салат с куриной Салат с Салат с Салат “Ананас” печенью цветком мандаринами с курицей Снегирь Салат с 8 Марта Селедка под шубой с тунцом плавленым сыром ЗАПРЕЩЕНЫ ЛЮБЫЕ ИЗМЕНЕНИЯ В КНИГЕ, А ТАК ЖЕ ЕЕ ПРОДАЖА! Салат Нефритовое кольцо Салат Нефритовое кольцо интересен по оформлению и вкусен за...»

«ГОРОДСКАЯ ДУМА ГОРОДА ТАГАНРОГА РЕШЕНИЕ 27.02.2006 № 198 Об утверждении информации о ходе реализации и финансировании в 2005 году первоочередных мероприятий по оздоровлению окружающей среды г. Таганрога на 2004-2005гг. Заслушав и обсудив информацию Отдела по охране окружающей среды и природных ресурсов о ходе реализации и финансировании в 2005 году первоочередных мероприятий по оздоровлению окружающей среды г. Таганрога на 2004 – 2005г.г., утвержденных Решением Городской Думы от 31.07.2003...»

«© 2004 WEB-Студия НТЦ “АТЛАС” http://www.atlaswebstudio.ru/ http://www.cmsmysite.com/ Данный документ является собственностью НТЦ “Атлас”. Документ не может копироваться, использоваться или передаваться третьим лицам без разрешения автора. Авторские права защищены законодательством Республики Беларусь. Содержание 1. Вход и авторизация 2. Интерфейс системы 3. Управление структурой сайта 4. Редактирование страниц сайта 4.1. Интерфейс модуля 4.2. Описание панели инструментов WYSIWYG-редактора 4.3....»






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

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