Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>>>Например Эйлерова характеристика, а из алгоритмов чаще всего обход
BFE>>Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов?
EP>Да, с маркировкой посещённых.
А с какой целью был обход графа? Что нужно было найти?

BFE>>>>Наличие цикла внутри списка свидетельствует об ошибке,
EP>>>Не обязательно.
BFE>>Иначе это уже не список.
EP>Почему? Например кольцевой список
Например потому, что std::find к нему применить прямо не получится.

BFE>>Ну, это всё-таки был тестовый код, а не продакшен.
EP>А какая разница? Вот тебе пригодилось для решения вполне практичной задачи
Разница в оптимизации. Для тестового кода она не нужна.

EP>>>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%.
BFE>>Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён.
EP>1. Порядок сложения определён. Более того, для плавающей точки изменение порядка даст разный результат, так как такие операции как раз не ассоциативны.
Насколько я помню стандарт, порядок не определён до тех пор, пока он не влияет на результат. Точно, см в стандарте 1.9/9

EP>2. Я про другую ассоциативность — про свойство бинарной операции, а не про порядок вычисления в отсутствии скобок.

Note: Operators can be regrouped according to the usual mathematical rules only where the operators
really are associative or commutative.

BFE>>>>Эти графы, о которых вы пишите — они ведь в голове, а не в коде.
EP>>>Не все, но не суть, допустим что все. И какой вывод ты делаешь из этого?
BFE>>Из этого я делаю такой вывод: что даже не зная, что такое граф, человек может запрограммировать верное решение.
EP>Во-первых, этот вывод никак не является следствием из обозначенных предпосылок.
Согласен, следствием не является. Но и вопрос был не о следствии, а о выводе.

EP>То что где-то например граф зашит в алгоритме неявно, совсем не означает что до этого алгоритма додумались без теории графов.
Но и об обратном это так же не говорит.

EP>Лучше знать как можно больше способов, чтобы было из чего выбирать.
Ага. Я так во вторник сидел и три часа выбирал, чем лучше разобрать строку вида 'id=3 ssid="FreeBox" auth_fail=20'
То ли std::regex, то ли boost::tokenizer, то ли boost::xpressive, то ли boost::spirit, то ли руками...


EP>Эта ветка началась совсем с другого:
EP>

F>>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
LVV>>Зависит от решаемых задач.
LVV>>Но полезно знать алгебру, вероятности, графы — это по-любому.

"графы — это по-любому" как понимать?
Я понял — в обязательном порядке. Хотя, конечно, 'никак не знать' — это тоже "по-любому"...

Здравствуйте, B0FEE664, Вы писали:

BFE>>>Однако! Бывает же... Что, настоящий обход дерева с запоминанием посещённых узлов?
EP>>Да, с маркировкой посещённых.
BFE>А с какой целью был обход графа? Что нужно было найти?

Компоненты связности.

BFE>>>Иначе это уже не список.
EP>>Почему? Например кольцевой список
BFE>Например потому, что std::find к нему применить прямо не получится.

Это не "не список", а "не диапазон по определению STL". Но речи о том что это будет диапазоном STL — не было.

EP>>>>Ты же, как я понимаю, пытаешься подвести к тому что графы в явном виде редки, и поэтому не нужны. Вот тут с ассоциативностью аналогия 100%.
BFE>>>Ассоциативность в С++ встречается в каждом выражении, где есть через аргумент идущие одинаковые знаки a+b+c. Порядок сложения не определён.
EP>>1. Порядок сложения определён. Более того, для плавающей точки изменение порядка даст разный результат, так как такие операции как раз не ассоциативны.
BFE>Насколько я помню стандарт, порядок не определён до тех пор, пока он не влияет на результат. Точно, см в стандарте 1.9/9

Это только для встроенных ассоциативных типов

http://eel.is/c++draft/intro.execution#footnote-7
Overloaded operators are never assumed to be associative or commutative.

EP>>2. Я про другую ассоциативность — про свойство бинарной операции, а не про порядок вычисления в отсутствии скобок.
BFE>

