@lisabugx любая программа представляет из себя какой-то алгоритм

@avp, что скажешь про использование алгоритмов в работе с железками? :)

@lisabugx МК - это видимо микроконтроллер? А что такое олпрога, алгопрога? Я уже видимо, слишком старый, раз не знаю этих слов...

@MSDN.WhiteKnight МК - микроконтроллер, да. Олпрога - это олимпиадная прога. Это слово известно как раз в кругах школьников, занимающихся этой темой, поэтому нет, старость ещё не настигла так скоро)

@Grundy никаких особых алгоритмов. Мы занимаемся так называемым функциональным тестированием, т.е. проверяем, что все элементы чипа работают как задумано. Ну, конечно, иногда надо поломать голову, чтобы придумать, как подтвердить задуманную функциональность

@lisabugx олимпиадное программирование нигде не нужно

@Grundy чисто технически - да, но я всё-таки имею ввиду применение каких-то известных алгоритмов, на графы например или на строки ( Z-функция, КМП и т.п. )

@Grundy жаль(

@lisabugx зависит от задачи, большая часть алгоритмов уже имеет реализацию, причем оптимизированную

нет смысла вручную повторять

@Grundy ну понятно, что нет смысла вручную повторять ( хотя не всегда бывает так - на графы например бывает нужно реализовать алгос, реализация которого есть, но она, скажем, несовместима с представлением - алгос использует списки смежности, а прога матрицу ), но бывают же и конструктивные задачи?

@lisabugx _ реализация которого есть, но она, скажем, несовместима с представлением_ - как правильно есть несколько реализаций, ну и перевести из списка в матрицу проще чем разбираться с алгоритмом

@lisabugx конструктивность - слишком размытое понятие

@Grundy под конструктивностью имеется ввиду алгоритм, который ещё не придумали. В олимпиадах например бывают конструктивные задачи, где нужно самому придумать алгос. Там он как правило не особо сложный и решает какую-то узкую задачу.

@lisabugx тогда любая задача является конструктивной :)

@lisabugx а для чего на практике нужны графы? Я вот за 40+ лет ни разу их не использовал

@avp честно, я это и хотел спросить у старших, потому что сам так и не нашёл им применения

@Grundy ну получается так конечно) Но для решения одной задачи существует несколько алгоритмов, есть т.н. "наивные", которые для данной задачи не подходят ( я рассуждаю с точки зрения олимпиад, чтобы понятнее выразиться ), а есть нормальные, которые приходят в голову, если немного покумекать над задачей и придумать решение, которое лучше подходит под условия задачи ( скажем, считать не за квадрат, а за линию; в олимпиадах очень часто ограничение по времени очень мало - 1 с ).

@lisabugx абсолютно. Массивы и иногда связные списки, а деревья (ну, может кроме чего-то простого, что и деревом (где балансировка нужна) назвать стыдно) и графы ни разу

@avp ну почему в каких-нибудь поисках да бд под капотом деревьев много, просто как правило не важно как оно внутри работает :)

@lisabugx на практике, если что-то надо искать, обычно спасает сортировка

@avp графы максимум используются в картах каких-нибудь, но на этом их применение заканчивается ( известное мне по крайней мере ).

@lisabugx в олимпиадах слишком специфические задачи

@lisabugx так поиск путей же - в геймдеве почти все через них

@Grundy это да, они вообще не имеют отношения к реальной жизни - тем и интересны впрочем

@Grundy ну это один лишь дейкстра, если про поиск путей

@lisabugx ну это с какой стороны посмотреть

@lisabugx вообще нет

Дейкстра просто самый известный

да и простой довольно - но он не везде нужен

@Grundy СУБД я делал на первой работе (в начале 80-х) и до реализации полноценных деревьев мы не дошли

@Grundy ну я думаю есть алгосы проще него ( правда и менее эффективные; впрочем, они, в отличии от дейкстры, способны обрабатывать отрицательные веса в путях )

@lisabugx картами не занимался

@lisabugx эффективность слишком зависит от задачи и входных данных - если бы все было просто был только один Дейкстра

@Grundy ну возможно алгоритм для создания маршрутов для ботов - действительно конструктивная задача. Хотя тогда уж сюда можно приплести и bsp, если уж про игры зашёл разговор.

