Рубрика «граф»

Что забыли Графы в программировании?

Для начала уточню: граф Монте‑Кристо и прочие персонажи тут ни при чём. Речь пойдёт о математических графах — структуре, которая помогает решать массу задач в программировании, математике и олимпиадной информатике.

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

Впервые я встретил графы примерно в четвёртом классе, но начал активно использовать, только когда начал заниматься олимпиадным программированием.

Читать полностью »

Статья является продолжением «Пишем агента на Kotlin: KOSMOS», но может читаться независимо. Мотивация к написанию — сохранить читателю время на возьню с фреймворками для решения относительно простой задачи.

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

Как и везде, в программирование важен маркетинг, поэтому обертку над http-запросами в цикле называют революцией:

Читать полностью »

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

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

Читать полностью »

Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор

В этой статье:

Матрица смежности

Матрица инцидентности

Список смежности (инцидентности)

Взвешенный граф (коротко)

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

Матрица является удобной для представления плотных графов в которых количество ребер (E) примерно равно количеству вершин (V).

Читать полностью »

Всем привет.

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

Итак, начнем. Но не с самого начала – думаю, что такое граф и какие они бывают (ориентированные, неориентированные, взвешенные, невзвешенные, с множественными ребрами и петлями или без них), мы все уже знаем.

Итак, поехали. Какие же варианты структур данных для «графохранения» мы имеем.
Читать полностью »

image

Представьте ваш первый день на новой работе. Офис находится в районе совершенно незнакомой вам станции метро Курская. Приближается время обеда. Вы открываете поисковое приложение, пишете «поесть на Курской» и получаете подборку вариантов, где можно отобедать.

Что стоит за запросом «поесть на Курской» и как он обрабатывается, чтобы найти именно то, что нужно вам? В статье я расскажу, как команда Поиска 2ГИС делает всё возможное для того, чтобы жизнь в городах была удобнее и комфортнее для пользователей.
Читать полностью »

КДПВ: LLTR Часть 0 - пневмотранспорт из Футурамы

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

Начну с причины возникновения LLTR (Link Layer Topology Reveal).

У меня был один “велосипед” - синхронизатор больших файлов “на полной скорости сети”, способный за 3 часа целиком залить 120 GiB файл по Fast Ethernet (100 Мбит/с; 100BASE‑TX; дуплекс) на 1, 10, 30, или 200 ПК. Это был очень полезный “велосипед”, т.к. скорость синхронизации файла почти не зависела от количества ПК, на которые нужно залить файл. Все бы хорошо, но он требует знания топологии сети для своей работы.

Подробнее в статье про него:

Ладно, а зачем понадобилось “гонять” 120 GiB файл по сети на такое количество ПК?


Этим файлом был VHD с операционной системой, программами, и т.п. Файл создавался на мастер‑системе, а затем распространялся на все остальные ПК. VHD был не только способом доставки системы на конечные ПК, но и давал возможность восстановления исходного состояния системы при перезагрузке ПК. Подробнее в статье: “Заморозка системы: история перехода с EWF на dVHD”.


Можно продолжить цепочку дальше, но на этом я прервусь.

Существующие протоколы обнаружения топологии канального уровня (LLDP, LLTD, CDP, …) для своей работы требуют соответствующей поддержки их со стороны всех промежуточных узлов сети. То есть они требуют как минимум управляемых свитчей, которые бы поддерживали соответствующий протокол. На Хабре уже была статья, как используя эти протоколы, “определить топологию сети на уровнях 2/3 модели OSI”.

Но что же делать, если промежуточные узлы – простые неуправляемые свитчи?

Если интересно как это можно сделать, то добро пожаловать под кат. Обещаю наличие множества иллюстраций и примеров.

Читать полностью »

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

Геометрия данных 5. Преобразование базиса - 1

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

Особенность координатных систем на точечном базисе (ди- и би-координат) состоит в том, что их можно использовать как в обычном геометрическом пространстве, так и в пространстве графа.

Геометрия данных 4. Пространство графа - 1

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

Определение системы координат

Задачу построения системы координат (СК) на графе можно сформулировать следующим образом.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js