Алгоритмы *

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

Модели выкладываются в формате float16, где на один вес выделяется 16 бит. Два года назад человечество научилось хорошо сжимать нейросети до 4 бит с помощью таких методов, как GPTQ. Но на этом исследователи не остановились, и сейчас актуальная задача — сжатие моделей до 2 бит, то есть в 8 раз. 

Недавно исследователи Yandex Research совместно с коллегами из IST Austria и KAUST предложили новый способ сжатия моделей в 8 раз с помощью комбинации методов AQLM и PV-tuning, который уже доступен разработчикам и исследователям по всему миру — код опубликован в репозитории GitHub. Специалисты также могут скачать сжатые с помощью наших методов популярные опенсорс-модели. Кроме того, мы выложили обучающие материалы, которые помогут разработчикам дообучить уменьшенные нейросети под свои сценарии.

О том, как исследователи пришли к сегодняшним результатам, мы расскажем на примере двух «конкурирующих» команд и их state-of-the-art алгоритмов сжатия — QuIP и AQLM. Это короткая, но увлекательная история «противостояния» исследователей, в которой каждые пару месяцев случаются новые повороты, появляются оптимизации и оригинальные подходы к решению проблем.

А знаете ли вы, как на самом деле работают таймеры в node.js? В этой статье мы разберемся, как хранятся таймеры, когда запускаются и как в целом все работает вплоть до системных вызовов.

Рекурсивные методы в Java — это методы, которые вызывают сами себя и требуют осторожности с их обращением.

Чтобы не увидеть «StackOverflowError» на экране, нужно помнить о двух штуках: базисе и шаге рекурсии.

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

Самый частый пример, который можно встретить в интернете при попытке найти информацию о рекурсии — нахождение факториала числа. Быстренько пройдемся по нему перед рассмотрением более интересной задачки с leetCode.

Поисковые системы — без них не представить сегодняшний мир, они облегчают доступ к информации и улучшают пользовательский опыт. Однако, чтобы поисковая система работала эффективно, необходимы некоторые алгоритмы для обработки строк. Одни из них — Knuth-Morris-Pratt и Boyer-Moore.

Их мы и рассмотрим в сегодняшней статье, начнем с первого.

Изучение чисел простых и составных, четных и нечетных длится не одно тысячелетие, а теория чисел пока далека от завершения. Даже для простых и понятных арифметических операций поиск обратных им операций на сегодняшний день не завершен. Например, для n-й степени числа обратной является операция извлечение корня n-й степени, для умножения чисел обратной является факторизация произведения, но простой и доступный алгоритм ее реализации до сих пор не открыт. Оказалось, что это очень большая и сложная проблема. Универсальный способ факторизации до сих не найден. В мире людей предпринимаются огромные усилия огромным числом математиков (судя по публикациям) для отыскания такого способа, но пока без особого успеха.

Известно несколько подходов к решению проблемы (алгоритм Ферма, числовое решето, эллиптические кривые, CFRAC, CLASNO, SQUFOF, Вильямса, Шенкса и др.), которые критикуются и не кажутся перспективными и которые даже не претендуют на универсальность. Автором публикации предлагается оригинальный подход к решению проблемы с претензией на универсальность, т.е. без каких либо ограничений на факторизуемые числа, в частности, ограничений на разрядность чисел.

Существо подхода состоит в разработке такой модели числа, которая использует концепцию закона распределения делителей (ЗРД) числа, открытого автором (публикация 2014г). Подход позволяет находить инволюцию в конечном числовом кольце вычетов (КЧКВ) по составному модулю N, путем разложения предлагаемой модели числа (аналогичного разложению кольца Пирса) в цикловые множества строк (ЦМС) модели.

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

Привет, Хабр! В предыдущем тексте мы рассмотрели все существующие матричные расширения. Возникает вопрос: ждать ли в ближайшее время новых расширений для матричных операций? Ответ — да, они разрабатываются прямо сейчас для архитектуры RISC-V. Новость может вызвать удивление, ведь в обзоре уже есть целых два матричных расширения RISC-V. Но оба эти расширения — кастомные, и, конечно же, в консорциуме RISC-V International задумались о разработке стандартного решения. 

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

Привет, друзья!

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

• Первая часть
• Третья часть
• Четвертая часть
• Пятая часть

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

Код, представленный в этой и других статьях серии, можно найти в этом репозитории.

Интересно? Тогда прошу под кат.

Дана система, состоящая из большого количества уравнений (необязательно линейных), где вам необходимо найти всего лишь несколько переменных. Как это сделать эффективно? Какой минимальный набор уравнений вам потребуется? В этой статье мы обсудим графовое представление систем уравнений, применим алгоритм Тарьяна и формализуем процесс на Python.

Привет, Хабр! Меня зовут Николай, я разработчик С++ в SimbirSoft. В предыдущей статье мы с вами рассмотрели применение стандартных алгоритмов в повседневном коде и их преимущества над обычными циклами. В продолжение этой темы мне хотелось бы рассказать о недостатках стандартных алгоритмов и способах их решения с помощью библиотеки Ranges. Практические примеры я разбил на три части: в первой показаны обычные циклы, во второй — вариант написания с помощью алгоритмов (но не всегда можно это сделать), в третьей – с использованием Ranges. Этот материал будет полезен тем разработчикам, которые хотят применять новые стандарты и подходы у себя на проектах.

Графы для меня особенная тема, в них есть нечто таинственное и мощное.

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

Я не буду рассказывать основы графов, они есть в Википедии.

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

Ну что, поехали, будет интересно!

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

Решил попробовать написать несколько статей о синтезе речи с поддержкой эмоций.

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

Но в процессе реализации, я использовал разные модели. Начиная от Fastpitch и Tocatron2 до Bark от Suno. Когда я тестировал свой первый MVP, то при длительном прослушивании синтетического голоса у меня начинала болеть голоса и возникало раздражение. Это особенно сильно возникало, когда озвучка голоса не соответствовала контексту. Возникал аналог эффекта «зловещей долины», но только для звука.

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

Первым моим шагом, была разработка модели «вдоха‑выдоха». Идея заключалась в том, что 99,999% человек говорит исключительно на выдохе (это касается и животных).

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

Свойство: Если какой‑то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что каждый из отрезков в нем не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь — зеленым цветом.

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

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

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

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

Я Frontend разработчик с опытом около 4 лет, и за это время алгоритмы в чистом виде мне ни разу не пригодились. Однако я понял, что использовал алгоритмы всю жизнь, просто не называл это так.

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

Один из вариантов эффективного решения — умножать по модулю, вообще при этом не используя операции деления, с помощью алгоритма Монтгомери.

Про него я и хотел бы поговорить.

Привет сообществу, в свободный час, решил поделиться с вами историей поиска работы в США в 2023-2024 году. На текущий момент живу в Беркли в Калифорнии. Нахожусь тут с лета 2021-го. И это, можно сказать, мой второй поиск работы.

Сейчас работаю в Realm, занимаюсь там созданием фичей вокруг генеративного ИИ и выведением их в прод. Два года довольно интенсивной работы, в настоящем кремнево-долинном стартапе. До этого работал в Сколтехе, в группе компьютерного зрения Е. Бурнаева, с ним и с другими невероятно талантливыми людьми.

Многие из вас когда‑то поступали (или будут поступать) в вузы. Это происходит обычно 1 раз в жизни, поэтому абитуриенты часто не понимают всей специфики работы приёмной комиссии, построения списков, сроков зачисления и т. п. Часто этим просто лень заниматься. Да плюс ещё эти правила приёма меняются каждый год (более того скажу — чаще чем раз в год) и уследить за этим обычному человеку не представляется возможным.

→ Первая часть

В мире современных технологий учёные всё чаще обращаются к природе за вдохновением для создания новых алгоритмов. Одним из таких примеров является бактериальный алгоритм поиска (Bacterial Foraging Algorithm, BFA), который моделирует процесс поиска пищи бактериями. С момента своего появления в 2002 году BFA привлекает внимание благодаря своей эффективности в решении сложных задач оптимизации. Мы рассмотрим, как именно работает этот алгоритм, какие биологические процессы лежат в его основе и как он может быть применён.