Предлагаю обсудить философскую тему. Что если представить нашу жизнь как взвешенный ориентированный ациклический граф? Визуализация графа приведена на рисунке:
Рубрика «графы» - 3
Жизнь как граф
2022-01-15 в 20:42, admin, рубрики: алгоритм беллмана-форда, Алгоритмы, графы, детерминизм, жадный алгоритм, математика, философия, Читальный залКак определить самый авторитетный фильм всех времен и народов
2021-09-17 в 10:28, admin, рубрики: data mining, python, анализ данных, графы, исследование, кино, парсингКакое произведение киноискусства оставило самый большой отпечаток в современной поп культуре? Предлагаю подумать над этим вопросом некоторое время. Может быть это Апокалипсис сегодня? Или Крестный отец? А вдруг главный фильм всех времен и народов это шедевр отечественного кинематографа - фильм Викинг?
К счастью, это можно посчитать.
Отсылки в современных произведениях популярного искусства - забавная вещь. Люди их любят. Возьмем популярный мультсериал Читать полностью »
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
2021-07-31 в 18:12, admin, рубрики: Алгоритмы, веса, граф, графики, графы, искусственный интеллект, массив, математика, матрица, машинное обучение, петли, ребра графа, Сетевые технологии, списки, теория графовВсе, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
В этой статье:
Матрица смежности
Матрица инцидентности
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов в которых количество ребер (E) примерно равно количеству вершин (V).
Новый алгоритм проверки пересечений в графах прятался на виду
2020-10-12 в 11:27, admin, рубрики: графы, математика, Научно-популярное, планарные графы, теория графовДва специалиста по информатике нашли в весьма неожиданном месте идею, которая как раз пригодилась им для прорыва в теории графов
В октябре 2019 Джейкоб Холм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.
Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.
Холм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Холм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос».
Читать полностью »
Компьютерный поиск помог разобраться с 90-летней математической задачей
2020-08-31 в 14:03, admin, рубрики: Гипотеза Келлера, графы, заполнение пространства, измерения, математика, Научно-популярное, плиткаПереведя гипотезу Келлера на понятный компьютерам язык поиска в графах, исследователи, наконец, решили задачу покрытия пространств плиткой
Команда математиков, наконец, разобралась с гипотезой Келлера – однако не своими силами. Вместо этого они обучили целый парк компьютеров, и те решили её.
Гипотеза Келлера, выдвинутая 90 лет назад Отт-Генрихом Келлером, связана с задачей покрытия пространств идентичными плитками. Она утверждает, что если замостить двумерное пространство двумерными квадратными плитками, то хотя две из них должны будут соприкасаться сторонами. То же предсказание гипотеза делает для любых измерений – то есть, при заполнении 12-мерного пространства 12-мерными «квадратами», хотя бы у двух из них должна будет найтись общая сторона.
Годами математики бились над этой гипотезой, доказывая её истинность для одних измерений и ложность для других. И к прошлой осени вопрос оставался нерешённым только для семимерного пространства.
Читать полностью »
Может ли геймпад заменить клавиатуру? Пробуем программировать на стиках
2020-08-10 в 6:28, admin, рубрики: pyautogui, pygame, python, ввод текста, геймпады, графы, Игры и игровые приставки, периферия, слепой набор
Введение
Для печати на клавиатуре необходимо неподвижно сидеть или стоять. Геймпады, в отличие от них, портативные и компактные. Управляя ими, можно ходить по комнате или прилечь на диван.
Из-за малого количества кнопок на геймпаде никто не рассматривал их как средство ввода объёмных текстов, например, в программировании.
Однако аналоговые стики (а у большинства геймпадов их два) имеют потенциал обеспечения бесконечного количества вариантов ввода. Вопрос сводится к выбору подходящих жестов для максимальной эффективности и минимального напряжения больших пальцев.
Для геймпадов существует множество способов ввода текста. Если вы когда-нибудь играли в консольные игры, то, скорее всего, использовали какой-то из них.
Экранный ввод текста в Legend of Zelda
В Legend of Zelda игрок должен по очереди выбирать буквы при помощи крестовины со стрелками и каждый раз нажимать кнопку подтверждения для добавления буквы в поле ввода текста.
Читать полностью »
Графовые рекомендации групп в Одноклассниках
2020-05-14 в 9:38, admin, рубрики: big data, data mining, Блог компании Одноклассники, графы, машинное обучение, рекомендательные системы
Графовые рекомендательные системы показывают state of the art результаты, но про них редко пишут и еще реже используют в продакшене. В этой статье мы расскажем про опыт Одноклассников в применении графового подхода для задачи рекомендации групп, разберем причем тут нейросети и что делать, если не все рекомендации одинаково полезны для пользователей и портала.
Лекарей сжигать нельзя беречь сейчас
2020-05-04 в 11:00, admin, рубрики: python, sap, Блог компании Open Data Science, глубинное обучение, графовые сверточные сети, графы, инновации, кадровые перестановки, математика, машинное обучение, мода, модели, организационные структуры и потоки, проекты, процессы, светская хроника, трансформации, тренды, управление, управление персоналом, управление проектамиTLDR: кому перестановки делают больнее — меряем свёрткой графов.
Код: RolX и ванильная трёхслойная GCN на мотифах.
Выгорание на рабочем месте повстречал ещё в начале своей карьеры — и с тех пор живо интересуюсь этим вопросом. Представьте обстановку. Большой проект внедрения SAP. Высокие ставки. Амбициозные сроки. Нагрузку каждый воспринимал по-своему. Кто-то сорвался и самоустранился от выполнения обязанностей, кто-то стал токсичнее, у меня самого в какой-то момент чувство юмора пропало. Ненадолго.
Управление изменениями (дисциплина, направленная на снижение напряжения во время внедрения информационных систем) многим обязана медикам. Во-первых, сам феномен эмоционального выгорания впервые зафиксировали у медицинских работников. Во-вторых, первое масштабное исследование, обобщающее 68 кейсов значительных перемен в английских госпиталях, открыло правила успеха для агентов изменения. Кроме того, моделирование эпидемий решает задачу максимизации влияния и позволяет внедрять нововведения быстрее и естественнее через (суб)оптимально выбранных людей на нужных местах.
Всё больше медучреждений перепрофилируют и это вызывает у работников ожидаемый стресс. Покажем, как его можно измерить, а уж где знаки препинания в заголовке ставить — решайте сами.Читать полностью »
Анализ комбинации жадного алгоритма поиска клики с частичным перебором вершин графа
2020-03-16 в 13:35, admin, рубрики: Алгоритмы, графы, жадные алгоритмы, клики, математикаДоброго времени суток.
В свободное время провёл небольшое исследование.
В теории графов известен жадный алгоритм поиска кликового числа. Далеко не всегда он даёт верный результат. Под катом проводится анализ результатов работы жадного алгоритма при его комбинации с частичным перебором множеств вершин на графах из «DIMACS benchmark set».
Город и данные: анализ пешеходной доступности объектов в Праге с помощью data science
2020-03-16 в 8:25, admin, рубрики: data engineering, визуализация данных, графы, открытые данные, Программирование, статический анализ, урбанистика
Несколько лет назад компания Veeam открыла R&D центр в Праге. Изначально у нас был небольшой офис примерно на 40 человек, но компания активно растет, и сейчас, в новом просторном офисе Rustonka нас уже больше двухсот. Veeam нанимает сотрудников не только из Чехии и Евросоюза, но и активно релоцирует успешных кандидатов из России. Многие переезжают вместе с женой и детьми, и вот тут у них возникает вопрос, с которым я и моя семья столкнулись четыре года назад, когда мы впервые оказались в Праге: нам надо было решить, где выбрать жилье, в какой садик будет ходить дочка, и решить множество других проблем, которые возникали по причине полного незнания города. Конечно, можно проверить всё это своими ногами, но мне захотелось подойти к вопросу с инженерной точки зрения и решить эту задачу с помощью дата-сайнс подхода — с помощью анализа данных в открытом доступе определить наиболее благоприятные для проживания районы Праги.
Определение степени благоприятности района — довольно обширная задача, и оценка может быть весьма субъективна, поэтому для начала, я немного конкретизирую и опишу проблему следующим образом:
Какой район Праги наиболее привлекателен с точки зрения пешеходной доступности инфраструктуры для детей в возрасте от 10 до 16 лет?
Под пешеходной доступностью в своей работе я беру расстояние в 1300 метров. Именно такой порог, согласно различным исследованиям, считается оптимальным для этой возрастной группы.
В качестве объектов инфраструктуры я выбрал такие, которые, по моему мнению, посещает большинство детей. Это школы, библиотеки, образовательные центры, спортивные центры и игровые площадки.