Как-то во время учебы на инженера-теплоэнергетика я наткнулся на одну книгу [Попырин Л.С. Математическое моделирование и оптимизация теплоэнергетических установок. М. Энергия 1978г.], в которой был описан алгоритм построения расчётных схем энергетических установок, разработанный в Сибирском энергетическом институте (ныне - ИСЭМ СО РАН). Этот алгоритм заложен в основу СМПП (система машинного построения программ) - кодогенератора, который используется в исследованиях в ИСЭМ и по сей день. Собственно алгоритм предназначен для решения систем нелинейных уравнений, и, условно говоря, обобщает метод подстановки, знакомый многим из школьной алгебры.

Зачем это нужно?

В процессе проектирования или эксплуатации отдельных энергоблоков и электростанций в целом часто требуется решить задачу оптимизации - например, подобрать начальные параметры пара (температуру и давление перед турбиной), давление за турбиной, площадь поверхности нагрева котла, при которых достигается максимальный КПД цикла станции, экономический эффект за заданный период, или любой другой параметр.

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

Именно над этим мы и работаем. Эта теория, если у нас всё получится, станет единой метатеорией всего.

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

Как и всё что мы делали до этого, теория связей публикуется и передаётся в общественное достояние и принадлежит человечеству. То есть именно тебе. У этого труда множество авторов, однако сам этот труд намного важнее конкретного авторства. И мы надеемся уже сегодня это сможет быть полезно каждому.

Мы приглашаем тебя стать частью этого увлекательного приключения.

Статья подготовлена в преддверии старта курса «Алгоритмы и структуры данных»

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

О, как звучит! Давайте разберём условие задачи по частям.

Математики доказали, что копиями графов меньшего размера всегда можно идеально покрыть графы большего размера

В ноябре Nature опубликовал работу учёных Женевского университета (UNIGE) и канадского Университета Макгилла, которые решили заменить привычную систему PIN-кодов на более безопасную. В поисках сверхнадежной аутентификации исследователи предложили пересмотреть фактор владения и опираться на метод математического доказательства с нулевым разглашением в связке со специальной теорией относительности. 

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

Пытаюсь объяснить, как представлять матрицы смежности, инцидентности и списки смежности (инцидентности). И немного говорю о взвешенном графе.

Здесь я попытался в максимально доступной форме объяснить, как же это делать. И в первую очередь я делаю это для студентов, которые изучают данную тему и могут не понимать, зачем вообще графы нужны. Учась, я лично убедился, что для многих эта тема была «проходной» и они не извлекли из нее никакой ценной информации, а также так и не поняли, как работать с матрицами.

ИМХО для IT-студентов нужно сразу сказать, что списки (стеки, очереди) и бинарные деревья это графы. И всякие схемы, типа схемы метро, автодорог, принципиальные в электронике можно рассматривать как графы. Приложения теории графов — это фундаментальные свойства всяких подобных схем.

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

AntipovSN and MihhaCF

UPD Часть вторая здесь
UPD Часть третья здесь

Часть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо

Вступление от авторов:

Добрый день! Сегодня мы начинаем цикл статей, посвященных скорингу и использованию в оном теории графов (Т.Г.). Надеюсь, нам хватит запала, сил и терпения, т.к. тема достаточно объемная и, на наш взгляд, интересная.

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

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

А теперь к делу.

Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.

Термины и определения:

• Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
• Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»

Полный граф может выглядеть следующим образом:

Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…

AntipovSN and MihhaCF

Часть вторая, в которой Атосу все норм, а вот Графу де ля Фер чего-то не хватает

UPD Часть первая здесь
UPD Часть третья здесь

Вступление от авторов:

Добрый день! Сегодня мы продолжаем цикл статей, посвященный скорингу и использованию в оном теории графов. С первой статьей Вы можете ознакомиться здесь.

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

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

Термины и определения:

• Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Поиск по хеш-таблице, в среднем, осуществляется за время О(1).

Аудиторы, нанятые ПАО «Король» для оценки кредитоспособности НПАО «Один за всех», столкнулись с некоторыми проблемами. С одной стороны, описать схему взаимодействия 10-15 компаний и провести первичную оценку взаимодействия между компаниями очень просто, достаточно иметь под рукой лист бумаги и ручку. Но, что делать, если у вас имеется информация о взаимодействии десятков или сотен тысяч компаний? Например, если Вам нужно описать взаимодействия Арамиса со всеми его пассиями или Д’артаньяна со всеми, с кем он дрался?

В этом туториале описан алгоритм поиска в глубину (depth first search, DFS) с псевдокодом и примерами. Кроме того, расписаны способы реализации поиска в глубину в C, Java, Python и C++.

“Поиск в глубину” или “обход в глубину” — это рекурсивный алгоритм по поиску всех вершин графа или дерева. Обход подразумевает под собой посещение всех вершин графа.

Два специалиста по информатике нашли в весьма неожиданном месте идею, которая как раз пригодилась им для прорыва в теории графов

Давид Конлон и Асаф Фербер подняли нижнюю границу для значений многоцветных чисел Рамсея. Эти числа говорят о том, насколько можно увеличивать граф, пока в нём не начнут появляться неизбежные закономерности

В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.

Граф - это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.

Инженеры могли бы использовать этот прорыв в теории графов для разработки невероятно эффективных квантовых компьютерных микросхем.

Доцент кафедры информатики в Копенгагенском университете Джейкоб Холм просматривал доказательства из научной статьи, опубликованной в Интернете в октябре 2019 года им и его коллегой Евой Ротенберг (доцентом кафедры прикладной математики и информатики Датского технического университета), и обнаружил, что их результаты невольно дали решение многовековой проблемы графов.

На Хабре можно найти немало статей, посвящённых оптимизациям поиска кратчайшего пути на графе. Я расскажу ещё про еще один подход. Речь пойдёт о распараллеливании алгоритма A* и исполнении его на двух потоках, а также о сложностях, с которыми я столкнулся при реализации, и их преодолении.