Алгоритмы *

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

Продолжаем публикацию лекций по курсу "Управление в Технических Системах" автор - Олег Степанович Козлов на кафедре Э7 МГТУ им. Н.Э. Баумана.

Данные лекции готовятся к публикации в виде книги, а поскольку здесь есть специалисты по ТАУ, студенты и просто интересующиеся предметом, то любая критика приветствуется. В предыдущих сериях:

1. Введение в теорию автоматического управления.
2. Математическое описание систем автоматического управления 2.1 — 2.3, 2.3 — 2.8, 2.9 — 2.13.
3. ЧАСТОТНЫЕ ХАРАКТЕРИСТИКИ ЗВЕНЬЕВ И СИСТЕМ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ РЕГУЛИРОВАНИЯ.
3.1. Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ. 3.2. Типовые звенья систем автоматического управления регулирования. Классификация типовых звеньев. Простейшие типовые звенья. 3.3. Апериодическое звено 1–го порядка инерционное звено. На примере входной камеры ядерного реактора. 3.4. Апериодическое звено 2-го порядка. 3.5. Колебательное звено. 3.6. Инерционно-дифференцирующее звено. 3.7. Форсирующее звено.  3.8. Инерционно-интегрирующее звено (интегрирующее звено с замедлением). 3.9. Изодромное звено (изодром). 3.10 Минимально-фазовые и не минимально-фазовые звенья. 3.11 Математическая модель кинетики нейтронов в «точечном» реакторе «нулевой» мощности. 4 Структурные преобразования систем автоматического регулирования.

Будет как всегда позновательной увлекательно и интересно.

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

Статья состоит из четырёх частей, переходите сразу ко второй или третьей, если знакомы с проблематикой, или читайте по порядку, чтобы составить полную картину:

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

Основные алгоритмы решения задачи многорукого бандита: эпсилон-жадный подход, сэмплирование Томпсона, Upper Confidence Bound.

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

Заметки о практической реализации — о тонкостях внедрения, бизнес-требованиях и результатах на примере сервиса рекомендации игр и стикеров.

В этой статье обсудим такую структуру данных, как «префиксное дерево» (оно же нагруженное дерево, бор, trie, prefix tree). Кратко рассмотрим основы и реализуем наиболее важные операции: вставку, поиск по ключу и префиксный поиск.

Совершенный алгоритм. Жадные алгоритмы и динамическое программирование - это третья часть лекций от Тима Рафгардена. Стиль первых частей сохранён: тем и алгоритмов не много, но разобраны они детально и даны не просто готовыми, но автор показывает, как к ним можно было бы прийти.

Первое, что удивило так это неожиданная встреча с WSJF - weighted shortest job first. WSJF - это популярная методика приоритизации задач в Scrum и Kanban. Например, Дин Леффингуэлл в своём руководстве по SAFe (Agile Software Requirements: Lean Requirements Practices for Teams, Programs, and the Enterprise) на пальцах иллюстрирует результаты нескольких вариантов порядка выполнения задач (распределение эпиков, функциональностей и историй по инкрементам, итерациям и спринтам):

В этом году мы много работали над качеством предсказания времени в пути (ETA) в навигаторе 2ГИС и на 30% увеличили количество маршрутов, у которых прогнозное время совпадает с реальным с точностью до минуты. Меня зовут Кирилл, я Data Scientist в 2ГИС, и я расскажу, как максимально точно рассчитывать время прибытия из точки А в точку Б в условиях постоянного изменения дорожной ситуации.

Поговорим про то, как мы постепенно меняли подходы к оценке времени в пути: от простой аддитивной модели до использования ML-моделей прогноза пробок и корректировки ETA. Ввели Traversal Time на смену GPS-скоростей, а ещё проводили эксперименты и оценивали качество изменений алгоритма, чистили мусор из данных и закатывали модели в продакшн. Обо всём по порядку.

В предыдущих статьях "PostgreSQL Antipatterns: навигация по реестру", "PostgreSQL 13: happy pagination WITH TIES" и "SQL HowTo: курсорный пейджинг с неподходящей сортировкой" я уже рассматривал проблемы навигации по данным, представленных в виде плоского реестра.

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

Я начал интересоваться биржевой торговлей 15 лет назад, после того, как прочитал книгу Ричарда Смиттена "Жизнь и смерть величайшего биржевого спекулянта". В этой книге автор рассказал историю жизни трейдера Уолл-стрит, Джесси Ливермора, который смог дважды предсказать падение фондового рынка в 1907 и 1929 году и заработать на этом в переводе на современные деньги миллиарды долларов. Перед смертью Ливермор написал книгу "Как торговать акциями", в которой поделился своими математическими формулами для определения уровней поддержки и сопротивления, тренда и ценовых паттернов.

Всем привет! Мы — команда Smart vision в Домклик, и мы предлагаем нашим клиентам различные инструменты для помощи в подборе жилья, чтобы им было как можно комфортнее. Один из таких инструментов — автоматическая расстановка мебели, чтобы наши пользователи смогли посмотреть на трёхмерную квартиру с обстановкой и лучше понимали размеры помещения. Пока программа доступна в тестовом контуре внутри экосистемы Домклик. Мы не рассматриваем этот алгоритм в качестве инструмента для идеальной расстановки мебели, это лишь помощь клиенту в расстановке мебели для дальнейшей работы с ней.

