Семинар (осень 2014)

Общая информация
Семестросень 2014
Дата начала21.09.2014
Количество пар10
Язык курсарусский
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Задача редактирования графа до графа с заданными степенями (Пётр Головач, Университет Бергена)
(18.09.2014 - 18:00 - 20:00)

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph $ G $, non-negative integers $ d,k $ and a function $ \delta \colon V(G) \to \{1,...,d\} $, whether it is possible to obtain a connected graph $ G’ $ from $ G $ such that the degree of $ v $ is $ \delta(v) $ for any vertex $ v $ by at most $ k $ edge editing operations. As the problem is NP-complete even if $ \delta(v)=2 $, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by $ d+k $. For the special case $ \delta(v)=d $, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. We also investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. In particular, we obtain polynomial-time algorithms for the Edge Editing to an Eulerian Graph problem and its directed variant.
2. Введение в онлайн-алгоритмы (Сушмита Гупта, University of Southern Denmark)
(22.09.2014 - 18:00 - 20:00)

In this lecture we will survey the area of online algorithms using some well known examples and problems. We will look at classical approaches as well as new ones, and discuss the underlying principles and objectives that drive research in the online paradigm.
3. Решение задачи о k-пути в неориентированных графах за 2^{3k/4} (А. Куликов, ПОМИ РАН)
(06.10.2014 - 18:00 - 20:00)

Будет рассказан недавний алгоритм Бьорклунда, Хусфельда, Каски, Коивисто решения задачи нахождения простого пути длины $ k $ в неориентированном графе за время $ O^*(2^{3k/4}) $. Из этого, в частности, следует, что найти гамильтонов путь в неориентированном графе можно быстрее $ 2^n $. Алгоритм основан на построении специального многочлена, в котором каждому простому $ k $-пути соответствует уникальный моном, а самопересекающиеся $ k $-пути разбиваются на пары с одинаковыми мономами. Таким образом, данный многочлен тождественно равен нулю в поле характеристики два (достаточно большого размера) тогда и только тогда, когда в графе есть простой $ k $-путь.

Место: аудитория 106.

4. Решение задачи о гамильтоновом пути с помощью базиса совершенных паросочетаний (Павел Кунявский, СПбГУ)
(27.10.2014 - 18:00 - 20:00)

В докладе будет рассказано вероятностное решение задачи о гамильтоновом цикле за время $ O^*(1.888^n) $ в неориентированном графе, в ориентированном двудольном из статьи Цыгана, Кратча и Недерлофа [STOC 2013]. Алгоритм основан на разложении гамильтонова пути на два полных паросочетания, и проверки на тождественное равенство нулю специального многочлена над достаточно большим полем характертистики 2. Построение базиса паросочетаний позволяет сгруппировать части многочлена и вычислить их быстрее. Если останется время, будет также рассказан вероятностный FPT-алгоритм, параметризованный путевой шириной, со временем работы $ O^*((2 + \sqrt 2)^{pw}) $, использующий тот же базис. Место: аудитория 106 ПОМИ РАН.
5. Программируемые языки программирования: введение в системы с открытой реализацией (Роман Попов, РГПУ им. Герцена)
(09.11.2014 - 15:35 - 17:10)

В лекции будет рассказано о метапрограммировании на примере семейства языков Lisp. Для начала будет небольшое введение в Common Lisp, потом будет рассказано о таких традиционных средствах метапрограммирования как макросы (в том числе будут затронуты анафорические макросы). Будет объяснено, почему только в семействе Lisp макросы нашли широкое применение. Далее речь пойдет о менее очевидных способах расширения языков программирования, таких как fexpr и реификаторы. В контексте последней темы будут разъяснены такие идеи как вызов с текущим продолжением и cps-преобразование. https://www.youtube.com/watch?v=tXukFEXyChA
6. Компьютерное зрение: обучение методов распознавания со слабой разметкой данных (Иван Лаптев, INRIA Paris-Rocquencourt, France)
(17.11.2014 - 18:00 - 19:30)

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

English version. Computer Vision: Weakly-supervised learning from images and video. Recent progress in visual recognition goes hand-in-hand with the supervised learning and large-scale training data. While the amount of existing images and videos is huge, their detailed annotation is expensive and often prohibitive. To address this problem, in this talk we will focus on weakly-supervised learning methods using incomplete and noisy annotation for training. I will first address the learning of human actions from videos and corresponding video scripts. I will describe our recent formulation of this problem in the form of a quadratic program with constraints and will show its successful application to the joint learning of actions and actors from movies and corresponding movie scripts. In the second part of the talk I will focus on recognition from still images and will describe our work on weakly supervised convolutional neural networks. I will present a network that learns to recognize and localize objects as well as human actions without using location supervision at the training time. Somewhat surprisingly, our weakly-supervised method achieves state-of-the-art performance comparable to its strongly-supervised counterparts.

Short bio. Ivan Laptev is a research director at INRIA Paris-Rocquencourt, France. He received Habilitation degree in 2013 from École Normale Supérieure (ENS) in Paris. He also received a PhD degree in Computer Science from the Royal Institute of Technology (KTH) in 2004 and a Master of Science degree from the same institute in 1997. He was a research assistant at the Technical University of Munich (TUM) during 1998-1999. He has joined INRIA as a postdoc in 2004 and became a full-time INRIA researcher in 2005. Ivan's main research interests include visual recognition of human actions, objects and interactions. He has published over 50 papers at international conferences and journals of computer vision and machine learning. He serves as an associate editor of IJCV, TPAMI and IVC journals, he was/is an area chair for CVPR 2010, ICCV 2011, ECCV 2012, CVPR 2013, ECCV 2014, ACCV 2014 and CVPR 2015, he has co-organized several tutorials, workshops and challenges on human action recognition at major computer vision conferences. He has also co-organized a series of INRIA summer schools on computer vision and machine learning (2010-2013). Ivan was awarded ERC Starting Grant in 2012.

Место: Мраморный зал ПОМИ РАН

Слайды (PDF)

7. Хроматические числа графов, жадные алгоритмы раскраски и их уточнения (Андрей Райгородский, МФТИ/Яндекс)
(23.11.2014 - 15:35 - 17:10)

В лекции мы расскажем о хроматических числах графов, т.е. об экстремальных характеристиках графов, равных наименьшему количеству цветов, в которые можно так раскрасить вершины графов, чтобы между вершинами одного цвета не было ребер. Сперва речь пойдет о жадных раскрасках, и пафос будет в том, что даже они дают в определенном смысле весьма точные результаты. Затем мы поговорим об уточнениях жадных раскрасок. А под конец поговорим о раскрасках случайных подграфов в некоторых последовательностях графов.
8. Законы нуля или единицы для случайных графов (Максим Жуковский, Яндекс)
(24.11.2014 - 18:00 - 19:30)

В докладе речь пойдет об асимпотическом поведении свойств первого порядка случайного графа Эрдеша-Реньи $ G(n,p) $. В 1988 году Дж. Спенсер и С. Шела доказали, что если $ p=n^{-a} $, $ a $ — положительное иррациональное число, то для любого свойства первого порядка с вероятностью, стремящейся к $ 1 $, случайный граф либо обладает этим свойством, либо нет (иными словами, выполнен закон нуля или единицы). Если же $ a $ из интервала $ (0,1) $ — рациональное число, то закон нуля или единицы не выполнен. Позже мной было доказано, что для любого свойства первого порядка с ограниченной числом k кванторной глубиной выполнен закон нуля или единицы, если $ a $ принадлежит интервалам $ (0,1/(k-2)) $ и $ (1-1/(2^{k}-2),1) $. На концах этих интервалов закон нуля или единицы не выполнен.

В 1990 году Дж. Спенсер доказал, что существует свойство первого порядка $ L $ и бесконечно много таких рациональных чисел $ a $ из интервала $ (0,1) $, что вероятность того, что случайный граф $ G(n,n^{-a}) $ обладает свойством $ L $, не стремится ни к $ 0 $, ни к $ 1 $ (множество $ S(L) $ таких рациональных чисел a называется спектром формулы $ L $). В докладе буде рассказано о недавней совместной работе с Дж. Спенсером, в которой нам удалось получить новые результаты о распределении точек в спектре.

Место: ПОМИ, аудитория 106.

9. Прямо-двойственный метод в приближённых алгоритмах (Всеволод Опарин, ПОМИ РАН/АУ РАН)
(01.12.2014 - 19:00 - 21:00)

Доклад будет о различных техниках получения приближенных алгоритмов через прямо-двойственный метод. Общую идею метода я расскажу на примере задачи о взвешенном покрытии множествами (демонстрация метода, f-приближение, где f — максимальное число множеств покрывающее отдельный элемент). Потом будут различные вариации того, как метод применять, на задачах о поиске кратчайшего пути в графе (зачистка прямого решения, алгоритм Дейкстра), дереве Штейнера (множественное увеличение переменных, 2-приближение) и рюкзаке (усиление неравенств, 2-приближение). Если успею, то будет еще рассказ про uncapacity facility location problem. Место: аудитория 106, ПОМИ РАН.
10. Алгоритм Эпштейна-Бейгеля решения задачи нахождения 3-раскраски графа (Сергей Копелиович)
(15.12.2014 - 18:00 - 19:30)

1. Оценки на смежные задачи: CSP, Vertex 3-List-Coloring, Edge 3-Coloring, 3-SAT.
2. Применение результатов для CSP и Vertex 3-Coloring для решения перечисленных задач.
3. Основная идея алгоритма. Простой результат за 1.34488^n.
4. Улучшения до 1.3289^n.

11. Mathematics in Synchronization and Concurrency (Пётр Кузнецов, Telecom ParisTech)
(22.12.2014 - 18:00 - 19:00)

Докладчик: Пётр Кузнецов (Telecom ParisTech).

Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Therefore, understanding fundamentals of distributed computing is of crucial importance.

The main complication here is the immense diversity of applications, models of distributed computations, and performance metrics, combined with the lack of mathematical tools to handle this complexity. In this talk, we discuss understanding of what can and what cannot be implemented in specific distributed environments, with a focus on how to apply modern mathematics in deriving new algorithms and lower bounds for distributed computing problems.

Место: Мраморный зал. Доклад будет читаться на русском языке.

Ваша оценка: Пусто Средняя: 5 (1 голос)
Share |