BFE>Note: Operators can be regrouped according to the usual mathematical rules only where the operators
BFE>really are associative or commutative.
BFE>

BFE>

Я выше сноску процитировал. В любом случае, перегруппировка скажем сложения unsigned'ов на результат не влияет.

И повторюсь, я не про ту ассоциативность которая левая или правая, а про ту которая позволяет скобки переставлять без изменения результата. И вот она в явном виде в коде практически не выражается, при этом используется неявно (без выражения непосредственно в коде) например при параллельной редукции. Собственно это пример к моему исходному поинту о том, что даже если что-то в коде не выражается явно, это не означает что эти знания не полезны и не нужны.

EP>>То что где-то например граф зашит в алгоритме неявно, совсем не означает что до этого алгоритма додумались без теории графов.
BFE>Но и об обратном это так же не говорит.

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

EP>>

F>>>>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
LVV>>>Зависит от решаемых задач.
LVV>>>Но полезно знать алгебру, вероятности, графы — это по-любому.

BFE>"графы — это по-любому" как понимать?
BFE>Я понял — в обязательном порядке. Хотя, конечно, 'никак не знать' — это тоже "по-любому"...

Я это распарсил как "полезно знать (x,y,z) — это по-любому". Но это уже вопрос толкования, и не суть важно.

Мои основные тезисы:
— обозначенные знания не являются жёстким требованием ко всем программистам. Да, без них получится создавать реальный код, решающий некоторые реальные задачи, и получать за это реальное вознаграждение.
— для тех кто хочет стать хорошим программистом — эти знания обязательны.
— даже если допустить что эти знания являются балластом и на практике не нужны — они всё равно проверяются на некоторых реальных собеседованиях, что немаловажно.
— программирование по большей части это математическая активность — так как происходит оперирование абстрактными объектами, идеями и структурами. Более того — это строгая (rigour) математическая активность, так как нет возможности пропустить "очевидные" этапы и шаги — нужно закодировать всё — от самых низших уровней до высших. ЕМНИП, подобный тезис был у Александра Степанова. С этой позиции заявления вида "программистам математика не нужна" нелепы.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Я этого не говорил, это был его гротеск.
Разумеется, но гротеск мне показался уместным и по существу разговора.

EP>Я не говорил что для деревьев нужно применять не деревянные алгоритмы, там где есть специальные деревянные.
А специальные деревянные алгоритмы это порождение теории графов, и лучше не будем путать?

EP>Я говорю что деревья это один из подвидов графов, в том числе изучаемый в теории графов.
Так это годится только для вводной лекции — "посмотрите какие еще графы бывают"

EP>>Да например те же вездесущие социальные сети, там графы в полный рост.
S>Там уже полная бигдата, со всем своим хозяйством, которая уже гораздо обширней чем теория графов, и которая к математике не относится.
Оля-ля!!! Бигдата — это и статистика, и классификация, и кластеризация. Да еще на нечеткостях...

BFE>>>Единственное, что приходит на ум, это граф переходов конечного автомата.
EP>>А как же например вездесущие деревья?
BFE>Деревья — это частный случай, который намного проще.
Не. Зависит от графа и дерева...
В-деревья, АВЛ-деревья — покруче некоторых графов будут...

EP>>Да даже сложность кода меряют через характеристику графа https://en.wikipedia.org/wiki/Cyclomatic_complexity
BFE>И что это даёт на практике?
А это признак того, что надо рефакторинг начинать.
Пока код вообще в лабиринт не превратился.

EP>> И чем раньше ты распознаешь этот неявный граф, тем раньше расширишь понимание задачи и получишь дополнительный инструментарий.
BFE>Что это такое — неявный граф?
Это значит, отсутствует представление графа в виде структуры данных, но свойства его имеются в наличии.
BFE>Собственно единственное реальное применение графа, которое вы указали — это GC. Вероятно графы ещё используются в навигаторах и, быть может, в моделировании электрических схем. В остальных областях графы используются разве что для рисования красивых картинок под грифом "аналитика".
Читай книгу Касьянова-Емельянова о применении графов в программировании.
Они несколько штук написали про это.
Весь анализ кода построен на теории графов.
То есть, компиляторы в полный рост графы используют.
Иногда — в явном виде, чаще — в неявном.

