Бакалавр
Дипломные и курсовые на заказ

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

Диссертация: О сложности и структуре минимальных самокорректирующихся контактных схем из некоторых классов
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В работе получен каталог минимальных КС для всех монотонных функций от пяти переменных. В работах был предложен метод, позволяющий получать нетривиальные нижние оценки для функций обладающих некоторыми свойствами. В частности, в них были получены минимальные КС для произвольной линейной функции, корректирующие любое заданное число обрывов. Одним из самых простых и естественных классов булевых… Читать ещё >

Содержание

  • Введение
    • 1. 1. Общая характеристика работы
    • 1. 2. Основные определения
    • 1. 3. Формулировка полученных результатов
  • 2. О сложности и структуре эквивалентных минимальных контактных схем, корректирующих растущее число неисправностей
    • 2. 1. Метрические свойства схем
    • 2. 2. Потоки в контактных схемах
    • 2. 3. Некоторые критерии самокорректируемое&trade- схем
    • 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. — С. 147 172.
  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. — С. 171 183.
  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. — С. 119 138.
  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.
Заполнить форму текущей работой

Сдать сессию!