Computer Science семинар (весна 2013)

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

1. Алгоритмы для задачи коммивояжёра (Александр Куликов, ПОМИ РАН)
(24.02.2013 - 15:35 - 17:10)

Задача коммивояжёра — классическая 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-трудным задачам.

Лекция предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями.

http://www.lektorium.tv/lecture/?id=14235
2. Быстрое решение задачи о наименьшей общей надстроки для случая коротких строк (Иван Михайлин, СПбАУ/CS центр)
(10.03.2013 - 15:35 - 17:10)

Задача о наименьшей общей надстроке это задача поиска минимальной строки, которая содержит все данные в качестве подстрок Это наиболее естественная NP-полная задача, работающая со строками. Хотя задача о наименьшей общей надстроке выглядит проще, чем другие перестановочные задачи (например, она не сложнее, чем задача коммивояжера), однако до сих пор не существует алгоритмов обгоняющих тривиальный, получаемый динамическим программированием. В докладе будет рассказано, как использовать графы де Брюйна и похожие на них структуры, для того, что бы получить существенный выигрыш в скорости, для частного, но все еще NP-трудного случая коротких строк.
3. DPLL алгоритм с вероятностным отсечением: оценка времени работы (Елена Иконникова, СПбГУ/CS центр)
(17.03.2013 - 15:35 - 17:10)

DPLL алгоритмы (алгоритмы расщепления) --- один из основных подходов к решению задачи выполнимости пропозициональных формул (задачи SAT). На вход алгоритм получает формулу, на выход выдает выполняющий набор либо сообщение о том, что формула невыполнима. Он действует рекурсивно, выбирая переменную и присваиваемое ей значение и вызывая себя на формуле, получившейся при подстановке. Если выполняющий набор не найден, переменной присваивается другое значение и происходит еще один рекурсивный вызов. Работу такого алгоритма можно представить как дерево ("дерево расщепления"). DPLL алгоритм характеризуется двумя процедурами (эвристиками): A, выбирающей переменную для расщепления, и B, выбирающей первое присваиваемое этой переменной значение. Можно рассмотреть такую модификацию, как DPLL алгоритм с отсечением, т.е., добавить эвристику C, ''обрезающую ветви'' дерева расщепления: если C возвращает 0, то алгоритм вместо рекурсивных вызовов сразу выдает, что формула невыполнима. В таком случае, алгоритм может ошибаться на выполнимых формулах. В докладе будет рассмотрен случай, когда B и C --- вероятностные процедуры. Будет показано, что если для выполнимой формулы, построенной по матрице смежности граничного экспандера, вероятность ошибки мала, то велика вероятность того, что алгоритм будет работать экспоненциально долго. http://www.lektorium.tv/lecture/?id=14297
4. Эвристические классы и оценки на схемную сложность класса HeurMA (Александр Кноп, СПбГУ/CS центр)
(24.03.2013 - 15:35 - 17:10)

В докладе будет рассказано про математическое определение понятия "эвристика". Дан небольшой обзор известных результатов про эвристические задачи. И рассказано про нижнюю оценку на схемную сложность класса HeurMA. http://www.lektorium.tv/lecture/?id=14328
5. Поиск дубликатов (Александр Уланов, HP Labs)
(31.03.2013 - 15:35 - 17:20)

Лекция посвящена задаче поиска и группировки или согласования различных реализаций одного и того же объекта. Данная задача часто решается в контексте интеграции данных. Также рассматриваются функции близости строк. http://www.lektorium.tv/lecture/?id=14352
6. Анализ мнений (Александр Уланов, HP Labs)
(07.04.2013 - 15:35 - 17:20)

Лекция посвящена задачам численного анализа мнений, настроений, субъективности, оценок, отношения, эмоций и т.д., которые выражены в текстовом виде. В последнее время это направление анализа текстов получило широкое применение из-за появления большого количества текстовой информации, создаваемой пользователями. Это форумы, блоги, комментарии в интернет-магазинах, твиты, сайты с отзывами; другими словами это Web 2.0. Анализ мнений позволяет численно оценить отношение пользователей к той или иной теме, например, к телефону, законопроекту, компании или человеку. В лекции будут рассмотрены типичные подзадачи анализа мнений, такие как классификация тональности текстов, поиск достоинств и недостатков товаров, реферирование мнений, поиск спама в отзывах и пр. Также рассматриваются реализации анализа мнений в коммерческих приложениях. http://www.lektorium.tv/lecture/?id=14375
Ваша оценка: Пусто Средняя: 5 (1 голос)
Share |