Рубрика «граф» - 2

Мы продолжаем рассказывать об системе адаптивного обучения на Stepic.org. Первую вводную часть этой серии можно почитать здесь.

В данной статье мы расскажем о построении рекомендательной системы (которая и лежит в основе адаптивности). Расскажем о сборе и обработке пользовательских данных, о графах переходов, хендлерах, оценке реакции пользователя, формировании выдачи.

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

Рекомендательные системы в онлайн-образовании. Продолжение - 1

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

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

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

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

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

Привет, Друзья!

Хотел поделиться с вами своим последним мини-проектом: трехмерной визуализацией всего npm. Вселенная выглядит примерно так:

весь npm

Можно летать клавишами WASD, или если вы смотрите ее из телефона — просто вращая телефон вокруг (телефон должен поддерживать WebGL).
Читать полностью »

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

Диаграммы и графы в LaTeX с использованием PGF/TikZ 3.0

Несколько месяцев назад вышел графический пакет для LaTeX PGF/TikZ 3.0, и в нём появилось немало интересных штук. В этой статье мы попробуем их применить для рисования простой блок-схемы. Нарисуем, например, кусочек известной схемы определения языка по письменности. Средства, уже рассмотренные в ранее опубликованной статье, трогать не будем, а поговорим об упрощённой нотации записи графов и управлением позиционированием узлов и ветвлением графа.

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

Теория памяти человека, зачатки ИИ

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

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

Предположим, а может так оно и есть, все нейроны объединены в одни очень большой граф со сложной структурой. Данная структура сложна и не может работать хаотично, т.е. передаваемые импульсы передаются строго в определённом порядке, поэтому тут есть 2 варианта:

  1. Ребра графа имеют только положительные веса
  2. Ребра графа могут иметь, как положительные так и отрицательные веса

Рассматривая второй случай в реальной работе памяти человека, можно предположить, что такая ситуация возникает при провалах памяти человека, т.е. к нейрону содержащему ту информацию которая нам необходимо либо поступает недостаточно сигналов, для накопления и дальнейшей передачи, либо этих сигналов вообще нет. В случае с графами это можно представить, как узел у которого мало путей, либо они отрицательны, либо их вообще нет (рис 1).
image

Что же касается первого случая, когда все ребра имеют положительные веса, т.е. головной мозг человека не поврежден. Тогда почему же человек не может вспомнить моменты из своего детства? Ответ прост: “Любое тело стремится к покою”, так же и наша с вами нейронная сеть старается оптимизировать свою работу. (Владельцам навигаторов должно быть знакомо, что прокладка маршрута, как раз таки строится на принципах работы графа, нахождения кратчайшего пути и т.д.). Мозг человека более изощренная система и его оптимизация заключается в разрыве связей с малыми весами, и построении новых связей с более высокими. (рис. 2). Таким образом объяснятся многочисленные разрывы и новые соединения нейронов. Чем больше узел имеет связей, тем легче вспомнить необходимую информацию.
image
Читать полностью »

Маскируем класс под граф Boost. Часть 3: Находим путь
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса
Часть 2: Завершаем реализацию поддержки концепций

В прошлых статьях цикла описывался процесс адаптации класса клеточного игрового поля под концепции графов boost. Сейчас рассмотрим собственно то, ради чего все затевалось — поиск пути на клеточном поле. Реализация поиска boost позволяет достаточно тонко настраивать алгоритм, в этой статье будет приведет только один пример такой параметризации — возможность задавать различную длину ребер графа.
Читать полностью »

Маскируем класс под граф Boost. Часть 2: Завершаем реализацию поддержки концепций
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса

Кратко напомню задачу. Есть двумерное игровое поле из клеток, часть из которых свободна, а часть занята. Требуется найти путь по свободным клеткам из одной позиции поля в другую. Алгоритм поиска пути реализован в Boost. Но он требует, чтобы наше поле подходило под определение графа. Точнее класс должен удовлетворять двум концепциям — boost::VertexListGraph и boost:: IncidenceGraph. При этом интерфейс игрового поля менять не хочется — для всего остального проекта это не граф и графом никогда не станет.

В прошлой части было рассмотрено подключение внешних ассоциированных типов, необходимых для интерпретации класса как boost-графа. Конечно, одних типов недостаточно. Также требуется реализовать несколько функций с заданной сигнатурой и итераторов, с помощью которых библиотека сможет манипулировать игровым полем как графом.
Читать полностью »

Маскируем класс под граф Boost. Часть 1: Не трогаем интерфейс
Потребовалось недавно алгоритм поиска пути для нашей игры переделать. Прошлый был полностью самописный — шаг в сторону, и все плохо… Захотелось взять готовый из хорошего источника. Тут-то и вспомнилось, что в boost есть функциональность для работы с графами. К сожалению подход, «найди функцию, вызови — и все заработает» не состоялся. Упор в библиотеке сделан на максимальную гибкость использования, что негативно сказалось на простоте. В то же время и ничего смертельного — все лучше, чем с нуля делать (и потом исправлять). С другими библиотеками тоже связываться желания не было, в то время как boost в проекте используется давно…
Читать полностью »

Медленно, но верно, я продолжаю делать серию туториалов о WxPython, где я хочу рассмотреть разработку ферймворка для создания нодового интерфейса с нуля и до чего-то вполне функционального и рабочего. В прошлых частях уже рассказано как добавлять ноды, в этой же части, мы их будем соединять, а на этой картинке показан результат, который мы в этой статье получим:
Пример использования WxPython для создания нодового интерфейса. Часть 5: Соединяем ноды
Еще не идеально, но уже вырисовывается что-то вполне полезное и рабочее.

Прошлые части живут тут:
Часть 1: Учимся рисовать
Часть 2: Обработка событий мыши
Часть 3: Продолжаем добавлять фичи + обработка клавиатуры
Часть 4: Реализуем Drag&Drop

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


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