С. Капулкин (АУ)

Information retrieval

В докладе будут рассмотрены основные алгоритмы информационного поиска. В начале
будет рассказана общая конструкция поисковой машины на примере бинарного
поиска (boolean retrieval), далее рассматривается vector space model для
задачи ранжированного поиска, приводятся методы оценки поисковых систем.

Д. Соколов (АУ)

Нижняя оценка длины доказательств

Доклад по статье:
Edward A. Hirsch, Sergey I. Nikolenko. "Simulating Cutting Plane proofs with restricted degree of falsity by Resolution."

В докладе будет рассмотрено доказательство нижней оценки на размер доказательства в
системе Cutting Plane для языка тавтологий. Будет продемонстрировано моделирование Cutting Plane
при помощи резолюций для ограниченной "степени ошибочности" неравенств.

Ю. Беляева (АУ)
Поиск кратчайших путей в дорожной сети

В докладе будет рассказано об алгоритмах поиска кратчайшего пути в дорожных сетях. Широко известный алгоритм Дейкстры оказывается слишком медленным для поиска путей на больших дорожных сетях, таких, как дорожная сеть США или Европы. Алгоритмы с предобработкой в данном случае работают гораздо лучше: на первой стадии по карте подсчитывается вспомогательная информация, которая далее помогает быстро выполнять запросы. В лекции будут рассмотрены несколько вариантов подобных алгоритмов.

Доклад основан на лекциях, прочитанных Ренато Вернеком в рамках летней школы Microsoft Data Structures and Algorithms School (MIDAS) 2010 (http://logic.pdmi.ras.ru/midas).