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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве первой жертвы мы выбрали открытый 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/

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

Головоломки с балансом. Поиск фальшивой монеты (часть 1)

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

Итак, как найти одну фальшивую монету среди нескольких, сравнивая вес различных наборов монет и используя наименьшее возможное количество сравнений?

Для начала проведём анализ проблемы.

https://habr.com/ru/companies/first/articles/858872/

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

Pushy на пределе: рост и развитие WebSocket-прокси Netflix

Pushy — это WebSocket‑сервер Netflix, который поддерживает долговременные WebSocket‑соединения с устройствами, на которых работает приложение Netflix. Благодаря этому данные с бэкенд‑сервисов можно отправлять на устройства по мере необходимости. При таком подходе нет нужды в постоянного опроса сервисов устройствами. За последние несколько лет Pushy пережил огромный рост, превратившись из сервиса для негарантированной доставки сообщений в неотъемлемую часть экосистемы Netflix. В этом материале вы узнаете о том, как мы развивали и масштабировали сервер Pushy, стремясь к тому, чтобы он хорошо справлялся со своими текущими обязанностями, и к тому, чтобы подготовить его к будущим нагрузкам. Он поддерживает сотни миллионов одновременных WebSocket‑подключений, доставляет адресатам сотни тысяч сообщений в секунду и удерживает стабильный уровень надёжности доставки сообщений в 99,999%.

https://habr.com/ru/companies/wunderfund/articles/861996/

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

Как мы приняли участие в соревновании по машинной диагностике затемнений в лёгких MIDRC XAI Challenge

Всем привет! Мы — научно‑исследовательская лаборатория «Сильный ИИ в медицине» в Институте AIRI. Наша группа разрабатывает решения на основе искусственного интеллекта в медицине. На днях стало известно, что мы заняли призовое, пятое место в конкурсе «MIDRC XAI Challenge: Decoding AI Decisions for Pneumonia on Chest Radiographs» с опытом участия в котором, мы хотели бы поделиться.

https://habr.com/ru/companies/airi/articles/862288/

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

GIMP Script-Fu Первый Дан. Удобная передача параметров в функцию

Script-fu (Тинисхема) передает параметры в функцию в виде списка и позволяет передавать значения в обязательные именованные параметры, функции с одним параметром принимающим неограниченное количество значений , или функции смешанного типа, с обязательными именованными параметрами и параметром остатком в виде списка.

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

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

Машинное обучение: Линейная регрессия. Теория и реализация. С нуля. На чистом Python

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

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

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

8 вопросов начинающего аналитика

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

Основную проблему, которую я наблюдаю в затягивающихся задачах:
Заказчик, который не понимает, какой эффект он получит от задачи.
Аналитики, которые боятся отстаивать свое мнение.

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

Сегодня детальнее я бы хотела поговорить о второй проблеме.

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

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

Как устроены очереди: визуальное объяснение

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

В этом посте мы изучим очереди в контексте HTTP-запросов. Начнём мы с простого, и постепенно будем вводить более сложные структуры очередей.

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

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

На чём учатся современные модели машинного перевода: опыт команды Яндекс Переводчика

В этой статье я расскажу о том, как из общедоступных текстов интернета в 100 ПБ найти терабайты суперчистых данных с переводами между любыми языками. Вы узнаете, почему эта задача требует обучения больше десятка различных вспомогательных ML‑моделей. А ещё коротко подсвечу, какое место в этом процессе занимает наша YandexGPT и что это за зверь такой — YandexGPT‑MT.

https://habr.com/ru/companies/yandex/articles/862718/

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

Как «яжепрограммист» построил всю свою родню

Алгоритм визуализации древа — вот что самое интересное и заставляет серьёзно загрузить голову. Про него и буду рассказывать. Для нетерпеливых сразу скажу, что исходники пока не выкладываем, но есть демонстрационный сайт, куда можно загрузить своё древо в формате GEDCOM — ссылка ближе к концу статьи.

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

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

Сегрегация общества: модель Шеллинга и распределение этнических групп в городах Израиля

Модель сегрегации Шеллинга – это агент-ориентированная модель, которая иллюстрирует, как индивидуальные тенденции в отношении соседей могут привести к сегрегации. Модель особенно полезна для изучения жилищной сегрегации этнических групп, где агенты представляют домовладельцев, которые переселяются в город. В модели каждый агент принадлежит к одной из двух групп и стремится жить в районе, где доля "друзей" достаточно высока: выше определенного порогового значения F. В зависимости от F, для групп равного размера, модель проживания по Шеллингу сходится либо к полной интеграции (случайное распределение), либо к сегрегации.

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

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

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

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

Применимость Java в искусственном интеллекте: 7 библиотек для нейросетей, которые стоит изучить

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

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

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

Как TF-IDF обошел SOTA-модель BERT4Rec в персональных рекомендациях

я Data Scientist персональных рекомендаций Wildberries. В этой статье разберем, как можно тюнингом TF-IDF побить BERT4Rec в ретро-тесте рекомендательной системы.

https://habr.com/ru/companies/wildberries/articles/861466/

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

Порядок из хаоса. Напишем клеточный автомат «Муравей Лэнгтона» на p5py в браузере и анимируем с помощью state machine

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

Продолжим экспериментировать с клеточными автоматами прямо в браузере (или в VS Code), используя Python + p5py, чтобы вы могли быстро опробовать свои идеи.

https://habr.com/ru/companies/sberbank/articles/864100/

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

Почему освоить Python невозможно, и почему это нормально | Pydon't

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

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

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

Меры центральности в Network Science

За последние 10 лет интерес к науке Network Science неимоверно возрос, что повлекло за собой закономерное развитие всевозможных инструментов для исследований в данной области. Одним из таких инструментов является python-библиотека NetworkX, предназначенная для анализа графов или других сетевых структур. Этот пост будет направлен на объяснение и демонстрацию работы основных мер центральности, вычисляемых в графах.

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

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

Что может быть проще (сложнее), чем упорядочивание чисел?

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

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

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