Данный проект посвящен исследованию и разработке эффективного программного решения для определения общего числа возможных путей между заданными вершинами в ориентированном ациклическом графе (DAG). Особенное внимание уделяется анализу вычислительной сложности различных алгоритмов, включая динамическое программирование и топологическую сортировку, для выбора наиболее оптимального подхода. Программа позволит визуализировать граф и отображать найденные пути, что делает ее ценным инструментом для обучения и научных исследований. Будут рассмотрены практические применения алгоритмов на графах в различных областях, таких как анализ зависимостей, планирование задач и маршрутизация. Цель – создать детерминированный и масштабируемый инструмент для решения задачи подсчета путей.
Разработать программное средство, которое сможет точно и эффективно вычислять количество всех существующих путей между любой парой вершин в ориентированном ациклическом графе. Программа должна быть понятной и удобной в использовании, а также демонстрировать основные принципы работы алгоритмов на графах.
Готовая к использованию программа, позволяющая пользователю строить или загружать ориентированные ациклические графы, указывать начальную и конечную вершины, а затем получать точное число всех возможных путей между ними. Результаты работы программы будут сопровождаться наглядной визуализацией графа и, при необходимости, списком найденных путей.
Определение количества путей в ориентированных ациклических графах является классической задачей теории графов, имеющей важное значение в информатике и смежных областях. Неэффективные алгоритмы могут приводить к значительным временным затратам при обработке больших графов, что ограничивает их практическое применение.
Актуальность данной работы обусловлена повсеместным использованием ориентированных ациклических графов для моделирования различных процессов, таких как разработка программного обеспечения, планирование проектов, анализ зависимостей и управление рабочими процессами. Эффективное решение задачи подсчета путей необходимо для оптимизации и анализа этих процессов.
Основная цель проекта – создать и протестировать алгоритм, а также его программную реализацию, которая позволит эффективно и корректно подсчитывать общее количество путей в ориентированных ациклических графах. Мы стремимся достичь высокой производительности и точности вычислений, делая инструмент доступным для широкого круга пользователей.
Целевой аудиторией проекта являются студенты, изучающие алгоритмы и структуры данных, исследователи в области теории графов и информатики, а также разработчики, которым требуется решение для анализа графовых структур. Программа будет полезна для образовательных целей и решения практических задач, связанных с графами.
Для реализации проекта понадобятся персональный компьютер с установленной операционной системой, среда разработки Python, а также библиотеки для работы с графами (например, NetworkX) и создания графического интерфейса (например, Tkinter или PyQt).
Отвечает за глубокий анализ теоретических основ, выбор и адаптацию наиболее эффективного алгоритма для подсчета путей в DAG, а также за формальную доказательность корректности его работы.
Осуществляет непосредственную реализацию выбранного алгоритма на выбранном языке программирования, уделяя внимание чистоте кода, производительности и соблюдению стандартов кодирования.
Занимается проектированием и внедрением интуитивно понятного графического интерфейса, обеспечивая удобство взаимодействия пользователя с программой и наглядность представления данных.
Отвечает за систематическое тестирование всех компонентов программы, выявление и документирование ошибок, а также анализ производительности и корректности работы на разнообразных наборах данных.
Выполнил: ФИО
Руководитель: ФИО
