Программа дисциплины «Методы визуализации информации при помощи графов»



Скачать 172.58 Kb.
Дата17.04.2013
Размер172.58 Kb.
ТипПрограмма дисциплины


ПРОЕКТ ПРОГРАММЫ ДИСЦИПЛИНЫ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение высшего профессионального образования

Новосибирский государственный университет(НГУ)

Факультет Информационных технологий


УТВЕРЖДАЮ

_______________________
«_____»__________________201__ г.


РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

«Методы визуализации информации при помощи графов»

Магистерская программа

«Технология разработки программных систем»
НАПРАВЛЕНИЕ ПОДГОТОВКИ 230100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Квалификация (степень) выпускника

Магистр
Форма обучения очная

Новосибирск

2011

Программа дисциплины «Методы визуализации информации при помощи графов» составлена в соответствии с требованиями ФГОС ВПО к структуре и результатам освоения основных образовательных программ магистратуры по «профессиональному» циклу по направлению подготовки «Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации Программы развития НГУ.
Автор: АПАНОВИЧ Зинаида Владимировна, к.ф.-м.н., с.н.с. ИСИ СО РАН

Факультет информационных технологий

Кафедра Систем информатики
1. Цели освоения дисциплины

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

Указанные цели в полной мере отвечают основным целям данной магистерской программы:


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

  • развитие у студентов личностных качеств и формирование общекультурных и профессиональных компетенций в соответствии с ФГОС ВПО по данному направлению подготовки.



Для достижения поставленной цели выделяются задачи курса:

  • Ознакомление с областями применения методов и средств визуализации информации и классификацией используемых алгоритмов.

  • Изучение математических основ и сравнительный анализ методов и алгоритмов, применяемых для решения различных подзадач на каждом этапе разработки реальных систем.


  • Ознакомление с реальными приложениями и демонстрация значимости и полезности теоретических результатов, излагаемых в курсе, для решения практических вопросов на уровне создания систем.


2. Место дисциплины в структуре образовательной программы
Данная дисциплина относится к циклу профессиональных дисциплин М2 (дисциплины по выбору). С другими частями образовательной программы соотносится следующим образом:
Требования к первоначальному уровню подготовки обучающихся для успешного освоения дисциплины:
Уровень «знать»:

  • Теория графов;

  • Теория алгоритмов (понятие временной сложности алгоритма);

  • Методы вычислений (решение систем уравнений, поиск экстремумов);

  • Компьютерная геометрия (метод сканирующей прямой, диаграмма Вороного, триангуляция Делоне);


Уровень «уметь»:


  • Уметь составлять и отлаживать программы на языках программирования высокого уровня.


Дисциплины, последующие по учебному плану:


  • Научно-исследовательская работа

  • Итоговая государственная аттестация



3. Компетенции обучающегося, формируемые в результате освоения дисциплины " Методы визуализации информации при помощи графов"
В результате освоения дисциплины студент должен:

Знать:

  • основные области, в которых используются методы данного курса;

  • наиболее важные программные системы;

  • о проблемах, решаемых при создании программных средств визуального анализа;

  • об основных требованиях, предъявляемых к системам в зависимости от области применения.

  • оценки сложности основных алгоритмов и характеристики получаемых результатов;

  • способы оптимизации различных целевых функций;

  • границы применимости существующих алгоритмов на практике.

Уметь:

  • применять методы и средства визуализации информации при помощи графов;

  • выбирать алгоритмы, наиболее адекватные конкретному приложению;

  • выбирать структуры данных, позволяющих эффективную реализацию выбранных алгоритмов.

Владеть:

  • навыками разработки алгоритмов, а также реализации программных систем, использующих методы визуализации информации,

  • навыками применения методов визуализации информации в задачах построения систем бизнес-аналитики и бизнес-разведки, виртуальной реальности, автоматизированного проектирования, био-информатики, систем искусственного интеллекта и др.

В результате освоения дисциплины у учащегося формируются следующие компетенции:

Общекультурные компетенции:

  • Способность совершенствовать и развивать свой интеллектуальный и общекультурный уровень (ОК-1)

  • Способность к самостоятельному обучению новым методам исследования, к изменению научного и научно-производственного профиля своей профессиональной деятельности (ОК-2)

  • Способность свободно пользоваться русским и иностранным языками, как средством делового общения (ОК-3)

  • Способность самостоятельно приобретать с помощью информационных технологий и использовать в практической деятельности новые знания и умения, в том числе в новых областях знаний, непосредственно не связанных со сферой деятельности (ОК-6)

  • Способность к профессиональной эксплуатации современного оборудования и приборов (в соответствии с целями магистерской программы) (ОК-7)

  • Способность использовать углубленные знания правовых и этических норм при оценке своей деятельности, ее социальных последствий(ОК-8)

