Интеллектуальные игры, подобные головоломкам, дисциплинируют мышление, формируют мыслительную культуру, значение которой трудно переоценить, развивают воображение, причем, все эти собственные усовершенствования человек приобретает в самой захватывающей форме – в форме игры.
Головоломка «Instant Insanity» (Мгновенное Безумие), возможно, одна из самых востребованных для иллюстрации применимости теории графов в решении задач подобного ей типа. Читать полностью »
Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.
Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».
Читать полностью »
Недавно, на Geektimes я опубликовал статью, где привёл немного поверхностной статистики из серии книг «Песнь льда и пламени». Но я не стал углубляться в самую интересную часть, в граф социальных связей, ибо тема заслуживает отдельного внимания. В этой статье я продемонстрирую как теория графов может помочь при анализе подобных данных и приведу реализации алгоритмов, которыми я пользовался.
Всем кому интересно, добро пожаловать под кат.
Читать полностью »
Сегодня я хотел бы поведать вам о написании класса для упрощения работы с цепями Маркова.
Прошу под кат.
Читать полностью »
Если вы часто пользуетесь картами Google Maps, то наверняка заметили изменения, которые произошли после редизайна примерно три года назад. Самое заметное, что стало гораздо меньше меток, карты как будто опустели.
Вот как выглядят окрестности Нью-Йорка, в сравнении с картой 2010 года.
Сколько городов исчезло с карты? Давайте посчитаем.
Читать полностью »
Визуализация связей между 7563 основными персонажами вселенной «Звездных войн»
Используя новое программное обеспечение, исследователи из EPFL проанализировали вселенную «Звездных войн», построив карту связей между персонажами, мирами и цивилизациями. Всего было задействовано около 20 тысяч персонажей и 640 сообществ в рамках временного отрезка в 36 тысяч лет.
Основа используемого ПО — это теория графов, при помощи которой ученые провели анализ сотен веб-страниц, посвященных «Звездным войнам». Эта работа — демонстрация возможностей нового программного обеспечения. Использоваться оно может, конечно, не только для работы с литературными произведениями и фильмами. Но поскольку авторы исследования — поклонники мира «Звездных войн», то и первая серьезная работа была выполнена на их основе.
Читать полностью »
Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.
Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.
Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?
Читать полностью »
Данная статья представляет собой перевод статьи Альберта Барабаши и его соавторов, под названием «Controllability of complex networks». Оригинал которой в формате PDF можно скачать здесь.
Кстати сказать, некоторые считают, что Эйнштейна XXI века будут тоже звать Альберт. А именно Альберт Барабаши.
Для тех, кто уважает чужой труд, напомню, что перевод является авторским, и любое цитирование или упоминание требует указания ссылки на оригинал перевода. Надеюсь, что те, кто не уважают чужой труд, не заморачивают себе голову тем, о чем будет идти речь в статье.
В переводе, жирным шрифтом будут выделены важные заключения и основные понятия, приведенные в статье, выделенные автором перевода. Курсивом будут выделены комментарии автора перевода и ссылки на определения и дополнительную информацию по некоторым понятиям и методам, приведенным в статье.
Читать полностью »
Сегодня я хотел бы рассказать про ноябрьский конкурс по функциональному программированию, несмотря на то, что с момента его проведения уже прошло практически два месяца. Соорганизатором конкурса выступил наш уважаемый коллега Алексей Кишкин, который предложил задачу, реализовал её решение на нескольких языках программирования, а также подготовил некоторую вспомогательную инфраструктуру для проверки решений.
Задача на кункурс была вынесена крайне известная. Необходимо было решить банальную проблему раскраски карты, то есть поиска хроматического числа графа. Предполагалось, что конкурсанты представят на суд общественности общее решение, которое они проверяли на задаче раскраски карты России на уровне субъектов федерации. Ну и так вышло, что задача, несмотря на свою известность и давнишность, заинтересовала многих участников, так что на конкурс были присланы решения на многих языках программирования.
Ну а мы, как обычно, далее в этой краткой заметке мы рассмотрим решение указанной задачи на языке программирования Haskell. Впрочем, я сразу хочу оговориться — программа написана соорганизатором конкурса, который обычно пишет свои программы на языке OCaml, так что сегодня, как я ни старался, в определениях функций мы будем постоянно видеть торчащие верблюжьи уши OCaml'я :).