Вот вам реальная задача, которую у нас в Астрахани сейчас пишут.
Об автоматизации мобильных сотрудников — модное ныне направление.

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

Решать подобную задачу без обращения к графам — немыслимо...

Здравствуйте, LaptevVV, Вы писали:

LVV>Оля-ля!!! Бигдата — это и статистика, и классификация, и кластеризация. Да еще на нечеткостях...

Дык, а я о чём? Cоцсети сейчас-это и статистика, и кластеризация, и классификация.

Здравствуйте, LaptevVV, Вы писали:

LVV>Решать подобную задачу без обращения к графам — немыслимо...
Так это и есть классическая задача с использованием графов. Но даже взявшись её решать, копать имеет смысл сразу же именно задачу коммивояжера, даже не особо помня, кроме основ терминологии, впрочем незатейливой, чему там учили в ВУЗовском курсе дискретной математики по поводу теории графов и учили ли.

LVV>>Решать подобную задачу без обращения к графам — немыслимо...
P>Так это и есть классическая задача с использованием графов. Но даже взявшись её решать, копать имеет смысл сразу же именно задачу коммивояжера, даже не особо помня, кроме основ терминологии, впрочем незатейливой, чему там учили в ВУЗовском курсе дискретной математики по поводу теории графов и учили ли.
Ну, хотя бы представление о представлении графов надо иметь...
И поиски минимальных путей.
А еще неплохо иметь понятие о генетических и роевых алгоритмах...

Здравствуйте, LaptevVV, Вы писали:

LVV>Ну, хотя бы представление о представлении графов надо иметь...
Несомненно.

LVV>А еще неплохо иметь понятие о генетических и роевых алгоритмах...
Неплохо. Но там много методов и возможных алгоритмов.
И для начала стоит оценить к чему стремиться. К решению задачи наиболее близкой к оптимальной, наиболее оптимальному по быстродействию решению, или стоит сэкономить на трудозатратах разработчиков и использовать наиболее простой в реализации алгоритм, вписывающийся разумеется в разумное время расчета.

Здравствуйте, pagid, Вы писали:

P>>>"целое число — это такой вырожденный граф состоящий из одной вершины"
EP>>Я этого не говорил, это был его гротеск.
P>Разумеется, но гротеск мне показался уместным и по существу разговора.

Я привёл пример с вполне практическим значением — граф односвязного списка с циклом. Аналогичная структура возникает например внутри псевдослучайных генераторов.
А вот какое какое практическое значение имеет подчёркнутое, и в чём аналогия?
Я же не предлагаю например любое множество представлять как граф вершин без связей, исключительно ради того чтобы натянуть сову на глобус определение "граф", а показываю вполне реальные применения теории графов

EP>>Я не говорил что для деревьев нужно применять не деревянные алгоритмы, там где есть специальные деревянные.
P>А специальные деревянные алгоритмы это порождение теории графов, и лучше не будем путать?

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

Здравствуйте, smeeld, Вы писали:

EP>>>>Да например те же вездесущие социальные сети, там графы в полный рост.
S>>>Там уже полная бигдата, со всем своим хозяйством, которая уже гораздо обширней чем теория графов, и которая к математике не относится.
LVV>>Оля-ля!!! Бигдата — это и статистика, и классификация, и кластеризация. Да еще на нечеткостях...
S>Дык, а я о чём? Cоцсети сейчас-это и статистика, и кластеризация, и классификация.

Ты о том что это к математике не относится.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Ты о том что это к математике не относится.

Бигдата не относится? Конечно, привык к стройности и строгости построения теории, что и является отличительной чертой математики, и что не относится к тем сумбурным сочинениям, которые относятся к бигдате.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Я привёл пример с вполне практическим значением — граф односвязного списка с циклом.
И в чем польза представления последовательности псевдослучайных чисел в виде графа?