Профессиональные компетенции:


  • Способность применять перспективные методы исследования и решения профессиональных задач на основе знания мировых тенденций развития вычислительной техники и информационных технологий (ПК-1)

  • Способность формировать технические задания и участвовать в разработке аппаратных и/или программных средств вычислительной техники (ПК-4);

  • Способность выбирать методы и разрабатывать алгоритмы решения задач управления и проектирования объектов автоматизации (ПК-5);

  • Способность применять графовые методы визуализации информации для оптимального графического представления информации (ПК-13)



4. Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 2 зачетных единицы, 72 часа.


№ п/п

Раздел дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и
трудоемкость

(в часах)

Формы текущего контроля успеваемости
(по неделям семестра)

Форма промежуточной аттестации
(по семестрам)

Лекция

Семинары

Самост. работа

Всего

1.1

1. Введение в методы и средства визуализации информации при помощи графов.

Математическая формулировка задачи построения изображения графа.

Эстетические критерии и основные стили при построении изображений графов.

Проблемы, возникающие при работе с реальными приложениями.

3

1

2




4

6







1.2

Методы построения статических изображений деревьев для анализа иерархической информации, теоретические оценки.

  • Эстетические критерии, используемые при визуализации деревьев.

  • Алгоритм построения поуровневого изображения бинарных деревьев и деревьев произвольной степени. Структуры данных, необходимые для реализации за время O(n).

3

2

1

1

2

4

Разбор решений задач и ответы на вопросы, предложенные студентам для самостоятельной работы в течение предыдущей лекции










3

3

2

2

2

6

Мастер-класс. Рассмотрение одной из практических проблем, решаемых при помощи визуализации информации, из предлагавшихся на конкурс IEEE VAST, обсуждение возможных путей решения.





1.5

Радиальные и круговые изображения деревьев

3

4

1

1

4

6







1.6

От диаграмм связей к методам заполнения пространства

3

5

1

1

4

6







1.7

Интерактивные методы визуализации деревьев и графов

3

6

2




4

6













3

7

0

2

2

4

Контрольная работа




1.8

Построение st-нумерации двусвязных графов, Проверка планарности графов и построение комбинаторной укладки, каноническое упорядочение вершин.

3

8

2




2

4







1.9

Построение прямолинейных изображений планарных графов.

3

9

2




2

4







1.10

Информация, представимая с помощью неориентированных графов, и методы визуализации, основанные на физических аналогиях.

«Пружинные алгоритмы» для построения изображения неориентированных графов общего вида.

Алгоритма, имитирующие действие сил гравитации и магнитные силы

Алгоритмы, основанные на минимизации энергии

3

10

1

1

2

4

Разбор решений задач и ответы на вопросы, предложенные студентам для самостоятельной работы в течение предыдущей лекции










3

11




2

4

6

Мастер-класс. Рассмотрение лучших решений одной из проблем, решаемых при помощи визуализации, из предлагавшихся на конкурс IEEE VAST.





1.10

Метод Сугиямы поуровневого изображения ориентированных графов, основные критерии, принимаемые во внимание при поуровневых визуализациях. Основные этапы метода поуровневого размещения

3

12

2




4

6













3

13




2

2

4

Мастер-класс, встреча с представителями ИТ-компаний










3

14




2

2

4

Заслушивание рефератов







Промежуточная аттестация

3

15







2

2

Зачет







Итого за первый семестр:







16

14

42

72








Общая трудоемкость дисциплины составляет 2 зачетных единицы (72 часа).


5. Образовательные технологии
Помимо представления теоретического материала, устраиваются обсуждения, так называемые case-study (анализ реальных проблемных ситуаций и поиск решений), инициированные следующими вопросами:

  • Можно ли модифицировать алгоритм (указание конкретного алгоритма), с тем, чтобы появилась возможность визуального анализа новых свойств изображаемой информации? Если да, то как именно?

  • Какие недостатки Вы видите в изученном алгоритме (изображениях, создаваемых при помощи изученного алгоритма) и как Вы бы предложили устранять эти недостатки?

