Алгоритмы *

Всем салют! Давайте решим задачу "Fruit Into Baskets"

Нужно собрать как можно больше фруктов на ферме, но с учетом правил, которые установил владелец фермы

Всем салют! Давайте решим задачу "Longest Substring Without Repeating Characters"

Дана строка s, нужно найти длину самой длинной подстроки без повторяющихся символов.

Всем привет! Меня зовут Денис Бобков, я сейчас обучаюсь на совместной магистерской программе ВШЭ и ШАД под названием «Современные компьютерные науки», а также работаю исследователем в AIRI в команде Controllable Generative AI лаборатории FusionBrain. Область моих исследований касается методов редактирования изображений.

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

Совсем недавно нашу статью приняли на одну из топ‑конференций по компьютерному зрению CVPR 2024 (эта конференция недавно стала самой цитируемой!). Наша статья про то, как можно редактировать лица в высоком качестве с помощью генеративной модели StyleGAN. Почитать её целиком можно на архиве, а здесь же я хотел кратко рассказать о том, что именно мы сделали.

Доброго времени суток, харбачитатель.

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

Вот мы и добрались до написания программ.
В этой статье напишем скрипты для расчётов резистивного расстояния и для моделирования случайных блужданий. В качестве ЯП был выбран Octave (всё-таки математикой занимаемся).

Алгоритм Хорспула используется для нахождения подстроки в строке. Например, у нас есть строка «The game is over» и подстрока «over». Алгоритм Хорспула вернет значение первого вхождения подстроки «over» в строку «The game is over», а именно 12. 

Фактически, данный алгоритм является упрощенным алгоритмом Бойера-Мура, который, считается работает лучше, чем стандартный алгоритм на случайных текстах, но в худшем случае его скорость равна |needle| * |haystack| вместо 3 х |haystack|. 

Тем не менее, для восприятия, на мой взгляд, он гораздо проще.

Итак, погнали.

Условие задачи с leetcode: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

Как работает алгоритм?

Строка и подстрока совмещаются по первому символу, и начинаются сравниваться от последнего символа к первому.

Для примера возьмем строку: «aabcdadbc» и подстроку «adb»

Совмещаются строки следующим образом (слева направо):

Привет, меня зовут Рома. Я работаю в KTS на позиции Python backend-разработчика. 

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

TLDR

В этой статье мы научим авто самостоятельно парковаться с помощью генетического алгоритма.

Мы создадим первое поколение авто с произвольными геномами, которое будет вести себя примерно так:

Примерно на сороковом поколении авто начнут понимать, что такое авто-парковка, и начнут приближаться к парковочному месту:

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

Мы живём в эпоху 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. Этот материал будет полезен тем разработчикам, которые хотят применять новые стандарты и подходы у себя на проектах.

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

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

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

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

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