dtЦифровая трансформацияDigital Transformation2522-96132524-2822Educational Establishment “Belarusian State University of Informatics and Radioelectronics”10.35596/1729-7648-2022-28-4-72-79dt-719Research ArticleТЕХНИЧЕСКИЕ НАУКИTECHNICAL SCIENCESИнтерактивная визуализация алгоритмов трассировки печатных проводников в учебном процессеInteractive Visualization of the Printed Circuits Tracing Algorithms for Educational PurposesПетровД. О.PetrovD. O.

Петров Дмитрий Олегович, к. т. н., доцент кафедры ЭВМ и системы

224017, г. Брест, ул. Московская, 267Тел. +375 29 523-87-23

Petrov Dmitriy Olegovich, Cand. of Sci., Associate Professor of the Computer and Computer Sciences Department

224017, Brest, Moskovskaya St., 267Tel. +375 29 523-87-23

polegdo@gmail.comБрестский государственный технический университетBrest State Technical University2022010220232847279Copyright © Петров Д.О., 20232023Петров Д.О.Petrov D.O.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://dt.bsuir.by/jour/article/view/719

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

A software module that allows interactive demonstration of maze routing algorithms for tracing printed conductors, which, during their operation, use a grid representation of a discrete working space of a printed circuit board has been developed. The main difference between the developed module and the software of similar purpose is the possibility of step-by-step annotated execution of various algorithms for tracing printed conductors with the possibility of changing the order of routing user-specified conductors. The interrelation of algorithms for finding the shortest paths on graphs and algorithms for tracing printed conductors and the influence of the order of making connections between pairs of contact pads on the length of printed electrical connections are considered. An analysis of the advantages and disadvantages of the wave algorithm (Lee algorithm) and the heuristic algorithm A* was carried out with a description of their step-by-step operation. The use of the development is justified when giving lectures and conducting laboratory research on the theoretical foundations of automation systems for the design of radio electronic equipment and contributes to solving the complex problem of digitalization of the educational process with the help of visualization programs that allow you to observe the results of the algorithms they implement on various sets of initial data.

