LVV>>Но полезно знать алгебру, вероятности, графы — это по-любому.
BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
Полезная абстракция.
Да и в алгоритмах обязательно читаются алгоритмы на графах.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>>>Но полезно знать алгебру, вероятности, графы — это по-любому. BFE>>Зачем графы? LVV>Полезная абстракция.
С этим не поспоришь.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
BFE>>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>>Так математика как раз и делает неявные структуры явными, BFE>>Но это ничего не даёт на практике. EP>Именно что даёт.
Что именно?
EP>>>что упрощает коммуникацию и аккумулирование знаний. BFE>>Да, разумеется, только вот я не помню, что бы кто-то говорил нечто вроде: BFE>>"образование цикла внутри графа построенного на смарт указателях привёло к утечке памяти". EP>Именно так и говорят — пруф
:
Ладно, здесь я не прав. Раз графы преподают, значит они такие слова будут использоваться.
BFE>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>А как же например вездесущие деревья?
Деревья — это частный случай, который намного проще.
EP>Или например односвязные списки
А список проще дерева.
EP>и генератор псевдослучайных чисел?
Причём тут генератор псевдослучайных чисел?
EP>Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity
И что это даёт на практике?
EP>Например сортировка часто используется? А там те самые графы
.
И такая реализация где-то используется?
BFE>>Но и этот граф, опять же, присутствует в неявном виде. EP>Да не важно в каком виде он выражен в коде.
Чаще всего тот граф, о котором идёт речь, воображаемый и явно никак не присутствует в коде.
EP>Это не лишает его математических свойств, применимости алгоритмов и их характеристик.
Математические свойства, конечно, остаётся, а вот насчёт алгоритмов есть большие сомнения.
EP> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий.
Что это такое — неявный граф?
EP>>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач. EP>Да например те же вездесущие социальные сети, там графы в полный рост.
Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые. Исключение — это когда какие-нибудь студенты проводят аналитическую работу, а на практике работа с такими графами сводится к работе со списком друзей.
BFE>>>>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню. EP>>>Это вообще ни разу не аргумент и не оправдание. В стандартной библиотеке очень много чего нет, но это означает что нужно знать только то что в неё включено, очевидно же BFE>>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. EP>Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет
Граф — это довольно простое построение и не распознать его не получится.
EP>Или тебе приходят разжёванные задачи вида "вот тут примени вектор, вот тут граф, вот тот обход в ширину"
Последние десять лет все задачи сводились примерно к таким: вот тут у нас есть несколько потоком изображений с камер, надо надо в реальном времени убрать с них все искажения вносимые оптикой. Или. Вот мы тут девайс с моторчиками спаяли, надо обеспечить плавность и согласованность их работы, написать графический интерфейс, удалённое управление, мониторинг, обеспечить нескольких режимов ассистирования, какие нужны — спросишь у операторов.
BFE>>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. EP>И что с того что реже чем массив? Массив например используется реже чем целые числа
Ага. А целое число — это такой вырожденный граф состоящий из одной вершины.
EP>Да даже если допустить что графы встречаются хотя бы в 2% задач — этого уже с головой достаточно для того чтобы их изучить хотя бы на базовом уровне, так как рано или поздно такая задача обязательно попадётся.
У меня такое впечатление, что как человек взявший в руки молоток во всём видит гвозди, так и человеку изучившему теорию графов во всем мерещатся графы.
Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика".
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, Evgeny.Panasyuk, Вы писали:
BFE>>>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>>>Так математика как раз и делает неявные структуры явными, BFE>>>Но это ничего не даёт на практике. EP>>Именно что даёт. BFE>Что именно?
то же, что дает любое обобщенное знание — за частностями становится видна общая структура, которая позволяет "экономить мышление" (размышлять по дедукции).
вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
Здравствуйте, B0FEE664, Вы писали:
BFE>>>>>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде. EP>>>>Так математика как раз и делает неявные структуры явными, BFE>>>Но это ничего не даёт на практике. EP>>Именно что даёт. BFE>Что именно?
Даёт понимание структуры, даёт целый набор готовых математических свойств и алгоритмов.
BFE>>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>>А как же например вездесущие деревья? BFE>Деревья — это частный случай, который намного проще.
Тем не менее, это широкий раздел теории графов.
EP>>Или например односвязные списки BFE>А список проще дерева.
Это смотря как посмотреть. Список может иметь цикл, а дерево — нет
EP>>и генератор псевдослучайных чисел? BFE>Причём тут генератор псевдослучайных чисел?
При том что переходы между seed'ами образуют графы аналогичные графам односвязных списков. И для определения циклов в обоих случаях используются одинаковый алгоритм.
EP>>Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity BFE>И что это даёт на практике?
Метрика сложности кода. Позволяет найти код с запашком в готовом проекте, либо автоматическая верификация нового.
EP>>Например сортировка часто используется? А там те самые графы
Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде.
BFE>>>Но и этот граф, опять же, присутствует в неявном виде. EP>>Да не важно в каком виде он выражен в коде. BFE>Чаще всего тот граф, о котором идёт речь, воображаемый и явно никак не присутствует в коде.
Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение
EP>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>Что это такое — неявный граф?
Здесь это граф который присутствует в задаче, но который ты ещё не распознал.
EP>>>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>>>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач. EP>>Да например те же вездесущие социальные сети, там графы в полный рост. BFE>Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые.
Ага, ещё друзей друзей, ещё поиск пути между двумя людьми
BFE>>>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. EP>>Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет BFE>Граф — это довольно простое построение и не распознать его не получится.
Чтобы распознать его, нужно как минимум знать что это такое.
Ты выше не распознал граф в генераторе псевдослучайных чисел
Да и вообще, далеко не всегда лежит на поверхности
EP>>Или тебе приходят разжёванные задачи вида "вот тут примени вектор, вот тут граф, вот тот обход в ширину" BFE>Последние десять лет все задачи сводились примерно к таким: вот тут у нас есть несколько потоком изображений с камер, надо надо в реальном времени убрать с них все искажения вносимые оптикой. Или. Вот мы тут девайс с моторчиками спаяли, надо обеспечить плавность и согласованность их работы, написать графический интерфейс, удалённое управление, мониторинг, обеспечить нескольких режимов ассистирования, какие нужны — спросишь у операторов.
У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации.
Более того, писал некоторые алгоритмы для обработки 3D-моделей, которые в том числе применимы и для изображений, так вот — там также возникают графы.
BFE>>>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. EP>>И что с того что реже чем массив? Массив например используется реже чем целые числа BFE>Ага. А целое число — это такой вырожденный граф состоящий из одной вершины.
Я этого не говорил. Мой поинт в том, что если графы применимы реже массивов, или что их нет в стандартной библиотеке (хотя внутри они таки используются) — из этого никак не следует что их не нужно знать программисту. Точнее хорошему программисту.
EP>>Да даже если допустить что графы встречаются хотя бы в 2% задач — этого уже с головой достаточно для того чтобы их изучить хотя бы на базовом уровне, так как рано или поздно такая задача обязательно попадётся. BFE>У меня такое впечатление, что как человек взявший в руки молоток во всём видит гвозди, так и человеку изучившему теорию графов во всем мерещатся графы.
Вот только помимо графов есть много других рабочих инструментов математических структур, которые "мерещатся" в том числе. Это позволяет смотреть на задачу с множества разных сторон, вычленяя отдельные структуры из оригинального ансамбля — тут графы, тут симплексы, тут моноид, тут векторное пространство и т.п.
BFE>Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика".
Ещё в компиляторах, системах сборки, пакетных менеджерах, да и вообще практически везде. А в остальном да, не используются
Граф это настолько базовая структура, считай связь между чем либо, что встречается повсеместно. Тут разве что басня Крылова на ум приходит про ГрафДуб
Здравствуйте, _hum_, Вы писали:
__> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
Каким тут боком графы? Ordering и классы эквивалентности — скорее концепции из теории множеств и бинарных отношений. Понять их лучше всего опять же из абстрактной алгебры, где полно примеров их применения.
Здравствуйте, _hum_, Вы писали:
__> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
Графы тут только как частное, это самостоятельная математическая тема. А прогеру для упомянутой экономии мышления или, если правильней сказать, времени, достаточно изучить доку по либе.
Здравствуйте, andyp, Вы писали:
A>Здравствуйте, ferz1, Вы писали:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
A>Минимум хорошо бы алгебру (не ту, что в школе, а общую алгебру) знать. Остальное предметная область диктует.
Интересно, где программист будет использовать общую алгебру и какие конкретно разделы этой науки ему пригодятся?
Математика программисту нужна только в отдельных предметных областях: 3d графика(аналитическая геометрия), обработка звука/видео(функциональный анализ), статистика, криптография. И разумеется, нужны графы/сортировки.
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Здравствуйте, lpd, Вы писали:
lpd>Интересно, где программист будет использовать общую алгебру и какие конкретно разделы этой науки ему пригодятся? lpd>Математика программисту нужна только в отдельных предметных областях: 3d графика(аналитическая геометрия), обработка звука/видео(функциональный анализ), статистика, криптография. И разумеется, нужны графы/сортировки.
1.Ниже по ветке, например, рассматривали ограничения на типы, с которыми стандартная библиотека работает.
2.Аналогично, неплохо бы представлять на какие объекты можно бы натравить, скажем, алгоритм Евклида. Тут уже понимание того, что такое кольцо нужно. Ну кто ж из программистов НОД не искал.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Даёт понимание структуры, даёт целый набор готовых математических свойств и алгоритмов.
Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде.
BFE>>>>Единственное, что приходит на ум, это граф переходов конечного автомата. EP>>>А как же например вездесущие деревья? BFE>>Деревья — это частный случай, который намного проще. EP>Тем не менее, это широкий раздел теории графов.
Когда я говорю про графы, я не говорю про деревья.
EP>Это смотря как посмотреть. Список может иметь цикл, а дерево — нет
Что-то я не припомню, чтобы я когда-то использовал список с циклом внутри... Наличие цикла внутри списка свидетельствует об ошибке, так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом...
EP>>>и генератор псевдослучайных чисел? BFE>>Причём тут генератор псевдослучайных чисел? EP>При том что переходы между seed'ами образуют графы аналогичные графам односвязных списков. И для определения циклов в обоих случаях используются одинаковый алгоритм.
И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов?
EP>Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде.
Ну, а я о чём? Вы мне в явном виде граф покажите.
BFE>>>>Но и этот граф, опять же, присутствует в неявном виде. EP>>>Да не важно в каком виде он выражен в коде. BFE>>Чаще всего тот граф, о котором идёт речь, воображаемый и явно никак не присутствует в коде. EP>Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение
Для многих алгоритмов распараллеливания вычислений ассоциативность имеет важное практическое значение. Я не вижу тут аналогии.
EP>>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>>Что это такое — неявный граф? EP>Здесь это граф который присутствует в задаче, но который ты ещё не распознал.
Т.е. воображаемый граф.
EP>>>>>Естественно можно использовать что-то неявно, не подозревая об опыте и знаниях накопленных столетиями. Но зачем заново пытаться переоткрыть то, что давно изучено? NIH? BFE>>>>Я не о том, чтобы что-то переоткрывать, а о том, что графы вообще не используются в подавляющем большинстве задач. EP>>>Да например те же вездесущие социальные сети, там графы в полный рост. BFE>>Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые. EP>Ну так услышь: https://developers.facebook.com/docs/graph-api/overview
Ну и где там граф? Там нельзя получить граф, как структуру. Нельзя запустить поиск по графу, если я правильно понимаю.
BFE>>а на практике работа с такими графами сводится к работе со списком друзей. EP>Ага, ещё друзей друзей, ещё поиск пути между двумя людьми
С какой практической целью пользователю мог бы понадобится поиск такого пути?
BFE>>>>Как и любое теоретическое знание, знание графов пользу принести может. Однако, на практике знание графов нужно только если этого требует задача. EP>>>Так не зная графов, не умея их распознавать, не получится и понять требует ли их задача или нет BFE>>Граф — это довольно простое построение и не распознать его не получится. EP>Чтобы распознать его, нужно как минимум знать что это такое.
Если бы это было так, граф бы никогда не был придуман.
EP>Ты выше не распознал граф в генераторе псевдослучайных чисел
Покажите мне в коде генератора граф переходов.
EP>Да и вообще, далеко не всегда лежит на поверхности
Эти графы, о которых вы пишите — они ведь в голове, а не в коде. С вашей точки зрения любая функция над целыми числами — это граф, любая программа — это граф, любая последовательность символов — это граф... Алгоритмы сжатия данных без потерь — это построение графа из последовательности символов и его перенумерация, т.е. преобразования одного графа в другой граф... А поиск ошибки в программе это — это поиск неверного перехода в графе состояний программы... А программирование — это всего лишь создание графа переходов между различными состояниями в записанными в памяти машины. Это вы хотите сказать?
EP>У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации.
Понимаете... Иногда патерны применяются в коде исключительно потому, что программист о них знает.
EP>Более того, писал некоторые алгоритмы для обработки 3D-моделей, которые в том числе применимы и для изображений, так вот — там также возникают графы.
Графы при обработке 3D моделей? В коде? Для чего?
BFE>>>>Количество задач в которых используются графы существенно меньше, чем, скажем, задач, где используется массив. EP>>>И что с того что реже чем массив? Массив например используется реже чем целые числа BFE>>Ага. А целое число — это такой вырожденный граф состоящий из одной вершины. EP>Я этого не говорил.
Это сарказм.
EP>Мой поинт в том, что если графы применимы реже массивов, или что их нет в стандартной библиотеке (хотя внутри они таки используются) — из этого никак не следует что их не нужно знать программисту. Точнее хорошему программисту.
Хорошему программисту много чего надо знать, но это не значит, что всё что он знает ему обязательно пригодиться. На практике один из 10
разворот списка написать может, а вы тут про графы вещаете...
EP>Вот только помимо графов есть много других рабочих инструментов математических структур, которые "мерещатся" в том числе. Это позволяет смотреть на задачу с множества разных сторон, вычленяя отдельные структуры из оригинального ансамбля — тут графы, тут симплексы, тут моноид, тут векторное пространство и т.п.
Уверяю вас, на свете есть много программистов, которые даже не слышали "этих ваших страшных слов". И все они что-то пишут, зарплату получают...
Это мне напоминает одну реальную историю: "-Товарищ преподаватель, вот вы говорите что у вектора есть длина. А толщина у вектора есть?".
BFE>>Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика". EP>Ещё в компиляторах, системах сборки, пакетных менеджерах, да и вообще практически везде. А в остальном да, не используются
А они там точно в коде присутствуют?
EP>Граф это настолько базовая структура, считай связь между чем либо, что встречается повсеместно. Тут разве что басня Крылова на ум приходит про ГрафДуб
Ага. Вы ещё теорему Котельникова спрашивайте при приёме на работу web-программиста.
Здравствуйте, andyp, Вы писали:
A>Здравствуйте, _hum_, Вы писали:
__>> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
A>Каким тут боком графы? Ordering и классы эквивалентности — скорее концепции из теории множеств и бинарных отношений. Понять их лучше всего опять же из абстрактной алгебры, где полно примеров их применения.
ну, так граф и есть множество с бинарным отношением а тот факт, что он имеет графическое представление, позволяет легко воспринимать такие сложные в чисто сухом алгебраическом изложении вещи, как типы отношений (антисимметричность, рефлексивность и т.п.), понятия наподобие транзитивности, классы эквивалентности и т.п.
например, строгий порядок — это транзитивно замкнутый направленный ациклический граф [легко в голове нарисовать картинку], слабый порядок — связный как ненаправленный транзитивно замкнутый направленный граф (который после факторизации по компонентам связности даст линейный список [отсюда понятно его использование при сортировке]) и т.д.
Здравствуйте, B0FEE664, Вы писали:
EP>>Даёт понимание структуры, даёт целый набор готовых математических свойств и алгоритмов. BFE>Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде.
Например Эйлерова характеристика, а из алгоритмов чаще всего обход
EP>>Тем не менее, это широкий раздел теории графов. BFE>Когда я говорю про графы, я не говорю про деревья.
Вот только непонятно почему, это та же самая теория графов
BFE>Наличие цикла внутри списка свидетельствует об ошибке,
Не обязательно.
BFE>так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом...
Тем не менее это она и есть.
EP>>>>и генератор псевдослучайных чисел? BFE>>>Причём тут генератор псевдослучайных чисел? EP>>При том что переходы между seed'ами образуют графы аналогичные графам односвязных списков. И для определения циклов в обоих случаях используются одинаковый алгоритм. BFE>И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов?
Нет, я не хочу этого сказать.
Я хочу сказать что в генераторах псевдослучайных чисел структурно есть граф, и к нему применимы соответствующие алгоритмы. И выделение этой графовой структуры из общего ансамбля, помогает лучше понять суть вещей.
EP>>Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде. BFE>Ну, а я о чём? Вы мне в явном виде граф покажите.
Зачем именно в явном?
EP>>Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение BFE>Для многих алгоритмов распараллеливания вычислений ассоциативность имеет важное практическое значение. Я не вижу тут аналогии.
Аналогия в том что эта ассоциативность вообще в явном виде редко где встречается, что тем не менее не умоляет полезность знаний о ней.
Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%.
EP>>>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий. BFE>>>Что это такое — неявный граф? EP>>Здесь это граф который присутствует в задаче, но который ты ещё не распознал. BFE>Т.е. воображаемый граф.
И что с того что "воображаемый"? Это делает алгоритм поиска размера цикла не рабочим?
BFE>>>а на практике работа с такими графами сводится к работе со списком друзей. EP>>Ага, ещё друзей друзей, ещё поиск пути между двумя людьми BFE>С какой практической целью пользователю мог бы понадобится поиск такого пути?
Нужно достучаться до лично незнакомого но важного человека, это можно сделать через общих знакомых. Одна из популярных соц.сетей именно такой сценарий и предоставляет.
BFE>>>Граф — это довольно простое построение и не распознать его не получится. EP>>Чтобы распознать его, нужно как минимум знать что это такое. BFE>Если бы это было так, граф бы никогда не был придуман.
Нет, я не об этом. Переоткрыть граф и связанные свойства/алгоритмы — естественно возможно, хотя и трудоёмко.
Речь о том что ты не поймёшь что эту вновь открытую структуру люди уже столетиями называют "графом". Да и вообще непонятно зачем переотркывать то что давно известно, и имеет устоявшеюся терминологию.
EP>>Да и вообще, далеко не всегда лежит на поверхности BFE>Эти графы, о которых вы пишите — они ведь в голове, а не в коде.
Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого?
EP>>У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации. BFE>Понимаете... Иногда патерны применяются в коде исключительно потому, что программист о них знает.
Говори прямо, намекаешь на то что я их применял не по делу?
EP>>Более того, писал некоторые алгоритмы для обработки 3D-моделей, которые в том числе применимы и для изображений, так вот — там также возникают графы. BFE>Графы при обработке 3D моделей? В коде? Для чего?
Например для сжатия, как с потерями, так и без.
EP>>Мой поинт в том, что если графы применимы реже массивов, или что их нет в стандартной библиотеке (хотя внутри они таки используются) — из этого никак не следует что их не нужно знать программисту. Точнее хорошему программисту. BFE>Хорошему программисту много чего надо знать, но это не значит, что всё что он знает ему обязательно пригодиться.
разворот списка написать может, а вы тут про графы вещаете...
Так зачем равняться на них?
EP>>Вот только помимо графов есть много других рабочих инструментов математических структур, которые "мерещатся" в том числе. Это позволяет смотреть на задачу с множества разных сторон, вычленяя отдельные структуры из оригинального ансамбля — тут графы, тут симплексы, тут моноид, тут векторное пространство и т.п. BFE>Уверяю вас, на свете есть много программистов, которые даже не слышали "этих ваших страшных слов". И все они что-то пишут, зарплату получают...
Я знаю. Также есть много продавцов, водителей и т.п., и они точно также получают зарплату, при этом ничего не зная про упомянутые тобой массивы — и что с этого?
EP>>Ещё в компиляторах, системах сборки, пакетных менеджерах, да и вообще практически везде. А в остальном да, не используются BFE>А они там точно в коде присутствуют?
Где-то нет — и что с того? А где-то присутствуют https://en.wikipedia.org/wiki/Graph_coloring#Register_allocation
EP>>Граф это настолько базовая структура, считай связь между чем либо, что встречается повсеместно. Тут разве что басня Крылова на ум приходит про ГрафДуб BFE>Ага. Вы ещё теорему Котельникова спрашивайте при приёме на работу web-программиста.
Послушай, я не говорю что нужно знать всем, я говорю лишь что нужно знать хорошему программисту.
Для простейших кодерских задач а-ля "от забора до обеда" достаточно уровня техникума, а то и вовсе шести классов школы
Здравствуйте, smeeld, Вы писали:
S>Здравствуйте, _hum_, Вы писали:
__>> вот. например, c++ concepts: compare. для незнакомого с теорией графов будет дремучим лесом, что за странное "strict weak ordering relation", что за классы эквивалентности, как такое может быть, что два элемента нельзя сравнить?? и ему придется слепо следовать условия, которым должно удовлетворять compare, не понимая, что они означают.
S>Графы тут только как частное, это самостоятельная математическая тема. А прогеру для упомянутой экономии мышления или, если правильней сказать, времени, достаточно изучить доку по либе.
это когда у вас есть функция CompareCandidate(), и нужно проверить, удовлетворяет она требуемому условию на Compare() или нет. на практике же больше встречаются обратные задачи — нужно самому построить подходящую функцию. и вот тут-то как раз и проявляется выгода понимания сути всех этих вещей и эффект "экономии времени".
ребята, не спорьте на пустом месте. каждый из вас прав, просто B0FEE664 ведет речь про программирование в области embedded system (в которой затребованы в первую очередь алгоритмы работы с физическими устройствами), а Evgeny.Panasyuk в области, предполагающей несколько более высокий уровень абстрактного программирования.
Здравствуйте, _hum_, Вы писали:
__>ребята, не спорьте на пустом месте. каждый из вас прав, просто B0FEE664 ведет речь про программирование в области embedded system (в которой затребованы в первую очередь алгоритмы работы с физическими устройствами), а Evgeny.Panasyuk в области, предполагающей несколько более высокий уровень абстрактного программирования.
Мне показалось, что все несколько не так.
B0FEE664 полагает, что из осознания того, что список это граф, и "целое число — это такой вырожденный граф состоящий из одной вершины" практической пользы не извлечь. И даже к деревьям лучше применять алгоритмы разработанные именно для них, а не старательно вспоминать теорию графов завидев дерево.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Например Эйлерова характеристика, а из алгоритмов чаще всего обход
Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов?
EP>>>Тем не менее, это широкий раздел теории графов. BFE>>Когда я говорю про графы, я не говорю про деревья. EP>Вот только непонятно почему, это та же самая теория графов
Дерево много проще графа, встречается повсеместно и интуитивно понятно для человека. Вот даже интерфейс этого форума — дерево.
BFE>>Наличие цикла внутри списка свидетельствует об ошибке, EP>Не обязательно.
Иначе это уже не список.
BFE>>так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом... EP>Тем не менее это она и есть.
Ну, это всё-таки был тестовый код, а не продакшен.
EP>>Речь не про реализацию, а про то что даже при сортировке возникают те самые графы, пусть и в неявном виде. BFE>>Ну, а я о чём? Вы мне в явном виде граф покажите. EP>Зачем именно в явном?
В неявном виде можно много чего где найти...
EP>>>Например ассоциативность тоже в коде явно редко присутствует, тем не менее имеет вполне практическое значение BFE>>Для многих алгоритмов распараллеливания вычислений ассоциативность имеет важное практическое значение. Я не вижу тут аналогии. EP>Аналогия в том что эта ассоциативность вообще в явном виде редко где встречается, что тем не менее не умоляет полезность знаний о ней. EP>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%.
Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён.
EP>Нужно достучаться до лично незнакомого но важного человека, это можно сделать через общих знакомых. Одна из популярных соц.сетей именно такой сценарий и предоставляет.
Ну, ок. Пусть будет ещё и такое применение.
BFE>>Эти графы, о которых вы пишите — они ведь в голове, а не в коде. EP>Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого?
Из этого я делаю такой вывод: что даже не зная, что такое граф, человек может запрограммировать верное решение.
EP>>>У меня задачи в основном связанны с CAE, CAD, 3D — и частенько возникают графы в реализации. BFE>>Понимаете... Иногда патерны применяются в коде исключительно потому, что программист о них знает. EP>Говори прямо, намекаешь на то что я их применял не по делу?
Нет. Я хочу сказать, что одни и те же задачи имеют несколько способов решения. Из всех способов решений человек выбирает тот, которым он лучше владеет. И это правильно.
BFE>>На практике один из 10
разворот списка написать может, а вы тут про графы вещаете... EP>Так зачем равняться на них? EP>Я знаю. Также есть много продавцов, водителей и т.п., и они точно также получают зарплату, при этом ничего не зная про упомянутые тобой массивы — и что с этого? EP>Послушай, я не говорю что нужно знать всем, я говорю лишь что нужно знать хорошему программисту. EP>Для простейших кодерских задач а-ля "от забора до обеда" достаточно уровня техникума, а то и вовсе шести классов школы
Вот приходит к нам ferz1 и спрашивает: "какой должен быть минимальный уровень знания математики?"
А вы ему сразу: без знания теории графов, алгебры и тории вероятности даже не пытайся...
Здравствуйте, B0FEE664, Вы писали:
EP>>Например Эйлерова характеристика, а из алгоритмов чаще всего обход BFE>Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов?
Да, с маркировкой посещённых.
BFE>>>Наличие цикла внутри списка свидетельствует об ошибке, EP>>Не обязательно. BFE>Иначе это уже не список.
Почему? Например кольцевой список
BFE>>>так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом... EP>>Тем не менее это она и есть. BFE>Ну, это всё-таки был тестовый код, а не продакшен.
А какая разница? Вот тебе пригодилось для решения вполне практичной задачи
EP>>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%. BFE>Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён.
1. Порядок сложения определён. Более того, для плавающей точки изменение порядка даст разный результат, так как такие операции как раз не ассоциативны.
2. Я про другую ассоциативность — про свойство бинарной операции, а не про порядок вычисления в отсутствии скобок.
BFE>>>Эти графы, о которых вы пишите — они ведь в голове, а не в коде. EP>>Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого? BFE>Из этого я делаю такой вывод: что даже не зная, что такое граф, человек может запрограммировать верное решение.
Во-первых, этот вывод никак не является следствием из обозначенных предпосылок. То что где-то например граф зашит в алгоритме неявно, совсем не означает что до этого алгоритма додумались без теории графов.
Во-вторых, я не спорю с тем что можно до чего-то додуматься самостоятельно. Вот только изучить готовое проще, и потом тратить силы на реально неизведанное, чем постоянно переоткрывать колесо. Тяжело в учении легко в бою.
Я например лет в 12-13 налисапедил рекурсивный калькулятор арифметических выражений, без всяких знаний о парсерах, токенизаторах, грамматиках и т.п. Но со всеми этими знаниями было бы и проще и быстрее и качественнее.
BFE>Нет. Я хочу сказать, что одни и те же задачи имеют несколько способов решения. Из всех способов решений человек выбирает тот, которым он лучше владеет. И это правильно.
Лучше знать как можно больше способов, чтобы было из чего выбирать.
EP>>Послушай, я не говорю что нужно знать всем, я говорю лишь что нужно знать хорошему программисту. EP>>Для простейших кодерских задач а-ля "от забора до обеда" достаточно уровня техникума, а то и вовсе шести классов школы BFE>Вот приходит к нам ferz1 и спрашивает: "какой должен быть минимальный уровень знания математики?" BFE>А вы ему сразу: без знания теории графов, алгебры и тории вероятности даже не пытайся...
Эта ветка началась совсем с другого:
F>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
LVV>Зависит от решаемых задач.
LVV>Но полезно знать алгебру, вероятности, графы — это по-любому.
Здравствуйте, pagid, Вы писали:
P>"целое число — это такой вырожденный граф состоящий из одной вершины"
Я этого не говорил, это был его гротеск.
P>И даже к деревьям лучше применять алгоритмы разработанные именно для них, а не старательно вспоминать теорию графов завидев дерево.
Я не говорил что для деревьев нужно применять не деревянные алгоритмы, там где есть специальные деревянные.
Я говорю что деревья это один из подвидов графов, в том числе изучаемый в теории графов.
а тот факт, что он имеет графическое представление, позволяет легко воспринимать такие сложные в чисто сухом алгебраическом изложении вещи, как типы отношений (антисимметричность, рефлексивность и т.п.), понятия наподобие транзитивности, классы эквивалентности и т.п.
