Визуализация графов

Общая информация
ЛекторА. Дайняк
Семестрвесна 2014
Дата начала29.03.2014
Количество пар5
Язык курсарусский
Анонсы
Анонс habrahabr.ruhttp://habrahabr.ru/events/4242/
Аннотация

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

  • поговорим о том, какие критерии используются для определения того, насколько «хорошо» или «плохо» изображён граф,
  • затронем обобщения хорошо знакомого слушателям понятия планарных графов и поговорим, как эти графы можно отрисовывать, так, чтобы минимизировать число пересекающихся рёбер, обсудим, какие оптимизационные задачи при этом возникают,
  • обсудим, какие из задач отображения графов NP-трудны, а какие гарантированно полиномиальны,
  • посмотрим на несколько алгоритмов в действии.

Страница курса на сайте автора: http://www.dainiak.com/teaching/courses/current/graphdrawing_s2014

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение
(29.03.2014 - 17:20 - 18:00)

Ранние примеры изображений графов. Основные требования и соглашения при визуализации. Трудности задач визуализации. http://www.youtube.com/embed/SdXeKJJAwBY
2. Барицентрические укладки и силовые методы
(29.03.2014 - 19:05 - 20:40)

Свойства трёхсвязных планарных графов. Теорема Татта о правильности «резиновой» укладки трёхсвязных графов. Силовые методы укладки. http://www.youtube.com/embed/Y86lEnFSVP4
3. Тестирование графов на планарность
(30.03.2014 - 11:15 - 12:50)

Тестирование графов на планарность и построение топологической укладки: left-right planarity test. http://www.youtube.com/embed/oCtzMEBQT0U
4. Визуализация деревьев
(30.03.2014 - 13:00 - 14:35)

Визуализация деревьев. h-v-укладки. Укладка упорядоченных деревьев: метод «направляющего пути». http://www.youtube.com/embed/5CXyJRDxfb0
5. Нижние оценки в визуализации графов
(30.03.2014 - 15:35 - 17:10)

Экспоненциальные нижние оценки площади. Оценка числа скрещиваний. Методы доказательства NP-трудности задач. http://www.youtube.com/embed/ixoQsvNuEnU
Ваша оценка: Пусто Средняя: 4.2 (5 votes)
Share |
Александр Дайняк
Александр Дайняк
Александр Дайняк и студенты