Результаты, полученные на кафедре математической кибернетики факультета ВМК МГУ в области теории синтеза и контроля дискретных управляющих систем

Аннотация

В статье приводятся основные результаты, полученные с 2000 по 2024 гг. на кафедре математической кибернетики факультета ВМК МГУ в области теории синтеза и контроля дискретных управляющих систем.

Литература

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

2. Shannon C.E. The synthesis of two-terminal switching circuits // Bell Syst. Techn. 1949. 28. No 1. Р. 20-98.

3. Лупанов О.Б. О синтезе контактных схем // ДАН СССР. 1958. 119. No 1. С. 23-26.

4. Лупанов О.Б. Об одном методе синтеза схем // Изв. вузов. Радиофизика, 1958. 1. No 1. С. 120-140.

5. Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. С. 61-80.

6. Лупанов О.Б. О сложности реализации функций алгебры логики линейно-контактными схемами // Проблемы кибернетики. Вып. 11. М.: Наука, 1964. С. 25-48.

7. Ложкин С.А. Асимптотические оценки высокой степени точности для сложности управляющих систем: Дис....д-ра физ.-мат. наук. М., МГУ имени М.В. Ломоносова, 1997.

8. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука; Физматлит, 1996. С. 189-214.

9. Никитин А.А. О реализации функций алгебры логики автоматными конвейерными схемами: Дис. ... канд. физ.-мат. наук. М., МГУ имени М.В. Ломоносова, 2000.

10. Никитин А.А. О сложности реализации функций алгебры логики в некоторых классах автоматных схем // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 1999. No 3. С. 41-49.

11. Никитин А.А. Оценки высокой степени точности для сложности реализации функций алгебры логики в некоторых классах автоматных схем // Вестн. Нижегородского гос. ун-та. Математическое моделирование и оптимальное управление. Вып. 1(22), 2000. С. 133-143.

12. Грибок С.В. О реализации функций алгебры логики в некоторых классах программ: Дис. ... канд. физ.-мат. наук. М., МГУ имени М.В. Ломоносова, 2003.

13. Жуков В.В. Методы синтеза и оценки сложности программ с некоторыми структурными ограничениями: Дис. ... канд. физ.-мат. наук. М., МГУ имени М.В. Ломоносова, 2020.

14. Грибок С.В. Об одной модели рекурсивных схем из функциональных элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2002. No 4. С. 31-36.

15. Жуков В.В. Асимптотически наилучший метод синтеза булевых рекурсивных схем ограниченной глубины // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2017. No 4. С. 29-35.

16. Жуков В.В. Методы синтеза бинарных программ, допускающих рекурсивный вызов процедур // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2021. No 3. С. 3-12.

17. Жуков В.В., Ложкин С.А. Асимптотически наилучший метод синтеза булевых рекурсивных схем // Дискретная математика. 2019. 31. No 1. С. 99-110.

18. Кузьмин В.А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Вып. 29. Новосибирск: Институт математики СО АН СССР, 1976. С. 11-39.

19. Касим-Заде О.М. О сложности реализации функций в одном классе алгоритмов // Материалы ІХ межгосударственной школы-семинара "Синтез и сложность управляющих систем". М.: Изд-во механико-математического факультета МГУ, 1999. С 25-30.

20. Шиганов А.Е. Синтез схем контактного типа с ограничениями на смежные контакты: Дис. канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2010.

21. Шиганов А.Е. О синтезе ориентированных контактных схем с некоторыми ограничениями на смежные контакты // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2009. No 3. С. 46-52.

22. Шиганов А.Е. О сложности ориентированных контактных схем с ограниченной полустепенью исхода // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2009. 151. No 2. С. 164-172.

23. Lozhkin S.A., Shiganov A.E. High accuracy asymptotic bounds on the BDD size and wright of the hurdest functions // Fundementa Informaticae. 104. 2010. Р. 239-253.

24. Шуплецов М.С. Методы синтеза и оценки сложности схем, построенных из элементов предикатного типа: Дис. канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2011.

25. Шуплецов М.С. Оценки высокой степени точности для сложности предикатных схем в некоторых базисах // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2009. 151. No 2. С. 173-184.

26. Коноводов В.А. Методы синтеза и оценки сложности схем с некоторыми структурными ограничениями: Дис. ... канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2015.

