Computer Science семинар

Санкт-Петербург, весна 2013

Описание

Открытый семинар по всем областям Computer Science. Если вы хотели бы выступить на семинаре, напишите, пожалуйста, Александру Куликову.

Преподаватели

Список лекций

Алгоритмы для задачи коммивояжёра (Александр Куликов, ПОМИ РАН)

Задача коммивояжёра — классическая NP-трудная задача с достаточно простой формулировкой: даны \( n \) городов и попарные расстояния между ними, необходимо найти кратчайший маршрут, проходящий по всем городам ровно по одному разу. Практические применения данной задачи включают в себя разработку микросхем, планирование, сборку генома. Трудность данной задачи объясняется тем, что с ростом количества городов количество потенциальных маршрутов растёт очень быстро. Например, даже для пятнадцати городов количество таких маршрутов равно 43 589 145 600. Если считать, что компьютер может перебрать миллиард маршрутов в секунду, то искать решение для задачи с сотней городов ему придётся больше триллиона лет. В то же время в задачах, возникающих на практике, количество городов обычно составляет десятки тысяч. К счастью, всё же есть методы, позволяющие решать такие примеры на практике. Например, в 2004 году был найден оптимальный цикл по 24 978 городам Швеции, а в 2006 был вычислен оптимальный маршрут лазера при построении интегральной схемы через 85 900 точек.

Задаче коммивояжёра посвящено огромное количество статей и исследований, как практических, так и теоретических. На сайте http://www.tsp.gatech.edu/index.html можно найти множество ссылок (статьи, книги, датасеты, программы, игры, соревнования и даже фильм).

В докладе мы рассмотрим методы практического и теоретического решения задачи коммивояжёра. Методы, которые мы рассмотрим, включают в себя: метод ветвей и границ, локальный поиск, метод имитации отжига, динамическое программирование, перебор с возвратом, приближённые алгоритмы, формула включений-исключений, матрицы Татта и проверка равенства нулю многочлена.

Более подробный план:

  • методы, с помощью которых задачу коммивояжёра решают на практике, — метод ветвей и границ и метод локального поиска; почему в общем случае для данной задачи приближённые алгоритмы вряд ли существуют;
  • \( 1.5 \)-приближённый алгоритмы для задачи коммивояжёра в метрическом пространстве (когда длины рёбер графа удовлетворяют неравенству треугольника);
  • \( 2/3 \)-приближённый алгоритм для случая, когда найти необходимо не минимальный, а максимальный путь коммивояжёра;
  • классический алгоритм, основанный на методе динамического программирования, со временем работы \( O^*(2^n) \);
  • алгоритм, основанный на формуле включений-исключений, со временем работы \( O^*(2^n) \) и псевдополиномиальной памятью;
  • алгоритм со временем работы \( O^*(4^nn^{\log n}) \) и полиномиальной памятью, основанный на методе перебора с возвратом;
  • недавний алгоритм, улучшающий верхнюю оценку \( O^*(2^n) \), основанный на матрицах Татта и быстрой проверке на равенство нуля многочлена;
  • применения к другим NP-трудным задачам.
Лекция предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями.

Быстрое решение задачи о наименьшей общей надстроки для случая коротких строк (Иван Михайлин, СПбАУ/CS центр)

Задача о наименьшей общей надстроке это задача поиска минимальной строки, которая содержит все данные в качестве подстрок Это наиболее естественная NP-полная задача, работающая со строками. Хотя задача о наименьшей общей надстроке выглядит проще, чем другие перестановочные задачи (например, она не сложнее, чем задача коммивояжера), однако до сих пор не существует алгоритмов обгоняющих тривиальный, получаемый динамическим программированием. В докладе будет рассказано, как использовать графы де Брюйна и похожие на них структуры, для того, что бы получить существенный выигрыш в скорости, для частного, но все еще NP-трудного случая коротких строк.

DPLL алгоритм с вероятностным отсечением: оценка времени работы (Елена Иконникова, СПбГУ/CS центр)

DPLL алгоритмы (алгоритмы расщепления) — один из основных подходов к решению задачи выполнимости пропозициональных формул (задачи SAT). На вход алгоритм получает формулу, на выход выдает выполняющий набор либо сообщение о том, что формула невыполнима. Он действует рекурсивно, выбирая переменную и присваиваемое ей значение и вызывая себя на формуле, получившейся при подстановке. Если выполняющий набор не найден, переменной присваивается другое значение и происходит еще один рекурсивный вызов. Работу такого алгоритма можно представить как дерево (дерево расщепления). DPLL алгоритм характеризуется двумя процедурами (эвристиками): A, выбирающей переменную для расщепления, и B, выбирающей первое присваиваемое этой переменной значение. Можно рассмотреть такую модификацию, как DPLL алгоритм с отсечением, т.е., добавить эвристику C, обрезающую ветви дерева расщепления: если C возвращает 0, то алгоритм вместо рекурсивных вызовов сразу выдает, что формула невыполнима. В таком случае, алгоритм может ошибаться на выполнимых формулах. В докладе будет рассмотрен случай, когда B и C — вероятностные процедуры. Будет показано, что если для выполнимой формулы, построенной по матрице смежности граничного экспандера, вероятность ошибки мала, то велика вероятность того, что алгоритм будет работать экспоненциально долго.

Эвристические классы и оценки на схемную сложность класса HeurMA (Александр Кноп, СПбГУ/CS центр)

В докладе будет рассказано про математическое определение понятия эвристика. Дан небольшой обзор известных результатов про эвристические задачи. И рассказано про нижнюю оценку на схемную сложность класса HeurMA.

Поиск дубликатов (Александр Уланов, HP Labs)

Лекция посвящена задаче поиска и группировки или согласования различных реализаций одного и того же объекта. Данная задача часто решается в контексте интеграции данных. Также рассматриваются функции близости строк.

Анализ мнений (Александр Уланов, HP Labs)

Лекция посвящена задачам численного анализа мнений, настроений, субъективности, оценок, отношения, эмоций и т.д., которые выражены в текстовом виде. В последнее время это направление анализа текстов получило широкое применение из-за появления большого количества текстовой информации, создаваемой пользователями. Это форумы, блоги, комментарии в интернет-магазинах, твиты, сайты с отзывами; другими словами это Web 2.0. Анализ мнений позволяет численно оценить отношение пользователей к той или иной теме, например, к телефону, законопроекту, компании или человеку. В лекции будут рассмотрены типичные подзадачи анализа мнений, такие как классификация тональности текстов, поиск достоинств и недостатков товаров, реферирование мнений, поиск спама в отзывах и пр. Также рассматриваются реализации анализа мнений в коммерческих приложениях.