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

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

Адрес e-mail:

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

В 2009/10 учебном году заседания кафедрального семинара проходили по вторникам в здании МФТИ в Климентовском переулке в аудитории 303 с 17:00 до 18:30.

25 мая 2010 г.
А.В. Леонидов (Физический институт им. П.Н. Лебедева РАН) «Сложные сети (complex networks) глазами физиков»
В докладе обсуждаются некоторые задачи, в которых системы, связанные со сложными сетями, обсуждаются методами, характерными для теоретической физики. В частности, речь пойдет о критических явлениях в сложных сетях, аномальной диффузии на них и их флуктуационных свойствах.


18 мая 2010 г.
С. К. Ландо (ГУ ВШЭ, НМУ, НИИ системных исследований РАН) «Меандры»
Меандр представляет собой пару пересекающихся, но не самопересекающихся замкнутых кривых на плоскости. Задача перечисления меандров с данным числом точек пересечения восходит к последней работе Анри Пуанкаре, в которой исследовались неподвижные точки сохраняющих площади отображений кольца на плоскости в себя, вращающих граничные окружности кольца в противоположные стороны. Меандры оказались связаны с самыми разными математическими теориями — например, с матричными моделями математической физики и алгебрами Темперли-Либа. Несмотря на признанную важность задачи, ни она, ни ее многочисленные варианты до сих пор не нашли удовлетворительного решения. Нельзя исключать, что меандры открывают принципиально новый класс перечисляемых объектов, исследование которого еще предстоит выполнить.
В докладе будут приведены некоторые оценки на количество меандров, описаны различные варианты постановки задачи, методы, которые применялись к ее решению и другие возможные подходы.


11 мая 2010 г.
А. Е. Ромащенко «Экспандеры и надёжные булевы схемы»
В докладе будет рассказано о том, как строить надёжные (глобально) булевы схемы из ненадёжных (локально) функциональных элементов. Основным комбинаторным инструментом в предлагаемых конструкциях служат графы-расширители.


20 апреля 2010 г.
Ю. Гончаров (ВЦ РАН) «Минимаксная задача выбора признаков для построения классификатора методом SVM»
Определение подмножества информативных признаков является одним из направлений совершенствования алгоритмов обучения классификации. Алгоритм обучения классификации методом SVM считается одним из наиболее используемых на практике. В докладе рассказывается о задаче выбора признаков, в результате решения которой происходит одновременный выбор подпространства признаков и построение SVM классификатора в этом подпространстве.
Математически задача сводится к решению минимаксной задачи оптимизации. Описываются методы решения задачи с помощью алгоритма поиска седловой точки и алгоритма недифференцируемой оптимизации субградиентного типа. При решении минимаксной задачи требуется вычислять проекцию на пересечение простых множеств, для каждого из которых в отдельности операция проекции вычисляется просто.
Рассказывается о эффективном алгоритме Дейкстры для вычисления проекции на пересечение простых множеств. Приводятся результаты численных экспериментов.


6 апреля 2010 г.
А. В. Гасников (МОУ МФТИ) «Модели расчета матрицы корреспонденций и распределения потоков»
Будут приведены постановки задач (на примере пассажирских потоков), пришедшие от прикладников, и некоторые "рецепты" решения этих задач. Для объяснения некоторых рецептов потребуется достаточно интересная математика. А именно, планируется обсудить:

1) Явление концентрации меры (Пуанкаре, Леви, Мильман, Громов, Талагран) или геометрическое (изопериметрическое) толкование предельных теорем и законов больших чисел теории вероятностей (объяснение концентрации значений “хороших” функций (таких, например, как хроматическое число графа или перманент матрицы), определенных на случайных комбинаторных объектах (графах или матрицах) большой размерности, в окрестности медианы функции (асимптотически, по размерности объекта, равной математическому ожиданию); а также объяснение “фазовых переходов” в случайных комбинаторных объектах большой размерности), нелинейный закон больших чисел (некоторые результаты В.И. Опойцева), элементы стохастического агрегирования, предельные формы (А.М. Вершик, Я.Г. Синай);

2) Концепцию энтропии, элементы теории макросистем: Будет приведен основной аппарат, необходимый для исследования динамики макросистем при больших значениях времени. В основе динамики лежит дискретный эргодический марковский процесс с огромным числом состояний. При больших значениях времени распределение макросистемы по микросостояниям будет близко к стационарному. С ростом размерности макросистемы (количества состояний марковского процесса) стационарное распределение концентрируется в окрестности наиболее вероятного макросостояния, которое и принимается за равновесное для данной макросистемы. В качестве примера применения описанного формализма будет приведен вывод статической гравитационной модели расчета матрицы корреспонденций (одной из наиболее популярных в приложениях) исходя из “разумной” (индивидуально выгодной) динамики обменов местами работы и местами жительства. Другими, более известными, примерами, являются вывод распределения Больцмана–Парето населения по доходу (кинетика социального неравенства) и вывод модели хищник – жертва (по Николису–Пригожину)).


30 марта 2010 г.
М. Матдинов (СУНЦ МГУ) «О сдвигах клетчатого пространства»
В докладе будет приведен и доказан критерий существования биекции между множеством целочисленных точек N-мерного пространства и некоторым подмножеством этого множества, удовлетворяющей лишь только одному условию, состоящему в том, что евклидово расстояние между точкой и ее образом ограничено.


23 марта 2010 г.
Д. А. Шабанов «Теорема Ван дер Вардена и гиперграфы без треугольников»
Знаменитая теорема Ван дер Вардена утверждает, что в любой раскраске множества целых чисел в конечное число цветов найдется сколь угодно длинная одноцветная арифметическая прогрессия. Конечный вариант теоремы Ван дер Вардена говорит о том, что при фиксированном количестве цветов k и заданной длине прогрессии n искомую одноцветную прогрессию можно найти в начальном отрезке натурального ряда фиксированной длины. В докладе речь пойдет об оценках функции Ван дер Вардена W(n,k) — нижней границе длины начального отрезка натурального ряда, в любой k-цветной раскраске которого найдется одноцветная арифметическая прогрессия длины n. Будут представлены последние результаты в данной задаче, в том числе и полученные докладчиком с помощью вероятностной техники раскраски гиперграфов.


16 марта 2010 г.
В. А. Кошелев «Применение компьютера для решения задач комбинаторной геометрии на примере проблем Эрдеша–Секереша»
Речь пойдет о следующих задачах: 1) Из любых 17 точек на плоскости в общем положении можно выбрать вершины выпуклого 6-угольника и, более того, выпуклого шестиугольника не более чем с двумя точками внутри 2) Из любых 18 точек на плоскости можно выбрать вершины выпуклого шестиугольника не более чем с одной точкой внутри. Более того, 17 и 18 есть минимальные значения.
Это частные случаи классических задач, которым более 70 лет. В общем виде решения нет, а частные случаи решались довольно тяжело. Так, для шестиугольников (пункт 1а) доказательство было получено всего четыре года назад с помощью компьютера. О том, как получить, компьютерные решения для задач 1 и 2, и пойдет речь в докладе.


2 марта 2010 г.
А. Рябченко, Е. Самосват «Оценка числа треугольников (и других подграфов) в случайных графах в модели Барабаши–Альберт»
Считается, что графы в модели Барабаши–Альберт хорошо моделируют веб-графы. В частности, имеют схожее распределение степеней вершин и значение диаметра.
Докладчиками была разработана техника подсчёта числа подграфов различного вида. На докладе будет проведён подсчёт для случая полного графа на трех и четырех вершинах.


9 февраля 2010 г.
Л. Д. Беклемишев «Об одном комбинаторном утверждении, независимом от аксиом арифметики»
К. Гёдель построил первые примеры элементарных арифметических утверждений, независимых от аксиом арифметики или даже от аксиом теории множеств. Его утверждения получались кодированием понятий из логики и поэтому были достаточно сложны и не столь естественны с математической точки зрения. В конце 1970-х годов Пэрис, Харрингтон и Кирби нашли первые независимые от аксиом арифметики простые комбинаторные утверждения "математического характера". С тех пор список известных утверждений такого рода неуклонно, хотя и достаточно медленно, растёт. Мы расскажем об ещё одном недавнем, особенно простом, примере независимого комбинаторного утверждения, а также о некоторых идеях алгебраического подхода к анализу формальной доказуемости, на основе которого он был получен.


22 декабря 2009 г.
Ю. А. Калнишкан (Royal Holloway University of London) «Гребневая регрессия как байесовский метод»
В докладе будет рассказано о гребневой регрессии и её различных интерпретациях. Гребневую регрессию можно понимать как регуляризованный метод наименьших квадратов, т.е. алгоритм, основанный на поиске баланса между точностью описания данных и сложностью гипотезы. Если, однако, предположить, что данные подчиняются нормальному распределению, гребневая регрессия оказывается байесовским методом. Такой вероятностный подход позволяет вывести одно любопытное тождество, связывающее ошибку регрессии в секвенциальном и пакетном сценариях. Из тождества в частности следует, что ошибка гребневой регрессии при секвенциальном предсказании данных совсем немного отличается от ошибки, минимизированной ретроспективно.


15 декабря 2009 г.
Г. Г. Гусев «Вычисление эйлеровых характеристик некоторых бифуркационных множеств», продолжение
Для алгебраического многообразия, заданного в комплексном пространстве системой полиномиальных уравнений, имеется формула Бернштейна-Кушниренко-Хованского. Она вычисляет эйлерову характеристику множества общих нулей системы многочленов в терминах соответствующих многогранников Ньютона в случае, если система многочленов «невырождена».
На предыдущем докладе я рассказал, как по вееру строятся компактификации комплексного тора. В этот раз я расскажу с их помощью доказательство формулы Бернштейна-Кушниренко-Хованского и как с помощью техники интегрирования по эйлеровой характеристике получать обобщения этой формулы на некоторые интересные вырожденные случаи, возникающие (в частности) в теории особенностей.


8 декабря 2009 г.
Д. В. Мусатов, А. Е. Ромащенко, А. Шень «Теорема Мучника и вариации»
В первой части доклада 27 октября была сформулирована теорема Мучника об условном кодировании, и изложено её доказательство, опирающееся на онлайн-паросочетания. Во второй части будет изложено другое доказательство, опирающееся на свойства экстракторов, а также сформулированы некоторые обобщения.


1 декабря 2009 г.
Г. Г. Гусев «Вычисление эйлеровых характеристик некоторых бифуркационных множеств»
Для алгебраического многообразия, заданного в комплексном пространстве системой полиномиальных уравнений, имеется формула Бернштейна-Кушниренко-Хованского. Она вычисляет эйлерову характеристику множества общих нулей системы многочленов в терминах соответствующих многогранников Ньютона в случае, если система многочленов «невырождена». Я расскажу, как с помощью техники интегрирования по эйлеровой характеристике получать обобщения этой формулы на некоторые интересные вырожденные случаи, возникающие (в частности) в теории особенностей.


24 ноября 2009 г.
А. В. Савватеев «Миграционно-устойчивое разбиение мира на страны»
Доказана известная гипотеза Алесины о том, что линейный мир можно так разрезать на заданное число кусков-стран, что никто не захочет сменить свою прописку. Будет дана строгая математическая формализация этого утверждения и доказательство, базирующееся на лемме Гейла-Никайдо.


17 ноября 2009 г.
Д. А. Шабанов «Предписанное хроматическое число полных многодольных графов»
В докладе будет рассказано о связи между предписанными раскрасками полных r-дольных графов и полноцветными r-раскрасками равномерных гиперграфов. С помощью этой связи будет найдена асимптотика предписанного хроматического числа полного r-дольного графа, у которого все доли имеют одинаковый размер m. Полученный результат позволяет получить асимптотику в более широкой области изменения параметров, чем в ранее известных результатах.


10 ноября 2009 г.
Г. А. Кабатянский (ИППИ РАН) «Стеганография – вероятностная и комбинаторная модели»
В докладе будут описаны модели, указанные в названии, и рассказаны последние результаты в этой области : Рябко и Рябко (Проблемы передачи информации, 2009, №3) и докладчика совместно с Ф. Галаном (Проблемы передачи информации, 2009, №3).


3 ноября 2009 г.
А. В. Куликов (мехмат МГУ, ООО «Газпром-экспорт») «Многомерные когерентные меры риска и их применение к решению задач финансовой математики»
Аннотация


27 октября 2009 г.
Д. В. Мусатов, А. Е. Ромащенко, А. Шень «Теорема Мучника и вариации»
Допустим, Алисе нужно передать Бобу длинный файл через коммуникационный канал с дорогим трафиком. Ясно, что оптимальное решение - применить к файлу архиватор и послать архив. А что, если у Боба уже есть старая версия файла? Если и у Алисы есть эта старая версия, то ей достаточно послать архив не самого файла, а только списка исправлений. Но что делать, если никаких сведений о версии Боба у Алисы нет? Удивительный факт, доказанный Ан.А.Мучником, состоит в том, что Алиса может получить столь же короткий архив, используя совсем небольшую дополнительную информацию (логарифмическую по длине входа)!
В докладе будут даны все необходимые определения и формулировки, рассказаны два новых доказательства теоремы, предложенные авторами, а также сформулированы несколько обобщений.


20 октября 2009 г.
А. Б. Купавский «Топологические методы в комбинаторике: обзор»
В докладе будет рассказано о применении различных методов алгебраической топологии для получения оценок хроматических чисел графов и гиперграфов. Будет сформулирован ряд нерешенных задач.


13 октября 2009 г.
К. Воронцов (ВМК МГУ) «Точные комбинаторные оценки вероятности переобучения»
Рассматривается проблема переобучения - один из центральных вопросов теории статистического обучения (Statistical Learning Theory). Предлагается комбинаторный подход, основанный на слабых вероятностных предположениях и выводе точных формул для функционалов типа скользящего контроля. Обсуждаются эффекты расслоения и связности в семействах алгоримтов классификации. Благодаря этим эффектам вероятность переобучения в реальных ситуациях оказывается существенно ниже, чем предсказывают классические теории.


6 октября 2009 г.
М. А. Ройтберг (Институт математических проблем биологии РАН, Школа анализа данных Яндекса) «Выравнивание деревьев и его применение для выравнивания вторичных структур РНК»
Молекула РНК - это полимерная цепочка, состоящая из звеньев (мономеров) четырех видов. «Звенья» РНК могут «склеиваться», образуя т.н. вторичную структуру. Молекулу РНК удобно представлять в виде символьной последовательности в 4-буквенном алфавите, а вторичную структуру - в виде скобочной структуры, ассоциированной с этой последовательностью (парные скобки стоят около «склеенных» позиций). Выровнять две последовательности РНК с заданными вторичными структурами, говоря неформально, - значит сопоставить позиции в этих последовательности так, чтобы максимизировать как количество сопоставленных одинаковых букв, так и количество сопоставленных «склеиваний» (скобок).
В докладе будет представлена формальная постановка задачи выравнивания РНК и алгоритм ее решения. Предварительно будут рассказаны алгоритмы выравнивания деревьев, на которые опирается алгоритм выравнивания РНК.


22 сентября 2009 г.
А. В. Савватеев «Хроматическое число плоскости и миграционно-устойчивое разбиение мира на страны»
Речь пойдёт о двух разных сюжетах.
1. Сумасбродные идеи про хроматическое число плоскости.
В сообщении будет представлен «план» доказательства того факта, что хроматическое число n-мерного пространства не превосходит 2^n (в частности, для плоскости это даёт точный ответ 4). Доказательство изобилует пробелами, которые, может быть, можно когда-нибудь ликвидировать.
2. Существование миграционно-устойчивого разбиения «линейного мира» на страны.
Доказана известная гипотеза Алесины о том, что линейный мир можно так разрезать на заданное число кусков-стран, что никто не захочет сменить свою прописку. Будет дана строгая математическая формализация этого утверждения, и доказательство, базирующееся на лемме Гейла-Никайдо.


15 сентября 2009 г.
А. М. Райгородский «Дистанционные графы с большим хроматическим числом и без симплексов»
В докладе речь пойдет об одной классической задаче рамсеевского типа и ее обобщениях. Хорошо известно, что существуют графы, у которых и хроматическое число, и обхват превосходят любые наперед заданные величины. Аналогичные вопросы можно изучать в случае дистанционных графов. Я расскажу о различных подходах, помогающих давать ответы на эти вопросы, и о тех результатах, которые здесь удается получить.


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

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

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

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

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