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

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

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

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

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

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

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

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

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

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

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

Новый алгоритм проверки пересечений в графах прятался на виду - 1

В октябре 2019 Джейкоб Холм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.

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

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

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

Компьютерный поиск помог разобраться с 90-летней математической задачей - 1

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

Гипотеза Келлера, выдвинутая 90 лет назад Отт-Генрихом Келлером, связана с задачей покрытия пространств идентичными плитками. Она утверждает, что если замостить двумерное пространство двумерными квадратными плитками, то хотя две из них должны будут соприкасаться сторонами. То же предсказание гипотеза делает для любых измерений – то есть, при заполнении 12-мерного пространства 12-мерными «квадратами», хотя бы у двух из них должна будет найтись общая сторона.

Годами математики бились над этой гипотезой, доказывая её истинность для одних измерений и ложность для других. И к прошлой осени вопрос оставался нерешённым только для семимерного пространства.
Читать полностью »

image

Введение

Для печати на клавиатуре необходимо неподвижно сидеть или стоять. Геймпады, в отличие от них, портативные и компактные. Управляя ими, можно ходить по комнате или прилечь на диван.

Из-за малого количества кнопок на геймпаде никто не рассматривал их как средство ввода объёмных текстов, например, в программировании.

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

Для геймпадов существует множество способов ввода текста. Если вы когда-нибудь играли в консольные игры, то, скорее всего, использовали какой-то из них.

Может ли геймпад заменить клавиатуру? Пробуем программировать на стиках - 2

Экранный ввод текста в Legend of Zelda

В Legend of Zelda игрок должен по очереди выбирать буквы при помощи крестовины со стрелками и каждый раз нажимать кнопку подтверждения для добавления буквы в поле ввода текста.
Читать полностью »

Графовые рекомендации групп в Одноклассниках - 1

Графовые рекомендательные системы показывают state of the art результаты, но про них редко пишут и еще реже используют в продакшене. В этой статье мы расскажем про опыт Одноклассников в применении графового подхода для задачи рекомендации групп, разберем причем тут нейросети и что делать, если не все рекомендации одинаково полезны для пользователей и портала.

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

TLDR: кому перестановки делают больнее — меряем свёрткой графов.
Код: RolX и ванильная трёхслойная GCN на мотифах.

Выгорание на рабочем месте повстречал ещё в начале своей карьеры — и с тех пор живо интересуюсь этим вопросом. Представьте обстановку. Большой проект внедрения SAP. Высокие ставки. Амбициозные сроки. Нагрузку каждый воспринимал по-своему. Кто-то сорвался и самоустранился от выполнения обязанностей, кто-то стал токсичнее, у меня самого в какой-то момент чувство юмора пропало. Ненадолго.

image

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

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

Доброго времени суток.

В свободное время провёл небольшое исследование.

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

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

Город и данные: анализ пешеходной доступности объектов в Праге с помощью data science - 1

Несколько лет назад компания Veeam открыла R&D центр в Праге. Изначально у нас был небольшой офис примерно на 40 человек, но компания активно растет, и сейчас, в новом просторном офисе Rustonka нас уже больше двухсот. Veeam нанимает сотрудников не только из Чехии и Евросоюза, но и активно релоцирует успешных кандидатов из России. Многие переезжают вместе с женой и детьми, и вот тут у них возникает вопрос, с которым я и моя семья столкнулись четыре года назад, когда мы впервые оказались в Праге: нам надо было решить, где выбрать жилье, в какой садик будет ходить дочка, и решить множество других проблем, которые возникали по причине полного незнания города. Конечно, можно проверить всё это своими ногами, но мне захотелось подойти к вопросу с инженерной точки зрения и решить эту задачу с помощью дата-сайнс подхода — с помощью анализа данных в открытом доступе определить наиболее благоприятные для проживания районы Праги.

Определение степени благоприятности района — довольно обширная задача, и оценка может быть весьма субъективна, поэтому для начала, я немного конкретизирую и опишу проблему следующим образом:

Какой район Праги наиболее привлекателен с точки зрения пешеходной доступности инфраструктуры для детей в возрасте от 10 до 16 лет?

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

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

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

Построение графов для чайников: пошаговый гайд - 1

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

Прошлым летом я участвовал в Google Summer of Code — программе для студентов от компании Google. Ежегодно организаторы отбирают несколько Open Source-проектов, в том числе от таких известных организаций, как Boost.org и The Linux Foundation. Для работы над этими проектами Google приглашает студентов со всего мира. 

Как участник Google Summer of Code 2019 я делал проект в рамках библиотеки Alga с организацией Haskell.org, занимающейся развитием языка Хаскелль — одного из самых известных функциональных языков программирования. Alga — библиотека, представляющая типобезопасное представление для графов в Хаскелле. Она используется, например, в semantic — библиотеке компании Github, строящей по коду семантические деревья, графы вызовов и зависимостей и умеющей их сравнивать. Мой проект состоял в добавлении туда типобезопасного представления для двудольных графов и алгоритмов для этого представления. 

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

GSoC 2019: Проверка графов на двудольность и трансформеры монад - 1
Читать полностью »


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