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

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

Адрес e-mail:

Кафедральный семинар (2014 - 2015)

В весеннем семестре 2015 года кафедральный семинар кафедры Дискретной математики будет проходить в Яндексе в ауд. 7. Вода-на-киселе с 18:30 до 20:00. Однако будет и новшество. А именно, в рамках семинара, помимо обычных докладов, будут доклады, на которых наш семинар будет объединяться с семинаром член-корр. РАН Д.А. Новикова (Институт Проблем Управления РАН), на котором также есть ряд очень сильных специалистов по одной из интересных нам тем - по теме сложных сетей и их применений. Эту часть семинара мы назовем "совместным семестровым воркшопом" и явно будем указывать в расписании принадлежность семинара к воркшопу. Всего в воркшопе будет 6 заседаний, на одном из которых будет 2 лекции. При этом 3 из 6 заседаний пройдут не в Яндексе, а в Институте Проблем Управления РАН: м. Калужская, ул. Профсоюзная, д. 65.

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

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

17 февраля 2015 г. - совместный семестровый воркшоп, заседание в Яндексе
М.В. Губко «Оптимизация графовых индексов и приложения»
Многие задачи выбора рациональной структуры систем различной природы сводятся к оптимизации графового индекса на множестве допустимых структур (графов). Обычно это множество достаточно обширно, чтобы исключить возможность его полного перебора. В докладе описываются ранние модели оптимизации иерархических структур на основе концепции секционных функций затрат, а также исследуемая в настоящее время более общая модель связывающей сети.
Приводятся нижние оценки затрат оптимальной связывающей сети, точные и приближенные алгоритмы их построения. Кратко затрагиваются приложения: оптимизация структуры пользовательских меню, оптимизация декомпозиции бизнес-процессов, оптимизация топологических молекулярных индексов в интересах синтеза материалов с заданными свойствами.

24 февраля 2015 г. - обычное заседание в Яндексе
А.А. Приходько «Графы Шрейера групп, порождённых автоматами, и гиперболическая динамика в конечных полях»
Мы исследуем конечные графы Шрейера группы "мигающих лампочек" типа L(2) - одной из семейства групп, порождённых конечными автоматами с двумя состояниями, и даём классификацию графов Шрейера в случае, когда максимальная абелева подгруппа транзитивно действует на графе. Такие графы всегда имеют число вершин, равное степени двойки, изоморфны как графы графам де Брёйна, а также графам гиперболических действий L(2) в полях Галуа. Отметим также, что изоморфизм в сильном смысле графов де Брёйна и графов Шрейера для действия L(2) на n-м уровне бинарного дерева достигается в точности при мощности графа 2^2^n. Устанавливается связь полученных результатов со свойствами гиперболических динамических систем в больших конечных полях.

03 марта 2015 г. - совместный семестровый воркшоп, заседание в Яндексе
А.Г. Чхартишвили «Акциональная модель влияния в социальных сетях»
Доклад посвящен новому подходу к конструктивному определению влиятельности в онлайновых социальных сетях – акциональной модели. Исходя из данного подхода влиятельность вычисляется на основе действий пользователей с учетом установок управляющего органа (центра).
А.А. Гилязова «Алгоритм формирования случайного графа с заданными свойствами»
В докладе описывается новый алгоритм генерации случайных графов, основанный на методе отсева активных пользователей. Получаемые графы обладают статистическими характеристиками, схожими с реальными социальными сетями: степенным распределением степеней вершин, малым средним кратчайшим путём, положительной ассортативностью, высокой степенью кластеризации, низкой плотностью. Алгоритм моделирует процессы образования реальных социальных сетей, структурно прост и характеризуется малым количеством параметров.

10 марта 2015 г. - обычное заседание в Яндексе
Л. Островский, А.Б. Дайняк «Задача укладки деревьев. Алгоритм Чена»

17 марта 2015 г. - обычное заседание в яндексе
Ф. Рухович «Внешние биллиарды»
В докладе я расскажу о том, что такое внешние биллиарды, о двойственности их с внутренними биллиардами, а также немного о задачах, связанных с этим замечательным объектом; основную же часть доклада я посвящу проблеме поиска точек с бесконечной апериодической траекторией, а также возможным методам решения этой проблемы с помощью компьютерных вычислений.
Д. Гусев  «Поведение конечных автоматов в лабиринтах»
Рассматривается задача обходе лабиринта конечным автоматом, использующим "камни". Для простых лабиринтов, например Z^k, известны хорошие оценки на минимально необходимое для обхода количество камней. Также, известны лабиринты, которые невозможно обойти таким способом с любым конечным количеством камней. Тем не менее, построение лабиринта, который можно обойти за k камней, и нельзя за k-1, нетривиально. Этой задаче и будет посвящён доклад.
М. Попов  «Условные информационные неравенства и комбинаторные приложения»
На докладе будет рассказано доказательство энтропийного неравенства (Ingleton's inequality) при более слабых ограничениях. Затем мы продемонстрируем два комбинаторных применения полученного результата:
1) Пусть наш двудольный граф разбит на К непересекающихся паросочетаний, причем степень вершин из левой доли >= L, а степень вершин из правой доли >= R, тогда верно неравенство K >= L*R.
2) Новый метод оценивания (нижняя оценка) бикликового числа двудольного графа.

