О сложности и структуре минимальных самокорректирующихся контактных схем из некоторых классов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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] был получен каталог минимальных КС, корректирующих одно замыкание, для всех функций от трех переменных. Аналогичный результат для одного обрыва получен в работе [25]. Сравнивая значения сложности, полученные в этих работах, можно видеть, что для некоторых функций трех переменных сложность коррекции одного замыкания превосходит сложность коррекции одного обрыва. Это дает основания предполагать, что указанные типы неисправностей принципиально отличаются: корректировать замыкания в общем случае труднее, чем размыкания .

В работе [16] получен каталог минимальных КС для всех монотонных функций от пяти переменных. В работах[19,20] был предложен метод, позволяющий получать нетривиальные нижние оценки для функций обладающих некоторыми свойствами. В частности, в них были получены минимальные КС для произвольной линейной функции, корректирующие любое заданное число обрывов.

Одним из самых простых и естественных классов булевых функций является класс симметрических булевых функций. Первые результаты о сложности их реализации были получены Шенноном [44, 45]. В настоящее время о сложности реализации симметрических функций в основных классах управляющих систем известно следующее:

1) Схемы из функциональных элементов в полном базисе: сложность функций п переменных есть О(п) (см. напр. [21]).

2) Формулы в полном базисе: сложность всех симметрических функций, кроме 16 функций вида © • (х\ © • ■ • © хп) © 82 • х\ ■ ■ ■ хп © $3 • х\ ■ ■ ■ хп равняется О (/г log log п) (см. [42,43,34,35, 46]). Для базиса из всех не более чем двуместных функций имеет место оценка O(nlogn) (см. [40]).

3) Контактные схемы: сложность элементарных симметрических функций не превосходит 0(п log2 п/ log log п) [22], а монотонных симметрических функций - величины О(п log4 п/ log2 log п) [17]. Сложность элемен тарных периодических функций при больших п равняется An — В, где А легко выражается через период [14].

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

1) Контактные схемы: сложность есть An — А (см. [39]).

2) Контактные схемы, корректирующие г, г ^ О обрывов: сложность равна 4((n - 2)([r/2] + 1) + г + 1) (см. [19,20]).

2) Контактные схемы, корректирующие 1 замыкание: сложность не меньше, чем 6п — А (см. [31]).

4) Контактные схемы, корректирующие 1 замыкание и 1 размыкание: сложность равна 8п (см. [26]).

Результаты работы программы для некоторых функций трех переменных изложены в утверждении 2.8.7.

1. Андреев А.Е. Универсальный принцип самокорректирования. - Математический сборник, 1985. - Т.127(169), N 6. - С. 147172.

2. Быков А.Г. Каталог самокорректирующихся контактных схем для функций трех переменных (случай замыкания). -Проблемы кибернетики, вып. 19. М.гНаука, 1967. - С. 39-46.

3. Валентинов Е.В. О сложности реализации булевых функций от малого числа переменных контактными схемами, корректирующими произвольное число обрывов. Дипломная работа, кафедра математической кибернетики ф-та ВМК МГУ, 1998г.

4. Валентинов Е.В. О сложности булевых функций от трех переменных в классе контактных схем, корректирующих обрывы. Тр. II Межд.конф. "Дискретные модели в теории управляющих систем" (Красновидово, 23-28 июня 1997 г), -М.: Диалог МГУ, 1997. С. 10-14.

5. Валентинов Е.В. О сложности реализации произвольной булевой контактными схемами, корректирующими обрывы. Тр. III Межд.конф. "Дискретные модели в теории управляющих систем" (Красновидово, 22-27 июня 1998 г), - М.: Диалог МГУ, 1998. - С. 13-16.

6. Валентинов Е.В. О сложности реализации булевых функций самокорректирующимися контактными схемами. Тр. IV Межд.конф. "Дискретные модели в теории управляющих систем" (Красновидово, 19-25 июня 2000 г), - М.: Макс Пресс,2000. С. 144-145.

7. Васильев Ф.П. Численные методы решения экстремальных задач. М. 1980 г.

8. Васильев Ю.Л. Минимальные контактные схемы для булевых функций четырех переменных. ДАН СССР 1959 т. 127, N 2. - С. 242-245.

9. Горелик Е.С. О сложности реализации элементарных конъюнкций и дизъюнкций в базисе {.г|;г/}. Сб. "Проблемы кибернетики", вып. 26. - М.: Наука, 1973. - С. 27-36.

10. Гринчук М.И. О сложности реализации симметрических булевых функций контактными схемами. Сб. Математические вопросы кибернетики, выи. -3. - М.гНаука, 1991. - С. 77-104.

11. Грехем Р. Начала теории Рамсея. М.:Мир, 1984. - 96с.