EP>Аналогичная структура возникает например внутри псевдослучайных генераторов.
И уж если возвращаться к математике с её более-менее строгими формулировками, не структура возникает в генераторе, а последовательность чисел можно представить в виде графа. Можно и не представлять.

Здравствуйте, T4r4sB, Вы писали:

TB>Нах математику, надо кутэ, буст, линукс, гдб, свн, юнит-тесты, паттерны, питон, вот вся суть 99% цпп вакансий.
Питон особо доставляет

Здравствуйте, B0FEE664, Вы писали:

BFE>Зачем графы? Можно всю жизнь проработать программистом и ни разу не использовать граф в явном виде.
Можно даже быть не в курсе того, что прозой разговариваешь

BFE>В стандартной библиотеке даже ни одного алгоритма, ни одного класса для графа нет, насколько я помню.
Красно-чёрные деревья больше не графы что ли? Или map и set из std выкинули?

Здравствуйте, B0FEE664, Вы писали:

BFE>Да неужели? Никогда не слышал ни о каких реальных графах в социальных сетях. Эти графы почти всегда воображаемые. Исключение — это когда какие-нибудь студенты проводят аналитическую работу, а на практике работа с такими графами сводится к работе со списком друзей.

А какие представления графов ты знаешь?..

Здравствуйте, pagid, Вы писали:

EP>>Я привёл пример с вполне практическим значением — граф односвязного списка с циклом.
P>И в чем польза представления последовательности псевдослучайных чисел в виде графа?

Не самой последовательности псевдослучайных чисел, а последовательности значений внутреннего состояния генератора (seed).

1. Понимание структуры задачи. Увидев/представив/визуализировав граф в виде буквы Р (цикл с ручкой) — всё сразу становится предельно ясно.
2. Алгоритм поиска цикла, его длины и положения, для графов виде буквы P применим и для псевдослучайных генераторов.

EP>>Аналогичная структура возникает например внутри псевдослучайных генераторов.
P>И уж если возвращаться к математике с её более-менее строгими формулировками, не структура возникает в генераторе, а последовательность чисел можно представить в виде графа. Можно и не представлять.

Именно что возникает структура, и именно что с точки зрения математики. Речь не о структуре данных, а о математической структуре. И такие структуры существуют независимо от того выражены ли они явно в коде или нет.

Здравствуйте, B0FEE664, Вы писали:

BFE>Давайте конкретно: какие математические свойства и какие из алгоритмов для графов вы используете в коде.
Ну, A*, например, часто использую...

BFE>Когда я говорю про графы, я не говорю про деревья.
Если пользоваться общепринятой терминологией, понимать коллег будет проще...

EP>>Это смотря как посмотреть. Список может иметь цикл, а дерево — нет
BFE>Что-то я не припомню, чтобы я когда-то использовал список с циклом внутри... Наличие цикла внутри списка свидетельствует об ошибке, так что в тестовых целях я поиск цикла в списке писал, но назвать это работой с графом...

std::list когда-нибудь юзал?..

BFE>И вы хотите сказать, что где-то в коде, в явном виде хранится этот граф переходов?
А что такое "в явном виде"? Ну и ты же алгоритмы просил? Как найти длину цикла генератора?

BFE>Ну и где там граф? Там нельзя получить граф, как структуру. Нельзя запустить поиск по графу, если я правильно понимаю.
Таки std::vector<std::vector<int> > g, где g[i] — массив индексов соседних с i-й вершин -- одно из популярных ЯВНЫХ представлений графов

F>Допустим прихожу я устраиваться на с++ разработчика, какой должен быть минимальный уровень знания математики? каких разделов и где та линия после которой меня примут?
Да ничего особенного, просто уметь применять на практике
Скажем коллега иногда просит умножить два "широких" целых числа (в смысле код написать), тех кто не довел до рабочего состояния с 3го раза считает проф-непригодными
Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e

А дальше — специфика конкретной области.
В CAD и геймдеве понятное дело будет линейка, кватернионы, простые численные методы.
Яндекс любит всякие сортировки на внешней памяти, суффиксные деревья, стемминг и т.п.