Алгоритмы *

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

Сразу скажу, что моя статья относится лишь к условному ФААНГу. Многие аргументы из этой статьи теряют значимость в других случаях: если у вас маленькая фирма, мало кандидатов или у вас всего 10 пользователей.

Я утверждаю, что алгоритмические интервью - лучший вариант для ФААНГа из всех пока придуманных.

Прошу простить заранее за несколько кликбейтный заголовок )

Не так давно писал в соцсетях хейт‑пост по поводу «алгоритмических секций» при приёме на работу в Яндекс.

Да и многие другие софтверные компании это практикуют и считают навыки написания алгоритмов — чуть ли не самым важным навыком для программистов.

И ставят данной компетенции очень высокий приоритет при приёме на работу.

Попробую сегодня развить эту мысль и объяснить почему ставить навыки написания алгоритмов на первый план — не правильно, почему этот «алгоритмический» критерий не релевантен и не отражает реальной ценности / уровня / потенциальной пользы от данного программиста.

Фото до (слева) и после (справа) калибровки камеры

В первой части статьи мы немного поупражнялись на яблоках, чтобы понять, как 3D-объекты проецируются на 2D-плоскость фотографии. Заодно мы описали математическую модель камеры и ее параметры.

Знаешь параметры — живешь в Сочи можешь восстановить 3D-сцену или ее характеристики: высоту здания, расстояние до пешехода, загруженность самосвала. Словом, сплошная польза для целого ряда отраслей. 

А вот как именно определить эти заветные параметры, так и осталось за кадром. К тому же мы рассматривали простейшую модель pinhole, но в реальной жизни все сложнее. У большинства камер есть линзы, которые искажают изображения (вспомните эффект fisheye). Все эти «рыбьи глаза»‎ и другие отклонения нужно как-то корректировать.

О том, как восстанавливать параметры камеры (калибровать ее) и нивелировать искажения (дисторсию), читайте в этой публикации.

Также из нее вы узнаете:

• как выглядит математическая модель калибровки и дисторсии;

• как собрать датасет для калибровки;

• какие есть методы калибровки;

• детали одного из этих методов.

Так вышло, что спустя более чем 20 лет работы связанной с IT мне захотелось заглянуть в другие области знаний и таковой стала юриспруденция. Поступление на заочку, учёба, множество открытий, о которых и не задумывался раньше, привели меня к очередному этапу - учебной практике. Практика длилась месяц полноценной работы (рабочий день чуть короче обычного) и, помимо прочего, столкнула меня с большим количеством папок с документами. Поковырявшись недельку с этим добром мне пришла простая идея по структуризации этого дела в виде внедрения черкаш-кода, о чём и поведаю в данной статье.

Лучший способ изучить новую технологию это применить ее на практике. Но как быть, если у вас нет квантового компьютера, а на изучение физики нет времени/желания? Это не проблема, потому что сегодня мы разберем наиболее доступный и безболезненный способ погружения в квантовые алгоритмы на примере комбинаторной оптимизации. И начнем с распространенной задачи, которая возникает на производстве - диспетчеризация технологических операций. Устраивайтесь поудобнее, приготовьте чашку любимого напитка и поехали!

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

RabbitMQ - это открытая реализация протокола AMQP (Advanced Message Queuing Protocol), является мощным и гибким брокером сообщений. Он обеспечивает надежное и эффективное взаимодействие между компонентами системы, предоставляя разработчикам инструменты для создания гибких и масштабируемых архитектур.

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

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

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

Меня зовут Сергей Михайлин. Я разработчик группы машинного обучения в ОК. В данной статье дан обзор современных подходов к персонализации text-to-image моделей на базе открытой архитектуры Stable Diffision. Мы приводим технические подробности каждого подхода и анализируем его применимость в реальных высоконагруженных системах. На основании собственных экспериментов по персонализации text-to-image моделей мы выделяем список возникающих при решении этой задачи проблем и перспективных способов их решения.

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

«У самурая нет цели, есть только путь»

Первый блин на производстве не отличается красотой, но опыт был получен. Наиболее привлекательным мне пришелся генетический алгоритм: отбор успешных змеек, скрещивание, частичная мутация генов и так тысячи раз до результата. Змейки, без указания им правил выживания, в тысячном поколении «понимали», что нужно стремиться съесть яблоко и никуда не врезаться, это вызывало ощущение прикосновения к чуду "It's Alive!!!"

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

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

Алгориитм Шора — квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число M за время O((logM)^3) используя O(log M) логических кубитов.

Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.

Алгоритм Шора состоит из 2-х частей - квантовых и классических вычислений.

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

Классические вычисления решают задачу как по найденному периоду степенной функции найти разложение на сомножители.

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

А какие есть ещё варианты определить период функции используя квантовые вычисления?

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

• Фурье-вычисления для сравнения изображений

• Определение частоты сердечных сокращений методом корреляции с использованием быстрых Фурье преобразований

а так же начал повторять эту технологию при квантовых вычислениях

• Изучаем Q#. Алгоритм Гровера. Не будите спящего Цезаря

Так почему бы не повторить успешный успех и, заодно, обобщить теорию вопроса?

Как и бит, кубит допускает два собственных состояния, обозначаемых |0> и |1> (обозначения Дирака), но при этом может находиться и в их суперпозиции.
В общем случае его волновая функция имеет вид A|0>+B|1>, где A и B называются амплитудами вероятностей и являются комплексными числами, удовлетворяющими условию |A|^2+|B|^2=1 (но это не обязательно соблюдать при записи - всегда подразумевается, что происходит нормирование величин).
При измерении состояния кубита можно получить лишь одно из его собственных состояний.
Вероятности получить каждое из них равны соответственно |A|^2 и |B|^2.
Как правило, при измерении состояние кубита необратимо разрушается, чего не происходит при измерении классического бита.

В квантовых вычислениях, мы имеем факт, что применение трансформации Адамара H к кубиту в состоянии |0> даёт нам его в равновероятном состоянии для исходов |0> и |1>, то есть в состоянии |0>+|1>

Но как нам задать нужное состояние кубита, то есть с заранее заданными значениями A и B ?

Вернее, как задать нужное состояние кубита, используя только минимальный набор базовых операций? Ведь любой QDK должен включать в себя методы инициализации кубита (и желательно в требуемом состоянии).
Ну а мы ограничимся в данном примере операциями H и Controlled X.

Если вы занимались профилированием своего приложения, то, глядя на CPU Flame Chart, вероятно, испытывали смесь досады и азарта, глядя на особо «жирный» метод. Досады – что ваша программа всё ещё не идеальна по скорости. Азарт – от того, что вы можете докопаться до причины проблемы и отжать для процессора ещё немного свободного времени на более полезные вычисления. По крайней мере, я регулярно становлюсь жертвой обоих этих чувств, чему данная статья и обязана своим появлением.

Мой кейс – это попытка выжать из игрового движка Flame больше скорости и возможностей, чем он может «из коробки». Гейм-разработка имеет свои особенности по сравнению с «парсингом большого json» или устранением подлагивания при разовом проигрывании анимации, как минимум потому что здесь потенциально объёмные вычисления производятся абсолютно на каждом кадре. Так что, наверное, мой опыт не сильно будет перекликаться с теми проблемами, которые встречает большинство Flutter-разработчиков.

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

Транспортные, телекоммуникационные и компьютерные сети часто используют Hub-and-Spoke архитектуру для эффективной маршрутизации потоков между множеством отправителей и получателей. Особенность такой топологии заключается в использовании специального объекта сети - хаба. Хабом называется объект сети, который обеспечивает распределение, соединение, переключение, консолидацию, сортировку или перевалку в распределенных системах много-ко-многим. Кроме того, хабы позволяют соединить большой набор пар отправитель/получатель с использованием небольшого кол-ва соединений.

Задача размещения хабов (Hub Location Problem) относится к стратегическому уровню планирования сети. Это накладывает ограничения на возможность оперативной реализации и валидации решения. Одним из способов моделирования и анализа такого рода решений без рисков для текущей сети является математическое моделирование.

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

Алгоритм Шора

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

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

Казалось бы, жизнь невозможно повернуть назад, а предмет из фотографии не восстановишь. Хотя с последним можно поспорить: из плоского 2D-изображения реально восстановить 3D-модель объекта. Подобная «магия» часто практикуется в AR/VR, управлении беспилотниками и других сферах. Для этого первым делом производится калибровка камеры. Чтобы понять процесс калибровки, сперва следует освоить базовые принципы преобразования трехмерных координат точек в двухмерные на плоскости. 

Сегодня мы рассмотрим:

• геометрию формирования изображения на сенсоре камеры (pinhole модель);

• как рассчитываются координаты точки на сенсоре для точки из реального мира;

• как переходить от одной системы координат к другой;

• что такое внутренние и внешние параметры камеры и зачем они нужны.