цифровизация образованиявизуализация алгоритмасистема автоматизации проектированияпечатная плататрассировкадискретное рабочее пространствоdigitalization of educationvisualization of algorithmdesign automation systemprinted circuit boardtracingdiscrete workspaceReferencesМоглан, Д. Дидактический потенциал использования систем визуализации алгоритмов в процессе обучения программированию / Д. Моглан // Открытое образование. 2019. Т. 23, № 2. С. 31–41.Moglan D. (2019) The Didactic Potential of Using Algorithm Visualization Systems in the Process of Programming Teaching. Otkrytoe Obrazovanie [Open Education]. 23 (2), 31–41 (in Russian).Цехан, О. Б. Обучающая программа – визуализатор алгоритма направленного перебора по векторной решетке / О. Б. Цехан // Информатизация образования – 2012: педагогические основы разработки и использования электронных образовательных ресурсов: матер. Междунар. науч. конф., Минск, 24–27 окт. 2012 г. Минск: БГУ, 2012. С. 79–83.Tsehan O. B. (2012) Educational Visualizer Software for Directed Search Algorithm on Vector Lattice. Informatizaciya Obrazovaniya – 2012: Pedagogicheskie Osnovy Razrabotki i Ispol’zovaniya Elektronnyh Obrazovatel’nyh Resursov: Mater. Mezhdunar. Nauch. Konf. [Informatization of Education – 2012: Pedagogical Foundations for the Development and Use of Electronic Educational Resources: Materials of International Scientific Conference]. Minsk, Oct. 24–27, 2012. Minsk, Belarussian State University. 79–83 (in Russian).Казаков, М. А. Разработка логики визуализаторов алгоритмов на основе конечных автоматов / М. А. Казаков, Г. А. Корнеев, А. А. Шалыто // Телекоммуникации и информатизация образования. 2003. № 6. С. 27–58.Kazakov M. A., Korneev G. A., Shalyto A. A. (2003) Development of the Logic of Algorithms Visualizers Based on Finite State Machines. Telekommunikacii i Informatizaciya Obrazovaniya [Telecommunications and Informatization of Education]. (6), 27–58 (in Russian).Веренич, И. Ю. Планарные и координатные трассировщики на практике / И. Ю. Веренич, Ю.В.Лысенко // Вестник ЮУрГУ. 2011. № 2. С. 30–33.Verenich I. U., Lysenko U. V. (2011) Planar and Coordinate Tracers in Practice. Vestnik Uzhno-Ural’skogo Gosudarstvennogo Universiteta [Bulletin of South Ural State University]. (2), 30–33 (in Russian).Бершадский, А. М. Алгоритм улучшения трассировки печатных плат / А. М. Бершадский, П. А. Гудков, Е. М. Подмарькова // Модели, системы, сети в экономике, технике, природе и обществе. 2021. № 3. С. 80–90.Bershadskij A. M., Gudkov P. A., Podmar’kova E. M. (2021) PCB Routing Improvement Algorithm. Modeli, Sistemy, Seti v Ekonomike, Tekhnike, Prirode i Obshchestve [Models, Systems, Networks in Economics, Technology, Nature and Society]. (3), 80–90 (in Russian).Lee, C. Y. An Algorithm for Path Connections and its Applications / C. Y. Lee // IRE Transactions on Electronic Computers. 1961. No 10. P. 346–365.Lee C. Y. (1961) An Algorithm for Path Connections and its Applications. IRE Transactions on Electronic Computers. (10), 346–365.Rubin, F. The Lee Path Connection Algorithm / F. Rubin // IEEE Transactions on Computers. 1974. Vol. C-23, No 9. P. 907–914.Rubin F. (1974) The Lee Path Connection Algorithm. IEEE Transactions on Computers. C-23 (9), 907–914.Moore, E. F. The Shortest Path Through a Maze / E. F. Moore // Proc. International Symposium on the Theory of Switching. USA: Harvard University Press, 1959. P. 285–292.Moore E. F. (1959) The Shortest Path Through a Maze. Proc. International Symposium on the Theory of Switching. USA, Harvard University Press. 285–292.Hart, P. E. A Formal Basis for the Heuristic Determination of Minimum Cost Path / P. E. Hart, N. J. Nilsson, B. Raphael // IEEE Transactions on Systems Science and Cybernetics. 1968. Vol. 4, No 2. P. 100–107.Hart P. E., Nilsson N. J., Raphael B. (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Path. IEEE Transactions on Systems Science and Cybernetics. 4 (2), 100–107.Clow, G. W. A Global Routing Algorithm for General Cells / G. W. Clow // 21<sup>st</sup> Design Automation Conference Proceedings, June 25, 1984. P. 45–51.Clow G. W. (1984) A Global Routing Algorithm for General Cells. 21<sup>st</sup> Design Automation Conference Proceedings, June 25. 45–51.Yuan, C. ASA-routing: a-Star Adaptive Routing Algorithm for Network-on-Chips / C. Yuan, J. Xiang // 18<sup>th</sup> International Conference, ICA3PP 2018, Proceedings, Part II, Guangzhou, China, Nov. 15–17, 2018. P. 187–198.Yuan C., Xiang J. (2018) ASA-Routing: a-Star Adaptive Routing Algorithm for Network-on-Chips. 18<sup>th</sup> International Conference, ICA3PP 2018, Proceedings, Part II, Guangzhou, China, Nov. 15–17. 187–198.Chen, Huang-Yu. Global and Detailed Routing / Huang-Yu Chen, Yao-Wen Chang // Electronic Design Automation. Boston: Morgan Kaufmann, 2009. Chapter 12. P. 687–749.Chen Huang-Yu, Chang Yao-Wen (2009) Global and Detailed Routing. Electronic Design Automation. Boston, Morgan Kaufmann. Chapter 12. 687–749.

The authors declare that there are no conflicts of interest present.