Алгоритмы *

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

Большой мир генерирует большие данные. Вот и на нашу голову свалился большой граф. Настолько большой, что мы можем удержать в памяти его вершины, но не ребра. Кроме того, относительно графа приходят обновления – какое ребро добавить, какое удалить. Можно сказать, что каждое такое обновление мы видим в первый и последний раз. В таких условиях необходимо найти компоненты связности.

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

Категорически приглашаем всех желающих на онлайн-курс «Введение в теоретическую информатику» Александра Ханьевича Шеня, подготовленный совместно с Computer Science центром и платформой Stepic. Курс начнётся 24 февраля.



Александр Ханьевич — автор многих популярных книг по математике и программированию. Многие его книги и брошюры можно бесплатно скачать с сайта издательства МЦНМО: например, «Программирование: теоремы и задачи» (Шень, 2004), «Лекции по математической логике и теории алгоритмов» (Верещагин, Шень, 2012), «Классические и квантовые вычисления» (Китаев, Шень, Вялый, 1999). Под его редакцией вышел перевод первого издания классического учебника «Алгоритмы: построение и анализ» (Кормен, Лейзерсон, Ривеста, 1990), а также недавнего учебника «Алгоритмы» (Дасгупта, Пападимитриу, Вазирани, 2006).

В общем, у Александра Ханьевича огромный опыт чтения лекций как школьникам, так и студентам и аспирантам. Рассказывает он очень увлекательно и понятно. В онлайн-курсе он даст обзор различных направлений Theoretical Computer Science: криптография, инварианты циклов, вычислимость, переборные задачи, игры, коды, интерактивные доказательства и многое другое (всего в курсе восемнадцать глав!). В курсе будет много задач — как простых (закрепляющих изученный материал), так и более сложных, над которыми придётся поломать голову и тем, кто уже был знаком с теорией.

Будем рады видеть вас среди слушателей онлайн-курса!
stepic.org/104

Когнитивные вычисления (cognitive computing) — тренд последних нескольких лет. Это технологии, которые силами многих специалистов развиваются очень быстрыми темпами и помогают человеку справляться с огромным потоком информации. Причем поток этот очень глубокий и широкий, образно говоря, это весь поток информации, генерируемый человечеством. Мозг человека — мощнейшая система, способная анализировать неструктурированные массивы данных, обрабатывать их и «раскладывать по полочкам». Но даже этот инструмент не справляется с информационными потоками современности, поэтому на службу себе человек поставил компьютеры, как обычные персональные, так и сверхпроизводительные системы. Но тут возникла проблема уже иного характера, а именно — необходимость структурирования данных, которые обрабатываются. Каждый день человечество генерирует около 2,5 квинтиллионов байтов данных, и 80% из них являются неструктурированными. А это означает, что эти 80% невидимы для современных компьютерных систем, созданных по обычной технологии.

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

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

Онлайн-курсы

Начну с конца: если вы не заканчиваете школу или бакалавриат в этом году, то вы всё равно можете поучиться в Академическом университете благодаря нашим (совместно с Computer Science центром) онлайн курсам! (Кстати, скоро появятся курсы по физике от наших коллег, следите за новостями!)

Бакалавриат

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



Подробности о поступлении в бакалавриат

Магистратура

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

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

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

Привет, Хабр!

Итак, мы запустили третий курс Школы Данных «Билайн». Подробный отчет о занятиях от одного из участников можно почитать здесь.

Отчеты о работе Школы мы также будем выкладывать на официальной странице Школы в Facebook. Там же будем отвечать на вопросы, которые также можно направлять на dataschool@beeline.digital.

Набираем 4-ый курс, который стартует с 4 апреля. Запись, как всегда, на странице Школы.

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

Мы сейчас не будем говорить о том, что на заре больших данных считалось, что основные инсайты и применения аналитики идут скорее от данных. Это безусловно есть, но в нашей практике это происходит в соотношении 80 к 20, где 80 процентов всех задач для аналитика или даже больше рождается от бизнеса.

Однако, как же бизнес генерит эти задачи, если он, бизнес, не разбирается в аналитике данных? Да, очень просто. В нашей компании мы потратили какое-то время на объяснение бизнесу возможностей аналитики данных и теперь разные подразделения заваливают нас заказами придумывая все новые применения этим инструментам.

От переводчика: этот пост — перевод одной из частей масштабного обзора физики (Sonic Physics Guide) в играх серии Sonic the Hedgehog для Sega Genesis/Mega Drive и Sonic CD. В следующих частях рассматриваются такие темы: бег, прыжки, вращение, потеря колец, поведение под водой, суперскорость, специальные возможности, камера, анимации и некоторые другие. Так как частей много (14 штук), в конце поста я добавил опрос. Стоит ли продолжать — решать вам.

