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

• Автор: Лаусмаа, Тыну Мартинович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Таллин
• Количество страниц: 187 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ТАБЛИЦА ОБОЗНАЧЕНИЙ .

УКАЗАТЕЛЬ ТЕРМИНОВ

Глава 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^- ?