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

Статьи, лекции и курсы из подборки помогут опытным специалистам «вспомнить все» перед собеседованием или погрузиться в тему алгоритмов, если вы пока в ней не сильны. 

Мы будем считать 1000,000,000 число Фибоначчи со всеми цифрами. Для этого я буду использовать продвинутый алгоритм для поиска чисел Фибоначчи. Тут не будет базовых алгоритмов на подобии матричного возведения в степень и проще. Но эта статья будет понятна и школьнику :-)

Еще в 1940-х годах, Джон фон Нейман и Станислав Улам изобрели моделирование Монте-Карло или численный метод Монте-Карло. Они назвали его в честь известного места азартных игр в Монако, поскольку этот метод имеет те же случайные характеристики, что и игра в рулетку.

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

Метод Монте-Карло используется в реальной жизни, например, в задачах, связанных с физикой, создании искусственного интеллекта, прогнозировании погоды и так далее, а также имеет огромное применение в финансах, где числовой метод Монте-Карло используется для расчёта стоимости акций, прогнозировании продаж, управления проектами и многого другого.^[1]

Основное преимущество использования Монте-Карло заключается в том, что этот метод обеспечивает множество возможных результатов и вероятность каждого из большого пула случайных выборок данных, однако, метод зависит от предположений, и это иногда может быть сложной задачей. Некоторые другие преимущества Монте‑Карло: он изучает поведение системы без её построения, обеспечивает в целом точные результаты, по сравнению с аналитическими моделями, помогает обнаружить неожиданное явление и поведение системы, а также выполнить анализ «что, если». ^[2]

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

Немного теории для общего понимания сути.

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

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Продолжаем знакомство с моделью числа и ее свойствами, а конкретно, с симметриями, которое этой публикацией завершается. Симметрии излагались на разном уровне представления модели: областей строк, отдельных строк, элементов одной строки и элементов разных строк. Для читателей, ознакомившимися с моими предыдущими статьей 1(О разложении модели числа), статьей 2 (О симметриях...) и др. предлагается продолжить знакомство с проблемой моделирования и исследования чисел. Объект натуральный ряд чисел (НРЧ) настолько богат известными и совершенно новыми свойствами, что само их перечисление потребовало бы много места и времени.
В этой публикации рассматриваются симметрии, связанные с идемпотентами кольца. Их роль в отображении строк-дублей совершенно не похожа ни на что из рассмотренного ранее, как, впрочем, и для других «осей симметрии». Если, например, центральная строка СММ раздвигала\ сдвигала строки-дубли на постоянный интервал, то линия раздела строк идемпотентов, наоборот, как бы «склеивает» (делает смежными) удаленные строки.

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

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

Алгоритм

Привет, Хабр! Эта статья для тех, кто хочет понять, когда стоит использовать sync.Map, а когда достаточно обычной map с мьютексом.

В Каруне этот вопрос иногда возникал на код ревью, поэтому такая статья мне показалась полезной. TLDR: sync.Map лучше работает на задачах, где много операций чтения, и ключи достаточно стабильны.

Внутреннее устройство sync.Map

sync.Map — это потокобезопасная реализация мапы в Go, оптимизированная для определенных сценариев использования.

Основная структура sync.Map выглядит примерно так:

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

type readOnly struct {
    m       map[interface{}]*entry
    amended bool
}

type entry struct {
    p unsafe.Pointer // *interface{}
}

Здесь мы видим несколько ключевых полей:

Продолжаем знакомство с моделью числа и ее свойствами, а конкретно, с симметриями на разном уровне представления модели: областей строк, отдельных строк, элементов одной строки и элементов разных строк. Для читателей, ознакомившимися с моими предыдущими статьей 1(О разложении модели числа), статьей 2 (О симметриях...) и др. предлагается продолжить знакомство с проблемой моделирования и исследования чисел. Объект - натуральный ряд чисел (НРЧ) настолько богат известными и совершенно новыми свойствами, что само их перечисление потребовало бы много места и времени.

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

