Pull to refresh

Прогнозирование результатов матчей чемпионата мира

Artificial Intelligence
Недавно завершился чемпионат мира, в котором победила сборная Испании. Самым известным «предсказателем» мундиаля стал осьминог Пауль, безошибочно предсказавший восемь результатов футбольных матчей подряд (в том числе исход финала).

Но, как оказалось, английские ученые тоже решили не отставать от осьминога и разработали модель, которая позволила предсказать победу Испании в финале и объяснить поражении Англии против Германии.
Читать дальше →
Total votes 61: ↑37 and ↓24 +13
Views 1.8K
Comments 82

Скобочная форма описания графов

Algorithms *
Sandbox
Написать эту заметку меня побудила статья «Хранение иерархических данных в плоском виде», в которой автор занимается решением задачи хранения дерева комментариев в виде плоского текста. Дерево это ведь граф, поэтому я вспомнил о молодом и мало известном аппарате описания графов их скобочными образами, на который наткнулся в процессе написания диссертации. О технологии построения скобочных образов графов я и расскажу.
Читать дальше →
Total votes 23: ↑18 and ↓5 +13
Views 6.3K
Comments 15

Управляемость сложных сетей — перевод статьи Controllability of complex networks

Social networks and communities
Sandbox
Данная статья представляет собой перевод статьи Альберта Барабаши и его соавторов, под названием «Controllability of complex networks». Оригинал которой в формате PDF можно скачать здесь.

Кстати сказать, некоторые считают, что Эйнштейна XXI века будут тоже звать Альберт. А именно Альберт Барабаши.

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

В переводе, жирным шрифтом будут выделены важные заключения и основные понятия, приведенные в статье, выделенные автором перевода. Курсивом будут выделены комментарии автора перевода и ссылки на определения и дополнительную информацию по некоторым понятиям и методам, приведенным в статье.
Читать дальше →
Total votes 4: ↑4 and ↓0 +4
Views 5.7K
Comments 5

Дискретные структуры: матан для айтишников

Algorithms *Mathematics *
Sandbox


Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.

Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.

Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?
Читать дальше →
Total votes 63: ↑59 and ↓4 +55
Views 215K
Comments 43

Что случилось с Google Maps?

Interfaces *Usability *Graphic design *
Translation
Если вы часто пользуетесь картами Google Maps, то наверняка заметили изменения, которые произошли после редизайна примерно три года назад. Самое заметное, что стало гораздо меньше меток, карты как будто опустели.

Вот как выглядят окрестности Нью-Йорка, в сравнении с картой 2010 года.



Сколько городов исчезло с карты? Давайте посчитаем.
Читать дальше →
Total votes 89: ↑60 and ↓29 +31
Views 139K
Comments 129

Теория графов в Игре Престолов

Entertaining tasks Programming *C++ *Algorithms *


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

Всем кому интересно, добро пожаловать под кат.
Читать дальше →
Total votes 61: ↑55 and ↓6 +49
Views 64K
Comments 37

Курсы Computer Science клуба, весна 2017, часть вторая

Образовательные проекты JetBrains corporate blog Algorithms *Mathematics *Machine learning *

Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».
Читать дальше →
Total votes 11: ↑11 and ↓0 +11
Views 4.9K
Comments 2

Код Прюфера

Algorithms *
Sandbox

Деревья. Кратко напомним


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


Читать дальше →
Total votes 41: ↑34 and ↓7 +27
Views 58K
Comments 17

Занимательная математика с цветными кубиками

Entertaining tasks Game development *Mathematics *
Sandbox
iqbiki
Интеллектуальные игры, подобные головоломкам, дисциплинируют мышление, формируют мыслительную культуру, значение которой трудно переоценить, развивают воображение, причем, все эти собственные усовершенствования человек приобретает в самой захватывающей форме – в форме игры.



Совсем немного истории


Головоломка «Instant Insanity» (Мгновенное Безумие), возможно, одна из самых востребованных для иллюстрации применимости теории графов в решении задач подобного ей типа.
Читать дальше →
Total votes 26: ↑26 and ↓0 +26
Views 17K
Comments 6

Сложно ли сделать из мухи слона?

Entertaining tasks Programming *Game development *Algorithms *Mathematics *
Недавно, перед тем как написать про свои соображения о путях развития ИИ, решил посмотреть, что уже писали об ИИ на Хабре. В числе прочих наткнулся на статью с довольно сложным решением (через генетический алгоритм) широко известной задачи поиска метаграмм: дано два слова (существительных) одинаковой длины, нужно получить из первого второе, меняя только одну букву и получая при этом имеющее смысл слово.


Сальвадор Дали. Искушение св. Антония. 1946. (Фрагмент).
Бельгийский Королевский музей изящных искусств (Брюссель).

Читать дальше →
Total votes 20: ↑18 and ↓2 +16
Views 11K
Comments 29

Графы большие и маленькие: интеллектуальное решение проблемы выбора представления