24 марта 2015 г.
Семинара не будет.

31 марта 2015 г. - совместный семестровый воркшоп, заседание в Яндексе
В.В. Бреер, А.Д. Рогаткин «Модели порогового поведения в социальны сетях»
1.      Конформное и антиконформное пороговое поведение.
2.      Модели Шеллинга и Грановеттера.
3.      Игровая модель порогового поведения. Переход к стохастической модели.
4.      Идентификация пороговых моделей поведения для СС Facebook, Twitter, Live Journal
5.      Информационные противоборства в стохастических моделях управлении толпой.

07 апреля 2015 г. - обычное заседание в Яндексе
А.В. Савватеев «Многомерная гипотеза Тьебу: теорема существования равновесия»
Чарльз Тьебу, географ, высказал в 1956 году идею децентрализации принятия политических решений и решений в области экономики общественного сектора.
На проверку речь шла о математической задаче самоорганизации некоего пространства с заданной плотностью расселения - о задаче разбиения на группы, когда сами "жители" выбирают, в какой группе проживать.
Концепция равновесия предусматривает, что в предложенном разбиении никто не хочет никуда перебегать ("равновесие свободной миграции").
Целый ряд исследователей пытался по-своему её трактовать, и в рамках той или иной математической модели - доказать либо опровергнуть. Точки, то есть окончательного решения этой задачи, никогда не было поставлено.
Мы предлагаем модель, полностью имитирующую нестрогую конструкцию Чарльза Тьебу. Пространство характеристик при этом предполагается существенно многомерным (то есть размерность не ниже двух). Как ни странно, это предположение снимает все прошлые проблемы: пользуясь леммой Кнастера-Куратовского-Мазуркевича, мы доказываем наиболее общую теорему существования "равновесия по Тьебу".
А.С. Тарасов «Новый результат про плоские замощения»
Давно известно на основании формулы Эйлера: замостить плоскость одинаковыми выпуклыми семиугольниками нельзя. Можно немного уточнить этот результат: если плоскость замощена даже различными выпуклыми шестиугольниками и семиугольниками "соизмеримых размеров", то доля семиугольников стремится к нулю. Этот факт также доказывается с помощью формулы Эйлера.
Оказалось, что эти результаты обобщаются следующим образом: в любом разбиении плоскости на выпуклые шестиугольники и семиугольники соизмеримых размеров общее количество семиугольников обязано быть КОНЕЧНЫМ.

14 апреля 2015 г. - совместный семестровый воркшоп, заседание в Институте Проблем Управления РАН
Е.А. Самосват «Модель свежего веба и кроулинг»
Механизм предпочтительного присоединения (preferential attachment) был положен в основу модели развития Интернета в 1999 году Барабаши и Альберт. Их гипотеза состояла в том, что в Интернете новые страницы "предпочитают" цитировать более популярные страницы, т.е. с большей вероятностью ссылаются на те страницы, которые до этого уже много цитировались. С помощью идеи предпочтительного присоединения удалось объяснить многие свойства веб-графа.
Однако для некоторых частей Интернета модели предпочтительного присоединения в изначальном виде плохо подходят. Например, они плохо описывают эволюцию медиа-веба, т.е. высокодинамической части веба, где ежедневно появляется множество новых страниц, связанных с медиа-контентом: новостями, постами в блогах и форумах.  Действительно, в новостях и блогах редко цитируют сюжеты, потерявшие свою актуальность, какими бы популярными они ни были до этого.
В докладе будут предложены пути улучшения моделей предпочтительного присоединения для более адекватного описания поведения медиа-веба. Также будут рассмотрены приложения моделей медиа-веба для  улучшения его обхода роботом поисковых систем.

