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

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

Адрес e-mail:

Кафедральный научно-исследовательский семинар: заседания 2010/11 года

Заседания кафедрального семинара проходили по вторникам в здании МФТИ в Климентовском переулке в аудитории 315 с 17:30 до 19:00.

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


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

7 июня 2011 г.
С.В. Савченко «О числе циклов длины m=5,6 в регулярных турнирах порядка n»
Продолжение нашего доклада (семинар от 19 апреля) мы начнем с определения дважды регулярного турнира и построения важных примеров. Затем с помощью "фундаментального" тождества $T^{4}+2T^{3}-T=S^{2}+S+(\delta^{2}-\delta)J$ будет доказана справедливость формулы $2c_{5}(T,i)+5c_{4}(T,i)=(n-1)(n+1)(n-3)(n+3)/16$ для произвольной вершины $i$ регулярного турнира $T$ (нечетного) порядка $n.$ Это позволит свести случай длины $m=5$ к случаю $m=4.$ Для $m=6$ проблема является намного более сложной. Однако, как мы покажем, число циклов длины $m=6$ в регулярном турнире $T$ довольно просто выражается через следы $6$-ой и $4$-ой степеней его матрицы смежности и порядок $n.$ Хорошо известно, что все собственные значения $T,$ отличные от $\delta=(n-1)/2,$ лежат на прямой $\Re e\ z=-1/2$ и сумма квадратов их мнимых частей всегда равна $n(n-1)/4.$ Это позволяет заменить рассматриваемую экстремальную комбинаторную задачу на стандартный поиск условного экстремума при помощи средств математического анализа. В частности, при $n\ge 11$ максимум выражения для числа циклов длины $m=6$ достигается если и только если квадрат мнимой части комплексного собственного значения равен $n/4.$ Как известно, это бывает только в случае, когда турнир $T$ является дважды регулярным. В свою очередь, полученная формула для $c_{6}(T)$ и большая протяженность спектра регулярного локально транзитивного турнира $RLT_{n}$ позволяет предположить, что минимум числа циклов длины $m=6$ достигается на $RLT_{n}.$ По крайней мере, это подкрепляется результатами компьютерной обработки файлов Б. Маккея для $n=7,9,11,13$ и дополнительными спектральными рассуждениями. Если останется время, то будет прокомментирован случай произвольной длины $m.$


17 мая 2011 г.
В. Турчин «Операды и узлы»


26 апреля 2011 г.
А. Стояновский «Обобщенные гипергеометрические функции и негауссовы интегралы»
Я надеюсь рассказать о двух связанных сюжетах, имеющих далеко идущие и совершенно неисследованные обобщения и приложения. Первый сюжет --- задача вычисления интеграла экспоненты однородного полинома от $n$ переменных по $n$-мерному пространству. До недавнего времени был известен только интеграл экспоненты квадратичного полинома (гауссов интеграл). Оказывается, в общем случае интеграл является обобщенной гипергеометрической функцией от инвариантов однородного полинома. Обобщенные гипергеометрические функции представляют собой замечательный класс функций, включающий все элементарные функции и почти все специальные функции математической физики. Например, корень алгебраического уравнения любой степени от одной переменной есть обобщенная гипергеометрическая функция от коэффициентов уравнения. Я надеюсь рассказать основные определения и некоторые теоремы.


19 апреля 2011 г.
С. В. Савченко «О числе циклов длины m в регулярных турнирах порядка n»
Хорошо известно, что для любого $m\ge 3$ полный граф содержит максимальное число циклов длины $m$ среди всех (простых) графов порядка $n.$ Более того, легко даже определить это число. Однако, аналогичная экстремальная задача в классе всех направленных графов (в английской терминологии, oriented graphs) является намного более трудной. Очевидно, максимум теперь достигается на некоторой ориентации полного графа. В теории графов такие ориентации называются турнирами. В классе всех турниров порядка $n$ проблема максимума числа $m$-циклов полностью решена только для длин $m=3$ (Кендалл и Бабингтон-Смит, 1940) и $m=4$ (Коломбо, 1964). В обоих случаях для нечетного $n$ максимум достигается на регулярном турнире. В нашем докладе при помощи матричных методов мы сначала передокажем известные результаты для $m=3,4$, а затем сведем случай длины $m=5$ к случаю $m=4$ в классе регулярных турниров. При $m\ge 6$ число циклов длины $m$ в турнире уже не совпадает со следом $m$-ой степени матрицы смежности деленное на $m.$ Поэтому для $m\ge 6$ проблема является более сложной. Однако, как мы покажем, при $m=6$ число циклов длины $m$ в регулярном турнире также зависит только от его спектра. Этот факт и известные результаты о расположении собственных значений регулярного турнира позволяют применить метод множителей Лагранжа и, таким образом, решить рассматриваемую экстремальную комбинаторную задачу для $m=6$ и $n\ge 11$ при помощи стандартных средств математического анализа.