Всем привет!

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

Совсем недавно решал задачу построения стакана котировок на основе исторических данных Московской Биржи. В открытых источниках ничего подобного не нашел, пришлось начинать с нуля и копать самому. Есть некоторые нюансы, о которых нужно знать. Про них буду упоминать по ходу.

Про биржевую торговлю, инфраструктуру и тестирование алгоритмов на исторических данных много писал и пишет IT Invest, спасибо ему. От себя добавлю, что на данных OrderLogs мы анализируем глубину рынка, ликвидность, спреды и еще много чего. Результаты используем в наших торговых алгоритмах.

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

Цель: Получить стакан котировок на любой момент времени.

Это последняя статья из цикла о процедурно генерируемых с помощью Unity и C# картах мира. Осторожно, под катом 7 МБ картинок.

Это третья статья из цикла о процедурно генерируемых с помощью Unity и C# картах мира. Цикл будет состоять из четырех статей.

Это вторая статья из цикла о процедурно генерируемых с помощью Unity и C# картах мира. Цикл будет состоять из четырех статей.

Долгое время я задумывался, что же не в порядке с некоторыми частями кода. Раз за разом, в каждом из проектов находится некий «особо уязвимый» компонент, который все время «валится». Заказчик имеет свойство периодически менять требования, и каноны agile завещают нам все хотелки воплощать, запуская change request-ы в наш scrum-механизм. И как только изменения касаются оного компонента, через пару дней QA находят в нём несколько новых дефектов, переоткрывают старые, а то и сообщают о полной его неработоспособности в одной из точек применения. Так почему же один из компонентов все время на устах, почему так часто произносится фраза а-ля «опять #компонент# сломался»? Почему этот компонент приводится как антипример, в контексте «лишь бы не получился ещё один такой же»? Из-за чего этот компонент так неустойчив к изменениям?

В этом цикле статей мы научимся создавать процедурно генерируемые карты мира с помощью Unity и C#. Цикл будет состоять из четырех статей.

Этот мир просто охренеть какой сложный, каждый день поражаюсь.

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

И знаете, что удивительно? Этот подход замечательно работает. Ну, почти всегда. По крайней мере, ничего лучше мы до сих пор не придумали.

Но вообще-то я не об этом. Я хочу рассказать об одной чрезвычайно интересной как с эстетической, так и с математической точки зрения категории этих самых моделей.



Да, я о клеточных автоматах, а именно — об их подмножестве, простейших клеточных автоматах (Elementary cellular automaton). В этой статье я поведаю, что это такое, какие они бывают, какими свойствами обладают, а также отвечу на главный, на мой взгляд, и совершенно правильный вопрос, который часто несправедливо игнорируется в подобных статьях. Звучит он так: А это всё вообще зачем?

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

Я искренне надеюсь, что после прочтения статьи вы сами захотите поиграться с ними, и на этот случай у меня припасен собранный из JS и палок генератор.

Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке: для чего это нужно, где применяется, как это быстро сделать, какие подводные камни нас ожидают и многое другое. Рассмотрим различные способы для решения данной задачи, выясним плюсы и минусы каждого способа. Эта статья будет обзорной: если я что-то не описываю здесь, то постараюсь всегда дать вам набор ссылок, где всё подробно описано и расписано. Надеюсь, что материал будет интересен как новичкам в сфере алгоритмов, так и матёрым программистам. Что же, если я смог заинтересовать вас, то прошу под кат!

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

Этот день всё-таки пришел. Мы выкатили обновленную версию редакторов документов ONLYOFFICE Document Editors 3.6 с быстрым совместным редактированием, как в Google Docs. Его давно просили, требовали, угрожали, но мы были неумолимы. До тех пор, пока не сдались под напором пользователей, желающих редактировать свои секретные материалы, в режиме реального времени наблюдая, что набирает соавтор.

Далее расскажем, почему мы так противились «быстрому» совместному редактированию, чем наш вариант отличается от похожего режима в других онлайн-редакторах и как мы собираемся решать вопрос undo/redo.

Продолжаю зарисовки об использовании бесплатного математического редактора Mathcad Express. На этот раз предлагаю обратиться к численному решению дифференциальных уравнений (в сегодняшнем примере — с частными производными). Файл с дальнейшими расчетами в форматах Mathcad и XPS вы найдете здесь.

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



На графике показано начальное распределение температуры вдоль оси Х (красная линия) и два расчетных профиля – после первого шага и после нескольких шагов по времени.