В весеннем семестре 2012 года заседания кафедрального семинара будут проходить по вторникам 13 марта, 10 апреля, 24 апреля, 8 мая, 22 мая в Яндексе (м. Парк культуры, ул. Льва Толстого, д. 16) с 17:00 до 18:30 или с 18:30 до 20:00 (каждый раз время будет уточняться).

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

Ближайшие заседания:

22 мая 2012 г. 17:00 - 18:30
Ю. Закс «Синхронизируемость конечных автоматов в экстремальном и среднем случаях»
Доклад про бесконечные серии автоматов с длинным синхронизирующим словом, а также про вероятность того, что случайный автомат синхронизируем, и ожидаемую длину его синхронизирующего слова.

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

10 апреля 2012 г. 17:00 - 18:30
И. Разенштейн «Длинные кратчайшие пути в неориентированных графах»
Рассмотрим взвешенный неориентированный граф, в котором все кратчайшие пути уникальны. Будем интересоваться множеством вершин минимального размера, которое задевает все кратчайшие пути из epsilon n вершин, где epsilon - какой-то положительный параметр, а n - число вершин. Мы докажем некоторые верхние и нижние оценки на размер такого множества и рассмотрим два приложения подобных оценок: оракула больших расстояний и вложения метрических пространств в нормированные, которые сохраняют большие расстояния. Будет приведено несколько открытых вопросов.

13 марта 2012 г. 17:00 - 18:30
И.А. Евин «Сложные сети как модели сложных систем»
В последние годы сложилось новое направление изучения сложных систем, рассматривающее их как сетевые структуры, образованных взаимодействием элементов этих систем между собой. Эти исследования имеют дело с реальными сетями, такими как биологические (сети метаболических реакций, сети белковых взаимодействий), технические (Интернет, WWW, транспортные сети), социальные (сети друзей и знакомых, сети мобильной связи) и когнитивные (сетевые структуры произведений искусства). Оказалось, что распределение узлов по числу связей в таких сетях подчиняется степенному закону. Будет дан краткий обзор некоторых реальных сетей.

20 декабря 2011 г.
А.В. Булинский «Статистические методы оценки рисков сложных заболеваний»
Задачи, возникающие в генетике, стимулируют развитие статистических методов, способных оперировать с данными гигантских размерностей и учитывающих разнообразные формы зависимости различных факторов. Среди рассматриваемых в докладе новых статистических методов основное внимание уделяется многофакторному понижения размерности (MDR-метод), введеному M.D. Ritchie et al. Дается новая модификация этого метода предложенная докладчиком и его учениками в 2011 году. Кроме того, обсуждаются различные варианты метода логисеский регрессии, иницированного I. Ruczinski et al., а также возможности современных методов стохастической оптимизации (метод отжига). Затрагиваются также методы теории графов, марковские и гиббсовские случайные поля, а также комбинаторный анализ. Их применение будет продемонстрировано при анализе влияния генетических данных (нуклеотидных полиморфизмов) и внешних факторов на риски сердечно-сосудистых заболеваний. Это исследование было начато в 2010 году в рамках общего проекта, осуществляемого в сотрудничестве с факультетом фундаментальной медицины МГУ и направленного на изучение рисков сложных заболеваний (руководители проекта академики РАН В.А. Садовничий и В.А. Ткачук).

13 декабря 2011 г.
П.Е. Велихов «Эффективное вычисление мер семантической близости статей Википедии»
В последнее время в сети интернет стремительно развиваются открытые базы данных, такие как Wikipedia, dmoz и другие. Семантическая информация, накопленая в этих базах позволяет существенно улучшить методы автоматической обработки тесктов и информационно-поисковых систем. Вместо ключевых слов, обычно используемых в таких системах, становится возможным использовать термины предментой области с сопутсвующей семантикой. Википедия является ведущим источником среди выше перечисленных, и в настоящее время английская Википедия включает в себя: более 3,8 миллиона статей, среди которых порядка 300,000 статей-категорий и 700,000 многозначных терминов; и более 60 миллионов ссылок с одной статьи Википедии на другую. Такой объем данных в совокупности с широким покрытием предметных областей предоставляет возможность использовать Википедию как семантический словарь для обработки тесктов. В отличие от структурированных словарей глаголов, таких как FrameNet и VerbNet, Википедия – это словарь фразеологизмов, не покрывающий глаголы. Статьи Википедии не содержат семантические структуры, присущи словарям глаголов, поэтому требуются неточные методы работы с семантикой. Одним из таких методов является мера семантической близости. В данной работе мы рассмотрим предложенные в литературе меры семантической близости и рассмотрим их применения в контексте системы Texterra, разработанной в ИСП РАН.

6 декабря 2011 г.
А. Савватеев «Задача о коллективной ответственности»
В докладе ставится математический вопрос о стратегиях проверки деятельности нескольких работников - стратегиях, устойчивых к сговору (формально: реализующихся посредством сильного равновесия Нэша). Задача имеет богатую предысторию, весьма нетривиальный теоретико-игровой аппарат, а также решение, представленное в явной форме. Все необходимые понятия будут объяснены в ходе доклада.

29 ноября 2011 г.
М. Матдинов «Размер компонент раскраски куба»
Доказывается, что при раскраске куба размера n^d в несколько цветов так, что никакая грань триангуляции куба (являющейся подразделением стандартного разбиения на n^d кубов) не покрашена в m+2 различных цвета, то какой-то цвет встречается не менее f(d,m)n^(d-m) раз.

22 ноября 2011 г.
А.Б. Купавский, Л.А. Остроумова «О концентрации вторых степеней случайного веб-графа»
В докладе речь пойдет о применении неравенства Талаграна и улучшениях, которые это дает.

15 ноября 2011 г.
А.В. Куликов «Распределение капитала, проблема определения риск-вклада и их решение посредством одномерных и многомерных когерентных мер риска»
Традиционными мерами риска, используемыми на практике, являются стандартное отклонение (полудисперсия) и V@R. Но все эти меры риска обладают рядом недостатков. Чтобы исправить данные недостатки, определение одномерных когерентных мер риска было рассмотрено в осеовополагающей работе [1]. В работе [2] эти авторы доказали теорему о представлении когерентных мер риска, с тех пор теория когерентных мер риска начала активно развиваться. Основными примерами когерентных мер риска, используемыми на практике, являются хвостовой V@R, взвешенный V@R и MINV@R.
Кроме задачи измерения риска важной задачей теории риск-менеджмента является распределение риска портфеля между его частями. А, соответственно, тесно связанной с этой задачей является определение риск-вклада отдела в риск компании. Данные задачи могут быть решены посредством когерентных мер риска. Здесь мы представим теоретическое решение данной проблемы и практически используемый алгоритм.
Однако подход с использованием одномерных когерентных мер риска неудобен, например, при описании портфеля, состоящего из нескольких валют. В этом случае гораздо естественнее пользоваться подходом, при котором портфель описывается не как число, а как вектор. Понятие многомерной когерентной меры риска было введено в работе [3]. Однако в их модели операционные издержки являются неслучайными. В работе [4] рассмотрены многомерные когерентные меры риска, считывающие и риски, связанные с изменением валютного курса. Также мы приводим решение задач распределения капитала и определения риск-вклада в многомерном случае.

1 ноября 2011 г.
Р.Н. Карасев «Топологические препятствия к построению графов, свободных от двудольных подграфов заданного размера»
Число Турана $ex(H, n)$ графа $H$ --- это максимальное количество рёбер в графе $G$ на $n$ вершинах, не имеющем подграфа, изоморфного $H$. Для полных двудольных графов $H=K_{s,t}$ существуют конструкции $G$ с большим числом рёбер, заданные алгебраическим соотношением между парой точек в $\mathbb F_p^d$.
Мы изучим алгебраические отношения на парах точек в $\mathbb R^d$ или $\mathbb C^d$, которые определены над целыми числами, и таким образом дают графы над $\mathbb F_p^d$, для которых можно указать асимтотическое (с ростом $p$) число рёбер.
Оказывается, что всякая гиперповерхность в $\mathbb R^d\times \mathbb R^d$ содержит решётку (то есть произведение конечных множеств $S\times T$) размера примерно $(2d-3)x(2d-3)$ по топологическим причинам. Это исключает конструкции интересных с точки зрения числа Турана графов, свободных от $K_{s,s}$, при $s$ больших $3$. С другой стороны, мы конструируем гиперповерхности в $\mathbb R^d\times \mathbb R^d$ без решёток размера $d\times d^{4d}$. Построение поверхностей без решёток $d\times d^2$, например, пока остаётся открытым вопросом.
Будут обсуждаться и другие применения топологического факта о вложении двудольного подграфа в граф, заданный гиперповерхностью.

25 октября 2011 г.
А.А. Рябченко, Е.А. Самосват «О еще одной модели web-графа»
В докладе авторы расскажут о предложенной ими модели web-графа принадлежащей классу моделей предпочтительного присоединения. И о том как в этой модели устроены распределения степеней вершин и кластерный коэффициент.

18 октября 2011 г.
Д. Шабанов «Теорема Фриза и Мубаи: история и приложения»
В 2008 году А. Фризом и Д. Мубаи была доказана замечательная теорема об оценке хроматического числа простого однородного гиперграфа с максимальной степенью ребра d. Данный результат, в некотором смысле, завершает целую серию интересных результатов, связанных с исследованием хроматического числа и числа независимости в графах и гиперграфах с небольшой степенью вершины. В докладе будет рассказано об истории этих результатов, а также об их приложениях.

27 сентября 2011 г.
М. Жуковский «Закон больших чисел для модели эпидемии на полном графе»
В докладе будет рассказано про модели эпидемии, в которых частицы совершают случайные блуждания на графе. Будут сформулированы некоторые предельные законы для случая, когда в качестве графа рассматривается решетка в Z^d, а также для количества зараженных частиц для случая полного графа. Более подробно останавлюсь на своем результате, относящемуся к закону больших чисел.

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