29 марта 2011 г.
Ф. Цитович «Субоптимальные последовательные статистические решения, основанные на независимых наблюдениях»
В докладе будет рассказано о задаче робастной последовательной проверки простых гипотез, когда для обеспечения робастности осуществляется переход к задаче проверки сложных непараметрических гипотез. Для новых гипотез множества допустимых распределений являются некоторыми окрестностями заданных распределений, учитывающими априорную информацию о возможных ошибках в результатах наблюдений. Предлагаются робастные последовательные процедуры в случае равномерной оценки плотности распределения, а также в случае оценки поведения распределения на бесконечности, которые обеспечивают заданный уровень вероятности ошибок для всех распределений из окрестностей исходных распределений. В качестве функции риска используется максимальная средняя продолжительность процедуры. Для построенных процедур приводятся неасимптотические оценки для функции риска, проводится сравнение с функцией риска асимптотически оптимальной процедуры. Также предложена многоэтапная модификация процедуры, которая является более предпочтительной с практической точки зрения. Будут приведены результаты численного моделирования и сравнение рассматриваемых статистических решений с $\chi^2$ критерием.


1 марта 2011 г.
А. Е. Ромащенко «Экономные схемы хранения множества с быстрой операцией чтения»
H. Buhrman, P. B. Miltersen, J. Radhakrishnan, S. Venkatesh предложили способ хранения n-элементного множества S из m-элементного универсума со следующими замечательными свойствами:
* Размер хранилища составляет O(n \log m) битов, т.е., близок к оптимальному.
* Для того, чтобы с вероятностью 0.99 получить ответ на вопрос "принаждежит ли элемент x множеству S?", достаточно прочитать из хранилища единственный бит.
Конструкция Бюрмана и соавторов основана на неоднородных расширяющих графах (экспандерах). Существовование таких графов можно доказать вероятностно. Мы обсудим, как построить такую структуру данных конструктивно, используя генераторы псевдо-случайных битов.


22 февраля 2011 г.
А. Я. Канель, М. Харитонов «Субэкспоненциальные оценки в теореме Ширшова о высоте»
Работа посвящена получению субэкспоненциальных оценок в теореме Ширшова о высоте. Множество слов $V$ имеет высоту $h$ над множеством слов $Y$ (именуемым базисом Ширшова, если каждое слово из $V$ имеет вид $v_{i_1}^{k_1}\cdots v_{i_s}^{k_s}$ где $v_{i_\alpha}\in Y$ при всех $\alpha$ и $s\leqslant h$). Слово $W$ называется $n$-разбиваемым, если его можно представить в виде $W=W_0W_1\cdots W_n$ где подслова $W_1,\dots,W_n$ идут в порядке лексикографического убывания. Из не $n$-разбиваемых слов состоит базис алгебры с тождеством степени $n$. А. И. Ширшов показал, что множество слов, не являющихся $n$-разбиваемыми, над алфавитом из $l$ букв имеет ограниченную высоту $h$ над $Y$~-- множеством слов степени не выше $n-1$. Мы показываем, что $H\leqslant\Phi(n,l)$, где $$\Phi(n,l) = E_1 l\cdot n^{E_2+9(2e^2+1)\ln n} ,$$ где $E_1 , E_2$ -- константы.
Пусть $l$, $n$ и $d>n$ -- некоторые натуральные числа. Тогда все слова над $l$-буквенном алфавитом длины не меньше, чем $\Psi'(n,d,l)$, либо содержат $x^d$, либо являются $n$-разбиваемыми, где $$ \Psi'(n,d,l)=D_1 l(n^2d)^{(2e^2+1)\ln(n^2d)+D_2}(nd)^4 $$ здесь $D_1, D_2$ -- константы.
Тем самым получаются субэкспоненциальные оценки на индекс нильпотентности ниль-алгебр для произвольной характеристики. Изначальная оценка Ширшова носила рекурсивный характер, в 1982 году была получена двойная экспонента, в 1992 году -- экспоненциальная оценка (что означало положительный ответ на вопрос, поставленный Е. И. Зельмановым в Днестровской тетради). Доказательство использует идею В. Н. Латышева, связанную с применением теоремы Дилуорса к исследованию не $n$-разбиваемых слов.


