name: Значения функции перманента (0,1)-матриц и (-1,1)-матриц
keyword_list: Перманент (0,1)-матрицы (-1,1)-матрицы
abstract: Функция перманента является важным понятием комбинаторной теории матриц и теории графов. Она была впервые введена Бине и Коши, а её современное название ей дал Мюир, который также доказал для перманента аналоги некоторых базовых свойств детерминанта. Важное отличие перманента от детерминанта состоит в том, что он не инвариантен по отношению к одному из преобразований Гаусса, и, более общо, перманент не мультипликативен. Как следствие, к нему не применимы методы быстрого вычисления, применимые в случае детерминанта. Более того, на данный момент не найдено алгоритма вычисления перманента
  полиномиальной или меньшей сложности. Помимо интереса с точки зрения теории сложности вычислений, функция перманента представляет также и практический интерес. Приложения перманента можно найти как в смежных областях математики, например, в комбинаторике и теории графов, так и в других науках - экономике, генетике, квантовой физике. Необходимость вычислять значения перманентов (0,1)-матриц и, более общо, матриц с целыми неотрицательными элементами возникает в задачах теории механизмов в экономике, а перманенты (-1,1)-матриц используются в квантовой механике.
  В диссертации рассмотрены вопросы реализации значений перманента (0,1)-матриц, а также делимости и обращения в 0 перманентов (-1,1)-матриц. Получено улучшение оценки Бруальди-Ньюмена границы последовательных значений перманента (0,1)-матриц более чем в 2 раза. Вычислены наибольший нечётный и наибольший не делящийся на 3 значения перманента. Предъявлены для всех простых
  p<n и натуральных j, 1<j<n, матрицы, на которых функция перманента достигает наибольшего не делящегося на p значения и наибольшего не делящегося на j! значения соответственно. Оценено сверху количество значений перманента на множестве (0,1)-матриц порядка n, превосходящих наибольший нечётный перманент.  Предъявлена и доказана формула для перманента (-1,1)-матриц, позволяющая вычислять степень вхождения 2 как простого сомножителя в значение перманента. Предъявлены прямые доказательства предложений Кройтера и Сейфтера о делимости перманента на степени 2. Предъявлен и доказан критерий делимости перманента (-1,1)-матриц на более высокую степень двойки, чем было известно ранее. Перечислены все классы (-1,1)-матриц порядка не более 5 с перманентом 0.
chairman_dissertation_council.name: Владимир
chairman_dissertation_council.surname: Чубариков
chairman_dissertation_council.patronymic: Николаевич
chairman_dissertation_council.position: Председатель диссертационного совета МГУ.01.17
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: -
chairman_dissertation_council.scopus_author_id: 6602349502
chairman_dissertation_council.url: https://istina.msu.ru/profile/ChubarikovVN2012/
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Андрей
organization_supervisor.surname: Шафаревич
organization_supervisor.patronymic: Игоревич
organization_supervisor.position: Декан механико-математического факультета МГУ имени М.В.Ломоносова
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.17.29
rubrics.name: Линейная алгебра
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
speciality_codes.name: Математическая логика, алгебра, теория чисел и дискретная математика
speciality_codes.code: 1.1.5.
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.supervisor_name: ВИКТОР
protection_organization.supervisor_surname: САДОВНИЧИЙ
protection_organization.supervisor_patronymic: АНТОНОВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА, МГУ ИМЕНИ М.В.ЛОМОНОСОВА, МОСКОВСКИЙ УНИВЕРСИТЕТ ИЛИ МГУ
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА"
author_organization.ogrn: 1037700258694
author_organization.supervisor_name: ВИКТОР
author_organization.supervisor_surname: САДОВНИЧИЙ
author_organization.supervisor_patronymic: АНТОНОВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения