Адрес e-mail:

Межкафедральный научно-исследовательский семинар (2016 — 2017)

В весеннем семестре 2016/2017 года заседания межкафедрального семинара проходят в Долгопрудном по четвергам в 18:30 — 20:00 в аудитории Акт. зал ЛК. Семинар проводится совместно с кафедрой математических основ управления ФУПМ МФТИ и кафедрой высшей математики МФТИ.

Научный семинар поддержан Лабораторией структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб), МФТИ, грант правительства РФ дог. 11.G34.31.0073.

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

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

2 марта 2017 г.
В.Л. Дольников «Точки и прямые»

9 марта 2017 г.
А.Б. Скопенков «NP-трудность вложимости и почти вложимости гиперграфов в R^d»
Анонс

16 марта 2017 г.
М. Тихомиров «Графы-экспандеры и их применения»
Рассказ будет посвящен графам-экспандерам, их свойствам и применениям. В широком смысле, (мульти)граф является экспандером, если любая его небольшая область имеет сравнительно большую окрестность. Мы обсудим непосредственные применения экспандеров в таких задачах, как построение эффективных сетей и самоисправляющих кодов, и «экономия» случайных битов в рандомизированных алгоритмах. Кроме этого, мы поговорим про связь расширительной величины графа с его спектральными характеристиками, и случайные блуждания в экспандерах.

23 марта 2017 г. 
В. Подольский «Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates» 
Анонс

30 марта 2017 г. 
Е. Молчанов «Экономика: комбинаторные вызовы» 
В начале XX века экономика фактически являлась набором экспертных мнений: некоторые 
эксперты понимали и «чувствовали» тонкую структуру экономики, но не могли её объяснить. Начиная с середины XX века все больше и больше процессов в экономике стали описываться математическими моделями, которые смогли адекватно описывать существовавшие в то время экономические процессы и предсказывать влияние тех или иных решений. Но в последнее время эти модели перестали работать, а экономика стала возвращаться обратно к набору экспертных мнений. 
Почему? Основные причины две: глобализация и информационные товары (товары, которые дорого произвести, но пренебрежимо дешево размножить, например, ПО) Традиционно математические модели экономики опираются на такие науки, как линейная алгебра, дифференциальные уравнения, уравнения в частных производных. Исследование процесса глобализации и информационных товаров привело к тому, что экономистам теперь жизненно нужны модели и результаты в некоторых областях комбинаторики, в особенности, в комбинаторной геометрии. 
Зачем экономистам исследовать структуру разбиений плоскости прямыми? 
Зачем экономистам переопределять понятие выпуклых фигур для дискретного случая? 
Об этом будет рассказано на межкафедральном семинаре.

6 апреля 2017 г.
А.А. Полянский «Доказательство гипотезы Л.Ф.Тота о сферических полосках»
Полоской ширины w в R^d называется множество таких точек, которые лежат между двумя параллельными гиперплоскостями находящимися на расстоянии w друг от друга. Шириной выпуклого тела C в R^d называется наименьшая ширина полоски, которая содержит C. В 1932 году Тарский, почти дословно используя доказательство Моезе (для другой теоремы), доказывает теорему, следствием которого является знаменитое утверждение: 
Если круг покрыт полосками, то ширина круга не меньше суммарной ширины полосок. 
Позже Банг в 1950 году обобщает это утверждение (Банг говорит об этом утверждении как о задаче (гипотезе) Тарского о полосках, хотя Тарский не ставил эту задачу в своей статье от 1932): 
Если выпуклое тело покрыто полосками, то ширина этого выпуклого тела не меньше суммарной ширины полосок.
Задача Тарского о полосках стала одна из самых популярных задач дискретной геометрии. Было получено несколько доказательств и было поставлено несколько новых вопросов, которые обобщают задачу Тарского о полосках. В 1973 году Фейеш Тот поставил следующую гипотезу: 
Зоной ширины w на единичной двумерной сфере называется множество точек, которые находятся на расстоянии не более w/2 от большой окружности (экватора) в геодезической метрике (т.е. расстояние между двумя точками равно длине наименьшей дуги, их соединяющей). Если несколько зон покрывают единичную сферу, то их суммарная ширина по крайней мере π.
Совсем недавно докладчику и Цзылину Цзяну удалось решить эту задачу. Доклад будет посвящен доказательство данного результата и некоторым связанным с ним задачам. Предварительных знаний не требуется. 
Статья, которая послужит основой доклада, будет доступен по ссылке: https://arxiv.org/pdf/1703.10550.pdf

20 апреля 2017 г.
G.O.H. Katona «Two-part Erdos-Ko-Rado theorems»

4 мая 2017 г.
M. Tancer «Simplifying inclusion-exclusion formulas»
Abstract

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

14 сентября 2016 г.
А.Я. Канель-Белов «Значения многочленов от матриц» 
Общая постановка такова. Пусть P(x1, ..., xn) — некоммутативынй многочлен от матриц порядка n. Каким может быть множество его значений?
И.Капланский и И.В.Львов поставили вопрос (см. Днестровская тетрадь) о том, что множество значений полилинейного многочлена есть векторное пространство (в этом случае оно совпадает либо с нулем, либо с пространством  всех матриц, либо с пространством бесследовых матриц, либо со скалярными матрицами).
Решение проблемы Капланского для матриц второго порядка над квадратично замкнутым полем оказалась весьма нетривиальным и глубоким.
Вопросы, связанные с уравнениями в матрицах помимо прикладного значения , имеют отношение к конструкции алгебраически замкнутого тела, к теореме о свободе: если добавить новую некоммутативную переменную и соотношение где та участвует, то это не приведет к появлению новых соотношений.
Имеется ряд глубоких проблем, относящихся к множеству значений слов в группе — в частности в матицах второго порядка.

21 сентября 2016 г.
А. Коротин, Н. Верещагин «Самоподобные замощения плоскости многоугольниками»
В докладе будет рассказано о некоторых известных и не очень классах замощений плоскости (замощения Пенроуза, Амманна, Амманна-Бинкера, L-замощения и др.) Будет рассказано, как они определяются и какими интересными свойствами обладают (напр. самоподобность, апериодичность).

28 сентября 2016 г.
И.Д. Шкредов «Введение в теорию сумм произведений»
Пусть A - произвольное конечное множество целых чисел. Рассмотрим сумму и произведение A с собой, а именно, множества

A+A := { c=a+b : a, b \in A } и AA := { c=ab : a, b \in A }.

Существуют множества с малой суммой, например, арифметические прогрессии : P={1,…,n}, |P+P| = 2n-1. Аналогично, геометрическая прогрессия G={2,22, …, 2n } имеет малое произведение: |GG| = 2n-1. Гипотеза сумм произведений утверждает, что не существует множеств, имеющих, одновременно, малую сумму и произведение, а именно, для произвольного ε>0 и любых достаточно больших множеств A всегда выполнено

max{ |A+A|, |AA| } \ge |A|2-ε.

Неравенство выше до сих пор не доказано, но даже частичный прогресс в данной области уже привел к существенному продвижению в задачах теории чисел, аддитивной комбинаторики, криптографии, теории динамических систем.
В нашем докладе мы расскажем об этой замечательной области математики. 

12 октября 2016 г.
А. Милованов «Алгоритмическая статистика»
Допустим, у нас имеются некоторые экспериментальные данные, для которых требуется найти какое-нибудь «хорошее объяснение». Как такое объяснение найти, и вообще: какое объяснение следует считать хорошим? На последний вопрос можно ответить так: нужно найти такую модель, в которой вероятность произошедшего события была бы как можно больше. Однако такой ответ не следует считать удовлетворительным — мы всегда можем построить такую модель, в которой вероятность произошедшего события равняется единице (но такие модели редко являются приемлемыми с точки зрения практики). Поэтому следует добавить еще один критерий адекватности модели — она должна быть (по возможности) простой. Формализовать это требование удалось А. Н. Колмогорову с помощью алгоритмической теории информации в 1974 году. С этого момента и берет начало «алгоритмическая статистика». В докладе будет рассказано об основных ее достижениях.

19 октября 2016 г. (ФКН, аудитория 505, 18:10-19:30)
А.Б. Скопенков «Stability of intersections of graphs in the plane and the van Kampen obstruction»
Анонс

26 октября 2016 г.
Д.В. Мусатов «Сложностные классы задач поиска»
Вычислительная задача поиска ставится так: требуется либо найти объект с некоторым свойством, либо указать, что его не существует. В соответствующей задаче распознавания находить объект не требуется, нужно лишь понять, существует он или нет. Ясно, что задача распознавания не сложнее задачи поиска, но иногда может быть проще. Так, для задачи разложения на множителя сложности скорее всего различаются: проверить, что число составное, можно за полиномиальное время AKS-алгоритмом, а найти разложение скорее всего нельзя. А вот для NP-полных задач сложности одинаковы.
Отдельный интерес представляют тотальные задачи поиска, в которых объект точно существует и потому задача распознавания тривиальна. Оказывается, они разбиваются на классы в зависимости от того, какой именно аргумент используется для доказательства существования. Где-то это принцип Дирихле (класс PPP), где-то — теорема о том, что число вершин нечётной степени в любом графе чётно (класс PPA), где-то — частный случай этой теоремы для графов со степенями вершин не больше 2 (класс PPAD). Особенно интересен класс PPAD: в него попадают конструктивные версии задач, связанных с неподвижными точками и математической экономикой. Например, это поиск пёстрого симплекса в лемме Шпернера, неподвижной точки в теореме Брауэра, равновесия Нэша в матричных играх, равновесия Вальраса в экономике обмена и т.д. Более того, все эти задачи полны в классе PPAD, т.е. к ним сводится любая другая задача из этого класса.
В докладе будет сделан обзор классов задач поиска, определён ряд PPAD-полных задач и продемонстрированы основные идеи доказательства их полноты.

2 ноября 2016 г. 
Д.В. Мусатов «Сложностные классы задач поиска». Часть 2
Вычислительная задача поиска ставится так: требуется либо найти объект с некоторым свойством, либо указать, что его не существует. В соответствующей задаче распознавания находить объект не требуется, нужно лишь понять, существует он или нет. Ясно, что задача распознавания не сложнее задачи поиска, но иногда может быть проще. Так, для задачи разложения на множителя сложности скорее всего различаются: проверить, что число составное, можно за полиномиальное время AKS-алгоритмом, а найти разложение скорее всего нельзя. А вот для NP-полных задач сложности одинаковы. 
Отдельный интерес представляют тотальные задачи поиска, в которых объект точно существует и потому задача распознавания тривиальна. Оказывается, они разбиваются на классы в зависимости от того, какой именно аргумент используется для доказательства существования. Где-то это принцип Дирихле (класс PPP), где-то — теорема о том, что число вершин нечётной степени в любом графе чётно (класс PPA), где-то — частный случай этой теоремы для графов со степенями вершин не больше 2 (класс PPAD). Особенно интересен класс PPAD: в него попадают конструктивные версии задач, связанных с неподвижными точками и математической экономикой. Например, это поиск пёстрого симплекса в лемме Шпернера, неподвижной точки в теореме Брауэра, равновесия Нэша в матричных играх, равновесия Вальраса в экономике обмена и т.д. Более того, все эти задачи полны в классе PPAD, т.е. к ним сводится любая другая задача из этого класса. 
В докладе будет сделан обзор классов задач поиска, определён ряд PPAD-полных задач и продемонстрированы основные идеи доказательства их полноты. 

16 ноября 2016 г.
А.В. Савватеев «Простые числа в арифметических прогрессиях»
Более 100 лет назад Дирихле доказал следующую теорему:
«В любой арифметической прогрессии со взаимно-простыми начальным членом и разностью содержится бесконечное количество простых чисел.»
Мы докажем кустарными методами бесконечность числа простых вида (4k+1) и (4k+3), а затем на этом примере познакомимся с методом Дирихле. Слушатели узнают, что такое ряд Дирихле, гипотеза Римана, бесконечное произведение и характер Дирихле. Будет дан набросок доказательства общей теоремы, а также краткое введение в комплексный анализ.

23 ноября 2016 г.
A. Veremyev «Integer programming techniques for modeling clique relaxations and key players in networks»
Modern optimization software packages (Gurobi, Fico Xpress, CPLEX, etc.) have been demonstrating significant performance enhancements over the last decade. These improvements allow finding solutions for many combinatorial problems on real-life networks within a reasonable time via modeling efficient mixed integer programming (MIP) formulations. In this talk we will discuss various integer programming techniques for modeling so-called clique relaxations (subgraphs with a ‘relaxed’ clique defining property) and ‘key’ players in networks that we have developed. Many potential applications, effectiveness and flexibility of the proposed MIP formulations will also be demonstrated.

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

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

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