Следует заметить, что одной из важнейших компонент обучения европейских и американских студентов методам визуализации информации является их участие в соревнованиях, которые ежегодно организуются в рамках таких авторитетных конференций, как IEEE VAST.
Также для опережающей самостоятельной работы студентам в начале семестра предлагаются следующие задания.

А) Дается список публикаций, из которого каждый студент может выбрать одну публикацию и подготовить реферат.

Б) Дается описание графа или дерева в формате xml и студентам предлагается в течение двух-трех недель реализовать один из изучаемых алгоритмов применительно к конкретным данным и подсчитать значения различных параметров, определяющих эстетические требования к изображению.

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины

Для текущей и промежуточной аттестации рекомендуется организовывать 1 небольшую контрольную работу за семестр продолжительностью 45 минут. Для этого предлагаются задания следующего вида.


  1. «Дан граф G = (V, E) с каноническим упорядочением вершин. Построить для данного графа обзорное представление.



  1. Преобразовать полученное обзорное представление графа в ортогональное представление.

  2. При помощи оптимизирующих трансформаций минимизировать количество сгибов полученного ортогонального представления.

Примеры экзаменационных билетов


Билет 1

Теория Построение st-нумерации вершин двусвязного графа

Задача. Дано бинарное дерево (конкретные значения). Построить для него дерево разделителей.
Билет 2

Теория Проверка планарности графа и комбинаторная укладка

Задача. Дан прямоугольник размером 5*6. Разместить в нем прямоугольники из списка с конкретными значениями площади при помощи алгоритма “полосковая карта дерева”.

Билет 3


Теория Алгоритм Рейнгольда-Тилфорда.

Задача Дан прямоугольник размером 5*6. Разместить в нем прямоугольники площади 4, 4, 2,1, 5, 6, 8 при помощи алгоритма “квадрифицирующая карта дерева”.
Билет 4

Теория hv-изображения и строго нисходящие изображения бинарных деревьев

Задача Дан двусвязный граф (конкретные данные). Построить st-нумерацию его вершин.
Билет 5

Теория Методы визуализации численных атрибутов иерархических структур на основе техники Treemap (карта дерева).

Задача Дано каноническое упорядочение вершин планарного триангулированного графа (конкретные значения). Построить прямолинейное изображение этого графа.
Билет 6

Теория Фильтрация изображения дерева на основе функции степени интереса.

Задача Дана st-нумерация вершин двусвязного графа (конкретные значения). Проверить, планарен ли этот граф.
Билет 7

Теория Построение st-нумерации вершин двусвязного графа

Задача. Дано бинарное дерево (конкретные значения). Построить для него дерево разделителей.
Билет 8

Теория Проверка планарности графа и комбинаторная укладка

Задача. Дан прямоугольник размером 5*6. Разместить в нем прямоугольники из списка с конкретными значениями площади при помощи алгоритма “полосковая карта дерева”.
Билет 9

Теория Каноническое упорядочение вершин планарного триангулированного графа.

Задача Дано бинарное дерево (конкретные значения). Построить утяжеленное вправо изображение.




Билет 10


Теория Алгоритм построения прямолинейного изображения по каноническому упорядочению вершин планарного графа.

Задача Дано бинарное дерево (конкретные значения). Построить его изображение вторым методом Чана.
Билет 11

Теория Алгоритм построения обзорного изображения по каноническому упорядочению вершин планарного графа.

Задача Дано бинарное дерево (конкретные значения). Нарисовать его первым методом Чана.
Билет 12.

  1. Построение обзорного изображения для планарного графа. Понятие сильного и слабого обзорного представления.

  2. Алгоритмы размещения, имитирующие действие сил гравитации и магнитные силы



Билет 13


  1. Задача минимизации количества сгибов при построении ортогонального изображения. Стандартный способ описания ортогональных изображений.

  2. «Пружинные алгоритмы» для построения изображения неориентированных графов общего вида.


Билет 14

  1. Сведение задачи минимизации сгибов к поиску потока минимальной стоимости в сети. Построение сети для углов планарной укладки.

  2. Метод Сугиямы поуровневого изображения ориентированных графов, основные критерии, принимаемые во внимание при поуровневых визуализациях.



Билет 15


  1. Задача компактизации ортогонального изображения

  2. Алгоритмы и стратегии, реализуемые на этапе упорядочение вершин на одном уровне при поуровневом размещении с целью минимизации количества пересечений ребер.


7. Учебно-методическое и информационное обеспечение дисциплины

