name: О сложности реализации систем одночленов схемами композиции
keyword_list: схемная сложность операция композиции дискретная математика функция Шеннона
abstract: Объект исследования: схемы композиции как вычислительная модель. Цели исследования: изучение сложности реализации вычисления различных систем одночленов схемами композиции, нахождение асимптотики роста сложности реализации систем одночленов, задаваемых матрицами фиксированного размера, поиск и исследование новых свойств схем композиции, применение разработанных методов для изучения аналогичных задач в близких моделях вычисления систем одночленов. Результаты: Для реализации системы из двух одночленов схемами композиции найдено точное значение сложности. Для реализации системы одночленов от двух переменных схемами композиции найдены верхняя и нижняя оценки сложности, которые в совокупности устанавливают асимптотику роста сложности для этой задачи. Обнаружен новый эффект: показано, что в общем случае эта асимптотика не определяется асимптотикой роста сложности никакого несобственного подмножества рассматриваемой системы одночленов. Для функции шенноновского типа, характеризующей сложность реализации схемами композиции системы одночленов, все показатели степеней которых не превосходят соответствующих элементов фиксированной матрицы, найдена асимптотика роста. Этот результат с некоторыми слабыми ограничениями перенесён на классическую модель вычисления систем одночленов (схемы умножения). Для функции Шеннона, характеризующей максимальную сложность реализации схемами композиции системы из p одночленов от q переменных, все показатели степеней которых не превосходят заданной величины K, при некоторых ограничениях установлена асимптотика роста. Результаты могут найти применение в исследованиях по теории синтеза и сложности управляющих систем.
chairman_dissertation_council.name: Виктор
chairman_dissertation_council.surname: Садовничий
chairman_dissertation_council.patronymic: Антонович
chairman_dissertation_council.position: ректор
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Академик
chairman_dissertation_council.wos_research_id: K-6414-2012
chairman_dissertation_council.scopus_author_id: 7801673584
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Андрей
organization_supervisor.surname: Шафаревич
organization_supervisor.patronymic: Игоревич
organization_supervisor.position: декан
organization_supervisor.degree: Доктор физико-математических наук
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.47.15
rubrics.name: Математическая теория управляющих систем
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Кочергин В.В.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Аблаев Ф.М.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
opponents.fio: Романов Д.С.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
opponents.fio: Сергеев И.С.
opponents.scientific_degree: Кандидат физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
protection_organization.short_name: МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА, МГУ ИМЕНИ М.В.ЛОМОНОСОВА, МГУ
protection_organization.name: Федеральное государственное бюджетное образовательное учреждение высшего образования "Московский государственный университет имени М.В. Ломоносова"
protection_organization.ogrn: 1037700258694
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА, МГУ ИМЕНИ М.В.ЛОМОНОСОВА, МГУ
author_organization.name: Федеральное государственное бюджетное образовательное учреждение высшего образования "Московский государственный университет имени М.В. Ломоносова"
author_organization.ogrn: 1037700258694
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения