Всё про Алгоритмы и Структуры данных

Метод «Безумного Макса» для тренировки проектировщиков кастомных вычисляющих структур

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

Как натренировать такое умение? Для новых домашних работ в программе Школы Синтеза Цифровых Схем мы решили разодрать на блоки реальный процессор и дать студентам задачу собирать разные специализированные вычислительные устройства из этих блоков, примерно как герои фильма "Безумный Макс: Дорога ярости" собирали свои боевые драндулеты из частей реальных автомобилей.

В качестве первой жертвы мы выбрали открытый RISC-V процессор Wally, полное описание которого будет в книге RISC-V Microprocessor System-On-Chip Design, by David Harris, James Stine, Sarah Harris, Rose Thompson, которая выходит в следущем году.

Нам не нужно ждать выхода книги, так как исходный код Wally уже есть на гитхабе. Технология такая: мы клонируем репо Wally рядом с репо домашних работ systemverilog-homework, оборачиваем блок работы с числами с плавающей точкой (FPU - Floating Point Unit) в наши собственные врапперы, после чего даем студентам серию заданий построить вычислители фиксированных функций из этих блоков.

https://habr.com/ru/articles/862734/

Алгоритмы и Структуры данных

Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена

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

И уж конечно, никогда при написании a * b мы не задумываемся о том, как реализовано умножение чисел a и b в нашем языке. Какие вообще есть алгоритмы умножения? Это какая‑то нетривиальная задача?

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

https://habr.com/ru/articles/719648/

Алгоритмы и Структуры данных

Рецепты TypeScript: перевод ключей объекта в camelCase

С вами снова Костя Логиновских — ведущий разработчик из Cloud.ru. Я уже делился TypeScript-рецептами в предыдущих статьях — вот первая и вторая — и теперь хочу рассказать про еще один. Наши рецепты — это готовый код, который можно применить в конкретных ситуациях, а в некоторых случаях и подогнать ситуацию под код.

https://habr.com/ru/companies/cloud_ru/articles/860778/

Алгоритмы и Структуры данных

Истинная сложность алгоритма Bubble Sort

Согласно описанию алгоритма следует, что мы должны проходить по массиву последовательно, сравнивая 2 элемента между собой, и если первый окажется больше следующего, то меняем их местами, таким образом дойдя до предпоследнего элемента, в конце окажется самое большое значение, т.е. пузырек всплывет. И затем мы повторяем данную итерацию, но уже без учета последнего элемента, т.к. он на месте, ставя перед ним следующий элемент по порядку или очередной пузырек. Повторяем итерации до тех пор, пока не останется сравнить 2а первых элемента и на этом массив будет отсортирован. И как итог, говорится что у данной сортировки сложность в худшем случае составляет - O(n2).

https://habr.com/ru/articles/720450/

Алгоритмы и Структуры данных

В этой одежде системы распознавания будут считать вас животным

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


Проект родился в 2019 году в Нью-Йорке. В то время Рэйчел училась в Технологическом институте моды и однажды, во время беседы с одним из инженеров калифорнийского университета в Беркли, у Дидеро возникла идея сделать моду союзником в отстаивании права на конфиденциальность.

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

https://habr.com/ru/articles/719368/

Алгоритмы и Структуры данных

Создание двуязычных субтитров к видео, распознавание и перевод речи

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

https://habr.com/ru/articles/862716/

Алгоритмы и Структуры данных

Может ли машина мыслить?

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

Краткий курс в дело, я создаю сильный искусственный интеллект (СИИ) и рассказываю об этом. На научную работу не претендую, просто рассказываю свои мысли, как оказалось, это полезно.

https://habr.com/ru/articles/862656/

Алгоритмы и Структуры данных

Бесплатные аналоги ChatGPT в 2024 году \ ТОП-10 Альтернатив ChatGPT:

Я люблю оригинальный ChatGPT, не подумайте, что это не так, но ~ 1,5 миллиона людей страдают от проблем, связанных с ним. Chat не работает, нет времени, чтобы разобраться, а остальные убеждены, что ChatGPT невозможно или сложно открыть из России, и зря, я слышал, что оригинальный ChatGPT хорош. Я расскажу об альтернативах, о которых, возможно, вы и не знали: приятных глазу, бесплатных и легкодоступных аналогах. Доступ к ним получается с помощью бесплатного VPN или вовсе без него! Также проведу тестовое расследование и выясню: какая нейросеть сильная (не ошибается) и решает задачи быстро.

Спойлер: Телеграм-боты лучше не использовать. Будет интересно, а вы получите опыт, который поможет вам при использовании ИИ.

https://habr.com/ru/articles/862600/

Алгоритмы и Структуры данных

Как финансовый аналитик может использовать нейросеть ChatGPT / ТОП-10 Промптов:

Вы — финансовый аналитик, часто сталкиваетесь с большим объемом данных и задач, требующих точного и быстрого анализа? Думаю, да, но времени на выполнение дел всегда мало, и сил в том числе. Человечество придумало множество вещей, ускоряющих обыденные дела, чтобы времени было больше, но, к сожалению, его все равно нет. Но вот чудо: в ноябре 2022 года компания OpenAI выпустила ChatGPT — помощника, который всегда тут, всегда работает и всегда развивается. Время пришло, и на момент выкладки этой статьи все финансовые аналитики, да что греха таить, почти все офисные работники могут применять ChatGPT в своей работе, экономя время!

В этой статье я поделюсь 10 полезными применениями нейросети для финансового аналитика. Также я подготовил промпты (запросы), чтобы вы просто скопировали запрос и отправили в чат GPT, чуть изменив под себя.