12. Карпова Н.А. Минимальные схемы из замыкающих контактов для монотонных функций пяти переменных. Проблемы кибернетики, вып. 26. - М.:Наука 1973. - С. 53-94.

13. Красулина Е.Г. О реализации монотонных симметрических функций алгебры логики контактными схемами. Вестник Моск. ун-та, сер 15, Вычислительная математика и кибернетика, 1987. 2. - С. 69-71.

14. Кристофидес Н. Теория графов. Алгоритмический подход. -М.:Мир, 1978. с. 323-325.

15. Ложкин С.А. Об одном методе получения линейных нижних оценок сложности контактных схем и структуре минимальных схем для некоторых функций. сб. Методы и системы технической диагностики, вып 18. Изд. Саратовского университета 1993. - С. 110-112.

16. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: изд-во МГУ, 1984.

17. Лупанов О.Б. К вопросу о реализации симметрических функций алгебры логики контактными схемами. сб. "Проблемы кибернетики", вып. 15. - М.: Наука, 1965. - С. 85-99.

18. Нечипорук Э.И. О топологических принципах самокорректирования. Проблемы кибернетики, вып. 21. - М.:Наука, 1969. -С. 5-102.68

19. Потапов Ю.Г., Яблонский С.В. О синтезе самокорректирующихся контактных схем. ДАН СССР 1960, т.134, N 3. - С. 544-547.

20. Рабинович В.М. Каталог самокорректирующихся контактных схем для функций трех переменных (случай размыкания). -Проблемы кибернетики, вып. 21. М.:Наука 1969. - С. 171183.

21. Рабинович В.М. О самокорректирующихся схемах для счетчика четности. Проблемы кибернетики, вып.17. М.гНаука, 1966. С. 227-231.

22. Редькин Н.П. Доказательство минимальности некоторых схем из функциональных элементов. Сб. "Проблемы кибернетики", вып. 23. - М.: Наука, 1970. - С. 83-101.

23. Редькин Н.П. О минимальной реализации линейной функции схемой из функциональных элементов. Кибернетика, 1971, 6. - С. 31-38.

24. Редькин Н.П. О минимальной реализации двоичного сумматора. Сб. "Проблемы кибернетики", вып. 38. - М.: Наука, 1981. - С. 181-216.

25. Редькин Н.П. Надежность и диагностика схем. М.:изд-во МГУ, 1992.

26. Редькин Н.П. О самокорректировании контактных схем. -Проблемы кибернетики, вып. 33. М.: Наука, 1978. - С. 119138.

27. Сопруненко Е.П. О минимальной реализации некоторых функций схемами из функциональных элументов. сб. "'Проблемы кибернетики", вып. 15. - м.: Наука, 1965. - С. 117-134.

28. Стокмейер ЛДж. О комбинационной сложности некоторых симметрических булевых функций. Киб. сб., вып. 16, н.с. -М.:Мир, 1979. - С. 45-61.

29. Ходес JI., Шпекер Е. Длины формул и исключение кванторов.- Киб. сб., вып. 10, н.с. М.:Мир, 1973. С. 99-113.

30. Храпченко В.М. О сложности реализации симметрических функций алгебры логики формулами в конечных базисах, сб. "Проблемы кибернетики", вып. 31. М.: Наука, 1976. - С. 231-234.

31. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1972.

32. Шнорр К.П. Комбинационная сложность эквивалентности. Киб.сб., вып.16, н.с. М.:Мир, 1979. - С. 74-81.

33. Яблонский С.В. Основные понятия кибернетики. Проблемы кибернетики, Вып. 2. - М.:Физматгиз,1959.

34. Cardot, X. Quelques resiiltats sur rapplication de l'algebre de Boole a la synthese des circuits a relais. Annales des Telecommunictions, 7, 2, 1952, 75-84.

35. Fischer M.J., Meyer A.R., Paterson M.S. O(nlogn) lower bounds on length of Boolean formulas. SIAM J.Comput., 11, 3, 1962, 416-427.

36. Higonnet В., Grea R. Etude logique des circuits electriques et des System binaries. Paris, 1955.

37. Paterson M.S. An intodution to Boolean fmction complexity.— Aterisque

38. Pudlak P. Bounds for Hodes-Specker theorem. Lecture Notes in Computer Scence, 171, Springer-Verlag, NY, 1984, 421-445.

39. Shannon C.E. Asymbolic analisys of relay and switching circuits.- Trans. AIEE, 57, 1938, 713-722.

40. Shannon C.E. The synthesis of two-terminal switching circuits. -Bell Syst. Techn. J., 28, 1, 1949, 59-98.

41. Specker E. Elimination von Quatoren und Lange von Formeln (Abstract). J. Svmb. Logic, 32, 4, 1967, 567-568.