City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Visualization of graphs
Saint Petersburg / spring 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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