О сложности и структуре минимальных самокорректирующихся контактных схем из некоторых классов

• Автор: Валентинов, Евгений Валентинович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 70 с. : ил

Оглавление
1 Введение
1.1 Общая характеристика работы
1.2 Основные определения
1.3 Формулировка полученных результатов
2 О сложности и структуре эквивалентных минимальных контактных схем, корректирующих растущее число неисправностей
2.1 Метрические свойства схем
2.2 Потоки в контактных схемах
2.3 Некоторые критерии самокорректируемое схем . .
2.4 Операции над самокорректирующимися схемами . .
2.5 Универсальные схемы для класса контактных схем, корректирующих фиксированное число замыканий .
2.6 Сведение задачи коррекции растущего числа обрывов к задаче линейного программирования. Построение самокорректирующихся контактных схем
2.7 Подходы к получению нижних оценок
2.8 Сложность коррекции обрывов для функций трех переменных
3 О самокорректирующейся сложности некоторых симметрических периодических булевых функций при растущем числе переменных.
3.1 Сложность реализации симметрических функций. .
3.2 Правильные схемы и их существование
3.3 О вершинах правильных схем

3.4 Структура правильных схем
3.5 Правильные схемы, реализующие периодические функции
3.6 Сложность реализации линейной функции контактными схемами, корректирующими замыкания
Приложение
Программа, вычисляющая значения констант линейной
зависимости сложности
Список литературы

Глава
Введение
1.1 Общая характеристика работы
В теории синтеза управляющих систем одной из основных задан является построение минимальных, то есть наиболее простых, схем. Как известно, наибольшие трудности при этом вызывает доказательство минимальности построенных схем или получение нижних оценок сложности. Если для ”достаточно широких” классов функций есть возможность извлечения практически окончательных нижних оценок из мощностных соображений, то в случае ”узких” классов, или, тем более, конкретных функций, ситуация значительно усложняется. Первый нетривиальный результат в этой области принадлежит К.Кардо [39] - им доказана минимальность известной контактной схемы для линейной функции. Для схем из функциональных элементов результаты данного направления содержатся, например, в статьях [13, 27, 28, 29, 32, 33, 37].
Задача синтеза самокорректирующихся контактных схем (КС) была впервые поставлена в работе [24] и в дальнейшем решению этой задачи был посвящен целый ряд работ различных авторов (см. напр. [1,31,23]), а связанные с пей исследования продолжаются вплоть до настоящего времени. В некоторых работах был рассмотрен случай малого числа переменных и получены каталоги минимальных схем. Так, в работах [41],[12] были получены каталоги минимальных КС, для всех функций от трех и четырех переменных соответственно. В работе [2] был получен каталог минимальных КС, корректирующих одно замыкание, для

Утверждение 2.8.Т. Для любого г > 0 выполняется:
ігд(/і5) >6,5 г, (2.11)
ігД(/іб)> 3,75г. (2.12)
Заметим, что оценка (2.12) была также доказана в работе [3].
Таким образом утверждения 2.8.2-2.8.7 дают почти точные оценки сложности Тг,1(/) для любых целых г, г > 0 и булевых функций трех переменных /. А именно, для функций, инверсноподобных функции /к; и г таких, что г(то<Щ = 1, нижняя и верхняя оценки отличаются на единицу, для других г и функций / нижние и верхние оценки совпадают.