Двойственные графы на поверхностях (проект)

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Ментор Владимир Гурвич
Учебный семестр Осень 2016
Учебный курс 2-й курс
Проект можно развивать на летней практике
Максимальное количество студентов, выбравших проект: 2


Внимание! Данный проект находится в архиве и реализован не будет.

Что это за проект?

Охарактеризовать пары двойственных графов на поверхностях. Этот вопрос из топологии был недавно решён в чисто комбинаторных терминах. Однако, остался открытым вопрос, какие векторы валентностей могут иметь такие графы. Вопрос этот имеет важные приложения в топологии и в физике. Предлагается написать компьютерный код, перечисляющий все пары двойственных графов небольшого размера и выяснить, какие пары векторов валентностей возможны, какие нет. Результат может привести к решению важдой открытой проблемы.

Чему вы научитесь?

Применять программирование для постановки экспериментов в математических исследованиях

Какие начальные требования?

Свободное владение одним из языков программирования и опыт работы на нём. Желательно умение писать программы, работающие не только правильно, но и быстро.

Какие будут использоваться технологии?

Программирование на персональном компьютере. Прогонка программы на мощном компьютере.

Темы вводных занятий

Двойственные графы на поверхности и биматрицы. Комбинаторные условия на биматрицу, необходимые и достаточные для того, чтобы она соответствовала паре двойственных графов. Векторы валентностей двойственных графов.

Направления развития

Если задача будет успешно решена, она позволит получать новые результаты в топологии и в физике.

Критерии оценки

Успешное написание программы в разумные сроки (4-5 недель), правильность её работы и быстродействие. Сложность входных данных определяется количеством рёбер m в парах двойственных графов. Оценка будет вычисляться по простой формуле m + 2, то есть, если программа будет эффективно работать при m = 2,3 - оценка 4-5; при m = 4,5 - оценка 6-7; при m = 6,7,8+ - оценка 8-10.

Ориентировочное расписание занятий

Общение по скайпу и электронной почте возможно в любое время. Встречи в ВШЭ по договорённости.