Архив рубрики: видео

В пятницу, 19 апреля, на спецсеминаре состоялся доклад Сергея Федорова. В докладе рассматривалась следующая задача. Дан ненаправленный граф (изначально пустой), и набор запросов . Каждый запрос — это удаление, или добавление некоторого ребра, при этом все запросы известны заранее и … Читать далее →

В рамках Яндекс семинаров 14 февраля состоялся доклда Вали Боевой про анализ перестроек раковых геномов. Данная задача, как и большинство задач биоинформатики, является крайне интересной как с прикладной, так и с теоретической точки зрения. Если вам интересны задачи анализа данных … Читать далее →

В эту пятницу состоялся доклад Тани Стариковской, на котором рассказывался алгоритм M. Crochemore и W. Rytter поиска наибольшей общей подпоследовательности (longest common subsequence) двух строк. LCS является классической задачей в области строковых алгоритмов и может быть решена за время с … Читать далее →

В прошедшую пятницу на спецсеминаре состоялся доклад Дмитрия Петрашко, на котором рассказавались основы распределенных (параллельных) алгоритмов. Была рассмотрена классическая проблема race condition, теоретический алгоритм, который её решает, и методы, применяемые на практике. В частности были введены понятия state-free, wait-free и … Читать далее →

В эту пятницу состоялся доклад Максима Бабенко, где он рассказывал про задачу и некоторые её обобщения. Широко известно, что жадный алгоритм дает в данной задаче приближение , при этом алгоритма, дающего лучшее приближение, не существует (при условии ). Оказывается, что … Читать далее →

Поздравляем всех с началом нового учебного года! В этом семестре, спецкурс Максима Бабенко будет про строковые алгоритмы. Первое занятие уже состоялось, но, к сожалению, не было заснято на видео. На спецсеминаре состоялся доклад Руслана Савченко. Он рассказал о своей работе, … Читать далее →

16 мая состоялся доклад Андрея Гольдберга про задачу поиска путей в дорожных графах и самые новые результаты в этой области. На странице Андрея вы можете найти слайды доклада, также велась видеозапись доклада.

18 апреля был спецкурс Максима Бабенко и доклад Ильи Разенштейна. 25 апреля был только спецкурс Максима Бабенко. 2 мая состоялся доклад Сергея Рогуленко. Обзоры прошедших докладов появятся в скором времени. А на следующем занятии (16 мая) состоится доклад Андрея Гольдберга … Читать далее →

С этого занятия мы переходим к изучению новой темы, так называемых cache oblivious алгоритмов. Как и алгоритмы, рассмотренные нами ранее, они работают в предположени двухуровневой организации памяти. При этом происходит перераспределение ролей: роль жесткого диска играет оперативная память, а роль … Читать далее →

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