Алгоритмы *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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