21 апреля 2014 г. - обычное заседание в Яндексе
Г.Г. Гусев «Гипотеза, обобщающая теорему Абеля-Руффини на случай многих переменных: идеи доказательства»
Мы обобщили на случай многих переменных классическую теорему Абеля о том, что комплексные корни многочлена степени >4 от одной переменной нельзя выразить в радикалах через его коэффициенты. Сначала я расскажу о топологической теории Галуа, которая позволяет доказать неразрешимость уравнения, если ее группа монодромии совпадает с группой перестановок корней уравнения. Эта теория моментально обобщается на случай системы из n полиномиальных уравнений от n переменных. Недавно нам удалось разобраться, в каких случаях группа монодромии системы уравнений совпадает с группой перестановок ее решений. Оказалось, что за исключением тех случаев, когда система сводится к уравнениям одной переменной степени не выше 4, группа монодромии системы совпадает с группой перестановок множества ее решений, и она неразрешима.

28 апреля 2015 г. - совместный семестровый воркшоп, заседание в Институте Проблем Управления РАН
Л.А. Остроумова «Графы предпочтительного присоединения с устареванием»
В докладе будут обсуждаться модели веб-графов. В основу наиболее известной модели веб-графа положен принцип предпочтительного присоединения: новая вершина с большей вероятностью ссылается на те уже существующие вершины, у которых текущая степень больше. Было показано, что распределение степеней в графах предпочтительного присоединения подчиняется степенному закону. Кроме того, у таких графов маленький диаметр. Такими же свойствами обладают и многие реальные структуры.
Однако было замечено, что некоторые графы, например веб-граф, обладают так называемым свойством устаревания. А именно, очень большая доля ребер соединяет близкие по дате создания страницы. Поэтому возникла идея добавить фактор устаревания в модели предпочтительного присоединения. Когда появляется новая вершина, из нее проводятся ребра в предыдущие вершины. При этом вершины выбираются с вероятностью, пропорциональной их привлекательности. Привлекательность вершины – некоторая функция от «качества» вершины, ее степени и возраста. В докладе пойдет речь о различных функциях привлекательности и о том, какие из них приводят к степенному распределению степеней вершин.

05 мая 2015 г.
Семинара не будет.

12 мая 2015 г. - обычное заседание в Яндексе
Н. Волков «Раскраски специального вида для гиперграфов»
А.В. Крот «Local clustering coefficient in preferential attachment graphs»
In this talk we discuss some properties of generalized preferential attachment models. A general approach to preferential attachment was introduced in [1], where a wide class of models (PA-class) was defined in terms of constraints that are sufficient for the study of the degree distribution and the clustering coefficient.
It was shown in [1] that the degree distribution in all models of the PA-class follows the power law. Also, the global clustering coefficient was analyzed and a lower bound for the average local clustering coefficient was obtained. It was also shown that in preferential attachment models global and average local clustering coefficients behave differently.
In our study we expand the results of [1] by analyzing the local clustering coefficient for the PA-class of models. We analyze the behavior of C(d) which is the average local clustering for vertices of degree d. The value C(d) is defined in the following way. First, the local clustering of a given vertex is defined as the ratio of the number of edges between the neighbors of this vertex to the number of pairs of such neighbors. Then the obtained values are averaged over all vertices of degree d.
[1] L. Ostroumova, A. Ryabchenko, E. Samosvat, Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient, Algorithms and Models for the Web Graph, Lecture Notes in Computer Science Volume 8305, 2013, pp 185-202.

19 мая 2015 г.
Семинара не будет.

26 мая 2015 г. - совместный семестровый воркшоп, заседание в Институте Проблем Управления РАН
М.Е. Жуковский, А.В. Гасников «Методы обучения функций ранжирования, основанных на случайных блужданиях»
PageRank является одним из самых известных факторов, использующихся для ранжирования страниц по пользовательским запросам в Интернете. Тем не менее этот фактор сильно устарел и перестал представлять интерес для многих поисковых систем, так как не является динамическим (не зависит от запроса) и не использует информацию о текстах документов и других свойств страниц в Интернете. В докладе будет рассказано о различных вариантах фактора PageRank. Основное внимание будет уделено моделям, в которых вероятности переходов являются функциями от факторов вершин и ребер графа. Будет рассказано о том, как можно обучать параметры таких функций для оптимизации метрик ранжирования и о том, как сделать такой фактор динамическим. К сожалению, задача обучения в общем случае оказывается невыпуклой, к тому же содержащей огромную скрытую размерность. Планируется обсудить возможные постановки, когда задачу обучения удается сделать выпуклой. Также планируется рассказать о новом методе (подходящем для широкого класса задач с огромной скрытой размерностью), находящем локальный минимум задачи глобальной оптимизации, базирующийся на концепции прямых (безградиентных) методов с неточным оракулом. Метод локально работает по известным нижним оракульным оценкам для данного класса задач. Однако у рассматриваемой задачи обучения имеется определенная специфика (функционал имеет вид суммы). На базе работы Конечного-Рихтарика (2013) мы обсудим возможное ускорение метода за счет использования аддитивной структуры функционала. Кроме того, на основе известного метода рестартов планируется описать способы борьбы за адаптивность метода - априорного не знания параметров функционала (для этого также потребуется привлечь концепцию двойной рандомизации Дучи-Джордан и др. 2014).

 

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

