Кафедра математической логики и высшей алгебры (Нижегородский государственный университет)

Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/30 октября 2012. Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до окончания обсуждения. Администраторам: ссылки сюда, история (последнее изменение), журналы, удалить.

Кафедра математической логики и высшей алгебры (МЛиВА)
Факультет	Факультет вычислительной математики и кибернетики
Вуз	Нижегородский государственный университет им Н. И. Лобачевского
Зав. кафедрой	Шевченко, Валерий Николаевич
Юридический адрес	Нижний Новгород, пр. Гагарина, 23
Сайт	mliva.org

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

Научная работа

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

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

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

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

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

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

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

См. также

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

Примечания

1. ↑ Шевченко В. Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. (English. transl.: Shevchenko V. N. Qualitative topics in integer linear programming. — American Mathematical Society, 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 (1998). «Hereditary Properties of Graphs: Asymptotic Enumeration, Global Structure, and Colouring». Doc. Math. J. DMV ICM III: 333-342.
7. ↑ Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискретный анализ и исследование операций. Серия 1. — 1999. — Т. 6. — № 4. — С. 3-19.

Ссылки

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