Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Визуализация графов
Санкт-Петербург / весна 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

  • поговорим о том, какие критерии используются для определения того, насколько «хорошо» или «плохо» изображён граф,
  • затронем обобщения хорошо знакомого слушателям понятия планарных графов и поговорим, как эти графы можно отрисовывать, так, чтобы минимизировать число пересекающихся рёбер, обсудим, какие оптимизационные задачи при этом возникают,
  • обсудим, какие из задач отображения графов NP-трудны, а какие гарантированно полиномиальны,
  • посмотрим на несколько алгоритмов в действии.
Дата и время Занятие Место Материалы
29 марта
17:20–18:00
Введение, Лекция ПОМИ РАН слайды,  видео
29 марта
19:05–20:40
Барицентрические укладки и силовые методы, Лекция ПОМИ РАН слайды,  видео
30 марта
11:15–12:50
Тестирование графов на планарность, Лекция ПОМИ РАН слайды,  видео
30 марта
13:00–14:35
Визуализация деревьев, Лекция ПОМИ РАН слайды,  видео
30 марта
15:35–17:10
Нижние оценки в визуализации графов, Лекция ПОМИ РАН слайды,  видео