Как стать автором
Обновить
282.9

Алгоритмы *

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

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

Как алгоритмы KMP и Boyer-Moore улучшают поисковые системы

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

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

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

Читать далее
Всего голосов 2: ↑0 и ↓2-2
Комментарии0

Новости

Разложение модели числа на подмодели

Время на прочтение20 мин
Количество просмотров984

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

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

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

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

Читать далее
Всего голосов 10: ↑7 и ↓3+8
Комментарии3

Заглянем в хрустальный шар: как продвигается разработка стандартных матричных расширений RISC-V

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

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

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

Читать далее
Всего голосов 27: ↑27 и ↓0+35
Комментарии5

JavaScript: структуры данных и алгоритмы. Часть 2

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


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


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



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


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


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

Читать дальше →
Всего голосов 13: ↑13 и ↓0+19
Комментарии2

Истории

Алгоритм Тарьяна для поиска минимального набора уравнений

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

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

Читать далее
Всего голосов 6: ↑6 и ↓0+10
Комментарии6

Возможности С++: от стандартных алгоритмов до диапазонов (Ranges)

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

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

Читать далее
Всего голосов 6: ↑5 и ↓1+7
Комментарии6

Его величество Граф

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

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

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

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

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

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

Читать далее
Всего голосов 11: ↑11 и ↓0+17
Комментарии21

Russkaya latinica

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

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

Читать далее
Всего голосов 36: ↑11 и ↓25-9
Комментарии200

Синтез эмоций. Модель вдох-выдох

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

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

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

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

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

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

Читать далее
Всего голосов 19: ↑19 и ↓0+27
Комментарии3

Об одном интересном свойстве триангуляции Делоне

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

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

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

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

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

Читать далее
Всего голосов 37: ↑36 и ↓1+44
Комментарии6

Поговорим с языковой моделью

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

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

Читать далее
Всего голосов 6: ↑0 и ↓6-6
Комментарии8

Стоит ли решать задачи на Codewars? Или как я полюбил алгоритмы

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

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

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

Читать далее
Всего голосов 26: ↑18 и ↓8+16
Комментарии8

Умножение Монтгомери

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

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

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

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

Читать далее
Всего голосов 29: ↑29 и ↓0+40
Комментарии7

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

Job Market в США моими глазами

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

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

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

Читать далее
Всего голосов 14: ↑11 и ↓3+11
Комментарии18

Бот поиска заявлений абитуриентов по СНИЛС

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

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

Читать далее
Всего голосов 5: ↑4 и ↓1+5
Комментарии7

Алгоритмы, вдохновлённые природой. Часть 2

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

Первая часть

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

Читать далее
Всего голосов 11: ↑10 и ↓1+12
Комментарии8

Панорама матричных расширений: от x86 до RISC-V

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

Матричное расширение ISA CPU… Что это и что оно делает? Уже из названия понятно, что это расширение позволяет ускорять операции над матрицами на CPU. Но задумывались ли вы когда-нибудь, какие они бывают, когда появились, кто и как их создает?

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

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

Читать далее
Всего голосов 58: ↑57 и ↓1+71
Комментарии38

JavaScript: структуры данных и алгоритмы. Часть 1

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


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


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



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


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


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

Читать дальше →
Всего голосов 18: ↑16 и ↓2+17
Комментарии1

Эффективный запуск и инференс LLM на своем сервере с нуля (часть 1)

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

Привет, Хабр! На связи CEO команды Compressa AI. Недавно обнаружил для себя крутой базовый курс по эффективному запуску и инференсу LLM моделей от легенды AI мира — Andrew NG и его платформы DeepLearning. Он полностью на английском языке в формате видео, поэтому я осмелился адаптировать его под формат Хабра на русском языке. Знания должны быть доступны всем и в удобной форме, так ведь?

Многие команды (включая и Compressa AI) начинали LLM проекты с использования облачных API. Но по мере развития все больше разработчиков хотят использовать open-source LLM, чтобы экономить на токенах, снижать latency, запускать fine-tuning на собственных данных и в целом меньше зависеть от внешних моделей.

Из этого курса вы узнаете детали эффективного обслуживания и дообучения open-source LLM, включая методы обработки множества запросов от нескольких пользователей. Используя несколько таких методов одновременно, вы можете улучшить как задержку (latency), так и пропускную способность (throughput). Например, благодаря применению последних open-source технологий в своем продукте, мы добились увеличения пропускной способности до 70x на 1 GPU в сравнении с дефолтными Hugging Face & PyTorch.

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

Читать далее
Всего голосов 23: ↑23 и ↓0+27
Комментарии12

Изучаем новые структуры данных для iOS разработчика

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

Мобильные разработчики редко сталкиваются в работе со сложными структурами данных. Как правило, в рутинных задачах вполне достаточно уметь использовать  ArrayDictionary и Set. Но сегодня не об этом. Хороших статей о том, как устроены эти структуры данных, предостаточно.

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

Читать далее
Всего голосов 5: ↑5 и ↓0+5
Комментарии2
1
23 ...

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