Рубрика «теория графов» - 2

image

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

В психологии и литературе подобные мыслительные блуждания называются потоком сознания (автор этой метафоры — Уильям Джеймс). Но я бы выбрал другую метафору. Моё сознание, насколько я ощущаю, не течёт плавно от одной темы к другой, а скорее порхает по ландшафту мыслей, больше похожее на бабочку, чем на реку, иногда прибиваясь к одному цветку, а затем к другому, иногда уносимая порывами ветка, иногда посещающая одно и то же место снова и снова.
Читать полностью »

(Этюд для программистов или заявка на Интернет-поиск нового типа)

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

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

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

Пример 1. Характеристики графа существительных длиной 8 букв.
Читать полностью »

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

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

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

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


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

Головоломка «Instant Insanity» (Мгновенное Безумие), возможно, одна из самых востребованных для иллюстрации применимости теории графов в решении задач подобного ей типа. Читать полностью »

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

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

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

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

Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».
Читать полностью »

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

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

Всем кому интересно, добро пожаловать под кат.
Читать полностью »

Сегодня я хотел бы поведать вам о написании класса для упрощения работы с цепями Маркова.

Прошу под кат.
Читать полностью »

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

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

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

Сколько городов исчезло с карты? Давайте посчитаем.
Читать полностью »

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

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

Основа используемого ПО — это теория графов, при помощи которой ученые провели анализ сотен веб-страниц, посвященных «Звездным войнам». Эта работа — демонстрация возможностей нового программного обеспечения. Использоваться оно может, конечно, не только для работы с литературными произведениями и фильмами. Но поскольку авторы исследования — поклонники мира «Звездных войн», то и первая серьезная работа была выполнена на их основе.
Читать полностью »


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