Обновить
205.74

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Похоже, я придумал свой алгоритм поиска кратчайшего пути (upd: меня опередили...)

Уровень сложностиСредний
Время на прочтение17 мин
Количество просмотров39K

Всем привет! Я реализовал, похоже, собственный алгоритм поиска кратчайшего пути с отрицательными ребрами графа.

Почему собственный? Я искал подобное решение, но не нашел, возможно, оно уже было реализовано, просто плохо поискал. Жду Нобелевскую премию =)

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

Читать далее

Яндекс запустил Нейро. Рассказываем, как он работает

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров90K

Сегодня мы запустили новый сервис Нейро — новый способ поиска ответов на вопросы. Пользователь может задать Нейро любой вопрос, а тот сам подберёт подходящие материалы в Поиске, проанализирует их и соберёт найденную информацию в одном ответе, подкрепив его ссылками на источники. Нейро объединил опыт Яндекса в создании поисковых технологий и больших языковых моделей. 

Меня зовут Андрей Сюткин, и я отвечаю за ML-трек в Нейро. В этой статье покажу, как выглядит архитектура Нейро и как формируются ответы на технологическом уровне. Ну и, конечно же, поговорим о нейросетях, в том числе о YandexGPT 3, без обучения которых новый сервис просто не увидел бы свет.

Читать далее

Фильтр Блума

Уровень сложностиСредний
Время на прочтение9 мин
Количество просмотров12K



У каждого разработчика есть набор инструментов для решения различных задач. Однако со временем возникает необходимость расширять этот набор, чтобы эффективно справляться с более сложными задачами. В этой статье я хочу познакомить вас с инструментом, которым вы, скорее всего, раньше не пользовались. И хотя он подходит для решения узкого спектра задач, его использование может оказаться весьма полезным. Знакомьтесь — "фильтр Блума" (Bloom filter).

Читать дальше →

Про решаемость пятнашек

Уровень сложностиСредний
Время на прочтение8 мин
Количество просмотров24K

Привет, я создатель известного в узких кругах приложения 15 Puzzle для Android.

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

Читать далее

Как устроено пространство, в котором думают языковые модели?

Уровень сложностиСложный
Время на прочтение5 мин
Количество просмотров20K

С момента выхода первой статьи «Attention is All You Need» я с жадностью и любопытством, присущими любому исследователю, пытаюсь углубиться во все особенности и свойства моделей на базе архитектуры трансформер. Но, если честно, я до сих пор не понимаю, как они работают и почему так хорошо обучаются. Очень хочу разобраться, в чём же причина такой эффективности этих моделей, и есть ли предел их возможностей?

Такому изучению трансформеров «под микроскопом» и посвящена наша научная работа, только что представленная на конференции EACL 2024, которая проходила на Мальте — «The Shape of Learning: Anisotropy and Intrinsic Dimensions in Transformer-Based Models». В этой работе мы сфокусировались на наблюдении за пространством эмбеддингов (активаций) на промежуточных слоях по мере обучения больших и маленьких языковых моделей (LM).

Читать далее

Преобразование Уолша-Адамара

Уровень сложностиСложный
Время на прочтение11 мин
Количество просмотров17K

На сайте hackerrank.com есть отличная задача. По заданному массиву short[] A; найти максимальное количество его подмассивов, xor элементов которых будет одинаковым. Сам этот xor тоже нужно найти.

Максимальная длина массива равна 105, так что квадратичный алгоритм не укладывается в лимит по времени исполнения. Я в своё время с этой задачей не справился и сдался, решив подсмотреть авторское решение. И в этот момент я понял почему не справился — автор предлагал решать задачу через дискретное преобразование Фурье.

Читать далее

Quantization Deep Dive, или Введение в современную квантизацию

Уровень сложностиСредний
Время на прочтение16 мин
Количество просмотров34K

Привет! Меня зовут Василий Землянов, я занимаюсь разработкой ML-инфраструктуры. Несколько лет я проработал в команде, которая делает споттер — специальную маленькую нейросетевую модельку, которая живёт в умных колонках Яндекса и ждёт от пользователя слова «Алиса». Одной из моих задач в этой команде была квантизация моделей. На пользовательских устройствах мало ресурсов, и мы решили, что за счёт квантизации сможем их сэкономить — так в итоге и вышло.

Потом я перешёл в команду YandexGPT. Вместо маленьких моделей я стал работать с очень крупными. Мне стало интересно, как устроена квантизация больших языковых моделей (LLM). Ещё меня очень впечатляли истории, где люди берут гигантские нейросети, квантизируют в 4 бита и умудряются запускать их на ноутбуках. Я решил разобраться, как это делается, и собрал материал на доклад для коллег и друзей. А потом пришла мысль поделиться знаниями с более широкой аудиторией, оформив их в статью. Так я и оказался на Хабре :)

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

Читать далее

Основные типы распределений вероятностей в примерах

Уровень сложностиСредний
Время на прочтение15 мин
Количество просмотров59K

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

Читать далее

Как калькуляторы вычисляют синус?

Уровень сложностиПростой
Время на прочтение3 мин
Количество просмотров59K

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

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

Читать далее

Челлендж по обработке миллиарда строк на Go: от 1 минуты 45 секунд до 4 секунд

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров27K

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

Я немного опоздал, соревнования проводились в январе. И на Java. Меня не особо интересует Java, зато давно интересует оптимизация кода на Go.

Этот челлендж был очень прост: обработать текстовый файл названий метеорологических станций и температур, и для каждой станции вывести минимальное, среднее и максимальное значение. Чтобы упростить задачу, было ещё несколько ограничений, однако я проигнорировал те, что относятся только к Java.

Читать далее

Переворачивающиеся при умножении числа

Уровень сложностиСредний
Время на прочтение7 мин
Количество просмотров21K

Здравствуйте!

Расскажу о серии задач, которая случайно возникла в процессе решения другой задачи. Мне на глаза попалось равенство:

81 * 27 = 2187

– Интересно, – подумал я. – А бывают ли ещё такие числа, чтобы цифры слева и справа повторялись?

Читать далее

Вороной, Манхэттен, рандом

Уровень сложностиПростой
Время на прочтение34 мин
Количество просмотров22K

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

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

Осторожно, очень много картинок!

Читать далее

Метод конечных элементов своими руками

Уровень сложностиСредний
Время на прочтение9 мин
Количество просмотров26K

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

Мы напишем МКЭ для расчёта упругой двумерной пластины на прочность и жёсткость. Код займёт 1200 строк. Туда войдёт всё: интерактивный редактор, разбиение модели на треугольные элементы, вычисление напряжений и деформаций, визуализация результата. Ни одна часть алгоритма не спрячется от нас в недрах MATLAB или NumPy. Код будет ужасно неоптимальным, но максимально ясным.

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

Читать далее

Ближайшие события

Два сапога — пара, а три — уже community: как алгоритмы на графах помогают собирать группы товаров

Время на прочтение14 мин
Количество просмотров28K

Привет, Хабр! Меня зовут Иван Антипов, я занимаюсь ML в команде матчинга Ozon. Наша команда разрабатывает алгоритмы поиска одинаковых товаров на сайте. Это позволяет покупателям находить более выгодные предложения, экономя время и деньги.

В этой статье мы обсудим кластеризацию на графах, задачу выделения сообществ, распад карате-клуба, self-supervised и unsupervised задачи — и как всё это связано с матчингом.

Читать далее

Генератор случайных чисел, который можно запустить в голове

Уровень сложностиСложный
Время на прочтение8 мин
Количество просмотров27K

Люди ужасно плохо справляются с придумыванием случайных чисел. Я хотел научиться быстро генерировать «достаточно случайные» числа. Мне не нужно было что-то совершенное, просто способ придумывания случайных цифр за полминуты. Поискав онлайн, я нашёл старый пост в Usenet, написанный Джорджем Марсалья:

Выберите двухразрядное число, допустим, 23. Оно будет вашим «порождающим значением» (seed).

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

Пример последовательности: 23 –> (2 + 6 * 3) = 20 –> (2 + 6 * 0) = 02 –> 12 –> 13 –> 19 –> 55 –> 35 –> …

Его период будет порядком множителя (6) в группе остатков, простых относительно модуля, 10 (в данном случае 59).

«Случайными цифрами» будет количество единиц двухразрядных чисел, то есть 3,0,2,2,3,9,5,… то есть члены последовательности mod 10.

Больше всего Марсалья известен своим набором тестов diehard-генераторов случайных чисел (RNG), так что он в этом понимает (здесь и далее под RNG я имею в виду генератор псевдослучайных чисел (PRNG)). Мне стало любопытно, почему это работает и как он выбрал 6.

Мы будем писать на Raku, языке для гремлинов. На случай, если вы тоже гремлин, под спойлерами я буду объяснять все странные особенности.
Читать дальше →

Разбираем самый маленький PNG в мире

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров39K

Самый миниатюрный PNG в мире весит 67 байт и представляет собой один чёрный пиксель. Выше вы видите его в 200-кратном увеличении.

Красота, не так ли?

Состоит этот файл из четырёх частей:

  1. Сигнатура PNG, одинаковая во всех файлах этого формата: 8 байт.
  2. Метаданные изображения, включая его размеры: 25 байт.
  3. Данные пикселя: 22 байта.
  4. Маркер «конец изображения»: 12 байт.

Далее я опишу этот файл подробнее и постараюсь объяснить принцип работы формата PNG.

В качестве небольшой затравки скажу, что в конце предстоит неожиданный поворот. Хотя, надеюсь, вам и без того интересно побольше узнать о PNG.
Читать дальше →

«Пора ли гнать на мороз Computer Vision — scientist'ов ?» (Fondation Models и вокруг)

Уровень сложностиСредний
Время на прочтение8 мин
Количество просмотров20K

Прошлый год в Computer Vision запомнился тем, что появилось множество больших претрейненных сетей (Fondation Models). Самая известная - GPT4v (ChatGPT с обработкой изображений).
В статье я попробую простым языком объяснить что это такое (для тех кто пропустил), как меняет индустрию. Какие задачи стало проще решать. Какие продукты появились в последнее время и появятся в будущем.
И можно ли уже выгнать на мороз лишних "ресерчеров"?!

Читать далее

Компилятор за выходные: синтаксические деревья

Уровень сложностиСредний
Время на прочтение11 мин
Количество просмотров30K

Вам когда-нибудь приходилось задаваться вопросом, как работает компилятор, но так руки и не дошли разобраться? Тогда этот текст для вас. Мне тоже не доводилось заглядывать под капот, но тут так случилось, что мне нужно прочитать курс лекций о компиляторах местным третьекурсникам. Кто встречался с некомпетентными преподавателями? Здравствуйте, это я :)

Итак, чтобы самому разобраться в теме, я собираюсь написать транслятор с эзотерического языка программирования wend (сокращение от week-end), который я только что сам придумал, в обычный ассемблер. Задача уложиться в несколько сотен строк питоновского кода. Основной репозиторий живёт на гитхабе (не забудьте заглянуть в мой профиль и посмотреть другие tiny* репозитории).

Читать далее

Сказ о том, как я за год решил более 600 leetcode задач

Уровень сложностиПростой
Время на прочтение7 мин
Количество просмотров149K

Всем салют!

Хочу рассказать вам историю о том, как я начинал с уровня — «не могу решить даже 1 easy задачу из 10» до уровня — «могу решить каждую вторую medium задачу» и прошел несколько coding сессий в таких компаниях как Meta, Booking, Careem, Avito...

Читать далее

Кто знает, что значит GPT в названии ChatGPT, могут дальше не читать

Уровень сложностиПростой
Время на прочтение11 мин
Количество просмотров66K

В настоящее время искусственный интеллект (ИИ) стремительно развивается. Мы являемся свидетелями интеллектуальной мощи таких нейросетей, как GPT-4 Turbo от OpenAI и Gemini Ultra от Google. В Интернете появляется огромное количество научных и популярных публикаций. Зачем же нужна еще одна статья про ИИ? Играя с ребенком в ChatGPT, я неожиданно осознал, что не понимаю значения аббревиатуры GPT. И, казалось бы, простая задача для айтишника, неожиданно превратилась в нетривиальное исследование архитектур современных нейросетей, которым я и хочу поделиться. Сгенерированная ИИ картинка, будет еще долго напоминать мою задумчивость при взгляде на многообразие и сложность современных нейросетей.

Читать далее

Вклад авторов