Как теория графов применяется в программировании?

Question

[Человек Паук]

Постоянно вижу, что, чтобы правильно понять основы программирования, нужно знать кучу разделов дискретной математики, в том числе вышеназванную теорию графов. Объясните, пожалуйста, новичку, зачем нужно изучать ее и как и где она применяется.

Comments

[Довольный Айтишникъ]

Что-то вы не то читаете, я вот ни теорию графов не знаю, ни дискретной математики и прекрасно справляюсь со своей работой, вполне успешно пишу как прикладное ПО так и системное. Все зависит от того, в какой области вы будете работать

[Adamos]

Высшая математика нужна для написания алгоритмов. Современные программисты сплошь и рядом используют готовые алгоритмы, написанные и отлаженные другими и собранные в библиотеки. Так что даже для решения NP-полной задачи при помощи boost::graph, глубоких знаний может не понадобиться. Только знакомство с терминологией. При этом работу, в которой подобные задачи придется решать, без опыта программирования - именно опыта, а не знания теорий - вы не найдете.

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

[longclaps]

Довольный Жизнью, вы так бахвалитесь своей неграмотностью, что даже интересно: чего такого системного вы написали?

Answer 1

[Сергей Горностаев]

Прежде всего хочу заметить, что львиная доля программистов не имеют непосредственно дел с теорией и математикой. Можно быть успешным профессионалом, так никогда и не написав собственной реализации алгоритма Дейкстры и даже не имея представления о том, как он работает. Но всё же стоит хотя бы поверхностно познакомится с графами, так как это одна из основных структур данных. Сфера их применения очень обширна, часто это алгоритмы поиска решений - кратчайшего пути по маршруту, эффективного расположения дорожек на схеме, победной игровой стратегии и т.п. Реальный пример использования графов - это sea-of-nodes JIT-компилятора. JIT-компилятор строит граф потока данных и граф потока выполнения, в которых узлы - это инструкции программы, а рёбра - это порядок вызова инструкций и порядок присвоения данных переменным, потом ищет способы этот граф оптимизировать и по оптимизированному графу генерирует бинарный код.

int average(int a, int b) {
  return (a + b) / 2;
}

Answer 2

[Nurbol Suleimenov]

Человек Паук, для новичка программиста при обучении основ программирования в теории графов нет необходимости. Это я Вам говорю, как дипломированный математик прикладник с опытом работы в индустрии разработки ПО.

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

Для новичков, рекомендую "потреблять легкую пищу" при обучении. Основы алгоритмов, методологии программирования (хотя бы императивный подход и ООП), практические навыки работы с инструментами программистов (tooling: IDE, линтеры, VCS, инструменты для сборки и/или упаковщики), технологии (http, ajax, сериализация, ...), ...

Объясните, пожалуйста, новичку, зачем нужно изучать ее и как и где она применяется.

На практике, много где применяется:

1. Не понимая основ графов, можно запросто запутаться и испортить репозитории в git. Точно так же понадобится для анализа дерева зависимостей и разрешения проблем связанных с ним (смотри).
   
2. При отладке программ и профилировании зачастую приходится смотреть AST.
   
3. Нахождение путей, определение цикличностей и т.д. понадобятся, когда Ваши данные хорошо подходят для представления в качестве графов. К примеру социальные сети, GPS навигация, множество абстракции в компьютерных играх и т.д.
   

Answer 3

[Dmitri Sinitsa]

Ну, например, чтобы правильно ответить на собеседовании. :)
Многие компании спрашивают это хотя бы на каком-то базовом уровне.
Вообще, иногда спрашивают классические задачки из Computer Science.
Ну или чтобы успешно выступать на олимпиадах - там это сплошь и рядом.

Пример, который был бы наиболее близок к большенству разработчиков, с чем они сталкиваются каждый день - сборщик зависимостей (package manager, bundler или как угодно называйте) перед компиляцией/запуском.
Идёт построение т.н DAG - https://en.wikipedia.org/wiki/Directed_acyclic_graph , чтобы не было петель.

Answer 4

[Дмитрий Ковальский]

https://habr.com/post/65367/ 30 секунд поисков по запросу "теория графов в программировании". Там кратенько есть применение.

Answer 5

[Xilian]

Да везде. От построений маршрутов в навигаторов и генерации уровней в играх до расчета себестоимости в той-же 1С.

Answer 6

[zzzzzzzzzzzzz]

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