27. Ложкин С.А., Коноводов В.А. О синтезе и сложности формул с ограниченной глубиной альтернирования // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2012. No 2. С. 28-36.

28. Ложкин С.А., Коноводов В.А. О сложности реализации булевых функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования 3 // Вестн. Моск. ун-та. Матем. Мех. 2014. No 3. С. 14-19.

29. Коноводов В.А. Некоторые особенности задачи синтеза булевых формул в полных базисах с прямыми и итеративными входами // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2014. 156. No 3. С. 76-83.

30. Ложкин С.А., Коноводов В.А. О сложности формул алгебры логики в некоторых полных базисах, состоящих из элементов с прямыми и итеративными входами // Изв. высших учеб. заведений. Поволжский регион. Физ.-матем. науки. 2015. No 2. С. 55-68.

31. Ложкин С.А., Коноводов В.А. Оценки высокой степени точности для сложности булевых формул в некоторых базисах из элементов с прямыми и итеративными входами // Изв. высших учеб. заведений. Поволжский регион. Физ.-матем. науки. 2015. No 2. С. 16-30.

32. Ложкин С.А. Уточненные оценки функции Шеннона для сложности схем из функциональных элементов // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 2022. No 3. С. 32-40.

33. Ложкин С.А. Уточненные оценки функции Шеннона для сложности схем из некоторых классов // Математические вопросы кибернетики. Вып. 21. М.: ИПМ им. М.В. Келдыша, 2023. С. 168-193.

34. Ложкин С.А. О глубине функций алгебры логики в произвольном полном базисе // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 1996. No 2. С. 80-82.

35. Ложкин С.А. О синтезе формул, сложность и глубина которых не превосходит асимптотически наилучших оценок высокой степени точности // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 2007. No 3. С. 20-26.

36. Данилов Б.Р. Асимптотически наилучшие оценки для некоторых функционалов глубины и задержки схем из функциональных элементов: Дисс. ... канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2016.

37. Ложкин С.А., Данилов Б.Р. О задержке схем из функциональных элементов в модели с произвольным распределением задержек элементов базиса по входам и выходным наборам // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2013. No 4. С. 25-33.

38. Данилов Б.Р. О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов // Изв. высших учеб. заведений. Поволжский регион. Физ.-матем. науки. 2014. 3. No 31. С. 78-100.

39. Данилов Б.Р. Об одновременной оптимизации формул по сложности и задержке на наборах в модели с задержками соединений между элементами // Изв. высших учеб. заведений. Поволжский регион. Физ.-матем. науки. 2015. 4. No 36. С. 58-77.

40. Седелев О.Б. О реализации функций алгебры логики схемами из некоторых классов, вложенными в гиперкубы: Дис. канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2008.

41. Ложкин С.А., Седелев О.Б. О реализации функций алгебры логики BDD, вложенными в единичный куб // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2006. No 4. С. 29-35.

42. Седелев О.Б. Реализация функций алгебры логики схемами из функциональных элементов, вложенными в единичный куб // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2008. No 1. С. 44-50.

43. Ложкин С.А., Довгалюк Е.Л., Садовников О.А. О сложности и глубине вложенных в единичный куб схем, реализующих булевы функции // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. No 3. С. 41-48.

44. Ложкин С.А., Довгалюк Е.Л. О глубине схем, вложенных в единичный куб и реализующих типичные булевы функции // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. No 4. С. 33-36.

45. Власов Н.В. О сложности мультиплексорных функций в некоторых классах схем: Дис. ... канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2013.

46. Ложкин С.А., Власов Н.В. О сложности мультиплексорной функции в классе π-схем // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2009. 151. No 2. С. 98-106.

47. Ложкин С.А., Власов Н.В. О глубине мультиплексорной функции //Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2011. No 2. С. 40-46.

48. Власов Н.В. О сложности мультиплексорной функции в классе формул // Вестн. Нижегородского гос. ун-та им. Н.В. Лобачевского, 2012. No 5. С. 38-41.

49. Ложкин С.А. О глубине мультиплексорной функции от "небольшого" числа адресных переменных // Математические заметки. 2024. 115. No 5. С. 741-748.

50. Ложкин С.А., Зизов В.С. Уточненные оценки сложности дешифратора в модели клеточных схем из функциональных и коммутационных элементов // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2020. 162. No 2. С. 322-334.