@lisabugx что за бсп?

@lisabugx наверняка они еще в разных САПР-ах должны быть. Но такие модули в сапрах тоже не писал

@Grundy BSP - Binary Space Partitioning - формат хранения ( вообще алгос так то ) карт, который впервые был применён в первом думе. Там его прикол был в том, что с его помощью можно было сильно оптимизировать рендер тайм, за счёт чего увеличивался фпс => машины тех времён тянули Doom и Quake ( к последнему это особенно относилось, поскольку было уже полноценное 3д )

@lisabugx так формат хранения или алгоритм?

единственное что - это всё графика, развлечение, а на действительно полезном человечеству деле этот алгос не применить.

@lisabugx это намного полезнее олимпиадного программирования :) да и практичнее

@Grundy честно, я не люблю ввязываться термионологию, но название намекает на то, что это алгос.

@lisabugx название может быть каким угодно ¯\_(ツ)_/¯

@Grundy ну практичнее только тем, что развлекает больше людей)

@lisabugx хотя бы развлекает :) в отличие от

@Grundy олпрога тоже развлекает, очень даже

@lisabugx неа.

@Grundy не всем она конечно нравится, но мне лично она приносит кайф

@lisabugx просто оно бесполезно, в то время как даже BSP - полезно

@Grundy BSP полезно для развлекательных целей пока-что. Только тот же Quake развлекает массового потребителя, а спортпрога - непосредственно заинтересованных в ней программистов. На самом деле заинтересованных гораздо больше, чем 0, хотя, безусловно, меньше, чем любителей отдохнуть после работы)

@lisabugx то что ты увидел применение в игре - не означает, что это только в игре применяется

@Grundy ну это я согласен, но какое есть применение где-то за играми?

> performing geometrical operations with shapes (constructive solid geometry) in CAD,[3] collision detection in robotics and 3D video games, ray tracing, virtual landscape simulation,[4] and other applications that involve the handling of complex spatial scenes

@Grundy ухты, но в кадах я если честно не видел применения. Хотя, в кады то я особо и не смотрел..

@lisabugx пользователь вполне может не знать какие алгоритмы применяются "за кадром"

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

@Grundy ну это понятно, но я и не гадал на кофейной гуще) Посмотрел в исходники, просто интересовался.

@MSDN.WhiteKnight тут суть в том - что оно уже реализовано :)

То же самое можно сказать и про всякие остальные алгоритмы из олимпиад. Оно не оторвано от жизни, просто сталкиваться с этим придется лишь в определеных узких сферах.

@MSDN.WhiteKnight ну там применяются самые простые на мой взгляд алгоритмы - Дейкстра ( возможно Беллман-Форд или ещё что-то ) и Форда-Фалкерсона ( для максимального потока ). Да и как уже сказали выше - это реализованно, а интересно прям узнать, приходилось ли самому реализовывать.

@lisabugx Мне нет. Но я и в олимпиадах не участвовал, так что много бы не нареализовывал.

@Grundy Ну, то, что нареализовано, кто-то должен поддерживать. Может lisabugx будет разработкой стандартной библиотеки какого-нибудь языка заниматься, тогда упражнения на алгоритмы не будут бесполезными.

Так что если есть желание и возможность участвовать в олимпиадах, это не повредит.

@MSDN.WhiteKnight тем более - это нареализованно сейчас, а в 80-х я не думаю, что было прям много реализаций алгоритмов. Уверен, среди стекеров есть те ( кроме @avp ), кто программировал ещё в 80-е, когда алгоритмы действительно нужны были, и их вероятно приходилось реализовывать вручную..

@MSDN.WhiteKnight но если я буду заниматься разработкой стандартной библиотеки - боюсь, что ей больше никто пользоваться не будет :p

Сейчас многое с открытым кодом, поэтому поучаствовать в разработке реального проекта стало реальнее. Вот кстати живой пример, как студент в стандартную библиотеку .NET пытается добавить какой-то хитрый алгоритм: github.com/dotnet/runtime/pull/71588 Правда пуллреквест закрыли из-за неактивности.

@MSDN.WhiteKnight не, они там написали что используют наработки в другом пулреквесте

github.com/dotnet/runtime/pull/71588#issuecomment-1504091527