Что называется отладкой алгоритма
Большая Энциклопедия Нефти и Газа
Логическая отладка алгоритмов также может быть разбита на укрупненный анализ логики преобразования информации, заложенной в данном алгоритме, и детальный анализ маршрутов логических преобразований, соответствующих определенной входной информации. При укрупненном анализе необходимо получить все возможные маршруты преобразования информации при любых допустимых сочетаниях исходных данных и соответствующие им выходные результаты. Кроме того, должны быть проанализированы вероятностные и временные характеристики маршрутов. [1]
Проблемам отладки алгоритмов и программ посвящена шестая глава. В ней анализируются типовые ошибки алгоритмов и программ и методы поэтапного их устранения. Рассмотрена структура систем отладки и задачи основных отладочных операторов. Значительное внимание уделено технологии автономной и комплексной отладки. [5]
Система отладки алгоритмов и программ управляющей ЦВМ ( СОТ) представляет собой совокупность алгоритмических и программных средств, предназначенных для автоматизации процессов установления факта правильного функционирования разработанных программ в управляющей машине, а также для обнаружения, локализации и устранения ошибок в алгоритмах и программах. [6]
При отладке алгоритма время распределяется, как указано в табл. 3.4. В этом случае после последнего выхода анализ ошибок все еще нужно производить, а исправления уже не нужны. [8]
Как отмечалось, отладка алгоритма выполняется для проверки его правильности, выявления и исправления ошибок в нем. [9]
В некоторых случаях для отладки алгоритма достаточно лишь исполнить его. Например, в тех случаях, когда для оценки результата ( верен он или нет) достаточно сопоставить его с исходными данными задачи. [10]
Кроме достоверности для процессов отладки алгоритмов и программ в общем случае имеют большое значение затраты на отладку 5 до некоторого уровня ошибок аот. При этом следует учитывать нелинейный характер зависимости от РОТ ( S), когда резко возрастают затраты на отладку при ошибках алгоритмов и программ, характеризующихся малой вероятностью их проявления PI и малым весом в выходных результатах Аг. Поэтому в процессе отладки необходимо периодически оценивать ее достоверность с тем, чтобы ограничивать затраты на этот процесс такими величинами, когда повышение достоверности перестает быть достаточно существенным. Отсутствие необходимых статистических исследований затрат на отладку алгоритмов и программ позволяет высказать только общие предположения о характере зависимости 0ОТ от некоторых параметров, однако для получения расчетных формул требуются обширные и детальные исследования затрат на отладку алгоритмов и программ в каждой организации, ведущей эти процессы. [11]
Значительно снижается трудоемкость процессов отладки алгоритмов и программ при применении машинно-ориентированных языков типа автокодов. При этом благодаря применению символической записи разработчик избавляется от значительного количества избыточной информации, содержащейся в машинных кодах, и методами формального автоматического контроля могут быть выявлены многие типы программных ошибок. За упрощение процессов отладки приходится расплачиваться созданием систем трансляции и автоматизации контроля и отладки на машинно-ориентированном языке. Эти затраты могут дать эффект в тех случаях, когда достаточно велик объем программ, подлежащих отладке по сравнению с объемом программ трансляторов и системы отладки. [12]
Системы такого типа позволяют производить отладку алгоритмов и получать эффективные программы при отсутствии ЭВМ, для которой они предназначены. [13]
Отладка программы
Отла́дка — этап разработки компьютерной программы, на котором обнаруживают, локализуют и устраняют ошибки. Чтобы понять, где возникла ошибка, приходится :
Существуют две взаимодополняющие технологии отладки.
Содержание
Место отладки в цикле разработки программы
Типичный цикл разработки, за время жизни программы многократно повторяющийся, выглядит примерно так:
Инструменты
Способности программиста к отладке — это, по-видимому, важнейший фактор в обнаружении источника проблемы, но сложность отладки сильно зависит от используемого языка программирования и инструментов, в частности, отладчиков.
Инструменты отладки
Отладчик представляет из себя программный инструмент, позволяющий программисту наблюдать за выполнением исследуемой программы, останавливать и перезапускать её, прогонять в замедленном темпе, изменять значения в памяти и даже, в некоторых случаях, возвращать назад по времени.
Также полезными инструментами в руках программиста могут оказаться:
Использование языков программирования высокого уровня, таких как Java, обычно упрощает отладку, поскольку содержат такие средства как обработка исключений, сильно облегчающие поиск источника проблемы. В некоторых низкоуровневых языках, таких как ассемблер, ошибки могут приводить к незаметным проблемам — например, повреждениям памяти или утечкам памяти, и бывает довольно трудно определить что стало первоначальной причиной ошибки. В этих случаях, могут потребоваться изощрённые приёмы и средства отладки.
«Наш личный выбор — стараться не использовать отладчики, кроме как для просмотра стека вызовов или же значений пары переменных. Одна из причин этого заключается в том, что очень легко потеряться в деталях сложных структур данных и путей исполнения программы. Мы считаем пошаговый проход по программе менее продуктивным, чем усиленные размышления и код, проверяющий сам себя в критических точках.
Щёлканье по операторам занимает больше времени, чем просмотр сообщений операторов выдачи отладочной информации, расставленных в критических точках. Быстрее решить, куда поместить оператор отладочной выдачи, чем проходить шаг за шагом критические участки кода, даже предполагая, что мы знаем, где находятся такие участки. Более важно то, что отладочные операторы сохраняются в программе, а сессии отладчика переходящи.
Слепое блуждание в отладчике, скорее всего, непродуктивно. Полезнее использовать отладчик, чтобы выяснить состояние программы, в котором она совершает ошибку, затем подумать о том, как такое состояние могло возникнуть. Отладчики могут быть сложными и запутанными программами, особенно для новичков, у которых они вызовут скорее недоумение, чем принесут какую либо пользу…»
«Отладка сложна и может занимать непредсказуемо долгое время, поэтому цель в том, чтобы миновать большую её часть. Технические приёмы, которые помогут уменьшить время отладки, включают хороший дизайн, хороший стиль, проверку граничных условий, проверку правильности исходных утверждений и разумности кода, защитное программирование, хорошо разработанные интерфейсы, ограниченное использование глобальных переменных, автоматические средства контроля и проверки. Грамм профилактики стоит тонны лечения.»
Инструменты, снижающие потребность в отладке
Другое направление — сделать, чтобы отладка нужна была как можно реже. Для этого применяются:
Безопасность программного кода и отладка
В программном коде может быть так называемое недокументированное поведение — серьёзные ошибки, которые не проявляются при нормальном ходе выполнения программы, однако весьма опасны для безопасности всей системы в случае целенаправленной атаки. Чаще всего это результат ошибок программиста. Наиболее известные примеры — это SQL-инъекция и переполнение буфера. В данном случае задача отладки это:
Что называется отладкой алгоритма
В своих расчетах рабочая группа исходила из того, что для отладки некоторой усредненной программы требуется 5 выходов на машину для отладки синтаксиса и 5 выходов для отладки алгоритма. Причем при отладке синтаксиса после последнего пятого выхода анализ ошибок и исправление не требуются. Время распределяется, как указано в табл. 3.3. [c.107]
При отладке алгоритма время распределяется, как указано в табл. 3.4. В этом случае после последнего выхода анализ ошибок все еще нужно производить, а исправления уже не нужны. [c.107]
Все работы, связанные с нормированием с помощью ЭВМ, можно разделить на два вида единовременные работы, выполняемые НИИ и предприятием — переработка нормативных материалов к виду, удобному для расчета на ЭВМ, создание модели решения задачи, выбор метода расчета, разработка алгоритма расчета норм, составление и отладка программы расчета на ЭВМ работы, выполняемые на предприятии при проведении каждого расчета — заполнение бланков исходных данных, расчет на ЭВМ. [c.203]
Опытная эксплуатация задач заключается в проверке алгоритмов, программ и звеньев технологического процесса обработки данных в реальных условиях. Она проводится для окончательной отладки программ и отработки технологического процесса решения задач проверки подготовленности информационной [c.336]
Построение алгоритма проектирования ТПП и отладка программного обеспечения (ПО), возможно, приведут к коррективе состава и функций технических средств Еу и Ei2. [c.122]
Разрабатывает программы, обеспечивающие возможность выполнения алгоритма и соответственно поставленной задачи средствами вычислительной техники, проводит их тестирование и отладку. [c.350]
Должностные обязанности. На основе анализа математических моделей и алгоритмов решения экономических и других задач разрабатывает программы, обеспечивающие возможность выполнения алгоритма и соответственно поставленной задачи средствами вычислительной техники, проводит их тестирование и отладку. Разрабатывает технологию решения задачи по всем этапам обработки информации. Осуществляет выбор языка программирования для описания алгоритмов и структур данных. Определяет информацию, подлежащую обработке средствами вычислительной техники, ее объемы, структуру, макеты и схемы ввода, обработки, хранения и вывода, методы ее контроля. Выполняет работу по подготовке программ к отладке и проводит отладку. Определяет объем и содержание данных контрольных примеров, обеспечивающих наиболее полную проверку соответствия программ их функциональному назначению. Осуществляет запуск отлаженных программ и ввод исходных данных, определяемых условиями поставленных задач. Проводит корректировку разработанной программы на основе анализа выходных данных. Разрабатывает инструкции по работе с программами, оформляет необходимую техническую документацию. Определяет возможность использования готовых программных продуктов. Осуществляет сопровождение внедренных программ и программных средств. Разрабатывает и внедряет системы автоматической проверки правильности программ, типовые и стандартные программные средства, составляет технологию обработки информации. Выполняет работу по унификации и типизации вычислительных процессов. Принимает участие в создании каталогов и картотек стандартных программ, в разработке форм документов, подлежащих машинной обработке, в проектировании программ, позволяющих расширить область применения вычислительной техники. [c.179]
Должностные обязанности. Выполняет работу по обеспечению механизированной и автоматизированной обработки поступающей в вычислительный (информационно-вычислительный) центр (ВЦ, ИВЦ) информации, разработки технологии решения экономических и других задач производственного и научно-исследовательского характера. Принимает участие в проектировании систем обработки данных и систем математического обеспечения машины. Выполняет подготовительные операции, связанные с осуществлением вычислительного процесса, ведет наблюдение за работой машин. Составляет простые схемы технологического процесса обработки информации, алгоритмы решения задач, схемы коммутации, макеты, рабочие инструкции и необходимые пояснения к ним. Разрабатывает программы решения простых задач, проводит их отладку и экспериментальную проверку отдельных этапов работ. Выполняет работу по подготовке технических носителей информации, обеспечивающих автоматический ввод данных в вычислительную машину, по накоплению и систематизации показателей нормативного и [c.218]
Составить машинную программу, даже сравнительно простую, без ошибок практически невозможно. Поэтому программы после составления и перевода на машинный носитель требуют выполнения операций по отладке. Отладка заключается в том, что проверяется правильность функционирования программы в соответствии с заданным алгоритмом. Для этих целей обычно создаются специальные массивы исходных данных, результаты операций с которыми по заданному алгоритму заранее известны. [c.95]
После отладки производится внедрение программы на реальных данных или опытное внедрение. Опытное внедрение длится несколько месяцев и позволяет окончательно откорректировать программу, а в отдельных случаях и алгоритм ее решения и даже саму постановку задачи. [c.95]
Далее алгоритмом предусматривается получение.общей стоимости за период выполнения работ в соответствии с входными параметрами, затрат по категориям труда, стоимости, связанной с каждым видом выполняемой работы и использованием ЭВМ для контроля, отладки и тестирования. Выход алгоритма рассматривается как пробная оценка в смысле ее сопоставления g наложенными стоимостными ограничениями на проект. [c.93]
Выбор алгоритма. Одним из худших нарушений стиля программирования является желание улучшить программу с целью повышения эффективности до завершения ее отладки. Эти попытки не только снижают простоту, ясность, надежность и читаемость программы, но и не дают, как правило, серьезных результатов увеличения эффективности. [c.150]
Опытная эксплуатация состоит в проверке алгоритмов, программ и всего технологического процесса обработки данных в реальных условиях. Здесь осуществляется окончательная отладка программ и процесса принятия решений, проверяется готовность информационной базы, проводится отладке взаимосвязей подсистем АСУ. Персонал вычислительного центра и аппарат управления производственно-хозяйственного объекта приобретают необходимые навыки. [c.20]
Использование технологических операций класса Преобразование алгоритмов и Преобразование программ характерно для тех случаев, когда в типовом проекте содержатся только фрагменты (модули) алгоритмов и программ, необходимых для генерации программного обеспечения СМОД. Тогда возникает потребность выполнять действия, связанные с получением машинных алгоритмов, сборкой, тестированием и отладкой программ. [c.159]
Создание математической модели расчета оптималь- ных режимов резания и. норм времени Разработка алгоритмов Составление и отладка [c.310]
Должностные обязанности. На основе анализа математических моделей и алгоритмов (постановок экономических и других задач) разрабатывает программы, реализующие решение задачи. Разрабатывает технологию решения задачи по всем этапам. Осуществляет выбор языка программирования и перевод на него алгоритмов задач. Определяет информацию, подлежащую обработке на ЭВМ, ее объемы, структуру, макеты и схемы ввода, обработки, хранения и выдачи информации, методы ее контроля. Определяет объем и содержание, данных тестовых примеров, обеспечивающих наиболее полную проверку соответствия программ их функциональному назначению. Выполняет работу по подготовке программ к отладке и проводит отладку. Разрабатывает инструкции по работе с программами, оформляет необходимую техническую документацию. Определяет возможность использования готовых программных средств. Осуществляет сопровождение внедренных программ и программных средств. Разрабатывает и внедряет методы и средства автоматизации программирования, типовые и стандартные программные средства. Принимает участие в проектных работах. На основе логического анализа проводит камеральную проверку программ. Определяет совокупность данных, обеспечивающих решение максимального числа условий, включенных в программу, выполняет работу по ее подготовке к отладке. Проводит отладку разработанных программ, корректирует их в процессе доработки. Разрабатывает инструкции по работе с программами, оформляет необходимую техническую документацию. Определяет возможность использования готовых программ, разработанных другими предприятиями (учреждениями). Разрабатывает и внедряет методы автоматизации программирования, типовые и стандартные программы, программирующие программы, трансляторы, входные алгоритмические языки. Выполняет работу по унификации и типизации вычислительных процессов. Принимает участие в создании ка- [c.156]
Должностные обязанности. Выполняет работу по обеспечению механизированной обработки поступающей в ВЦ (ИВЦ) информации, эффективной работы вычислительной техники, средств приема и передачи информации. Принимает участие в проектировании систем обработки данных и систем математического обеспечения машины. Выполняет подготовительные операции, связанные с осуществлением вычислительного процесса, ведет наблюдение за работой машин. Составляет простые схемы технологического процесса обработки информации, алгоритмы решения задач, схемы коммутации, макеты, рабочие инструкции и необходимые пояснения к ним. Разрабатывает программы решения простых задач, проводит их отладку и экспериментальную проверку отдельных этапов работ. Выполняет работу по подготовке технических носителей информации, обеспечивающих автоматический ввод данных в вычислительную машину, по накоплению и систематизации показателей нормативного и справочного фонда, разработке форм исходящих документов, внесению необходимых изменений и своевременному корректированию рабочих программ. Участвует в выполнении различных операций технологического процесса обработки информации (прием и контроль входной информации, подготовка исходных данных, обработка информации, [c.169]
Документацию по разрабатываемой системе рекомендуется готовить не после завершения работ по всему комплексу в целом, а во время отладки по каждой программе в отдельности. Это связано с тем, что алгоритм и схема счета во время отладки свежи в памяти, а после завершения всех работ их нужно восстанавливать, повторно вникая в каждую программу. [c.100]
В автоматизированной системе обработки данных различают функцию развития системы и функционирование самой системы. Функция развития включает проектирование, программирование, отладку системы обработки и ее внедрение. Функция ведения состоит в использовании технических средств и систем обработки для получения входных данных, их обработки по определенным алгоритмам и представления пользователям выходной информации. Рациональное функционирование автоматизированной системы обработки учетных данных требует выявления в процессе обработки всех видов ошибок программным путем. На всех этапах разработки и эксплуатации автоматизированной системы обработки должны быть предусмотрены и реализованы необходимые процедуры контроля и внесения изменений как в файлы данных, так и программные средства. [c.105]
Тем не менее все задачи АСУ характеризуются общностью их постановки на ЭВМ. Эта общность выражается в том, что решение любой задачи в АСУ складывается из ее постановки, выбора метода решения, формирования алгоритма решения, информационного обеспечения рассчитываемой задачи, выбора типа ЭВМ для ее решения, разработки и отладки программы решения на ЭВМ, расчета экономической эффективности от автоматизации решения задачи. [c.79]
На основе разработанного алгоритма решения задачи, ее информационного обеспечения и принятого типа ЭВМ разрабатывается затем программа ее реализации на ЭВМ. Оговоримся, что нужная программа может быть выбрана и из имеющихся пакетов прикладных программ. Разработка программы складывается из формирования блок-схемы реализации задачи на ЭВМ, выбора языка программирования, формирования программы, разработки контрольного (отладочного) примера, отладки программы, экспериментальной проверки ее работы на реальных исходных данных в реальных условиях производства, внедрения разработанной программы в промышленную эксплуатацию. [c.81]
После того как сформирован алгоритм решения задачи, определено информационное ее обеспечение и выбран тип вычислительной техники, производятся разработка и отладка рабочей программы решения задачи. Ее разработка выполняется в три этапа. На первом этапе формируется блок-схема реализации задачи на ЭВМ, на втором — составляется рабочая программа, на третьем этапе производится ее отладка. [c.94]
Должностные обязанности. На основе анализа математических моделей и алгоритмов (постановок экономических и других задач) разрабатывает программы, реализующие решение задачи. Разрабатывает технологию решения задачи по всем этапам. Осуществляет выбор языка программирования и перевод на него алгоритмов задач. Определяет информацию, подлежащую обработке на ЭВМ, ее объемы, структуру, макеты и схемы ввода, обработки, хранения и выдачи информации, методы ее контроля. Определяет объем и содержание данных тестовых примеров, обеспечивающих наиболее полную проверку соответствия программ их функциональному назначению. Выполняет работу по подготовке программ к отладке и проводит отладку. Разрабатывает инструкции по работе с программами, оформляет необходимую техническую документацию. Определяет возможность использования готовых программных средств. Осуществляет сопровождение внедренных программ и программных средств. Разрабатывает и внедряет методы и [c.140]
На этапе рабочего проектирования в соответствии с разработанными ранее алгоритмами осуществляется разработка программ, их отладка и экспериментальная проверка (испытания) на ЭВМ и оформление документации по разработанной задаче (или комплексу задач). [c.336]
В процессе отладки проектировщик может использовать несколько методов контроля правильности работы программы, такие, как метод усеченного алгоритма выход на контрольные результаты контроль времени решения задачи и др. [c.199]
Если проектировщик использовал библиотеку стандартных подпрограмм, то в состав операций по проектированию должны входить такие операции, как декомпозиция задачи на функциональные блоки выбор типовых процедур и состава стандартных подпрограмм разработка принципов связи программных модулей, списков передаваемых параметров разработка алгоритмов оригинальных программных модулей выбор языка программирования, написание и отладка кодов программ соединение ти- [c.200]
Решение задач с помощью электронных таблиц освобождает от составления подробного алгоритма решения задачи и отладки соответствующей программы. Нужно только определенным образом записать в таблицу исходные данные и математические соотношения, входящие в модель решения задачи. [c.61]
Разработку программы моделирования проводят в несколько этапов составление принципиальной схемы моделирования разработка алгоритма моделирования наиисание и отладка программы проведение расчетов.. Составленная и отлаженная программа многократно имитирует работу системы при различных значениях ее параметров и устанавливает на этой основе искомые характеристики процесса — D, Н, L, k0 и др. для выбора оптимального варианта организации обслуживания и расчета норм обслуживания и численности. [c.338]
Разработка детальных алгоритмов, предназначенных для составления на их основе программ решения этой задачи на одном из алгоритмических языков высокого уровня, применяемых в ЕС ЭВМ. Такие алгоритмы разработаны НИС МГИАИ [42]. На основе этих алгоритмов получены фрагменты программ на языке «Алгол-60», и их разработка продолжается. Отладка и реализация этой программы на практике позво- [c.117]
Построение математической модели. Она включает в себя определение входных, выходных, управляющих переменных и их взаимосвязи в общем алгоритме функционирования системы с целью оценки значений выбранных критериев. В случае машинной имитации математическая модель часто представляется в виде алгоритмического описания моделируемого процесса. Основой для этого является содержательное описание процесса функционирования системы. При построении модели необходимо учитывать два противоречивых фактора. Усложнение модели, то есть включение в модель большого числа переменных, что приводит к большим временным затратам на составление, отладку модели, увеличивается и само время проведения имитационных экспериментов, а в некоторых случаях и возникают трудности с интерпретацией результатов. В результате может быть утрачена ценность полученных результатов в силу их большого времени запаздывани-я. Упрощение модели может привести к потере содержательности, модель становится неадекватной системе. [c.193]
Отладка алгоритмов на графах — теперь с картинками
Представим типичную ситуацию на первом курсе: вы прочитали про алгоритм Диница, реализовали, а он не заработал, и вы не знаете, почему. Стандартное решение — это начать отлаживать по шагам, каждый раз рисуя текущее состояние графа на листочке, но это жутко неудобно. Я попробовала исправить положение в рамках семестрового проекта по Software Engineering, а в посте расскажу, как у меня в итоге получился плагин для Visual Studio. Скачать можно тут, исходный код и документацию можно посмотреть тут. Вот скриншот графа, который получился для алгоритма Диница.
О себе
Меня зовут Ольга, я закончила третий курс направления «Прикладная математика и информатика» в Питерской Вышке по специализации Software Engineering. До поступления в университет я не занималась программированием.
НИР: требования
На нашем факультете практикуются ежесеместровые научно-исследовательские работы. Обычно это происходит так: в начале семестра происходит презентация НИРов — представители разных компаний предлагают всевозможные проекты. Потом студенты выбирают понравившиеся проекты, научные руководители выбирают понравившихся студентов и так далее. В конце концов, каждый студент находит себе проект.
Но есть и другой путь: вы можете самостоятельно найти научного руководителя и проект, а потом убедить куратора, что этот проект действительно может быть полноценным НИРом. Для этого нужно доказать, что:
План работы над проектом
Моя работа над проектом состояла из следующих этапов:
Исследование предметной области
Для начала, следовало убедить наше руководство, что эта тема достойна того, чтобы быть моим НИРом. И начать следовало с первого пункта: поиск аналогов.
Как оказалось, аналогов много. Но большинство из них были рассчитаны на визуализацию памяти. То есть они бы прекрасно справились с визуализацией Декартова дерева, но то, что кучу на массиве надо рисовать не как массив, а как дерево, они понять не могут. Среди этих аналогов были gdbgui, Data Display Debugger, плагин для Eclipse jGRASP и плагин под Visual Studio Data Structures Visualizer. Последний тоже создавался для задач олимпиадного программирования, но умел визуализировать только структуры данных на указателях.
Было ещё несколько тулов: Algojammer для питона (а мы хотели плюсы, как наиболее популярный язык у олимпиадников) и разработанный в 1994 году тул Lens. Последний, судя по описанию, делал почти то, что нужно, но, к сожалению, создавался под Sun OS 4.1.3 (операционную систему родом из 1992 года). Так что, несмотря на наличие исходников, было решено не тратить время на эту сомнительную археологию.
Итак, после некоторого исследования было установлено, что тула, который бы делал ровно то, чего нам хотелось, и при этом работал бы на современных машинах, в природе пока нет.
Определение функциональности
Вторым шагом нужно было доказать, что это задача достаточно сложная, но выполнимая. Для этого требовалось предложить что-то более конкретное, чем «хочу, чтобы была красивая картинка, и чтобы из неё всё сразу стало понятно».
В этом проекте мы решили сконцентрироваться на визуализации только графов: существует достаточно много алгоритмов на графах, которые могут быть по-разному реализованы, и даже будучи суженной, задача всё ещё остается нетривиальной.
Также более-менее очевидно, что тул должен быть как-то интегрирован с отладчиком. Нам надо уметь просматривать значения переменных и выражений, и по этим значениям рисовать готовую картинку.
После этого нужно было придумать некий язык, позволяющий по текущему состоянию программы строить граф так, как мы захотим. Кроме самого графа нужно было предусмотреть возможность менять цвет вершин и рёбер, добавлять к ним произвольные надписи и изменять прочие свойства. Соответственно, первой идеей было:
Создание прототипа пользовательского интерфейса
Прототип пользовательского интерфейса я нарисовала в NinjaMock. Это требовалось для лучшего понимания, как интерфейс будет выглядеть с точки зрения пользователя, и какие действия ему потребуется произвести. Если бы возникли проблемы с прототипом, мы бы поняли, что есть какие-то логические нестыковки, и эту идею следует отбросить. Для верности я взяла несколько алгоритмов. На картинке ниже примеры того, как я представляла себе настройки визуализации DFS и алгоритма Флойда.
Выбор зависимостей
Для следующего шага нужно было понять, как именно это всё делать. В первую очередь, требовалась интеграция с отладчиком. Первое, что приходит в голову при слове «отладчик» — это gdb, но тогда пришлось бы создавать весь графический интерфейс с нуля, что действительно сложно сделать студенту за семестр. Вторая очевидная идея — сделать плагин к какой-нибудь существующей среде разработки. В качестве вариантов я рассматривала QTCreator, CLion и Visual Studio.
Вариант с CLion отбросили почти сразу, потому что у него, во-первых, закрытый исходный код, а во-вторых, всё очень плохо с документацией (а дополнительные сложности никому не нужны). QTCreator, в отличие от Visual Studio, кроссплатформенный и имеет открытый исходный код, и поэтому вначале мы решили остановиться на нём.
Оказалось, однако, что QTCreator плохо приспособлен для расширения при помощи плагинов. Первый шаг при создании плагина для QTCreator — это сборка из исходников. У меня это заняло полторы недели. В итоге я отправила два баг-репорта (вот и вот), касающиеся процесса сборки. Да, вот столько усилий было потрачено на сборку QTCreator только для того, чтобы обнаружить, что отладчик в QTCreator не имеет публичного API. Я вернулась к другому варианту, а именно к Visual Studio.
Разумеется, не предполагалось, что я буду заниматься визуализацией графов с нуля — для этого есть куча специальных библиотек. Самая знаменитая из них — Graphviz, и именно её мы и планировали вначале использовать. Но для плагина под Visual Studio логичнее было бы использовать библиотеку для C#, так как я собиралась писать именно на нём. Я немножко погуглила и нашла библиотеку MSAGL: она обладала всей требующейся функциональностью и имела простой и понятный интерфейс.
Proof-of-concept
Теперь, имея механизм для вычисления произвольных выражений с одной стороны и библиотеку для визуализации графов с другой, требовалось сделать прототип. Первый прототип был сделан для DFS, потом в качестве примеров были взяты алгоритм Диница, алгоритм Куна, поиск компонент двусвязности, Декартово дерево, СНМ. Я брала свои старые реализации этих алгоритмов с первого-второго курса, создавала новый плагин, в нём рисовала граф, соответствующий этой задаче (все имена переменных были захардкожены). Вот пример графа, который у меня получился для алгоритма Куна:
На этом графе текущие рёбра паросочетания показаны фиолетовым, текущая вершина dfs — красным, посещенные вершины — серым, ребра чередующейся цепи не из паросочетания — красным.
Я считала допустимым немного менять код алгоритма, чтобы было проще визуализировать. Например, в случае Декартового дерева оказалось, что проще складывать все созданные node’ы в вектор, чем обходить дерево внутри плагина.
В моих пробных плагинах происходило примерно следующее (если граф хранился как список смежности):
Конфигурация графа
В графе могут быть разные типы вершин и рёбер. Например, в случае поиска максимального паросочетания в двудольном графе каждая доля может индексироваться отдельно. Поэтому было введено понятие семейства для вершин и рёбер. Для каждого семейства индексация и все свойства определяются независимо. При этом ребра могут соединять вершины из разных семейств.
Свойства бывают самые разнообразные. Для вершин: лейбл, цвет заливки, цвет границы, ширина границы, форма, стиль границы (например, пунктир). Для рёбер: лейбл, цвет, ширина, стиль, ориентация (можно задать две стрелки — от начала в конец или наоборот; при этом могут быть две стрелки одновременно).
Важно, что каждый раз граф рисуется с нуля, и предыдущее состояние никак не учитывается. Это может быть проблемой, если граф динамически меняется в процессе алгоритма — вершины и рёбра могут резко менять своё положение, и тогда сложно понять, что происходит.
Подробное описание конфигурации графа можно почитать тут.
Пользовательский интерфейс
С интерфейсом я решила особо не заморачиваться. Основное окно с настройками (ToolWindow) содержит textarea для сериализованного в JSON конфига и список семейств вершин и рёбер. Каждому семейству соответствует своё окошко с настройками, и каждому свойству в семействе — ещё одно окошко (получается три уровня вложенности). Сам граф рисуется в отдельном окошке. Поместить его в ToolWindow не получилось, поэтому я отправила bug report разработчикам MSAGL, но мне ответили, что это не является целевым сценарием использования. Ещё один bug report был отправлен в Visual Studio, так как в дополнительных окошках с настройками иногда подвисали TextBox’ы.
Плагин
Для того, чтобы задать конфигурацию графа, плагин имеет пользовательский интерфейс и возможность (де)сериализации конфига в JSON. Общая схема взаимодействия всех компонент выглядит следующим образом:
Голубым показаны компоненты, которые существовали исходно, серым — которые создала я. При старте Visual Studio расширение инициализируется (здесь основной компонент обозначен как Main). Пользователь получает возможность задать конфигурацию через интерфейс. При каждом изменении контекста отладчика основной компонент получает уведомление. Если конфигурация определена и отлаживаемая программа выполняется, запускается GraphRenderer. Он получает на вход конфиг и при помощи отладчика строит по нему граф, который после этого отображается в специальном окошке.
Примеры
В итоге я создала инструмент, позволяющий визуализировать графовые алгоритмы и требующий небольших изменений в коде. Он был опробован на восьми различных задачах. Вот несколько получившихся картинок:
Алгоритм Форда-Беллмана: вершина, до которой мы считаем кратчайшие пути, обозначена домиком, текущее найденное кратчайшое расстояние для вершин равно d, красным обозначено ребро, вдоль которого проходит релаксация.
Анимация с DFS — красным показана текущая вершина, серым — вершины в стеке, зелёным — прочие посещённые вершины. Малиновые рёбра показывают направление обхода.
Больше примеров алгоритмов доступно тут
Защита НИРа
На защите НИРов студентам требуется за семь минут рассказать о своей работе за семестр. При этом, вне зависимости от того, была ли тема предложена в рамках презентации НИРов или студент нашёл её самостоятельно, требуется уметь отвечать обосновывать, почему тема проекта попадает под требования, описанные вначале. Обычно доклад строится следующим образом: сначала идёт мотивация, после этого — обзор аналогов, говорится про то, почему они нас не устраивают, потом формулируются цели и задачи, и дальше про каждую из задач рассказывается, как она была решена. В конце идёт слайд с результатами, где ещё раз говорится, что поставленная цель достигнута и все задачи решены.
Так как с мотивацией и обзором аналогов я определилась уже на начальном этапе, мне требовалось просто собрать всю информацию воедино и сжать до семи минут. В итоге мне это удалось, защита прошла гладко, за НИР мне поставили максимальный балл.