- Кафедра математической логики и высшей алгебры
-
Кафедра математической логики и высшей алгебры Нижегородский государственный университет им Н. И. Лобачевского Факультет вычислительной математики и кибернетики Заведующий
кафедройШевченко, Валерий Николаевич Месторасположение Нижний Новгород, пр. Гагарина, 23 Официальный
сайтwww.unn.ru/vmk/chairs.php?id=3 Содержание
Общая характеристика кафедры
Кафедра образована в 1963 году при создании факультета вычислительной математики и кибернетики. Первый заведующий кафедрой — Юрий Васильевич Глебский. Научные направления, развиваемые на кафедре: дискретная оптимизация, теория графов, математическая логика.
Научная работа кафедры
Дискретная оптимизация
Основные результаты сотрудников кафедры к 1995 г. в направлении дискретной оптимизации собраны в монографии В. Н. Шевченко. [1]. За последние годы сотрудниками кафедры были получены также следующие результаты в области дискретной оптимизации и целочисленного линейного программирования:
- Получены верхние и близкие к ним нижние оценки сложности расшифровки пороговых функций многозначной логики. На этой основе установлены экспоненциальные нижние оценки сложности задачи о рюкзаке в классе оракульных алгоритмов (В.Н.Шевченко, Н.Ю.Золотых). [2]
- Доказана известная гипотеза Бороша-Трейбига и величине решения системы линейных диофантовых уравнений (С.И.Веселов). [3]
- Выделены классы полиномиально разрешимых задач многокритериального целочисленного линейного программирования. Описано строение множества оптимальных по Парето решений таких задач (В.Н.Шевченко, А.Ю.Чирков, Н.Ю.Золотых).
- Получен аналог уравнений Дена-Соммервиля, позволивший, в частности, описать множество f-векторов, получающихся при любых триангуляциях всевозможных трехмерных политопов и циклических политопов произвольной размерности (В.Н.Шевченко, Д.В.Груздев). [4]
Теория графов
К основным результатам последних лет в области теории графов относятся:
- Получена связь между двумя новыми параметрами: энтропией и рангом наследственного класса графов. Описано множество значений энтропии наследственных классов. Охарактеризованы наследственные классы с нулевой энтропией. [5] Эти результаты цитировались, например, на Международном математическом конгрессе (Берлин, 1998). [6]
- Для конечно определенного наследственного класса получено достаточное (а для классов с сильной наследственностью и необходимое) условие того, что задача о независимом множестве в этом классе является NP-трудной. Введено понятие граничного класса и обоснована его полезность для анализа сложности задач на конечно определенных классах графов. Выявлен граничный наследственный класс для задачи о независимом множестве. Доказана его единственность среди сильно наследственных классов. [7]
См. также
Премечания
- ↑ Шевченко В. Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. (English. transl.: Shevchenko V.N. Qualitative topics in integer linear programming. American Mathematical Society, Providence, Rhode Island, 1997.)
- ↑ Шевченко В.Н., Золотых Н.Ю. О сложности расшифровки пороговых функций k-значной логики // Доклады РАН. - 1998. - Т. 362, № 5. - С. 606-608.
- ↑ Веселов С.И. Доказательство обобщения гипотезы Бороша-Трейбига о диофантовых уравнениях // Дискретный анализ и исследование операций. Серия 1. - 2001. - Т. 8, № 1. - С. 17-22.
- ↑ Шевченко В.Н. О разбиении выпуклого политопа на симплексы без новых вершин // Известия ВУЗ. Математика. - 1997. - № 12. - С. 89-99.
- ↑ Алексеев В.Е. О нижних ярусах решетки наследственных классов графов // Дискретный анализ и исследование операций. Серия 1. - 1997. - Т. 4, № 1. - С. 3-12.
- ↑ Bela Bollobas. Hereditary Properties of Graphs: Asymptotic Enumeration, Global Structure, and Colouring. // Doc. Math. J. DMV, Extra Volume ICM III (1998), 333-342.
- ↑ Алексеев В.Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискретный анализ и исследование операций. Серия 1. - 1999. - Т. 6, № 4. - С. 3-19.
Ссылки
- Факультет вычислительной математики и кибернетики
- Официальный сайт кафедры математической логики и высшей алгебры
Wikimedia Foundation. 2010.