Search engines *Programming *Delphi *Algorithms *ООP *
(Этюд для программистов или заявка на Интернет-поиск нового типа)



Программа, делающая из мухи слона (далее программа МС), показала, что неориентированный граф существительных с заданным количеством букв хоть и содержит тысячи вершин, но при этом довольно «тощий» (т.е. имеет сравнительно не много ребер) и до полного графа ему далеко (см. Пример 1). Вслед за Чарлзом Уэзереллом (Charles Wetherell), автором широко известной книги «Этюды для программистов», выбрал жанр этюда, чтобы представить различные способы представления таких графов. (И сделать из этого выводы для автоматизации выбора представления – вплоть, может быть, до Интернет-поиска нового типа).

Start for word length 8
6016 words loaded from dictionary file: ..\Dictionary\ORF3.txt
Graph was made: edges number = 871


Пример 1. Характеристики графа существительных длиной 8 букв.
Читать дальше →
Total votes 5: ↑4 and ↓1 +3
Views 8.6K
Comments 0

Просто о графах. Попытка популяризации

Entertaining tasks Programming *Mathematics *
«Всякие звания (дворянина, купца, мещанина, крестьянина и пр., титулы — княжеские, графские и пр.) и наименование гражданских чинов (тайные, статские и проч. советники) уничтожаются...»
Об уничтожении сословий и гражданских чинов
Декрет ВЦИК и СОВНАРКОМа от 10.11.1917 года, ст. 2



image


Как-то же я обходился без этого раньше...


Есть ли польза рядовому программисту или, скажем, обывателю от теории графов, или вещь эта сугубо сакральная, из надменных математических абстракций?

Вероятно, специфика “случайно распределенных графов” окажется маловостребованной в нашей с вами повседневности, но некоторое представление о теории графов может оказаться полезным в самых разнообразных ситуациях даже человеку не особенно к математике расположенному, – что же касается людей, занятых в такой области, как программирование, то изощренная изобретательность, как правило, сопутствует ежедневно выпадающим на их долю задачам, оттого представители этой профессии, в поисках новых идей и инструментов, случается, азартно загружают свой ум вещами, казалось бы не пригодными для полезного использования, однако, заказав пиццу за 10 тысяч биткоинов, они дарят хорошее настроение другим хорошим людям на многие годы, и таки оправдывают свою пассионарность.
Читать дальше →
Total votes 30: ↑29 and ↓1 +28
Views 38K
Comments 16

Математики построили карту связей во вселенной «Звездных войн»

Professional literature *Popular science Science fiction

Визуализация связей между 7563 основными персонажами вселенной «Звездных войн»

Используя новое программное обеспечение, исследователи из EPFL проанализировали вселенную «Звездных войн», построив карту связей между персонажами, мирами и цивилизациями. Всего было задействовано около 20 тысяч персонажей и 640 сообществ в рамках временного отрезка в 36 тысяч лет.

Основа используемого ПО — это теория графов, при помощи которой ученые провели анализ сотен веб-страниц, посвященных «Звездным войнам». Эта работа — демонстрация возможностей нового программного обеспечения. Использоваться оно может, конечно, не только для работы с литературными произведениями и фильмами. Но поскольку авторы исследования — поклонники мира «Звездных войн», то и первая серьезная работа была выполнена на их основе.
Читать дальше →
Total votes 13: ↑11 and ↓2 +9
Views 11K
Comments 9

1000-мерный куб: можно ли сегодня создать вычислительную модель человеческой памяти?

Mathematics *Popular science Artificial Intelligence
Translation
image

Сегодня утром на пути к кампусу Беркли я провёл пальцами по листьям ароматного куста, а затем вдохнул знакомый запах. Я делаю так каждый день, и каждый день первое слово, которое всплывает в голове и приветственно машет рукой — это шалфей (sage). Но я знаю, что это растение — не шалфей, а розмарин, поэтому я приказываю шалфею успокоиться. Но слишком поздно. После rosemary и sage я не могу помешать появлению на сцене петрушки (parsley) и чабреца (thyme), после чего в голове возникают первые ноты мелодии и лица на обложке альбома, и вот я уже снова оказался в середине 1960-х, одетый в рубашку с огурцами. Тем временем розмарин (rosemary) вызывает в памяти Роуз Мэри Вудс (Rosemary Woods) и 13-минутный пробел (хотя теперь, проконсультировавшись с коллективной памятью, я знаю, что это должны быть Роуз Мэри Вудс и пробел в 18 с половиной минут). От Уотергейта я перепрыгиваю к историям на главной странице. Потом я замечаю в ухоженном саду ещё одно растение с пушистыми серо-зелёными листями. Это тоже не шалфей, а чистец (lamb’s ear). Тем не менее, sage наконец получает свою минуту славы. От трав я переношусь к математическому ПО Sage, а потом к системе противовоздушной обороны 1950-х под названием SAGE, Semi-Automatic Ground Environment, которой управлял самый крупный из когда-либо построенных компьютеров.

