Алгоритмы *

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

Как говорит Википедия «Поиск подстроки в строке — одна из простейших задач поиска информации», но это не совсем так, ниже я расскажу про разные алгоритмы решения и покажу примеры их реализации. Начнем!

Теперь к истокам задачи: часто, чтобы математическая модель была применима в реальном секторе, необходимо использовать очень много ограничений и большое количество переменных. Задачи, возникающие в бизнесе в реальных условиях, требуют использования моделей с большим количеством ограничений и большим количеством переменных.  Временами задача в лоб может и не решиться, поэтому были придуманы различные трюки. Один из них - метод « генерации столбцов» (Column generation).

Если вы увлекались математикой в возрасте до 12 лет, то, наверное, встречались с криптарифмами - арифметическими ребусами.

Арифметические ребусы хороши для тренировки у младшеклассников навыков логического мышления и счета в столбик. Однако и нам с вами может быть интересно поискать ответ на общий вопрос - а как, всё таки, алгоритмизировать процесс решения ребуса?

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

Всем привет! В данной статье рассмотрим паттерн проектирования Composite («Компоновщик»).

Начнем немного с теории.

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

Привет, Хабр!

Меня зовут Антон Черниговский, я участник профессионального сообщества NTA.

В публикации расскажу, как при решении задачи нечеткого сравнения строк, среди разных инструментов сравнения (по косинусному сходству, по сходству Левенштейна, по сходству Джаро‑Винклера) был выбран лучший вариант нечеткого сопоставления. Сравнение инструментов производилось исходя из скорости выполнения, правильности сравнения и простоты реализации, с помощью библиотек rapidfuzz и sklearn.

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

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

Будет полезна радиолюбителям, разработчикам и программистам для аналогичных задач.

Приветствую, сообщество Habr.

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

Представьте, что вам нужно ускорить работу огромной легаси-системы с 50 микросервисами, нагрузка на которую выросла в 2000 раз. При этом она обрабатывает затратные по времени операции, которые зависят друг от друга в плане данных. 

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

Есть несколько причин смотреть на игры как на нечто большее, чем просто на развлечения. Как станет яснее по ходу дела, многие игры основаны на сложных вычислительных задачах, хотя зачастую и с более низким «входным барьером», поскольку они редко требуют наличия формального образования.

Статья «When FTM Discovered MUSIC: Accurate WiFi-based Ranging in the Presence of Multipath» опубликована в материалах Международной конференции IEEE по компьютерным коммуникациям, которая прошла в Торонто, Канада, с 6 по 9 июля 2020 г. (IEEE International Conference on Computer Communications, INFOCOM 2020). Идеи, изложенные в этой публикации, получили дальнейшее развитие, в частности, в статье «FSI: A FTM Calibration Method Using Wi-Fi Physical Layer Information» («FSI: метод калибровки FTM с использованием информации о физическом уровне Wi-Fi»), опубликованной во 2-й части материалов 17-й Международной конференции по беспроводным алгоритмам, системам и приложениям, которая прошла в Даляне, Китай, с 24 по 26 ноября 2022 г. (Wireless Algorithms, Systems, and Applications; WASA 2022).

Аннотация. Недавно (относительно, в 2016 году – прим. пер.) стандартизирован IEEE протокол точного измерения времени (Fine Timing Measurement, FTM), основанный на измерении дальности по времени распространения сигнала (Time-Of-flight, TOF). Большое количество публикаций посвящены определению местоположения Wi-Fi-устройств в помещениях. С другой стороны доступных соответствующих решений по состоянию на данный момент очень мало. Поэтому появление FTM может стать поворотным моментом в преодолении разрыва между теорией и практикой. Эксперименты с первыми картами Wi-Fi, поддерживающими FTM, показывают, что в условиях прямой видимости (Line-Of-Sight, LOS), они обеспечивают точность до нескольких метров, но точность в условиях вне прямой видимости (Non-Line-Of-Sight, NLOS) может быть не такой высокой. В этой статье представлен FUSIC – первый метод, который улучшает точность измерений с помощью FTM в условиях LOS до значений в условиях NLOS без необходимости внесения каких-либо изменений в стандарт.

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // зловещий хакинг чисел с плавающей запятой на уровне битов
    i  = 0x5f3759df - ( i >> 1 );               // какого чёрта?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // первая итерация
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // вторая итерация, можно удалить

    return y;
}

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

Введение

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

Описание алгоритма

Алгоритм использует матрицу размером 5xN для хранения информации о графе и вычисления кратчайших путей. Каждая строка матрицы содержит следующую информацию:

ChatGPT генерирует разнообразный и привлекательный для человека текст. Но что делает текст «хорошим»? Это субъективно и зависит от контекста. Например, если вы попросите сочинить историю, нужен творческий подход. Если вы запрашиваете информацию, то хотите, чтобы она была правдивой. А если вы просите написать код, то ожидаете, что он будет исполняемым.

Вы наверняка слышали о том, что OpenAI привлекали сотрудников из Африки для помощи в разметке токсичности их ассистента. Менее известен факт найма реальных разработчиков, чтобы подготовить данные с пояснениями к коду на человечском языке.

Именно данные с фидбеком от людей позволили дообучить их языковую модель и сделать продукт таким «человечным».

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