а) основная литература:

  1. Апанович З.В. «Методы и средства визуализации информации на основе графовых моделей» Новосибирск, НГУ, 2009 (Электронный учебник).

  2. Апанович З.В. Методы навигации при  визуализации графов// Вестник НГУ, Том 6, выпуск 3.— 2008.— С. 35-47 .

  3. Апанович З.В. Методы визуализации информации – наукоемкое направление современных ИТ// Компьютерные инструменты в образовании .— N2 .— 2010 .— С 20-27.

  4. Евстигнеев В.А., Касьянов В.Н. Графы в программировании: обработка визуализация и применение. БХВ Петербург. 2003.

  5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов Наука, Физматлит, 1990.

  6. Bastert O., Matuszewski C. Layered Drawings of Digraphs. in M. Kaufmann D. Wagner Drawing Graphs LNCS 2025, pp.87-120, 2001.

  7. Brandes U. Drawing on Physical Analogies in M. Kaufmann D. Wagner Drawing Graphs LNCS 2025, pp.71-86, 2001.


б) дополнительная литература:

  1. Card S. K., Nation D., Degree-Of-Interest Trees: A Component of an Attention-Reactive User Interface// Palo Alto Reseaerch Center May 22-24, 2002.

  2. Chan T.M. A Near-Linear Area Bound for Drawing Binary trees. Proc. Of the 10th ACM-SIAM Symposium on Discrete Algorithms pp. 161-168.

  3. Coffman E., Graham R. Optimal scheduling for two processor systems. Acta Informatica, 1, pp.200-213, 1971.

  4. Collins C. Docuburst: Radial space-filling visualization of document content// Technical Report KMDI-TR-2007-1, Knowledge Media Design Institute. 2007.

  5. Crescenzi P., Di Battista G., Piperno A. A note on optimal area algorithms for upward drawings of binary trees. Computational Geometry: Theory and Applications N2, pp.187-200, 1992.

  6. Davidson R., Harel D. Drawing Graphs Nicely Using Simulated Annealing ACM Transactions on Graphics Vol 15, No 4, October 1996 pp. 301-333.

  7. Fiduccia C.M., Mattheyses R.M. A linear time heuristic for improving network partitions //Proc. 19th ACM/IEEE Design Automat. Conf., Las Vegas, 1982.— New Jersey, 1982.—P.175-181.

  8. Freeman L.C., Centrality in Social Networks: Conceptual Clarification// Social Networks N 1. 1978/79. P. 215-239.

  9. Fruchterman T. M. J. Reingold E. M.: Graph Drawing by Force-Directed Placement Software //Practice and Experience , 1991, Vol. 21, N11, P. 1129-1164.

  10. Furnas G. W. Generalized Fisheye Views // Proceedings of CHI’86. 1986. P. 16–23.