21 декабря 2010 г.
А.Х. Шень «Колмогоровская сложность в доказательствах»
Многие рассуждения могут быть неформально (а иногда даже формально) изложены с помощью колмогоровской сложности. В докладе я попытаюсь разобрать несколько характерных примеров по выбору слушателей (разной степени сложности и игрушечности)
- бесконечность множества простых чисел
- конструктивная лемма Ловаса по Мозеру
- матрицы без одноцветных миноров
- трудно вкладываемое семейство матриц (тут есть, кстати, открытый вопрос, который я бы хотел задать участникам семинара)
- покрытие множества однородными
- неравенства для объёмов и сложностей
- квадратичные нижние оценки для одноленточных машин Тьюринга
- закон больших чисел
- шенноновская энтропия и кодирование


14 декабря 2010 г.
С. Спирин «Реконструкция филогенетических деревьев»
Доклад будет состоять из двух частей. В первой я постараюсь рассказать о молекулярной филогенетике и понятиях, возникающих в задаче реконструкции филогенетических деревьев по последовательностям белков и нуклеиновых кислот. Во второй предполагается изложить содержание работы Mihaescu, Levy, Pachter "Why Neighbor-Joining Works" (Algorithmica 54, 2009), в которой доказано некоторое количество интересных, с моей точки зрения, утверждений об устойчивости к шуму во входных данных одного из лучших методов реконструкции филогении, а именно метода объединения соседей (Neighbor-Joining).


7 декабря 2010 г.
А. Ромащенко, А. Чуклин «О коммуникационной сложности синхронизации похожих строк»
Пусть на двух компьютерах хранятся достаточно "похожие" файлы X и Y. Будем считать, что оба файла X и Y состоят из n битов, и отличаются они друг от друга не более чем в доле alpha позиций. Компьютеры соединены линией связи. Как переслать файл X с первого компьютера на второй наиболее экономным способом (требуется минимизировать число битов, которыми обмениваются компьютеры)? Несложная количественная оценка показывает, что для решения задачи компьютерам необходимо обменяться не менее h(alpha)n+o(n) битами (где h обозначает двоичную энтропию). Известен 3-раундовый детерминированный коммуникационный протокол, который позволяет достичь данной оценки. Однако этот протокол требует выполнения обоими компьютерами экспоненциальных вычислений. Задача становится проще, если мы позволяем компьютерам использовать датчики случайных чисел. Мы покажем, что оптимальное число битов может быть достигнуто в вероятностном коммункационном протоколе с полиномиальными алгоритмами кодирования и декодирования. Предлагаемое решение является упрощением протокола Адама Смита (Adam Smith, 2006).


30 ноября 2010 г.
В. Горин «Случайные ступенчатые поверхности»
В докладе будет рассказано об интересной модели случайных ступенчатых поверхностей в трёхмерном пространстве, которая много и интенсивно изучалась в последнее десятилетие. Особенностью этой модели является появление так называемых "предельных форм": при уменьшение шага сетки случайная дискретная поверхность стремится к детерминистическому гладкому пределу. Предельная поверхность, в свою очередь, кодируется решением дифференциального уравнения Бургерса и оказывается связанной с некоторыми алгебраическими кривыми.


23 ноября 2010 г.
Семинар А. В. Булинского был отменен