09 сентября 2014 г.
Г.Г. Гусев «Информационный поиск: прикладные задачи оптимизации»
Я расскажу о двух важных и во многом нерешенных задачах оптимизации, которые встают перед разработчиками поисковых систем и которые связаны с извлечением информации из кликов пользователей по результатам поиска. Первая из них - это онлайн-обучение ранжирования результатов для относительно частотных запросов. Вторая - это интерпретация кликов и скипов при обучении персонализированного поиска. В каждой из задач предполагается, что у нас есть достаточно богатый набор различных факторов - функций от пары (запрос, документ) - которые несут ту или иную информацию о способности данного документа удовлетворить пользователя, задавшего данный запрос. Нужно оптимальным образом учитывать эти факторы при построении алгоритма ранжирования с помощью того или иного метода машинного обучения. Попутно я постараюсь объяснить все эти детали, которые нужны для понимания доклада.

16 сентября 2014 г.
Семинара не будет.

23 сентября 2014 г.
А.А. Приходько «Статистика больших бинарных последовательностей, графы Кэли и автоморфизмы Вершика»
Рассматриваются двоичные последовательности длины n, представляющие целые числа от 0 до 2^n-1. Пусть s_2(x) - число "1"-ц в двоичной записи x. Решается следующая задача: Для фиксированного натурального a как найти все x, такие, что s_2(x+a) = s_2(x)? (здесь сложение понимается в самом обычном смысле). Множество X(a) решений данного уравнения может быть описано в терминах деревьев, накрывающих граф Кэли группы BS(1,2) = < x --> 2x, x --> x+1 >. Оказывается, для каждого a множество X(a) задаётся конечным числом префиксов, кодирующих специальные пути в упомянутом накрывающем дереве. Далее исследуется распределение p(z) вероятностей событий s_2(x+a) - s_2(x) = z, и снова параметр дисперсии в центральной предельной теореме для p(z) определяется длиной кратчайшей геодезической на группе BS(1,2) относительно некоторой специальной метрики.
Наше исследование мотивированно возникновением асимптотического "эффекта Такаги" для класса автоморфизмов Вершика, благодаря которому возникает исследуемое уравнение.

30 сентября 2014 г.
Л. Прохоренкова, Е. Самосват «Глобальный кластерный коэффициент в графах со степенным распределением степеней вершин»
Как известно, во многих реальных сетях распределение степеней вершин подчиняется степенному закону, причем обычно параметр степенного закона лежит в интервале (2,3). Иными словами, доля вершин степени d в графе убывает как d^{-gamma}, 2 < \gamma <3. Другая известная характеристика графа – кластерный коэффициент. Существует несколько способов определить кластерный коэффициент графа, наиболее распространенные - это глобальный и средний локальный кластерные коэффициенты. Считается, что в реальных сетях и глобальный и средний локальный кластерные коэффициенты стремятся к некоторой положительной константе с ростом сети. Кроме того, существует несколько моделей случайных графов, для которых средний локальный кластерный коэффициент стремится к положительной константе. А мы расскажем о том, почему до сих пор не было предложено ни одной модели с константным глобальным кластерным коэффициентом и параметром степенного распределения 2 < \gamma <3 .

07 октября 2014 г.
П. Тарасов «О соотношении между глубиной и сложностью реализации функций многозначной логики формулами»
Пусть A - конечная система булевых функций. Через [A] обозначим множество функций, реализуемых нетривиальными формулами над A. Если f \in [A], то через L(f) и D(f) будем обозначить минимальную сложность и глубину реализации функции f формулами над системой A соответственно. Конечная система A функций из многозначной логики называется равномерной, если существуют константы c и d, такие, что  для любой функции f из [A] выполнено D(f) \leq c \log_2 L(f) + d (нетрудно заметить, что данная верхняя оценка для D(f) наилучшая по порядку). Известно, что все конечные системы булевых функций равномерны.
Для многозначной логики известны тривиальные примеры неравномерных систем, а также некоторые достаточные условия для равномерности систем, порождающих предполные классы. Я расскажу о некоторых необходимых и достаточных условиях равномерности в k-значной логике, а также о некоторых других соотношениях между глубиной и сложностью реализации функций формулами.