https://habr.com/ru/articles/862478/

Алгоритмы и Структуры данных

Зачем нам ИИ-агенты?

В этой статье я приведу некоторые доводы в пользу того, что при разработке LLM удобно прибегать к помощи интеллектуальных агентов (ИИ-агентов). Так удаётся переходить к решению всё более сложных задач. Под катом много интересного!

https://habr.com/ru/companies/piter/articles/862314/

Алгоритмы и Структуры данных

Разбираем алгоритм полнотекстового поиска BM25

BM25, или Best Match 25 — это широко используемый алгоритм полнотекстового поиска. Среди прочего, он по умолчанию применяется в Lucene/Elasticsearch и SQLite. В последнее время в рамках «гибридного поиска» часто начали комбинировать полнотекстовый поиск и поиск по схожести векторов. Мне захотелось понять, как работает полнотекстовый поиск и в частности BM25, поэтому в этой статье я постараюсь разобраться в этом.

https://habr.com/ru/articles/860830/

Алгоритмы и Структуры данных

Двухлинейный сумматор. Объективного измерения быстродействия в сравненнии произвести не удалось, но тем не менее…
В этот раз результатом стал двухлинейный сумматор. Намучался с ним достаточно - не одну неделю разрабатывал, в процессе какие только монстры не получались, но итогом вполне удовлетворён. Внушает надежды, что на его базе модно создать асинхронный триггер, который вообще будет в корне отличаться от предшественников. Объективных тестбенчей в сравнениях произвести не удалось по непонятным причинам - сначала они получились, но вечером следующего дня картина тестбенчей в корне изменилась, попробовал обойти трудности надстройкой над тестовой схемой - но увы, сигнал почему-то не отслеживается. Буду искать ошибки пару вечеров, а пока просто расскажу о том как собственно всё обстоит. Приступил сразу после предшествующих публикаций, разумеется всё в свободное время, пару недель вечеров было потрачено на попытки сократить цепь звеньев, потому как было ясно, что последовательная цепь лучше чем имеется на настоящий момент не получится. И вот однажды начиркал на клочке бумаги основу, а потом доработал в симуляторе. Получилось это, постил тут

https://habr.com/ru/articles/862214/

Алгоритмы и Структуры данных

О вреде GOTO-фобии (с примерами на C)

Готофобия – это боязнь использовать инструкции goto. Обычно возникает из-за непонимания и незнания контекста этой проблемы, а также из-за историй о незапамятных временах в истории программировании. Разработчики, страдающие готофобией, готовы жертвовать удобочитаемостью своего кода, только бы не прибегать к goto.

https://habr.com/ru/articles/720486/

Алгоритмы и Структуры данных

Пятничные клеточные автоматы: циклические конфигурации; камень-ножницы-бумага

На прошлой неделе мы снова расширили классическую «life-like» модель, добавив к ней параметр радиуса поиска соседей. Сегодня немного отойдём от этого вида и заглянем в область прочих конфигураций. Начнём с циклических КА.

https://habr.com/ru/companies/timeweb/articles/723414/

Алгоритмы и Структуры данных

OSDEV: Разработка аллокатора на С++ часть 2: Слияние блоков за константное время. Юнит тест для аллокатора

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

https://habr.com/ru/articles/861930/

Алгоритмы и Структуры данных

Создаём простой копирующий сборщик мусора

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

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

https://habr.com/ru/companies/ruvds/articles/861776/

Алгоритмы и Структуры данных

Как мы искали самый точный метод детектирования ключевых точек

Для автономного транспорта важно решить задачу автономной навигации. Один из методов автономной навигации – это SLAM (simultaneous localization and mapping), который в зависимости от типа используемых сенсоров бывает: визуальным, визуально-инерциальным, лидарным, радарным, RGBD и др.

Сегодня особый научный и практический интерес представляют методы визуально-инерциального SLAM (viSLAM) [1, 2], которые делятся на прямые и непрямые. Для непрямых методов viSLAM принципиально важна точность триангуляции трехмерных координат точек [3], а она в свою очередь зависит от точности работы детекторов ключевых точек [4].

Мы провели сравнительный анализ точности наиболее перспективных методов детектирования ключевых точек, как «эвристических» (hand-crafted), так и обучаемых. О наших экспериментах и их результатах расскажем ниже.

https://habr.com/ru/articles/724580/

Алгоритмы и Структуры данных

Как российские разработчики заставили GPT предсказывать биржевые котировки

18 мая 2024 на конференции «Тюльпаномания» Тихон Павлов, количественный аналитик «Финансовой компании Викинг» раскрыл секрет использования GPT-4 для прогнозирования биржевых котировок. Тема разделила аудиторию на скептиков и энтузиастов, породив жаркие дебаты о будущем трейдинга. Никто не остался равнодушным.

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

https://habr.com/ru/articles/861492/

Алгоритмы и Структуры данных

Рецепты TypeScript: типизированное преобразование объекта

Всем привет от ведущего разработчика из Cloud.ru! Как и обещал в предыдущей статье, продолжаю рассказывать про TypeScript-рецепты. Наши рецепты — это готовый код, который можно применить в конкретных ситуациях, а в некоторых случаях и подогнать ситуацию под код.

В этой статье предлагаю обсудить, как на обычном TypeScript приготовить такую функцию, которая из конфига роутинга по приложению вычислит объект, содержащий все пути внутри приложения. При этом сам объект роутинга будет иметь некоторую вложенность, а итоговая мапа с путями будет плоской структурой со значениями полей в виде строк. И всё это строго типизировано!

https://habr.com/ru/companies/cloud_ru/articles/860770/

Алгоритмы и Структуры данных