Gajer P., Kobourov S. G. GRIP: Graph dRawing with Intelligent Placement.// Lect. Notes Comput. Sci. 2001. Vol. 1984. P. 222-228.

  1. Hachul, S. and Jünger, M.l. An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs.// Lect. Notes Comput. Sci. 2005. Vol. 3843. P. 235-250.

  2. Kadmon, N., and Shlomi, E. A polyfocal projection for statistical surfaces//Cartographic Jour. —1978. Vol. 15, N 1. P. 36-41.

  3. Karypis G. Aggarwai R., Kumar V, Shekhar S. Multilevel hypergraph partitioning: Application in VLSI domain // Proc. 34th Design Automat. Conf., Anaheim, 1997.—P.526-529.

  4. Karypis G. Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs.// SIAM Journal on Scientific Computing. —1999.— Vol. 20, N 1. — P.359—392.

  5. Karypis G., Kumar V. Multilevel k-way Hupergraph Partitioning (http://www.cs.umn.edu/~metis).

  6. Kernighan B.M.,Lin S. An efficient heuristic for partitioning graphs. // The Bell System Technical Journal. — 1970. —Vol. 49, N2.—P. 291-307.

  7. Lee B., Parr C. S., Campbell D., et al. How users interact with biodiversity information using TaxonTree// Proceedings of the working conference on Advanced visual interfaces Gallipoli, Italy. — 2004. P. 320 – 327. 

  8. Lee B., Parr C. S., Plaisant C.,et al TreePlus: Interactive Exploration of Networks with Enhanced Tree Layouts// IEEE TVCG (Infovis’06 proceedings) . 2006. Vol.12, N 6.P. 1414–142.

  9. Lee, B., Plaisant, C., Parr, et al. Task Taxonomy for Graph Visualization// Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, Venice, Italy. 2006. P. 1-5.

  10. Plaisant, C., J. Grosjean, Bederson B. Spacetree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation// IEEE Symposium on Information Visualization. —2002. P. 57 -64.

  11. Noack, A. An Energy Model for Visual Graph Clustering// Lect. Notes Comput. Sci. 2004. Vol. 2912. P. 425-436.

  12. Rao R. TableLens: A Clear Window for Viewing Multivariate Data. —2006. http://www.perceptualedge.com/articles/b-eye/tablelens.pdf.

  13. Reingold E., Tilford J. Tidier drawings of trees. IEEE Transactions on Software Engineering, 7 (2) pp. 223-228,1981.

  14. Sarkar M., Brown M.H. Graphical Fisheye Views // Communications of the ACM. 1994. Vol. 37, N 12. P. 73-84.

  15. Sarkar M., Brown M.H. Graphical Fisheye Views // Communications of the ACM. 1994. Vol. 37, N 12. P. 73-84.

  16. Sarkar M., Reiss S.P. Manipulating Screen Space with Stretch Tools: Visualizing Large Structure on Small Screen//Technical Report CS-92-42/ Dept. of Comp. Sci., Brown U., Providence, RI, September 1992.

  17. Six J. M., Tollis I.G. Circular drawings of biconnected graphs. LNCS 1619, pp. 57-73, 1999.

  18. .Shneiderman, B., The Eyes Have It: A Task by Data Type. Taxonomy for Information Visualizations, Proc. of IEEE. Symposium on Visual Languages, Los Alamos. 1996. P. 336-343.

  19. Slack J., Munzner T. Composite Rectilinear Deformation for Stretch and Squish Navigation// Transactions on Visualization and Computer Graphics, September 2006. Vol. 12, N 5. P. 901-908.

  20. Sugiyama K., Tagawa S., Toda M. Methods for visual understanding of hierarchical system structures// IEEE Transactions on Systems, Man, and Cybernetics. 1981. Vol. SMC-11, N. 2. P. 109-125.

  21. Tamassia R. On embedding a graph in the grid with the minimum number of bends// SIAM. J. Comput. 1987. 16(3). P.421–444.

  22. Van Ham F., van Wijk J.J. Interactive Visualization of Small World Graphs//
    Proc. IEEE Symp. Information Visualization, IEEE CS Press. 2004. P. 199-206.

  23. Yang J., Ward M., Rundensteiner E., et al InterRing: a visual interface for navigating and manipulating hierarchies//Information Visualization. 2003. Vol. 2. P. 16-30.

  24. Walker J. A node-positioning algorithm for general trees. Software-Practice and Experience, 20(7) pp. 685-705,1990.


8. Материально-техническое обеспечение дисциплины

  • Ноутбук, медиа-проектор, экран.

  • Программное обеспечение для демонстрации слайд-презентаций.


Рецензент (ы)

Программа одобрена на заседании Методической комиссии ФИТ
от ___________ года, протокол № ____


Похожие:

Программа дисциплины «Методы визуализации информации при помощи графов» iconМетоды визуализации информации наукоемкое направление современных ит
В отличие от европейских и американских университетов, в программу обучения которых методы визуализации информации вошли достаточно...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПрограммные средства и методы трехмерной визуализации в томографии
Описаны методы, используемые при трехмерной визуализации реконструированных объектов: структуры данных, методы сегментации и методы...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Программа дисциплины «Методы визуализации информации при помощи графов» iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Программа дисциплины «Методы визуализации информации при помощи графов» iconТехнология визуализации учебной информации. Некоторые теоретические основы технологии визуализации
В этой связи назрела потребность в систематизации накопленного опыта визуализации учебной информации и его научного обоснования с...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПрограмма вступительного экзамена в аспирантуру по специальностям 05. 13. 05 "Элементы и устройства вычислительной техники и систем управления"
Комбинаторика и Комбинаторные объекты. Методы комбинаторного анализа. Теория графов. Основные понятия и определения. Способы задания...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПримерная программа наименование дисциплины: «Криптографические методы защиты информации»
Учебная дисциплина «Криптографические методы защиты информации» обеспечивает приобретение знаний и умений в соответствии с государственным...
Программа дисциплины «Методы визуализации информации при помощи графов» iconПрограмма дисциплины «избранные главы теории графов»
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org