Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Теоретическая информатика и комбинаторика (2015 — 2016)

«Теоретическая информатика и комбинаторика» — это совместный научный семинар ФИВТ МФТИ и ФКН ВШЭ. Он проходит 1-2 раза в семестр. Идея в том, чтобы обеспечить максимум научного взаимодействия между факультетами. Поэтому семинар проходит то на территории ФКН по адресу Кочновский проезд, д. 3. (метро Аэропорт, 15 минут пешком), аудитория 509, время среда 16:40 — 18:00, то на территории МФТИ (аудитория и время появится чуть позже).

Страница семинара на сайте ФКН

Заседания:

9 марта 2016 г. (ФКН)
М. Тихомиров «Геометрические графы и сложность их распознавания»
Классические дистанционные графы — это графы, которые можно  нарисовать на плоскости так, чтобы все ребра были отрезками длины 1,  возможно, пересекающимися. С дистанционными графами связано много  известных задач, таких как проблема Эрдеша о количестве единичных  расстояний среди n точек и проблема о хроматическом числе плоскости.
Возникает естественный вопрос: можно ли придумать алгоритм, эффективно распознающий дистанционные графы (а может быть, и позволяющий рисовать их на плоскости)? Оказывается, что нет, такая задача NP-трудна. Такую же задачу можно рассматривать в пространствах других размерностей, а также для других разновидности геометрических графов, т.е. графов с вершинами в точках пространства и ребрами, которые соответствуют некоторому геометрическому соотношению (например, расстояние = 1).
Рассказ будет про ряд результатов в этой области и некоторые подходы к их доказательству.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика