Теоретический семинар (осень 2010)

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

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

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

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

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

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

Страницы