Алгоритмы *

Привет, Хаброжители! Обратите внимание на большую распродажу в честь Старого Нового года.

Когда виртуальная машина Java компилирует ваш исходный код Java в машинный, одна из задач, которые она должна при этом выполнить – решить, где хранить локальные переменные Java и другие подобные временные значения. В вашей машине отсутствует концепция локальных переменных, поэтому на этапе компиляции необходимо определиться, какое место в памяти стека (какой машинный регистр) будет использоваться для хранения каждой переменной. Эта операция называется «выделение регистров». Может показаться, что выделение регистров – сложная абстрактная теоретическая тема, но в этом коротком посте я покажу, как сначала соотнести исходный код Java с теорией, потом понять, как его видит компилятор, а потом – показать результирующий машинный код. В данном случае моя цель – продемонстрировать, что все эти концепции очень легко опробовать на практике с реальным компилятором. 

Автор Лысый Камрад (@LKamrad)

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

Знакомьтесь, Physarum polycephalum  – не животное, не растение и даже не гриб...

Примечание: данную публикацию можно использовать для начала ознакомления учащихся с принципами динамического программирования.

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

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

Данная статья поможет начинающим iOS разработчикам разобраться в производительности алгоритмов в Swift.

Обозначение Big O нотация (или просто Big O) — это способ оценки относительной производительности структуры данных или алгоритма, обычно по двум осям: времени и пространству.

Мы ежедневно работаем с информацией из разных источников и поэтому имеем интуитивные представления о том, что означает, когда один источник является более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой «новой информации». Или другой пример: рассмотрим текстовый файл с романом «Война и мир» в кодировке UTF-8. Его размер — 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?

По мотивам открытой лекции для Computer Science центра рассказываю о том, как можно математически подойти к определению понятия "количество информации".

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

Также поговорим о проблемах метода SHAP и его дальнейшем развитии в виде метода Shapley Flow, объединяющего интерпретацию модели и многообразия данных.

Для бизнес-приложений очень важна возможность быстро сформировать нужный отчёт. Для этого, в частности, важно быстро получить результат запроса (часто – очень сложного запроса) к СУБД. Что не всегда просто, потому что с этой СУБД работают на чтение и запись тысячи (а иногда - десятки тысяч) пользователей.

 Чтобы не нагружать рабочую СУБД запросами для отчетов мы разработали механизм копий баз данных, копирующий данные (все или их часть) из рабочей БД в отдельную БД для отчетности. Пользователи могут строить отчеты на «отчетной» БД, быстрее получая результат и не нагружая рабочую базу.

 Для дальнейшего ускорения формирования отчетности мы разработали Дата акселератор — собственную SQL-совместимую in-memory базу данных, ориентированную на максимальную производительность в задачах OLAP. Дата акселератор может использоваться в качестве «отчетной БД» и позволяет существенно (иногда – на порядки) ускорить формирование отчетов.

Реализация алгоритма k-средних на диалекте SQL без питонов и дополнительных библиотек.

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

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

Сегодня 11 января исполняется 88 лет сэру Чарльзу Энтони Ричарду Хоару, разработчику алгоритма быстрой сортировки массивов. Тони Хоар — английский ученый в области информатики и вычислительной техники, он подарил миру не только алгоритмы Quicksort и Find, но и логику для доказательства корректности программ, формальный язык для описания моделей взаимодействия в параллельных системах (CSP), а также нулевую ссылку, за создание которой в дальнейшем принес свои извинения. 

Кстати, угадаете, что и почему изображено на нашей иллюстрации? Автору первого правильного ответа подарим мерч :)

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

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

Proof of Stake (PoS) – это мошенничество. Когда я говорю это, я имею в виду, что PoS 1) заявлен как система консенсуса, и 2) фактически неспособен на самом деле обеспечить консенсус.

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

Невесёлая жизнь у муравья Лэнгтона, но, как мы увидим, он не готов мириться с такой возмутительной ситуацией и всеми силами старается сбежать.

Решаем оптимизационную задачу с vk winter quest алгоритмами спортивного программирования

Стандартные методы планирования вычислительного времени оперируют с точностью 1 ms (0,001 s) и погрешностью — 1 ms (SysTick).

Этого достаточно для большинства задач бюджетных микроконтроллеров stm32; гарантированный период прикладной задачи 0,01 s. При этом MPU загружается на 5-10%, пребывая преимущественно в холостом цикле или в состоянии «сна».

Архитектура бюджетных микроконтроллеров stm32 допускает работу с меньшими интервалами и погрешностью менее 10 us ( 0,00001 s).

В первой части статьи я рассказал про понятие градиентного бустинга, библиотеки, с помощью которых можно реализовать данный алгоритм и углубились в одну из этих библиотек. Сегодня продолжим разговор о CatBoost и рассмотрим Cross Validation, Overfitting Detector, ROC-AUC, SnapShot и Predict. Поехали!

До этого момента мы мерили качество на каком-то конкретном fold’e (конкретной выборке), то есть взяли разделили нашу выборку на обучающую и тестовую, это не совсем корректно, вдруг мы взяли какой-то непрезентативный кусок нашего датасета, на этом самом куске мы получим хорошее качество, а когда модель будет работать с реальными данными, то с качеством все будет крайне грустно. Дабы избежать этого, необходимо использовать Cross Validation.

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