Кафедра математической логики и высшей алгебры

Кафедра математической логики и высшей алгебры
Нижегородский государственный университет им Н. И. Лобачевского
Факультет вычислительной математики и кибернетики
Заведующий кафедрой	Шевченко, Валерий Николаевич
Месторасположение	Нижний Новгород, пр. Гагарина, 23
Официальный сайт	www.unn.ru/vmk/chairs.php?id=3

Общая характеристика кафедры

Кафедра образована в 1963 году при создании факультета вычислительной математики и кибернетики. Первый заведующий кафедрой — Юрий Васильевич Глебский. Научные направления, развиваемые на кафедре: дискретная оптимизация, теория графов, математическая логика.

Научная работа кафедры

Дискретная оптимизация

Основные результаты сотрудников кафедры к 1995 г. в направлении дискретной оптимизации собраны в монографии В. Н. Шевченко. ^[1]. За последние годы сотрудниками кафедры были получены также следующие результаты в области дискретной оптимизации и целочисленного линейного программирования:

• Получены верхние и близкие к ним нижние оценки сложности расшифровки пороговых функций многозначной логики. На этой основе установлены экспоненциальные нижние оценки сложности задачи о рюкзаке в классе оракульных алгоритмов (В.Н.Шевченко, Н.Ю.Золотых). ^[2]
• Доказана известная гипотеза Бороша-Трейбига и величине решения системы линейных диофантовых уравнений (С.И.Веселов). ^[3]
• Выделены классы полиномиально разрешимых задач многокритериального целочисленного линейного программирования. Описано строение множества оптимальных по Парето решений таких задач (В.Н.Шевченко, А.Ю.Чирков, Н.Ю.Золотых).
• Получен аналог уравнений Дена-Соммервиля, позволивший, в частности, описать множество f-векторов, получающихся при любых триангуляциях всевозможных трехмерных политопов и циклических политопов произвольной размерности (В.Н.Шевченко, Д.В.Груздев). ^[4]

Теория графов

К основным результатам последних лет в области теории графов относятся:

• Получена связь между двумя новыми параметрами: энтропией и рангом наследственного класса графов. Описано множество значений энтропии наследственных классов. Охарактеризованы наследственные классы с нулевой энтропией. ^[5] Эти результаты цитировались, например, на Международном математическом конгрессе (Берлин, 1998). ^[6]

• Для конечно определенного наследственного класса получено достаточное (а для классов с сильной наследственностью и необходимое) условие того, что задача о независимом множестве в этом классе является NP-трудной. Введено понятие граничного класса и обоснована его полезность для анализа сложности задач на конечно определенных классах графов. Выявлен граничный наследственный класс для задачи о независимом множестве. Доказана его единственность среди сильно наследственных классов. ^[7]

См. также

• Нижегородский государственный университет
• Факультет вычислительной математики и кибернетики ННГУ

Премечания

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

Ссылки

• Факультет вычислительной математики и кибернетики
• Официальный сайт кафедры математической логики и высшей алгебры

Кафедры ВМК ННГУ

Кафедра теории управления и динамики машин | Кафедра численного и функционального анализа | Кафедра математической логики и высшей алгебры | Кафедра прикладной математики | Кафедра математического обеспечения ЭВМ | Кафедра прикладной теории вероятностей | Кафедра информатики и автоматизации научных исследований | Кафедра интеллектуальных информационных систем и геоинформатики | Кафедра теории статистических решений