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

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

Автор: Лаусмаа, Тыну Мартинович

Автор: Лаусмаа, Тыну Мартинович

Шифр специальности: 05.13.01

Научная степень: Кандидатская

Год защиты: 1984

Место защиты: Таллин

Количество страниц: 187 c. ил

Артикул: 4028267

Стоимость: 250 руб.

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ТАБЛИЦА ОБОЗНАЧЕНИЙ .
УКАЗАТЕЛЬ ТЕРМИНОВ
Глава I АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ПОНЯТИЯ ЭНТРОПИИ
1.1. Основные определения
1.2. Свойства энтропии для разбиений .
1.3. Отношение квазинезависимости для разбиений
1.4. Отношение независимости для разбиений .
1.5. Энтропия как полуоценка для решетки разбиений
1.6. Функция расстояния между разбиениями Выводы .
Глава II ИНФОРМАЦИОННЫЕ СВОЙСТВА СИСТЕМЫ РАЗБИЕНИЙ
2.1. Основные определения
2.2. Независимость и взаимная независимость систем разбиений .
2.3. Изоморфизм систем разбиений .
2.4. Отношение порядка в системе разбиений
2.5. Подструктуры
2.6. Информационная связка
Выводы
Глава III ИНФОРМАЦИОННЫЕ СООТНОШЕНИЙ ДЛЯ ПАР
РАЗБИЕНИЙ .
3.1. Основные определения
3.2. Информационные соотношения для
каналов
3.3. Свойства информационной связки для
булевых функций . ш
Выводы
Глава 1У КОМЬИНАТОРНОИНФОРМАЦИОННАЯ ОЦЕНКА СЛОЖНОСТИ
ПРИ СИНТЕЗЕ ДИСКРЕТНЫХ УПРАВЛЯЮЩИХ УСТРОЙСТВ 4
4.1. Оценка сложности булевых функций
4.2. Декомпозиция конечных автоматов по ИС .
4.3. Реализация булевых функций на сети
мультиплексоров .4Я
Выводы .
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ I
ПРИЛОЖЕНИЕ 2
ПРИЛОЖЕНИЕ 3 Ш
ПРИЛОЖЕНИЕ 4.
ЛИТЕРАТУРА


Применение понятия ИС позволяет нам оценивать различные варианты декомпозиции, учитывая при этом с единой позиции как внутреннюю сложность компонентов, так и сложность соединения компонентов, что в принципе невозможно при понимании сложности как минимального количества элементов объекта, необходимых для его реализации /- /. Также и ИС в сущности ближе к интуитивному представлению сложности как меры силы взаимосвязи между компонентами объекта, нежели понимание сложности как количества элементов объекта. Использование ИС при декомпозиционном синтезе ДУУ позволяет, начиная с ранних стадий, в процессе синтеза оценивать альтернативные варианты и тем самым значительно сократить перебор вариантов. Разбиение как алгебраическая интерпретация информации. В качестве интерпретации информации в настоящей работе выбрано разбиение как гомоморфный образ самого простого объекта - множества, определяя информацию о каком-то конечном множестве заданием соответствующего разбиения на том же множестве. Впервые разбиение было использовано в качестве алгебраического эквивалента понятия информации Дж. Хартманисом и P. Ими была и дана интерпретация произведения двух разбиений как суммарной информации, выраженной через эти разбиения, и суммы двух разбиений как информации, общей для этих разбиений. Эта интерпретация позволяет в решетке разбиений выражать все нужные информационные операции. Однако при сравнении разбиений Дж. Хартманис и P. E. Стирнз остались на качественном уровне, используя для этой цели только отношение частичного порядка между разбиениями. В рамках такого подхода многие важные декомпозиционные проблемы остаются нерешенными, ибо без количественной оценки разбиения большинство разбиений оказываются несравнимыми, не говоря о том, что невозможно оценивать количественно информационную зависимость между разбиениями. Для количественной оценки информационной содержимости разбиения будем пользоваться понятием энтропии. Приводимое в работе алгебраическое обоснование энтропии базируется на понятии полуоценки для решеток разбиений и является продолжением попытки У. Накамуры / / при обосновании информации на базе теории решеток / /. Наш подход является логически независимым от вероятностного и алгоритмического подходов и позволяет получить чисто алгебраическую основу информации. Представимая концепция информации представляет собой одну разновидность невероятностной информации /- /. С другой стороны, приведенный подход является естественным развитием теории решеток разбиений / - / и поэтому многие результаты представляют и самостоятельное значение для теории решеток разбиений. Учитывая, что любую конечную решетку можно вложить в решетку всевозможных разбиений на каком-то конечном множестве // эти же результаты обобщаются и для произвольных решеток. Ст. У &? Со^1б1) ). Г(* ( X ) его вес % (6Л = " X II . Н С^сС X)) — ~ X фд С&с ) ^ ) . Оказывается, что энтропия /У представляет собой нижнюю полуоценку /ТУ / для решетки всевозможных разбиений на каком-то множестве X , т. П^ СX) и (X) , в работе вводится отношение квазинезависимости Т для разбиений, что является обобщением известного понятия независимости* Именно считаем, что разбиение П~> (X) является квазинезависимым относительно ГГ;(Х) (П;(Х)Т П/(Х)) , если сужение ГТ/ (В*) разбиения 7ТС* (X) на блок 6 /Т. ГГ(- С 8) при & ? Щ и с 6 , т. Я;(в/*)аГГ? В) . Теорема 1. IV) для любых /5 6 + Г7у , 5/°° € /Г4* и 6. Теорема 1. Кваэинезависимость представляет собой отношение толерантности, т. Ъ + ? В & П[' + П]' сужения ГГ(' ( В) и ГГ: С б) независимы С т. VВ** В/? Пусть О (Г? ГГС* ( X) на всевозможных конечных множествах X . О (П;) представляет собой нижнюю полуоценку для каждой решетки разбиений <С ( X) , т. Сб) ОСЩ) + (3(^) ^ •? Тс'+ Ц). ИЗ) Для квазинезависимых разбиений неравенство полуоценки превращает^ равенство, т. Теорема 1. Стт;)- а НСЪ) +1 , где (X и $ некоторые положительные константы. Теорема 1. Это позволяет рассматривать энтропию разбиения как количественную оценку его информационной содержимости. При декомпозиционном синтезе ДУУ часто возникает надобность оценивать различие между разбиениями. Н(П}')- В работе показывается, что относительно расстояния с[ все сравнимые между собой разбиения находятся на одной и той же прямой, т. Т{ Г7^- ?

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.254, запросов: 244