Рубрика «графы»
Изящное шестистраничное доказательство. Как возникают случайные структуры
2022-04-30 в 20:39, admin, рубрики: Алгоритмы, Гипотеза Кана-Калаи, графы, математика, множества, Научно-популярноеРеализация алгоритма Краскала на С#
2022-01-22 в 23:02, admin, рубрики: .net, C#, алгоритм, алгоритм краскала, Алгоритмы, графы, Краскала, математика, минимальное остовное дерево, Программирование, реализация, система непересекающихся множеств, сортировка графа, структуры данных, хранение информацииВ данной статье для реализации алгоритма будут рассмотрены:
-
Система хранения графа на основе List<>
-
Сортировка рёбер графа по весу
-
Система непересекающихся множеств
Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.
О чём речь?
Если прочитав предложение выше вы невольно задались этим вопросом, то вам следует изучить пару книг по теории графов информацию, представленную в этом блоке.
Жизнь как граф
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 кейсов значительных перемен в английских госпиталях, открыло правила успеха для агентов изменения. Кроме того, моделирование эпидемий решает задачу максимизации влияния и позволяет внедрять нововведения быстрее и естественнее через (суб)оптимально выбранных людей на нужных местах.
Всё больше медучреждений перепрофилируют и это вызывает у работников ожидаемый стресс. Покажем, как его можно измерить, а уж где знаки препинания в заголовке ставить — решайте сами.Читать полностью »