Аноним

Техники визуализации при разработке алгоритмов: различия между версиями

Материал из WEGA

Техники визуализации при разработке алгоритмов (посмотреть исходный код)

Версия от 11:46, 29 июня 2018

11 448 байт добавлено ,  29 июня 2018
→‎Основные результаты
Нет описания правки
Строка 43: Строка 43:


'''Визуализация на основе отображения состояний'''
'''Визуализация на основе отображения состояний'''
Системы визуализации алгоритмов на основе отображения состояний полагаются на предположение, заключающееся в том, что наблюдение изменений переменных дает ключ к действиям, выполняемым алгоритмом. Главной задачей являются захват и мониторинг модификаций данных, а не обработка интересующих событий, выдаваемых аннотированным алгоритмическим кодом. По этой причине такие системы также называются системами визуализации данных, управляемыми данными. Обычные отладчики могут рассматриваться как системы, управляемые данными, поскольку они предоставляют непосредственную обратную связь в ответ на модификацию переменных. Основным преимуществом этого подхода по сравнению с подходом на основе события является намного большая степень допустимого игнорирования кода: для анимации программы необходимо знать только интерпретацию переменных. С другой стороны, если уделять внимание только модификации данных, это может привести к ограничению возможных вариантов настройки и усложнению процесса создания анимаций, естественным образом отражающих интересующие события. В качестве примеров инструментов визуализации на основе отображения состояний можно привести Pavane [23, 25], ставший воплощением первого изменения парадигмы визуализации алгоритмов с момента появления понятия интересующих событий, и Leonardo [10] – интегрированную среду разработки, визуализации и выполнения программ на C.
Исчерпывающее обсуждение других техник визуализации алгоритмов можно найти в работах [7, 21, 22, 24, 27].
== Применение ==
Техники визуализации при разработке алгоритмов находят применение в таких областях, как тестирование и отладка реализаций алгоритмов, визуальная проверка сложных структур данных, определение узких мест производительности системы и оптимизация кода. Некоторые примеры подобного использования приведены [12].
== Открытые вопросы ==
В области визуализации алгоритмов остается много нерешенных задач. Прежде всего, вся мощь систем визуализации алгоритмов должна быть доступна конечному пользователю, возможно, не имеющему опыта, а не только профессиональному программисту или разработчику инструмента. К примеру, преподавателям могла бы очень пригодиться возможность быстро и просто подстраивать анимации в соответствии с их конкретными учебными материалами, однако им вряд ли окажутся полезными системы визуализации, слишком сложные в установке или жестко привязанные к определенным программным или аппаратным платформам. Помимо простоты использования, инструмент визуализации ПО должен быть способен к анимации достаточно сложных алгоритмических кодов, не требуя при этом значительных усилий. Это представляется особенно важным для будущих процессов разработки визуальных отладчиков. И, наконец, дальнейших исследований заслуживает визуализация выполнения алгоритмов на больших наборах данных. В настоящее время даже системам, предназначенным для больших информационных пространств, нередко недостает продуманных механизмов навигации и методов устранения узких мест процесса отображения, таких как изменение масштаба и разрешения, селективно, а также пропуск информации.
== См. также ==
* [[Экспериментальные методы анализа алгоритмов]]
== Литература ==
1. Anderson, R.J.: The Role of Experiment in the Theory of Algorithms. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 59, pp. 191-195. American Mathematical Society, Providence, RI (2002)
2. Baker, J., Cruz, I., Liotta, G., Tamassia, R.: Animating Geometric Algorithms over the Web. In: Proceedings of the 12th Annual ACM Symposium on Computational Geometry. Philadelphia, Pennsylvania, May 24-26, pp. C3-C4 (1996)
3. Baker, J., Cruz, I., Liotta, G., Tamassia, R.: The Mocha Algorithm Animation System. In: Proceedings of the 1996 ACM Work shop on Advanced Visual Interfaces. Gubbio, Italy, May 27-29, pp. 248-250(1996)
4. Baker, J., Cruz, I., Liotta, G., Tamassia, R.: A New Model for Algorithm Animation over the WWW, ACM Comput. Surv. 27, 568-572(1996)
5. Baker, R., Boilen, M., Goodrich, M., Tamassia, R., Stibel, B.: Testers and Visualizers for Teaching Data Structures. In: Proceeding of the 13th SIGCSE Technical Symposium on Computer Science Education. New Orleans, March 24-28, pp. 261-265(1999)
6. Brown, M.: Algorithm Animation. MIT Press, Cambridge, MA (1988)
7. Brown, M.: Perspectives on Algorithm Animation. In: Proceedings of the ACM SIGCHI'88 Conference on Human Factors in Computing Systems. Washington, D.C., May 15-19, pp. 33-38 (1988)
8. Brown, M.: Zeus: a System for Algorithm Animation and Multi-View Editing. In: Proceedings of the 7th IEEE Workshop on Visual Languages. Kobe, Japan, October 8-11, pp. 4-9 (1991)
9. Cattaneo, G., Ferraro, U., Italiano, G.F., Scarano, V.: Cooperative Algorithm and Data Types Animation over the Net.J.VisualLang.Comp. 13(4): 391 - (2002)
10. Crescenzi,  P.,  Demetrescu,  C.,  Finocchi.  I.,  Petreschi,  R.: Reversible  Execution  and  Visualization  of Programs  with LEONARDO.  J.  Visual  Lang.  Comp.  11,  125-150  (2000). Leonardo    is    available    at:    http://www.dis.uniroma1.it/~demetres/Leonardo/. Accessed 15 Jan 2008
11. Demetrescu, C.: Fully Dynamic Algorithms for Path Problems on Directed Graphs, Ph.D. thesis, Department of Computer and Systems Science, University of Rome "La Sapienza" (2001)
12. Demetrescu, C., Finocchi, I., Italiano, G.F., Naher, S.: Visualization in algorithm engineering: tools and techniques. In: Experimental Algorithm Design to Robust and Effizient Software. Lecture Notes in Computer Science, vol. 2547. Springer, Berlin, pp. 24-50 (2002)
13. Demetrescu, C., Finocchi, I., Liotta, G.: Visualizing Algorithms over the Web with the Publication-driven Approach. In: Proc. of the4th Workshop on Algorithm Engineering (WAE'00), SaarbrCicken, Germany, 5-8 September (2000)
14. Fabri, A., Giezeman, G., Kettner, L., Schirra, S., Schonherr, S.: The cgal kernel: A basis for geometric computation. In: Applied Computational Geometry: Towards Geometric Engineering Proceedings (WACG'96), Philadelphia. Philadelphia, PA, May 27-28, pp. 191-202 (1996)
15. Goldberg, A.: Selecting problems for algorithm evaluation. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99). LNCS, vol. 1668. London, United Kingdom, July 19-21, pp. 1-11 (1999)
16. Johnson, D.: A theoretician's guide to the experimental analysis of algorithms. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59, 215-250. American Mathematical Society, Providence, RI (2002)>
17. Malony, A., Reed, D.: Visualizing Parallel Computer System Performance. In: Simmons, M., Koskela, R., Bucher, I. (eds.) Instrumentation for Future Parallel Computing Systems. ACM Press, New York (1989) pp. 59-90
18. McGeoch, C.: A bibliography of algorithm experimentation. In: Data Struktures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59, 251-254. American Mathematical Society, Providence, RI (2002)
19. Mehlhorn, K., Naher, S.: LEDA: A Platform of Combinatorial and Geometric Computing, ISBN 0-521-56329-1. Cambrige University Press, Cambrige (1999)
20. Moret, B.: Towards a discipline of experimental algorithmics. In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 59, 197-214. American Mathematical Society, Providence, RI (2002)
21. Myers, B.: Taxonomies of Visual Programming and Program Visualization.J. Visual Lang. Comp. 1,97-123 (1990)
22. Price, B., Baecker, R., Small, I.: A Principled Taxonomy of Software Visualization. J. Visual Lang. Comp. 4, 211-266 (1993)
23. Roman, G., Cox, K.: A Declarative Approach to Visualizing Concurrent Computations. Computer 22,25-36 (1989)
24. Roman, G., Cox, K.: A Taxonomy of Program Visualization Systems. Computer 26,11 -24 (1993)
25. Roman, G., Cox, K., Wilcox, C., Plun, J.: PAVANE: a System for Declarative Visualization of Concurrent Computations. J. Visual Lang. Comp.3,161-193(1992)
26. Stasko, J.: Animating Algorithms with X-TANGO. SIGACT News 23,67-71 (1992)
27. Stasko, J., Domingue, J., Brown, M., Price B.: Software Visualization: Programming as a Multimedia Experience. MIT Press, Cambridge, MA (1997)
28. Stasko, J., Kraemer, E.: A Methodology for Building Application-Specific Visualizations of Parallel Programs. J. Parall. Distrib. Comp. 18, 258-264 (1993)
29. Tal, A., Dobkin, D.: Visualization of Geometric Algorithms. IEEE Trans. Visual. Comp. Graphics 1,194-204(1995)
Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/13090