В психологии и литературе подобные мыслительные блуждания называются потоком сознания (автор этой метафоры — Уильям Джеймс). Но я бы выбрал другую метафору. Моё сознание, насколько я ощущаю, не течёт плавно от одной темы к другой, а скорее порхает по ландшафту мыслей, больше похожее на бабочку, чем на реку, иногда прибиваясь к одному цветку, а затем к другому, иногда уносимая порывами ветка, иногда посещающая одно и то же место снова и снова.
Читать дальше →
Total votes 38: ↑35 and ↓3 +32
Views 24K
Comments 8

Обнаружен универсальный метод сортировки сложной информации

Algorithms *Mathematics *
Translation


Открывая своё кафе, вы хотели бы узнать ответ на следующий вопрос: «где находится другое, ближайшее к этой точке кафе?» Эта информация помогла бы вам лучше понять ваших конкурентов.

Это пример задачи поиска "ближайшего соседа", которую широко изучают в информатике. Дан набор сведений и новая точка, и требуется найти, к какой точке из уже существующих она окажется ближайшей? Такой вопрос возникает во множестве повседневных ситуаций в таких областях, как исследование генома, поиск картинок и рекомендации на Spotify.

Но, в отличие от примера с кафе, вопросы о ближайшем соседе часто оказываются очень сложными. За последние несколько десятилетий величайшие умы среди специалистов по информатике брались за поиски наилучших способов решения подобной задачи. В частности, они пытались справиться с усложнениями, появляющимися из-за того, что в различных наборах данных могут быть очень разные определения «близости» точек друг к другу.
Читать дальше →
Total votes 43: ↑37 and ↓6 +31
Views 21K
Comments 19

Как быстро подготовиться к собеседованию, на котором будут вопросы по алгоритмам и технологиям обработки информации?

РДТЕХ (Разумные Деловые Технологии) corporate blog Entertaining tasks Java *System Analysis and Design *IT career
Приветствую всех читателей Хабра! Меня зовут Юрий, более 20 лет преподаю высокие технологии, Oracle, Microsoft и другие, а также занимаюсь созданием, разработкой и поддержкой нагруженных информационных систем для различных бизнес-заказчиков. Сегодня хотел бы рассказать вам об актуальном направлении: собеседованиях по технологиям обработки данных.

На собеседованиях такого плана работодателю бесполезно спрашивать у соискателя о технологиях, связанных с традиционным программированием. Поэтому я популярно расскажу, как готовиться к собеседованию только в одной узкой области, связанной с языками обработки информации, а именно — обработкой длинных целых чисел (длинная арифметика) и выявления информационных свойств объектов реального мира, которые описываются в длинных целых числах.
Читать дальше →
Total votes 30: ↑19 and ↓11 +8
Views 9K
Comments 8

Российский математик опроверг 53-летнюю гипотезу о раскраске сетей

Mathematics *Popular science
Translation

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




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

Задачи по раскраске сетей [см. хроматическое число / прим. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.
Читать дальше →
Total votes 105: ↑97 and ↓8 +89
Views 47K
Comments 78

Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора. Ч.1

Python *Data Mining *Big Data *Machine learning *Finance in IT
Sandbox

AntipovSN and MihhaCF


UPD Часть вторая здесь
UPD Часть третья здесь


Часть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо


Вступление от авторов:


Добрый день! Сегодня мы начинаем цикл статей, посвященных скорингу и использованию в оном теории графов (Т.Г.). Надеюсь, нам хватит запала, сил и терпения, т.к. тема достаточно объемная и, на наш взгляд, интересная.


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


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


А теперь к делу.


Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.


Термины и определения:


  • Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
  • Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»


Полный граф может выглядеть следующим образом:

Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…

Читать дальше →
Total votes 14: ↑12 and ↓2 +10
Views 7.2K
Comments 15

Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора. Ч.2

Python *Data Mining *Big Data *Machine learning *Finance in IT

AntipovSN and MihhaCF


Часть вторая, в которой Атосу все норм, а вот Графу де ля Фер чего-то не хватает


UPD Часть первая здесь
UPD Часть третья здесь


Вступление от авторов:


Добрый день! Сегодня мы продолжаем цикл статей, посвященный скорингу и использованию в оном теории графов. С первой статьей Вы можете ознакомиться здесь.


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


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


Термины и определения:


  • Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Поиск по хеш-таблице, в среднем, осуществляется за время О(1).

Аудиторы, нанятые ПАО «Король» для оценки кредитоспособности НПАО «Один за всех», столкнулись с некоторыми проблемами. С одной стороны, описать схему взаимодействия 10-15 компаний и провести первичную оценку взаимодействия между компаниями очень просто, достаточно иметь под рукой лист бумаги и ручку. Но, что делать, если у вас имеется информация о взаимодействии десятков или сотен тысяч компаний? Например, если Вам нужно описать взаимодействия Арамиса со всеми его пассиями или Д’артаньяна со всеми, с кем он дрался?

Читать дальше →
Total votes 14: ↑13 and ↓1 +12
Views 3.7K
Comments 8
1