16 ноября 2010 г.
Г.Г. Гусев «Комбинаторика смешанных объемов Минковского и элементарная алгебра»
Я расскажу про 2 недавних результата, полученных мною и Сашей Эстеровым в комбинаторной геометрии. Оба результата касаются смешанных объемов Минковского выпуклых тел и имеют непосредственное значение в школьной алгебре и алгебраической геометрии. В частности, один из результатов посвящен следующей задаче. Пусть дана система некоторого числа алгебраических уравнений от такого же числа комплексных переменных. При какой комбинации входящих в нее мономов следует ожидать, что система не имеет решений? Имеет ровно одно решение? Ответ на первый вопрос не опубликован, но является известным фольклором. По второму вопросу Саша сформулировал гипотезу, которую я доказал в некотором существенном случае простыми геометрическими методами. Доклад в основном будет опираться на обычную геометрическую интуицию. Знание топологии и алгебраической геометрии не понадобится.


9 ноября 2010 г.
Н.А. Ирхина «Принцип Ванга в математической теории страхования»


26 октября 2010 г.
Д. Мусатов «Эффективизация теорем о колмогоровской сложности при помощи генератора Нисана-Вигдерсона»
Многие теоремы о Колмогоровской сложности опираются на существование комбинаторных объектов с определёнными свойствами, таких как экспандеры или экстракторы. Обычно использование вероятностного метода для построения таких объектов приводит к лучшим параметрам по сравнению с явными конструкциями и, соответственно, к более сильным теоремам. Однако, поиск объекта с нужным свойством требует экспоненциально большого объёма памяти и потому вероятностный метод не даёт аналогичных теорем для сложности с ограничением на ресурсы. Оказывается, можно сократить требуемый объём памяти до полиномиального, если искать нужный объект среди значений генератора Нисана--Вигдерсона, и он там обязательно найдётся. Мы приведём два примера. Во-первых, мы докажем аналог теоремы Мучника для сложности с ограничением на память. Теорема утверждает, что для любых слов a и b существует программа p минимально возможной длины, переводящая a в b и простая относительно b. Во-вторых, мы построим аналог конструкции Зиманда колмогоровских экстракторов, т.е. функций от двух аргументов, выдающих слово длины около 2s и дефекта случайности не больше k при подаче на вход двух слов сложности не меньше s и зависимости не больше k.


19 октября 2010 г.
М. Матвеев «Теория порождающих многогранников»
Рассматривается отношение между множеством конусов и многогранником, при котором каждый конус есть коническая оболочка некоторой грани многогранника. Такое отношение называется порождением множества конусов многогранником. Исследование отношения порождения приводит к новым, часто неожиданным свойствам как порождаемых множеств конусов, так и порождающих эти множества многогранников. Среди них: существование непорождаемых множеств из трех конусов; возможность выпуклого объединения граней многогранников; обобщение понятия отделимости на случай более двух множеств; теоремы о среднем для многогранников.


12 октября 2010 г.
Бен Лившиц (Microsoft Research) «Обнаружение вредоносного программного обеспечения в вебе»
Доклад будет посвящен вопросам компьютерной безопасности и задачам обнаружения атак последнего поколения против браузеров. Будет рассказано о недавних разработках в этой области.
RePriv: The first project I'll describe is RePriv, a browser-based technology that allows for Web personalization, while controlling the release of private information within the browser. We demonstrate how to perform mining of core user interests within a browser. We propose a protocol on top of HTTP that can be used to seamlessly integrate RePriv with existing Web infrastructure and also show how pluggable miners can be used to extract more detailed information and how to check these third-party miners for privacy leaks. We show that RePriv's default in-browser mining can be done with no noticeable overhead to normal browsing, and that the results it produces converge quickly. We then go on to show similar results for each of our case studies: that RePriv enables high-quality personalization, and that the performance impact each case has on the browser is minimal. We conclude that personalized content and individual privacy on the Web are not mutually exclusive.
JSBench: The focus of the second project, JSBench, is on JavaScript performance in browsers. JavaScript is widely used in Web-based applications and is increasingly popular with developers. So-called browser wars in recent years have focused on JavaScript performance, specifically claiming comparative results based on benchmark suites such as SunSpider and V8. In our prior work, we evaluated the behavior of JavaScript Web applications from commercial Web sites and compare this behavior with the benchmarks. We conclude that benchmarks and real Web applications behave very differently when it comes to just about every aspect of runtime performance. I'll present more recent work that aims to create more realistic browser benchmarks using record and replay techniques through recording and replaying the behavior of real site interactions and share some of our preliminary results in that space.