21 октября 2014 г.
Д.А. Шабанов, И. Акользин «Гиперграфы с очень большим хроматическим числом»
В докладе пойдет речь об известной проблеме Эрдеша-Хайнала о раскрасках гиперграфов. Пусть m(n,r) - это минимально возможное число ребер n-однородного гиперграфа с хроматическим числом больше r. Нами получены новые нижние и верхние оценки m(n,r) в случае, когда значение параметра r очень велико по сравнению с параметром однородности n. Кроме того, будет рассмотрена аналогичная постановка задачи для максимальной реберной степени гиперграфа. Доказательства основаны на недавней работе Д. Черкашина и Я. Козика, а также на конструкции А. Сидоренко для верхних оценок турановских плотностей.

28 октября 2014 г.
А. Челноков «Агрегация урловых факторов на основе дерева шаблонов»
Рассмотрен новый подход к агрегации урловых факторов внутри одного хоста, объединяющий в себе подходы агрегации по директориям и параметрам. В качестве основной модели используется модернизированная версия дерева шаблонов.

04 ноября 2014 г.
Семинара не будет.

10 ноября 2014 г. (понедельник, ауд. 7 Небо)
Ю.Е. Нестеров «Subgradient methods for huge-scale optimization problems»
We consider a new class of huge-scale problems, the problems with sparse subgradients. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends logarithmically in the dimension. This technique is based on a recursive update of the results of matrix/vector products and the values of symmetric functions. It works well, for example, for matrices with few nonzero diagonals and for max-type functions.
We show that the updating technique can be efficiently coupled with the simplest subgradient methods. Similar results can be obtained for a new non- smooth random variant of a coordinate descent scheme. We present also the promising results of preliminary computational experiments.

18 ноября 2014 г.
М.Е. Жуковский «Распределение критических точек в законе нуля или единицы»
Число a из интервала (0,1) называется k-критическим, если случайный граф G(n,n^{-a}) не
подчиняется k-закону нуля или единицы. Иными словами, найдется свойство первого порядка, выражаемое формулой, кванторная глубина которой ограничена числом k, предел вероятности которой либо не существует, либо отличен от нуля и единицы. Оказывается, при достаточно больших k существует бесконечно много k-критических точек в k-законе нуля или единицы. В докладе мы сконцентрируемся на доказательстве этого факта, на оценках наименьшего k, при котором k-критических точек бесконечно много, а также на поиске наименьшей и набольшей k-критической точки.

25 ноября 2014 г.
Семинара не будет.

02 декабря 2014 г.
А.В. Кудинов «Об одной старой просто формулируемой нерешенной
задаче в модальной логике»
Я расскажу об одной старой просто формулируемой нерешенной задаче в модальной логике и о наших скромных попытках к ней подобраться.

09 декабря 2014 г.
А.А. Вороненко «Оценки размера области определения частичной булевой функции,
достаточной для порождения любой линейной»
Рассматривается задача нахождения частичной булевой функции n переменных, у которой для любой линейной функции найдется n+1 набор в общем положении, что позволяет однозначно задать линейную функцию. Такие функции называются универсальными и существуют при n>=4. Размер необходимой области определения ограничен линейными по n функциями. Их оценке и посвящен доклад.

16 декабря 2014 г.
Г.Г. Гусев «Обобщение школьной теоремы Абеля на случай произвольного количества переменных»
Классическая теорема Абеля заключается в том, что комплексные корни многочлена степени $d$ от одной переменной нельзя выразить в радикалах через его коэффициенты. Эта теорема может быть доказана с помощью групп Галуа, но я не буду ничего о них рассказывать во время своего доклада. Вместо этого я расскажу о топологической теории Галуа, изобретенной В.И. Арнольдом. Недавно нам удалось разобраться с помощью этого топологического подхода, в каких случаях решения системы $n$ полиномиальных уравнений от $n$ переменных могут быть выражены в радикалах через коэффициенты полиномов.

19 января 2015 г. (понедельник, 16:00 - 18:00, ауд. Гарвард)
S. Kristensen «Metric Diophantine approximation - from continued fractions to fractals»
The metric theory of Diophantine approximation dates back to Èmile Borel (1909) and Khintchine (1924). Starting from Khintchine, we will give a survey of metric Diophantine approximation, with tthe occurrence of fractal structures in number theory playing a major part. Particular emphasis will be put on recent efforts to tackle major outstanding problems via two different avenues: One uses classical techniques from fractal geometry and number theory, while the other uses methods from homogeneous dynamics.

Заседания 2013-2014 учебного года
Заседания 2012-2013 учебного года

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

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

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

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

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