Есть много статей о решении этой задачи: с применением GAN, который генерирует на плане помещения цветовую область для размещения мебели; с помощью классических методов на основе набора правил; или с помощью более редких графовых методов. Но все существующие методы объединяет объединяет то, что все они или не реализованы (либо находятся в закрытом доступе), или не учитывают, например, окна и двери, а также тип помещения (гостиная, спальня, детская, кухня, санузел и т.д.). Мы постарались избавиться от этих недостатков в своём инструменте.

В процессе изучения разных алгоритмов и структур данных приходит понимание, что не все они применимы в прикладных задачах (в отличие от задач про Васю и Петю/Алису и Боба). Но тот факт, что алгоритм/структура данных не является полезной на практике не означает, что идеи в них содержащиеся не привлекают пытливые умы даже из чистого любопытства. Потому речь пойдёт о красивых (субъективно) и, что важно, простых с точки зрения концепции структурах данных. 

Помните: если что-то не компилируется, это псевдокод. 

Научитесь внедрять рандомизацию в создаваемую игру, чтобы игроки оставались вовлечены в процесс и стремились перейти к следующей сцене. Это второй пост Кристо Ноббса, посвященный разработке систем, основанный на авторском вкладе Кристо в книгу The Unity game designer playbook. В данной книге подробнее рассказано о том, как прототипировать, собирать и тестировать игровой процесс (геймплей) в Unity.

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

Идея проста. Наблюдаем последовательность состояний. И требуется оценить насколько эта последовательность предсказуема. 

В предыдущем материале из этой серии мы рассказали о сетях Deep Q (Deep Q Network, DQN) и написали алгоритм их обучения на псевдокоде. Хотя такие сети, в принципе, работоспособны, практическая реализация алгоритмов обучения с подкреплением (Reinforcement Learning, RL), выполняемая без понимания их ограничений, может вести к нестабильности создаваемых систем и к плохим результатам обучения. В этом материале мы обсудим два важных ограничения, две проблемы, способных привести к нестабильности Q-обучения. Мы поговорим и о том, как, на практике, решать эти проблемы. Вспомните о том, что уравнение Беллмана связывает, с помощью рекурсии, Q-функции для текущего и следующего временных шагов.

Вообще-то я программирую в 1С, на языке, похожем на Visual Basic. Но мне кажется, что затронутый в этой теме вопрос касается всех языков программирования, т.к. затрагивает проблему, с которой рано или поздно сталкивается программист при работе со сложным кодом.

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

В современной веб разработке сложно переоценить значение такого инструмента как кэш. Мы сохраняем результаты выполнения длительных, дорогостоящих или часто выполняемых операций в некое хранилище, обратиться к которому будет быстрее и дешевле чем к первоисточнику или дешевле чем повторять операцию. В качестве такого хранилища обычно выступает оперативная память или же оптимизированные для быстрого доступа по ключу базы данных, такие как Redis. Кэш это незаменимый инструмент для уменьшения времени отклика и повышения масштабируемости приложения. Однако он имеет свои ограничения, которые связаны в основном с размером кэша. У нас не хватит оперативной памяти и пространства в Redis чтобы полностью закешировать таблицу базы данных с миллионами записей. Для решения проблемы использования кэша при большом объеме исходных данных и ограниченных ресурсах, мы должны применить некий алгоритм, который позволит нам кешировать только самое необходимое - часто запрашиваемые элементы. В этой статье мы детально рассмотрим применение одного из таких алгоритмов кэширования - LRU в контексте ASP NET Core приложения.

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

Всем привет! Меня зовут Владимир, и в этом я году оканчиваю магистратуру “Программирование и анализ данных” в Высшей школе экономики в Петербурге, а также работаю в JetBrains Research. В этом посте я хочу рассказать про нашу статью Scalable Multi-Agent Model-Based Reinforcement Learning, которую приняли на большую конференцию AAMAS’22 (A*). Над статьёй я работал вместе с Алексеем Шпильманом, заведующим Центром анализа данных и машинного обучения в Вышке. 

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

Всем привет! Меня зовут Пантелеев Александр и я бекенд разработчик в компании Bimeister. Постараюсь описать исчерпывающе, кратко и понятно суть основных паттернов хранения деревьев в реляционных базах данных. Надеюсь, что статья будет полезна тем, кто до сего момента не сталкивался с такими паттернами, и станет отправной точкой в их понимании.

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

Main Aspects of Reactivity

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

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

Повествование будет долгим, но если вы продержитесь до конца, то сможете смело идти к начальнику за повышением. Даже если вы сам себе начальник.

Продолжаем разбираться с линейной алгеброй для 3D-приложений вместе Александром Паничевым — ведущим разработчиком логики в UNIGINE. В прошлом уроке мы поговорили про предназначение математики в трехмерной графике и вспомнили основные операции над векторами. А в этом уроке переходим к более сложным темам: углы Эйлера и кватернионы.