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

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

Содержание
Введение.

Глава 1. Состояние проблемы и основные понятия

1.1. Краткая характеристика состояния проблемы

1.2. Функции на полурештках

1.3. Переключательные схемы и их поведение

1.4. Постановка задач реализации функций на полурештках

Глава 2. Условия реализуемости функций на полурештках

2.1. Необходимое условие реализуемости функции на полурештках

2.2. Необходимые и достаточные условия реализуемости функций со значениями в полурештке Р2.
2.3. Необходимые и достаточные условия реализуемости функций со значениями в полурештке 1
2.4. Условия реализуемости функций проводимости сетями с мостиковыми соединениями
Глава 3. Методы реализации функций на полурештках
3.1. Реализация функций проводимости со значениями в Р2.
3.1.1.1реализаци я.
3.1.2.2реализаци я.
3.2. Реализация функций проводимости со значениями в Рг.
3.3. Реализация систем функций на полурештках
3.3.1. Реализация систем функций со значениями в Р2.
3.3.2. Реализация систем функций со значениями в з.
Глава 4. Реализация функций на полурешетках схемами, функционально
9 устойчивыми к состязаниям.
4.1. Определение состязаний.
4.2. Тесты на наличие состязаний
4.3. Совместимость переходов
4.4. Условия реализуемости со свойством функциональной устойчивости к состязаниям.
4.5. Синтез функционально устойчивых схем.
Заключение
Литература


Все полученные в диссертации теоретические результаты имеют строгое математическое доказательство. Кроме того, работоспособность методов синтеза подтверждена экспериментально на ряде случайно сгенерированных и известных по литературе примеров. Частным случаем приведенного в диссертации определения состязаний для функций на полурешётках является известное ранее определение этого понятия для булевых функций. Теоретическая и прикладная ценность. В диссертационной работе решён ряд задач, связанных с реализуемостью функций на полурешётках в заданном неполном базисе. Апробация работы. Результаты диссертации обсуждались на совместных научных семинарах кафедр защиты информации и криптографии, программирования, информационных технологий в исследовании дискретных структур Томского государственного университета, докладывались на XV Международной школе-семинаре «Синтез и сложность управляющих систем» (Новосибирск, г. XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, г. Всероссийских конференциях «Новые информационные технологии в исследовании сложных структур» (Томск, и гг. Иркутск, г. Сибирских школах-семинарах «Компьютерная безопасность и криптография» (Томск, и гг. Публикации. Основные результаты диссертации опубликованы в работах [-]. Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и библиографии, включающей наименования; её объём -2 стр. Всюду под функцией будем иметь в виду функцию на полурешётках. В первой главе приводится обзор литературы, формулируются основные понятия и ставятся задачи, которые решаются в последующих главах. Строго определяются понятия переключательных элементов, сетей, схем и их функций при тех ограничениях, при которых в последующих главах решается задача реализации функций на полурешётках. Главы 2 и 4 носят теоретический характер, основные результаты в них формулируются в виде теорем. Глава 3 - прикладного характера, основными результатами в ней являются алгоритмы синтеза. Вторая глава диссертации посвящена формулировке условий реализуемости функций на полурешётках переключательными схемами. В. Вводится понятие (5, а)-раздслимости элементов полурешётки множеством функций, определённых на этой полурешётке, и отношение у сравнения проводимостей. Доказывается, что необходимым и достаточным условием реализуемости функции /однокаскадной схемой в ЛБ-базисе В является (1,0)-разделимость определённых пар элементов из области определения/множеством базисных функций, а необходимым и достаточным условием реализуемости функции/ двухкаскадной схемой в том же базисе является квазимонотонность отношения Г/^ и наличие в базисе элемента, функция которого не сохраняет отношения у. В последнем разделе главы устанавливается, что классы функций, реализуемых в ЛБ-базисе параллельно-последовательными схемами и схемами с мостиковыми соединениями, совпадают. Доказательства достаточности условий теорем главы 2 конструктивны и дают методы построения схем, реализующих функции на полурешётках. Будучи предназначенными лишь для доказательства существования схем при выполнении достаточных условий, эти методы доставляют, как правило, избыточные схемы. В главе 3 приводятся практические методы синтеза, направленные на получение более простых схем. Описывается модификация декомпозиционного параметрического метода В. Л. Павлова [], предназначенная для синтеза параллельно-последовательных сетей, реализующих функции со значениями в полурешётке ? Для данных функции / и множества функций в вводится понятие (/ <7)-дополняю1цей системы, существование которой является необходимым и достаточным условием реализуемости функции/в базисе элементов с функциями из в. Формулируются два алгоритма построения (/ ^-дополняющих систем, один из которых позволяет получать схемы с минимальным общим числом ячеек, второй минимизирует верхнюю оценку сложности реализации функции / Формулируется метод реализации функций со значениями в полурешётке Р3 схемами в ЛБ-базисе, а также методы реализации систем функций со значениями в Рг и в Р$.