Учебные заведения - Кафедра математической логики и высшей алгебры (Нижегородский государственный университет)
29 апреля 2011Купить ранец на каширке, derdiedasbags.ru/statii/rancy-dlya-malchikov.html.
Кафедра математической логики и высшей алгебры образована в 1963 году при создании факультета вычислительной математики и кибернетики. Первый заведующий кафедрой — Юрий Васильевич Глебский. Научные направления, развиваемые на кафедре: дискретная оптимизация, теория графов, математическая логика.
Научная работа
Дискретная оптимизация
Основные результаты сотрудников кафедры к 1995 году в направлении дискретной оптимизации собраны в монографии В. Н. Шевченко. За последние годы сотрудниками кафедры были получены также следующие результаты в области дискретной оптимизации и целочисленного линейного программирования:
- Получены верхние и близкие к ним нижние оценки сложности расшифровки пороговых функций многозначной логики. На этой основе установлены экспоненциальные нижние оценки сложности задачи о рюкзаке в классе оракульных алгоритмов.
- Доказана известная гипотеза Бороша-Трейбига и величине решения системы линейных диофантовых уравнений.
- Выделены классы полиномиально разрешимых задач многокритериального целочисленного линейного программирования. Описано строение множества оптимальных по Парето решений таких задач.
- Получен аналог уравнений Дена—Соммервиля, позволивший, в частности, описать множество f-векторов, получающихся при любых триангуляциях всевозможных трехмерных политопов и циклических политопов произвольной размерности.
Теория графов
К основным результатам последних лет в области теории графов относятся:
- Получена связь между двумя новыми параметрами: энтропией и рангом наследственного класса графов. Описано множество значений энтропии наследственных классов. Охарактеризованы наследственные классы с нулевой энтропией. Эти результаты цитировались, например, на 23-м международном математическом конгрессе.
- Для конечно определенного наследственного класса получено достаточное условие того, что задача о независимом множестве в этом классе является NP-трудной. Введено понятие граничного класса и обоснована его полезность для анализа сложности задач на конечно определенных классах графов. Выявлен граничный наследственный класс для задачи о независимом множестве. Доказана его единственность среди сильно наследственных классов.
Просмотров: 3221
|
|