51. Ложкин С.А., Зизов В.С. Асимптотически точные оценки для площади мультиплексоров модели клеточных схем // Дискретная математика, 2022. 34. No 4. С. 52-68.

52. Валентинов Е.В. О сложности и структуре минимальных самокорректирующихся контактных схем из некоторых классов: Дис. ... канд. физ-мат. наук. М., МГУ им. М.В. Ломоносова, 2001.

53. Валентинов Е.В. О сложности самокорректирующихся контактных схем при растущем числе обрывов // Вестн. Нижегородского гос. ун-та. Математическое моделирование и оптимальное управление, 2000. Вып. 1(22). С. 36-42.

54. Долгополова А.В. Задача синтеза и проблема полноты для одного класса схем из функциональных элементов, связанных с электронными схемами: Дис... канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2003.

55. Долгополова А.В. Асимптотическое поведение функции Шеннона для одного класса схем из функциональных элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 1997. No 1. С. 37-41.

56. Aleksandrova N.E., Romanov D.S. The length of a single fault detection test for constant- nonpreserving element insertions // Comput. Math. Model. 2020, 31. 4. Р. 484-493.

57. Albek М.K., Romanov D.S. On diagnostic test sets for local mirror reflections on circuit inputs // Math. Notes, 2024. 115. N 5. Р. 837-841.

58. Antiufeev G.V. Diagnostic tests under shifts with fixed filling tuple // Discr. Math. Appl. 2021. 31. 5. Р. 309-313.

59. Antyufeev G.V., Romanov D.S. Tests with stuck-at and shift faults on circuit inputs // Comput. Math. Model. 2020. 31. N 4. Р. 494-500.

60. Antyufeev G.V., Romanov D.S. On test sets concerning local stuck-at faults of fixed multiplicity at the inputs of circuits // Math. Notes. 2023. 114. N 3. Р. 397-402.

61. Кузнецов И.А., Романов Д.С. О полных проверяющих тестах относительно локальных слипаний переменных в булевых функциях // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2009. 151. N 2. С. 90-97.

62. Kurbatskaia V.K. Tests concerning certain types of faults at the scheme inputs // Moscow Univer. Comput. Math. and Cybern. 2019. 43. No 3. Р. 112-117.

63. Лопунов М.А. О проверяющих тестах относительно локальных перестановок входов схем // Интеллектуальные системы. Теория и приложения. 2021. 25. No 4. С. 153-156.

64. Любич И.Г. Улучшение верхней оценки функции Шеннона длины единичных диагностических тестов относительно инверсных неисправностей // Интеллектуальные системы. Теория и приложения. 2021. 25. No 4. C. 157-160.

65. Lyubich I.G., Romanov D.S. Single fault diagnostic tests for inversion faults of circuit elements over some bases // Computational Mathematics Modeling 2019. 30. N 1. Р. 36-47.

66. Liubich I.G., Romanov D.S. Single diagnostic tests for inversion faults of gates in circuits over arbitrary bases // Discr. Math. Appl. 2022. 32. N 1. Р. 1-9.

67. Любич И.Г., Романов Д.С. О k-диагностических тестах относительно инверсных неисправностей элементов // Интеллектуальные системы. Теория и приложения. 2021. 25. No 4. С. 161-165.

68. Морозов Е.В. Об оценках функций Шеннона длин тестов при некоторых неисправностях входов схем: Дис. ... канд. физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2015.

69. Романов Д.С. Об оценках длин минимальных тестов для логических схем: Дис. ... д-ра физ.-мат. наук. М., МГУ им. М.В. Ломоносова, 2019.

70. Темербекова Г.Г., Романов Д.С. О единичных проверяющих тестах относительно замен элементов на инверторы // Учен. зап. Каз. ун-та. Сер. Физ.-матем. науки. 2020. 162. No 3. С. 359-366.

71. Temerbekova G., Romanov D.S. The length of single-fault detection tests with respect to substitution of inverters for combinational elements in some bases // Computational Mathematics and Modeling. 2021. 32. N 3. P. 356–363.

72. Temerbekova G., Romanov D.S. The length of single fault detection tests with respect to substitution of gates with inverters // Computational Mathematics and Modeling. 2021. 32. N 4. Р. 505-513.

73. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Труды МИАН СССР. 1958. 51. С. 270-360.