Например, обращал ли кто-нибудь внимание на последовательности квадратичных вычетов (КВВ) элементов НРЧ по разным модулям, когда модель рассматриваем как фрагмент НРЧ или конечное числовое кольцо вычетов по модулю N. Эти квадраты следуют парами R_о, R₁ и получают вид (21 пара) для N = 1961. Пары КВК 484 = 22²;
529 =23² и 625 = 25²; 676 =26² образованы смежными числами, для N = 1961 они окаймляют в 4-м слое средний вычет r_cсс = 0; и для N = 2501 в 5-м слое средний вычет r_cсс = 0.

Почему во втором случае N = 2501 квадраты следуют вначале с флексиями 0, затем с 1²,
4= 2², 3², 4² ? Эти квадраты лежат в строках за пределами тривиальной области ТКВК и среди них нет кратных d_б.

В табличках приведен порядок следования КВВ = КВК полных квадратов, объединенных в пары (верх\низ), всего 42 квадрата (для N = 1961) и 48 квадратов (для N = 2501). Каждый квадрат получен в некоторой точке х_о и реализует решающий интервал (РИ), обеспечивающий получение решения задачи факторизации большого числа (ЗФБЧ) N, т.е. для вычисления делителей N. На основании закона распределения делителей можно записать соотношение d_i = х_о ±√КВК и при необходимости воспользоваться алгоритмом Евклида НОД.

Привет, Хабр! Я Андрей Соколов, инженер-программист в группе разработки математических библиотек. Месяц назад моя коллега Валерия запустила цикл статей про матричные расширения, ускоряющие операции над матрицами. Вы уже смогли узнать, что они делают и какие существуют, какие из них разрабатываются для открытой архитектуры RISC-V.

В заключительной статье цикла разберем пример использования матричного расширения T-Head под RISC-V для реализации алгоритма матричного умножения. Сначала кратко рассмотрим наивную скалярную реализацию и блочный вариант алгоритма. Затем реализуем аналогичный вариант с использованием матричного расширения — как для квадратных матриц, так и матриц произвольного размера. Второй случай интересен тем, что возникает необходимость обработки так называемых «хвостов» — блоков неправильной конфигурации. В заключение немного расскажу, какие идеи можно использовать для дальнейшей оптимизации матричного умножения, и поделюсь полезными ссылками.

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

Всем привет! Меня зовут Николай Лысенко, я занимаюсь рекомендательными системами в Яндекс Маркете. Сегодня хочу затронуть интересную тему: что делать, если в графе вычислений (aka нейронная сеть) возникает дискретное место, через которое не проходит градиент. Как многие знают, для решения этой проблемы есть такие методы, как REINFORCE и софтмакс Гумбеля (Gumbel-Softmax trick). О последнем и пойдёт речь.

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

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

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

Однажды мы решили, что грамотных инженеров эффективнее всего растить самим. Так 3 года назад родился Route 256 — курсы Ozon для разработчиков и тестировщиков уровней junior и middle.

Во время курса ведущие специалисты Ozon погружают в индустрию e-com, знакомят с актуальным стеком и бизнес-задачами. Самые успешные выпускники получают оффер в команду Ozon.

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

Уже много лет, начиная с 1966 года, во всем мире 20 июля отмечают Международный день шахмат. В честь недавно прошедшего праздника мы решили написать статью, в которой поговорим о шахматных задачах из курсов "Поколение Python".

Так получилось, что шахматные задачи являются одной из главных визиток наших курсов. Мы любим эти задачи потому, что они учат строить алгоритмы, находить закономерности, а также позволяют отточить работу с условными (if-else) и логическими (and и or) операторами.

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

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

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

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

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

