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

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

Адрес e-mail:

Изоморфизм графов (Д.В. Мусатов, М.И. Тихомиров, весна 2016)

Лекторы — доц. Д.В. Мусатов, М.И. Тихомиров

Спецкурс будет проходит по средам с 17:05 до 18:30 в ауд. 511ГК. Первое занятие — 24 февраля.

Анонс

Задача об изоморфизме двух графов — редкий пример задачи, для которой не известно ни полиномиального алгоритма, ни доказательства NP-полноты. В декабре 2015 года Ласло Бабаи объявил о создании квазиполиномиального алгоритма, т.е. работающего за O(n^polylog(n)) шагов. В первой половине курса мы изучим известные частные случаи, для которых задача решается быстро: деревья, графы ограниченной степени, планарные графы и др., — и поговорим о месте задачи в иерархии сложностных классов. Во второй половине курса мы попробуем разобраться в алгоритме, предложенном Бабаи.


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

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

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

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

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