Эта классическая картина, удостоенная «Оскара», продемонстрировала зрителям удивительно простую математическую задачу
Рубрика «теория графов»
Почему математики ненавидят фильм «Умница Уилл Хантинг»
2026-03-17 в 8:03, admin, рубрики: Мэтт Деймон, теория графов, умница уилл хантингКубик Рубика и суперспособности. Как думают компьютер, робот и человек, когда решают кубик 3×3×3?
2026-02-10 в 10:57, admin, рубрики: интеллект, кубик рубика, мозг, мышление, спидкубинг, теория графов, теория группНа днях произошло знаковое событие в мире спидкубинга. Человек впервые собрал кубик Рубика быстрее 3 секунд на соревнованиях WCA. Это произошло 8 февраля на турнире GLS Big Cubes Gdańsk 2026 в Польше. 9-летнему Теодору Зайдеру первому в истории удалась официальная сборка sub-3Читать полностью »
Рекомендательная система для вашего каталога научных работ (и не только!)
2025-04-15 в 17:37, admin, рубрики: machinelearning, ml, nlp, python, обработка естественного языка, рекомендательная система, теория графовИспользуем обработку естественного языка и теорию графов для сравнения и рекомендации различных типов документов.
Введение
Почти все проекты начинаются с одного важного этапа — активных исследований. Инвестировать в то, что уже было сделано другими, в развитие их работы — это один из путей к повышению ценности вашего проекта. Важно не только извлечь уроки из опыта других, но и понять, чего не стоит делать в своем проекте, чтобы повысить его шансы на успех.
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
2021-07-31 в 18:12, admin, рубрики: Алгоритмы, веса, граф, графики, графы, искусственный интеллект, массив, математика, матрица, машинное обучение, петли, ребра графа, Сетевые технологии, списки, теория графовВсе, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
В этой статье:
Матрица смежности
Матрица инцидентности
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов в которых количество ребер (E) примерно равно количеству вершин (V).
Новый алгоритм проверки пересечений в графах прятался на виду
2020-10-12 в 11:27, admin, рубрики: графы, математика, Научно-популярное, планарные графы, теория графовДва специалиста по информатике нашли в весьма неожиданном месте идею, которая как раз пригодилась им для прорыва в теории графов
В октябре 2019 Джейкоб Холм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.
Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.
Холм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Холм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос».
Читать полностью »
Радужное доказательство демонстрирует наличие стандартных составных частей у графов
2020-03-30 в 7:00, admin, рубрики: дерево, математика, Научно-популярное, полный граф, теория графовМатематики доказали, что копиями графов меньшего размера всегда можно идеально покрыть графы большего размера
8 января трое математиков опубликовали доказательство теоремы из комбинаторики, сформулированной почти 60 лет назад, известной, как гипотеза Рингеля. Грубо говоря, она предсказывает, что графы – конструкции, состоящие из точек и линий – можно идеально сложить из одинаковых частей меньшего размера.
Математики с восторгом приняли подтверждение этой гипотезы.
«Счастье в том, что эта работа решает очень старую гипотезу, которую невозможно было проверить другими методами», — сказал Гил Калай, математик из Еврейского университета в Иерусалиме, не связанный с этой работой.
Гипотеза Рингеля предсказывает, что особые типы сложных графов – с триллионами вершин и рёбер – можно «замостить», т.е. полностью покрыть, отдельными копиями меньших графов определённого типа. С концептуальной точки зрения этот вопрос похож на следующий: могу ли я полностью замостить пол на кухне одинаковыми копиями какой-либо плитки, имеющейся в магазине? В реальной жизни большинство типов плитки не подойдёт для вашей кухни – чтобы полностью покрыть пол, придётся комбинировать их разные формы. Но в мире теории графов гипотеза предсказывает, что замостить граф можно всегда.
Читать полностью »
Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора. Ч.2
2019-08-23 в 15:07, admin, рубрики: big data, data mining, python, Алгоритмы, графы, исследование, кредитный скоринг, машинное обучение, обучение, теория графов, финансы в ITЧасть вторая, в которой Атосу все норм, а вот Графу де ля Фер чего-то не хватает
Вступление от авторов:
Добрый день! Сегодня мы продолжаем цикл статей, посвященный скорингу и использованию в оном теории графов. С первой статьей Вы можете ознакомиться здесь.
Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения
Цель данной статьи: не более, чем за 30 минут, описать основные способы хранения данных о графах и описать правила и принципы построения нашей модели для скоринга заемщика.
Термины и определения:
- Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Поиск по хеш-таблице, в среднем, осуществляется за время О(1).
Аудиторы, нанятые ПАО «Король» для оценки кредитоспособности НПАО «Один за всех», столкнулись с некоторыми проблемами. С одной стороны, описать схему взаимодействия 10-15 компаний и провести первичную оценку взаимодействия между компаниями очень просто, достаточно иметь под рукой лист бумаги и ручку. Но, что делать, если у вас имеется информация о взаимодействии десятков или сотен тысяч компаний? Например, если Вам нужно описать взаимодействия Арамиса со всеми его пассиями или Д’артаньяна со всеми, с кем он дрался?
Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора
2019-08-20 в 16:51, admin, рубрики: big data, data mining, python, Алгоритмы, графы, исследование, кредитный скоринг, машинное обучение, обучение, теория графов, финансы в ITЧасть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо
Вступление от авторов:
Добрый день! Сегодня мы начинаем цикл статей, посвященных скорингу и использованию в оном теории графов (Т.Г.). Надеюсь, нам хватит запала, сил и терпения, т.к. тема достаточно объемная и, на наш взгляд, интересная.
Несмотря на шуточное название, мы постараемся затронуть отнюдь не шуточные темы, которые уже сейчас влияют на жизнь многих из нас, а в ближайшем будущем могут коснуться всех, без исключения.
Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения
А теперь к делу.
Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.
Термины и определения:
- Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
- Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»
Полный граф может выглядеть следующим образом:
Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…
Российский математик опроверг 53-летнюю гипотезу о раскраске сетей
2019-08-02 в 7:00, admin, рубрики: гипотеза Хедетниеми, графы, математика, Научно-популярное, теория графов, хроматические числаВсего три страницы потребовалось российскому математику, чтобы описать способ раскраски сетей определённого типа, превзошедший ожидания экспертов
В опубликованной в онлайне работе опровергается гипотеза 53-летней давности, касающаяся наилучшего способа назначения цветов узлам сети. В работе всего на трёх страничках показано существование способов раскраски определённых цветов, превзошедших все ожидания экспертов.
Задачи по раскраске сетей [см. хроматическое число / прим. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.
Читать полностью »
Обнаружен универсальный метод сортировки сложной информации
2018-08-26 в 9:00, admin, рубрики: Алгоритмы, математика, поиск, поиск ближайшего соседа, сортировка, теория графов
Открывая своё кафе, вы хотели бы узнать ответ на следующий вопрос: «где находится другое, ближайшее к этой точке кафе?» Эта информация помогла бы вам лучше понять ваших конкурентов.
Это пример задачи поиска "ближайшего соседа", которую широко изучают в информатике. Дан набор сведений и новая точка, и требуется найти, к какой точке из уже существующих она окажется ближайшей? Такой вопрос возникает во множестве повседневных ситуаций в таких областях, как исследование генома, поиск картинок и рекомендации на Spotify.
Но, в отличие от примера с кафе, вопросы о ближайшем соседе часто оказываются очень сложными. За последние несколько десятилетий величайшие умы среди специалистов по информатике брались за поиски наилучших способов решения подобной задачи. В частности, они пытались справиться с усложнениями, появляющимися из-за того, что в различных наборах данных могут быть очень разные определения «близости» точек друг к другу.
Читать полностью »