Привет, Хабр! Меня зовут Дмитрий Крюков, я — научный сотрудник лаборатории «Сильный ИИ в медицине» в AIRI. Недавно мы опубликовали статью на стыке биологии старения и машинного обучения, в которой раскритиковали использование так называемых эпигенетических часов старения для измерения омоложения клеток в процессе клеточного репрограммирования. Тема часов старения уже поднималась на Хабре (раз, два, три) — настолько она стала популярной в современной биологии с приходом в неё методов машинного обучения. А уж тема репрограммирования клеток, которую Юрий Дейгин (кстати, рекомендую его блог на Хабре) с легкой руки назвал «эпиоткатом», так вообще превратилась в гигантское направление клеточной биологии и инженерии тканей. 

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

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

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

• Первая часть
• Вторая часть
• Четвертая часть
• Пятая часть

Сегодня мы будем говорить о таких структурах данных, как деревья. В этой статье мы рассмотрим двоичное дерево поиска, АВЛ-дерево и красно-черное дерево.

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

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

Лето — прекрасное время для того, чтобы неспешно заниматься тем, что нам нравится. А что нам нравится? Конечно же, ИИ!

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

1. Coursera “Deep Learning Specialization” (Специализация глубокое обучение)

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

2. Coursera “ChatGPT Prompt Engineering for Developers” (Промт инжиниринг ChatGPT для разработчиков)

Маленький урок, в рамках которого вы научитесь быстро и эффективно создавать новые приложения с использованием LLM. Курс охватывает работу LLM, практики инженерии запросов и использование API LLM для различных задач. Знаете, кто ведет этот курс? Лиза Фулфорд (OpenAI) и Эндрю Нг (DeepLearningAI) —неплохой каст, да?

3. edX “HarvardX: Data Science: Machine Learning” (ГарвардХ: Наука о данных: Машинное обучение)

Крутой бесплатный курс от Гарвардского университета по машинному обучению — надо! Здесь вы пройдетесь по основам машинного обучения; узнаете, как выполнять кросс-валидацию; изучите несколько популярных алгоритмов машинного обучения и др.

4. Harvard University “Machine Learning and AI with Python” (Машинное обучение и ИИ на Python)

Пару статей назад я уже рассматривала один из алгоритмов Бойера-Мура, с помощью которого можно было найти подстроку в строке.

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

Предлагаю сразу использовать его на примере задачи «Majority Element» с leetcode.

Условие здесь: https://leetcode.com/problems/most-frequent-even-element/description/

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Возвращаемся к Муру!

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

Не супер очевидно, но это число занимает больше половины элементов массива, т.е.

Уже много лет IT компании проводят алгоритмические собеседования при найме технических специалистов. Подход введенный в FAANG плавно перетек в большинство крупных компаний. Яндекс, Авито, Т-Банк и многие другие хотят проверить алгоритмические знания кандидатов. Но на практике такое собеседование оказывается бесполезным созвоном на 45 минут, который ничего не говорит о кандидате.

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

Но очень мало можно встретить критики и конкретного разбора проблем алгоритмических собеседований и их внедрения в воронку найма. Эта статья будет первой в цикле “в чем проблема алгоритмов”.

Кто-то может сказать: “О, человека не приняли в компанию из-за алгоритмов и он решил обидеться и сказать всем, что алгоритмы бесполезны”. Отчасти это так и было, но я решил не останавливаться на своем чувстве несправедливости и пошел дальше: адаптировал алгоритмы в компании, прошел все этапы в Google и даже решал алгоритмы на протяжении года.

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

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

Сейчас я просто хочу рассказать свою историю.

Хабр, жаркий июльский привет тебе от отдела компьютерной томографии компании Smart Engines! Раньше мы тебе рассказывали о задаче поиска положения смещенной и наклоненной оси вращения объекта в компьютерной томографии. Мы обещали рассказать о нами разработанном методе решения этой задачи, и вот, мы здесь! Мы вернулись к тебе с опубликованной статьей о нашем методе и с полученным патентом РФ!