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

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

Адрес e-mail:

Кафедральный семинар

Заседания кафедрального семинара проходят по вторникам с 18:30 до 20:00 в аудитории "Оксфорд" в Яндексе (м. Парк культуры, ул. Льва Толстого, д. 16).

Вы можете подписаться на RSS-ленту или трансляцию в ЖЖ этого и других близких по тематике семинаров на сайте http://combalg.ru/seminars.

Предстоящие заседания:

13 мая 2014 г.
А.В. Савватеев «Равновесие дискретного отклика»
Общеизвестно, что целый ряд предсказаний классической теории игр, основанных на поиске равновесий Нэша и даже на решении задач по доминированию, идёт в разрез с результатами "полевых экспериментов", когда в те же игры подопытные люди играют даже на настоящие деньги. В первую очередь это такие игры, как "Ультиматум", "Производство общественного блага" и "Сороконожка".
В то же время введённая в конце 20 века в работах Палфри и Маккельви концепция равновесия дискретного отклика очень неплохо прогнозирует результаты эксперимента, например, для игры "Сороконожка".
По своему духу эта концепция несёт в себе элементы статистической механики, умело встроенные в теоретико-игровой контекст.
В лекции будет дано определение новой концепции решения игр, доказана теорема существования равновесия, а также приведён целый ряд результатов компьютерного поиска равновесий этого класса, соотнесённых с экспериментальными данными.

20 мая 2014 г.
О.В. Иванов, М.С. Игнатов «Двухмерная клеточная структура: от оцифровки до анализа»
Аннотация

Прошедшие заседания:

29 апреля 2014 г. (115 КПМ
J.H. Kim «A tale of models for random graphs» 
Since Erdős and Rényi introduced random graphs in 1959, two closely related models for random graphs have been extensively studied. In the G(n,m) model, a graph is chosen uniformly at random from the collection of all graphs that have n vertices and m edges. In the G(n,p) model, a graph is constructed by connecting each pair of two vertices randomly. Each edge is included in the graph G(n,p) with probability p independently of all other edges. Researchers have studied when the random graph G(n,m) (or G(n,p), resp.) satisfies certain properties in terms of n and m (or n and p, resp.). If G(n,m) (or G(n,p), resp.) satisfies a property with probability close to 1, then one may say that a `typical graph’ with m edges (or expected edge density p, resp.) on n vertices has the property. Random graphs and their variants are also widely used to prove the existence of graphs with certain properties. In this talk, a well-known problem for each of these categories will be discussed. First, a new approach will be introduced for the problem of the emergence of a giant component of G(n,p), which was first considered by Erdős–Rényi in 1960. Second, a variant of the graph process G(n,1),G(n,2),…,G(n,m),… will be considered to find a tight lower bound for Ramsey number R(3,t) up to a constant factor. No prior knowledge of graph theory is needed in this talk.


22 апреля 2014 г. 
А. Жернов «Использование поведения пользователей для улучшения качества ранжирования» 
Алгоритмы ранжирования поисковых систем за последние несколько лет шагнули далеко вперед от простого сопоставления текста запроса текстам документов. Лучшие поисковые системы используют сотни различных сигналов релевантности для обеспечения наилучших поисковых результатов. Одним из самых полезных сигналов для ранжирования является поведение пользователей. В докладе будут рассказаны способы усиления такого сигнала. 

15 апреля 2014 г.
С. Попова «Закон нуля или единицы для случайных дистанционных графов с вершинами в Z^n»
Говорят, что случайный граф подчиняется закону нуля или единицы, если для любого графового свойства, записываемого на языке первого порядка, вероятность того, что случайный граф обладает этим свойством, стремится либо к нулю, либо к единице. В докладе будет введена модель случайных дистанционных графов с вершинами в Z^n, являющаяся обобщением моделей случайных дистанционных графов с вершинами в {0, 1}^n и {-1, 0, 1}^n, для которых ранее М.Е. Жуковским и докладчиком были рассмотрены законы нуля или единицы, и рассказано про закон нуля или единицы для такой модели.

08 апреля 2014 г.
С.М. Апенко «Гиперболическая геометрия сложных сетей»
В докладе обсуждаются результаты, полученные в статье D. Krioukov et al., Phys. Rev. E82 (2010), 036106, в которой предложен алгоритм построения графов с заданным коэффициентом кластеризации, основанный на рассмотрении вспомогательного гиперболического многообразия.

01 апреля 2014 г.
С. Хорошеньких «Модели графов и алгоритмы для беспроводных самоорганизующихся сетей»
Самоорганизующиеся сети -- это децентрализованные сети передачи данных, не имеющие постоянной структуры (т.е. без маршрутизаторов и выделенных точек доступа). Хорошей моделью для беспроводных сетей является unit-disk граф. Большой интерес представляют модели построения таких сетей (т.е. модели случайных unit-disk графов), поскольку они позволяют создавать эффективные алгоритмы передачи данных.
Традиционно, в качестве модели таких сетей используется модель геометрических случайных графов, в которой вершины графа появляются независимо друг от друга в некоторой области. Будет дан краткий обзор имеющихся результатов и открытых задач для данной модели.
Также будет предложена новая модель построения случайного графа беспроводной сети, в которой вершины появляются равномерно в зоне покрытия. Для этой модели уже имеются некоторые результаты, которые будут изложены.

25 марта 2014 г.
С.П. Кикоть «Доступ к данным на основе онтологий. Длина переписывания конъюнктивных запросов относительно OWL 2 QL»
В докладе будет рассказано об использовании онтологий для доступа к данным. Вот пример математической задачи из этой области. Дана теория первого порядка T, которая может содержать аксиомы вида
(1) Ax( C_1(x) -> C_2(x)),
где C_i (x) имеют вид A(x) или Ey R(x,y),
и вида
(2) Ax Ay (R(x,y) -> S(y,x)),
и  экзистенциальная конъюнктивная формула q (запрос). Требуется построить такую позитивно экзистенциальную формулу первого порядка q' (переписывание запроса),
зависящую от q и T, чтобы для любого набора атомов I (данных), из I и Т следовало бы q, тогда и только тогда, когда из I следует q', и оценить сверху и снизу ее размер в зависимости от разных ограничений на Т.
Оказывается, что длина переписывания связана со схемной и формульной сложностью определенных булевых функций, которые задаются некоторым гиперграфом, который, в свою очередь,  строится по запросу и теории.
Доклад построен на основе серии работ в соавторстве с В. Подольским, Р. Кончаковым и М. Захарьящевым.

18 марта 2014 г.
М. Раскин «Парадокс потребительского выбора в играх на социальных сетях»

11 марта 2014 г.
Семинар был отменен

4 марта 2014 г.
Д.А. Шабанов «Раскраски гиперграфов в большое число цветов»
В недавней работе Д. Черкашина и Я. Козика была получена новая нижняя оценка максимальной степени вершины n-однородного гиперграфа с хроматическим числом больше r в случае, когда r не слишком велико по сравнению с n. В докладе мы обобщим данный результат на произвольное число цветов и дадим новую верхнюю оценку изучаемой экстремальной случайной величины.

25 февраля 2014 г.
С.С. Галкин «Пары точек и прямые на кубиках»
Я расскажу про совместную работу с Женей Шиндером. Пусть X — d-мерная кубическая гиперповерхность (множество нулей однородного уравнения степени 3 от (d+2) переменных). Оказывается, есть универсальное соотношение между X, S^2 X (многообразием неупорядоченных пар точек на X) и F_X (многообразием прямых на X): [S^2 X] = (1+q^d) [X] + q^2 [F] — q^d [Sing X]. Это соотношение выполнено в кольце Гротендика многообразий, а q это класс афинной прямой. Доказывается оно на удивление просто — надо рассмотреть прямую через пару точек на кубике, и третью точку пересечения прямой и кубики. Из этого почти мгновенно можно найти: сколько прямых лежит на (возможно особой) кубической поверхности, сколько из них вещественные, сколько определены над конечными полями, какие у многообразия прямых числа Ходжа, итп.

18 февраля 2014 г.
А.А. Вороненко «Порождение ложного образа функций»
Рассматривается ситуация, когда оппонент каким-либо образом получил ложную
информацию о функции (случайной либо конструируемой нами). Нашей задачей
является, сообщая ему истинные значения функции, внушить любую возможную
полную о ней информацию.

 

Осений семестр:

10 сентября 2013 г.
А.Б. Скопенков «Заузливание многообразий в евклидовых пространствах»
Аннотация

17 сентября 2013 г.
А.В. Савватеев «Задача многомерного размещения с неатомарным расселением»
Будут представлены новые результаты в теории многомерного размещения. Конкретно, будет доказана общая теорема существования миграционно-устойчивого разбиения на клубы при уравнивающем способе распределения издержек, а также показана потенциальность (в обобщённом смысле) игры размещения с принципом равнодолевого участия.

1 октября 2013 г.
Д.А. Шабанов «Вокруг проблемы Эрдеша-Ловаса для неоднородных гиперграфов»
В докладе будут обсуждаться различные вопросы, связанные с известной проблемой Эрдеша-Ловаса о раскрасках неоднородных гиперграфов. Будут представлены свежие результаты, полученные докладчиком в этой области.

8 октября 2013 г.
А. Сорокин «Автоматы на моноидах»
Автоматы на моноидах (M-автоматы) представляют собой обобщение конечных автоматов за счет введения дополнительного регистра памяти, в котором хранится элемент некоторого моноида М. При этом класс языков, распознаваемый М-автоматами, существенно зависит от моноида М. Известные варианты автоматов (автоматы с магазинной памятью, вложенные стековые автоматы и т.п.) являются частными случаями М-автоматов. Кроме того, М-автоматы показывают взаимосвязь между синтаксическими свойствами классов формальных языков и их алгебраической характеризацией. Доклад основан на работе Kambites. Formal languages and groups as memory и результатах автора.

22 октября 2013 г.
А. Полянский «О графах диаметров в [latex]\mathbb{R}^d[/latex], d=4, 5»
Граф диаметров в [latex]\mathbb{R}^d[/latex] --- это граф, множество вершин которого является конечным подмножеством [latex]\mathbb{R}^d[/latex], а ребрами соединены пары вершин, отстоящих на расстояние, равное диаметру множества вершин. Гипотеза Шура утверждает следующее: в любом графе диаметров в [latex]\mathbb{R}^d[/latex] на n вершинах не более n полных подграфов размера d. Доклад будет посвящен элементарному доказательству гипотезы Шура в [latex]R^4[/latex], [latex]R^5[/latex]. Также мы коснемся других вопросов, связанных с графами диаметров.
О гипотезе Шура можно прочитать здесь.

29 октября 2013 г.
А. Кудинов «Модальная логика знания»
Я дам определения модальной логики и семантики Крипке. Расскажу какие логики используются в качестве логик знаний, для моделирования того что "знают" агенты (знание здесь понимается, как множество всех формул выводимых из тех формул, про которые известно, что они истинны.)
Мы разберем, как моделируются в этом формализме несколько "головоломок", таких как задача про мудрецов с колпаками и задача про карты, в которой трем игрокам раздается 3, 3 и 1 карта и первым двум надо передать информацию о своих картах, так чтобы 3тий не узнал какие карты у кого.

12 ноября 2013 г.
Е. Самосват «Обзор приложений и методов анализа сложных сетей в Computer Science»
Интенсивное изучение сложных сетей (complex networks) началось сравнительно недавно, в конце 1990-х годов. В эту работу включились и физики, и математики, и исследователи в области информационных технологий. Причем взгляды представителей разных наук довольно сильно отличаются. В докладе будет данный краткий обзор приложений и методов анализа сложных сетей с точки зрения Computer Science. Среди рассмотренных проблем будут: поиск наиболее авторитетных узлов, обнаружение сообществ, визуализация сетей, архивация сетей для эффективного хранения, использование методов машинного обучения для проверки качества моделей сетей. Будут обозначены проблемы и возможные направления дальнейшего исследования.

26 ноября 2013 г.
М. Полякова «Моделирование динамики микротрубочек»
В докладе будет рассказано о самих микротрубочках, о том, как делают разные модели их динамики и насколько каждая модель приближена к реальности.

3 декабря 2013 г.
А. Куликов, П. Гусятников «Задача оптимальной остановки для фрактального броуновского движения»
В докладе будут рассмотрены различные свойства фрактального броуновского движения, различные способы симулирования броуновского движения, а также найдены средние значения для фрактального броуновского движения для некоторых моментов остановки, получены приближения оптимальной остановки.

10 декабря 2013 г.
С. Галкин «Пары точек и прямые на кубиках» (семинар отменен)
Я расскажу про совместную работу с Женей Шиндером. Пусть X - d-мерная кубическая гиперповерхность (множество нулей однородного уравнения степени 3 от (d+2) переменных). Оказывается, есть универсальное соотношение между X, S^2 X (многообразием неупорядоченных пар точек на X) и F_X (многообразием прямых на X):
[S^2 X] = (1+q^d) [X] + q^2 [F] - q^d [Sing X].
Это соотношение выполнено в кольце Гротендика многообразий, а q это класс афинной прямой. Доказывается оно на удивление просто - надо рассмотреть прямую через пару точек на кубике, и третью точку пересечения прямой и кубики. Из этого почти мгновенно можно найти: сколько прямых лежит на (возможно особой) кубической поверхности, сколько из них вещественные, сколько определены над конечными полями, какие у многообразия прямых числа Ходжа, итп.

17 декабря 2013 г.
Ф. Рухович «Внешние биллиарды»
В докладе будет рассказано о том, что такое внешние биллиарды, о двойственности их с внутренними биллиардами, а также о поиске периодических точек и комбинаторикой слов.
Е. Примако «Клеточная самоорганизация посредством клеточных моторов»
В докладе будет рассказано про то, как цитоскелет (система изначально неупорядоченная) под воздействием простейших внутренних сил способен самоорганизовываться, образуя сложные макроструктуры ("звёзды", "колодцы" и т.п.); про известные причины этого явления и про исследования, которые в этой области ведутся.

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

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

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

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

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