5 октября 2010 г.
Сергей Измалков, Дмитрий Ильинский, Алексей Савватеев (РЭШ) «Дуэли трёх лиц»
В докладе будет дано окончательное решение задачи о трёх дуэлянтах, из которых один бьёт наверняка, а два других — с произвольно заданными точностями.
Эта задача имеет целый ряд экономических приложений.
Стрельба ведётся в циклической очерёдности «слабый — средний — сильный». Разрешается «пропускать ход», но три пропуска подряд ведут к смерти всех трёх. Будут охарактеризованы все совершенные равновесия в чистых стратегиях в этой игре. Показано, что, чем точнее стреляют двое «слабых», тем хуже сильному: во всех чистых равновесиях его выигрыш стремится к нулю, когда точность слабейшего стремится к единице.
Неожиданным сюрпризом является существование смешанного равновесия, в котором (при точности слабейшего, стремящейся к единице) почти наверняка выигрывает сильнейший. Это равновесие, однако, существует только (при порядке стрельбы, указанном выше) тогда, когда начинает средний.


14 сентября 2010 г.
М. Е. Жуковский «Существование последовательности случайных дистанционных графов, подчиняющейся классическому закону нуля или единицы»
Классический закон нуля или единицы, который впервые был установлен в 1969 году для случайных графов в модели Эрдеша-Реньи, для случайных дистанционных графов не выполнен. Несмотря на это, нам удалось найти последовательность случайных дистанционных графов, подчиняющуюся этому закону. В ходе доказательства существования такой последовательности была решена одна интересная задача о существовании решения системы линейных уравнений с коэффициентами из {0,1}.


7 сентября 2010 г.
А. Я. Канель-Белов «Квантизация и проблема Якобиана»
Пусть F: Cn → Cn — полиномиальное отображение комплексного пространства в себя. Когда оно обратимо? Необходимым условием является локальная обратимость в каждой точке.Знаменитая проблема Якобиана утверждает, что это условие является достаточным. В течение более чем 20 лет, вплоть до 1968 года, проблема Якобиана считалась решённой для n=2, с тех пор каждые несколько месяцев появляются новые «доказательства».
С проблемой Якобиана тесно связана гипотеза Диксмье, формулировка которой для n=1 выглядит невинно: пусть P, Q — многочлены от x и (d/dx), причём PQ – QP = 1. Верно ли, что (d/dx)можно выразить через P и Q? Это утверждение до сих пор не доказано. Недавно мне удалось доказать экивалентность этого утверждения проблеме Якобиана для n=2. Стабильная эквивалентность гипотезы Якобиана и Диксмье доказана в работе http://arxiv.org/abs/math/0512171. Доказательство использует аналогию между классическими и квантовыми объектами. Предполагается дать элементарное объяснение этой аналогии.
Другое, близкое, утверждение именуется теоремой Абьенкара–Моха и выглядит как олимпиадная задача (каковой и является). Пусть P, Q, R — многочлены, причём R(P(x),Q(x)) = x. Доказать, что либо степень P делит степень Q, либо наоборот.


31 августа 2010 г.
А. А. Разборов (МИРАН) «Алгебры флагов»
Значительная часть экстремальной комбинаторики посвящена изучению вопроса о том, чему, при определённых предположениях, может быть равна плотность вхождений фиксированных комбинаторных объектов (таких, как графы, орграфы или гиперграфы) в большие неизвестные объекты того же типа. Используя сравнительно простые идеи и конструкции из логики, алгебры и теории меры, мы строим общую теорию, позволяющую рассматривать все такие задачи в рамках единого подхода, а также выделить несколько общематематических структур, неявно используемых в большинстве ранее известных аргументов. Ядром этой структуры служат специальные коммутативные алгебры, определяемые в терминах конечных моделей рассматриваемой теории первого порядка.
В настоящем докладе я попытаюсь дать общее представление об этой теории, уделив при этом особое внимание полученным с её помощью конкретным результатам.


Заседания семинара в 2009/10 учебном году
Заседания семинара в 2008/09 учебном году
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

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

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

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

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