Анализ подходов к решению олимпиадной задачи по программированию, связанной с диатомической числовой последовательностью Штерна. Или как незадачливый программист решил стряхнуть пыль со своих навыков и попробовал решить задачу из разряда простых с сайта https://www.spoj.com/
Этот материал посвящён исследованию восстановления текстов из текстовых эмбеддингов.
Рост популярности векторных баз данных
В последние годы наблюдается стремительное развитие генеративного искусственного интеллекта. Это привело к тому, что многие компании спешат внедрить соответствующие ИИ-инструменты в свои бизнес-процессы. Один из самых распространённых способов это сделать заключается в создании ИИ-систем, которые отвечают на вопросы, имеющие отношение к информации, которую можно найти в некоей базе данных, хранящей документы. Большинство решений этой задачи основано на подходе, называемом «генерация с дополненной выборкой»
Кто бы мог представить, что в современном мире ещё можно встретить языки программирования, в которых нет сортировки как штатной функции языка? Как себе можно вообще представить программирование без этой функции?! Ну что ж знакомьтесь, это язык tinyscheme и его GIMP порт под названием Script-fu.
Алгоритмы — они повсюду. Помните, грызли структуры данных в первую сессию? Или открывали лекции по ИТ и видели, что программирование начинается не с реальных жизненных задач.
Алгорсы — штука крайне полезная. Это быстрый легальный источник дофамина, сравнимый с прохождением хардкорной игры типа Dark Souls.
Я 6 лет преподаю ИТ-дисциплины детям, студентам и очень взрослым коллегам. В статье поделюсь, на каких сайты взбадриваюсь задачами, и как я вижу идеальный план развития алгоритмического мышления (ну вдруг вы растите дома айтишника или преподаёте сами).
Главная задача рекомендательной системы — предоставить пользователю контент, фильм, трек, книгу, товар или информацию, которые могут заинтересовать его в данный момент. Сложность в том, что у нас нет явного запроса пользователя, как в поиске, есть только история его взаимодействий с объектами и наша надежда на то, что мы верно распознали его скрытые желания.
Раньше для такой задачи нужно было строить сложные алгоритмы со множеством написанных вручную эвристик. Теперь с этим помогают ML‑технологии.
Меня зовут Кирилл Хрыльченко, я руковожу командой R&D рекомендательных технологий в Яндексе. Наша команда исследует и разрабатывает новые технологии, а также активно следит за тем, что появляется нового в индустрии. Сегодня я поделюсь трендами развития рекомендательных систем и расскажу, как нейросети продолжают улучшать качество рекомендаций: какие есть нюансы в работе с LLM, чем полезно обучение с подкреплением, что изменилось в плане анализа истории пользователя, а также на что обратить внимание при масштабировании.
Статья о том, что писал сам изобретатель Эдсгер Дейкстра о своём алгоритме поиска кратчайшего пути в первоисточнике. Приведён пример: как найти этот путь между двумя голландскими городами, которые посещал автор алгоритма.
Разбор известного алгоритма для начинающих с разбором моментов, с которыми я столкнулась. Приводится само объяснение механизма, без кода, чтобы лучше понимать саму суть. Да, поисковик выдаст 36 600 результатов при точном запросе. Но, возможно, кому‑то захочется знать историю вопроса и более неформального разбора.
Как писал сам автор алгоритма:
«Слава богу, у нас есть не только серьёзные проблемы, но и нелепые».
Как-то я исследовал способы наиболее эффективного определения простоты числа и наткнулся на показанный выше код.
Он меня заинтриговал. Хоть это, возможно, и не самый эффективный способ, но определённо один из наименее очевидных, поэтому мне стало любопытно. Каким образом соответствие регулярному выражению .?|(..+?)\1+ должно показать, что число непростое (после его преобразования в унарную систему счисления)?
Если вы заинтересовались, продолжайте чтение, я проанализирую это регулярное выражение и объясню, что же в нём происходит. Объяснение не зависит от языка программирования, однако я приведу версии показанного выше Java-кода на Python, JavaScript и Perl и объясню, почему они немного различаются.
Я объясню, как регулярное выражение ^.?$|^(..+?)\1+$ способно отфильтровывать все простые числа. Почему это выражение, а не .?|(..+?)\1+ (использованное в примере кода на Java)? Это связано с тем, как работает String.matches(), о чём я расскажу ниже.
Хотя по этой теме есть несколько постов, я считаю, что они недостаточно глубоки и в них приводится лишь высокоуровневое объяснение, недостаточно хорошо излагающее важные подробности. В своей статье я попытаюсь объяснить подробности, чтобы их мог понять любой. Моя цель — сделать этот код понятным каждому, будь вы гуру регулярных выражений или впервые о них услышали.
Ранжирование — это уникальная разновидность задач в машинном обучении, обособленная как от классификации, так и регрессии. Заключительная статья по нейрооптимизаторам в РСУБД, как ни странно, связана именно с ней. Бум в развитии подобных моделей произошёл совсем недавно — в 2023 году, что мы с вами подробно разберём. Сначала погрузимся в ранжирование в целом, а затем увидим, как в соответствии с новой постановкой задачи адаптировались методы поиска оптимального плана исполнения запроса.
Помните пост о разумной слизи, умеющей решать непростые задачи? Так вот, грибы тоже не лыком шиты. Японские исследователи установили, что мицелий некоторых видов грибов может реагировать на расположение пищи, оптимизируя сеть гифов (нити грибницы) для более эффективного освоения ресурсов.
В статье «Как исследователи нарушают привычные подходы в ИИ, исключая матричное умножение» упоминалось, в частности, что перспективным кажется хранение в нейросетевых матрицах лишь троичных значений: (-1, 0, 1), иначе говоря - тритов. Такие матрицы умножать друг на друга проще. И в моей статье я расскажу, как собственно, матрицы из тритов хранить и умножать.
Не только в играх вроде "Го" или "Жизнь" - но и в создании фильтров для изображений - часто нужно для клетки или точки (x, y) перечислить её "соседей". Либо только четырех (по горизонтали и вертикали), либо все восемь (с диагоналями).
Можно не задумываясь написать массивчик с 4-мя или 8-ю парами смещений, вроде[(-1, 0), (0, 1), (1, 0), (0, -1)] - а можно ли вместо него жахнуть какую-нибудь формулу? Давайте попробуем для утренней разминки ума в понедельник :)
В этой статье будет несколько 2-3 строчных примеров кода - уж извините пожалуйста :) зато она довольно короткая.
Почему я не готовлюсь к алгоритмическому интервью
И не очень люблю людей, которые к нему готовы. Когда я провожу интервью, то главное - это понять как человек думает и как решает проблемы.
Цель проекта Boson — это разработка встроенного движка базы данных документов JSON, написанный на C++. Основные возможности: стандартное хранилище JSON-документов в формате ключ/значениями с постоянным хранением на диске. Размер документов до 4Gb. Быстрый поиск документов по ID с использованием индекса B+ дерева. Поддержка курсоров для линейного обхода записей. База данных в одном файле, без временных файлов. Простое, чистое и легкое в использовании API. Самодостаточный и не требующий настройки.
В предыдущих двух статьях мы прошли шаги от кэширования файлового ввода/вода (часть I) до построенного на его базе хранилища записей произвольной длины (часть II) с проверкой целостности, возможностью получения записей списком и повторным использованием свободного места. Теперь мы переходим к завершающей части и "сердцу" СУБД - индексу.
Зачем нужен индекс: предположим, что в базе есть 1 млрд не отсортированных записей документов, тогда поиск конкретного документа по ID потребует O(n) операций, то есть до 1 млрд операций в худшем случае. Однако, если бы документы в базе были бы отсортированы по ID, то поиск в сортированной базе, тем же бинарным поиском занял бы O(log n) занял бы 30 операций. Что, теоретически, на базе в 1 млрд записей будет в 33.3 млн раз быстрее.
В этом тексте я показал как конечный автомат может работать ядром для драйвера аппаратного I2C трансивера.
Меня удивляет, что в оригинальном коде от вендоров микроконтроллеров программисты прошли мимо конечных автоматов при написании I2C кода внутри своих официальных uHAL. Непорядок...
В связи с этим мне пришлось разрабатывать собственный полноценный драйвер I2C буквально на физических регистрах I2C трансивера.
Определение. Алгоритм – некоторая конечная последовательность предписаний (правил, инструкций и т.п.), однозначно определяющая процесс преобразования исходных P и промежуточных данных в результат Q решения задачи.
Теория алгоритмов - это наука, изучающая общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления. На основе формализации понятия алгоритма возможно сравнение алгоритмов по их эффективности и другим показателям, проверка их эквивалентности, определение областей применимости.
Абстракция потенциальной осуществимости. Как уже отмечалось, алгоритмический процесс при выработке результата Q из исходных данных P совершает несколько отдельных шагов. Число таких шагов может быть настолько велико, что достижение результата Q является практически неосуществимым. Однако в теории алгоритмов мы не учитываем практическую неосуществимость и считаем возможным выполнить любое конечное число шагов. Это положение называется абстракцией потенциальной осуществимости. Это же положение предполагает, что мы можем оперировать со сколь угодно большими объектами, например, сколь угодно длинными словами и т.п.
Описание алгоритмов и формулирование используемых правил могут осуществляться различными математическими средствами. Каждый способ задания алгоритма характеризуется абстрактным алфавитом и математическим формализмом. При этом вводится понятие алгоритмической системы, как общего способа задания алгоритмов
Синтаксический анализатор на стеках и lambda-выражениях (Axolotl)
В этой статье рассматривается практическая реализация синтаксического анализатора, основанного на стеке состояний и lambda-выражениях. Такой подход упрощает обработку синтаксиса, делая его гибким и легко масштабируемым. В статье описана архитектура анализатора, от лексического анализа до правил обработки состояний и обработки ошибок. Обсудим, как использовать состояния для синтаксического анализа ключевых конструкций и продемонстрируем простые, но эффективные методы для управления состояниями. Эта реализация — отличный выбор для быстрого прототипирования и собственных учебных языков.
Волновой алгоритм — это алгоритм поиска пути, который использует волновое распространение для определения кратчайшего пути от начальной вершины до целевой вершины.
В этой статье мы не будем рассматривать основной принцип данного алгоритма (поиск кратчайшего пути), а лишь обратимся к идее волнового алгоритма. Название алгоритма происходит от способа распространения, напоминающего распространение волн.
В прошлой части мы разбирали алгоритм поиска в ширину, который находил самый короткий путь между узлами, основываясь на количестве пройденных рёбер.
Теперь вы, как специалист на посту разработчика 2GIS изучили местность более подробно и поняли, что BFS не подходит для решения вашей задачи, так как дороги имеют разную протяженность и маршрут от A до B не может исчисляться в условной единице.
Давайте представим, что вы устроились много лет назад в 2GIS и вам выпала честь написать алгоритм, который будет прокладывать самый короткий автомобильный маршрут от точки A к точке B.
Вы отправляетесь искать информацию и к счастью натыкаетесь на эту статью, где мы с вами подробно обсудим популярные алгоритмы поиска пути.
