Всем доброго времени суток!
Публикую обзор книги "Грокаем алгоритмы". Автор: Адитья Бхаргава
Стоит читать? Да! Почему? Опишу в статье.
Алгоритмы - важны для программиста, а это лучшая книга для начала их изучения с нуля.
Решение задачи и пояснение алгоритма: Есть n стандартных игральных костей (6-ти гранных кубиков) со стандартным обозначением всех граней от 1 до 6. Бросаем все n кубики разом. Нужно найти вероятность выпадения числа k, а именно суммы всех значений, выпавших на этих кубиках
Когда я взялась решать задачку по динамическому программированию — реализовать алгоритм, который рассчитывает расстояние Левенштейна — мне пришлось послушать пару небольших лекций и прочесть несколько статей (приведу их в конце), чтобы разобраться. Я решила попытаться пересказать алгоритм настолько просто, чтобы по этому объяснению можно было снять ролик для тиктока (когда он снова возобновит свою деятельность в РФ). Дальше — мало формул и много картинок.
Существующие алгоритмы работающие с о смыслом слов:
• Векторное представление слов, GPT-3 - статистика
• Алгоритм Леска - подбор значения многозначного слова по статистике встречаемости слов в предложении
• Семантическая сеть - информационная модель предметной области, имеет вид ориентированного графа. Вершины графа соответствуют объектам предметной области, а дуги (ребра) задают отношения между ними. (см. рис. 1)
• В других вариантах - по сути поиск закономерностей через нейросети.
Совершенный алгоритм. Алгоритмы для NP-трудных задач - четвертая и заключительная часть лекций от Тима Рафгардена.
Для NP-трудных задач мы снова имеем треугольник, в котором для решения предлагается выбрать две характеристики из трех:
- Универсальность
- Правильность (точность)
- Скорость
Компромисс по универсальности рассмотрен вскользь на примере задач о рюкзаке и взвешенном независимом множестве (максимизация суммы весов несмежных вершин). Хотелось бы больше примеров на эту тему ведь данный подход может дать наилучший результат. Тут и там можно встретить дополнительные примеры частных случаев, но какая-либо систематизация по данной теме не приводится.
Неточные алгоритмы - самые многочисленные из рассмотренных в книге.
Префиксное дерево (нагруженное дерево, trie) — структура данных для эффективного поиска. С его помощью сложность поиска можно довести до оптимального уровня — длины ключа. Вспомним, что в хорошо сбалансированном бинарном дереве поиска данные можно найти за время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. В префиксном дереве — O(M), но увеличиваются требования к памяти. Подробнее о применении префиксных деревьев см. в этой статье.
Меня зовут Сергей Петренко, вот уже четыре года я работаю над репликацией в Tarantool, и сегодня хочу рассказать про слабые места алгоритма Raft и способы их преодоления. Эта статья — вольный пересказ нашего с Борисом Степаненко доклада на Hydra 2022. Если читатель не знаком с Raft, то предлагаю ознакомиться с моей статьёй о нём.
Привет, Хабр! Я работаю инженером компьютерного зрения в направлении искусственного интеллекта компании Норникель. Мы разрабатываем и внедряем модели с применением машинного обучения на наши производственные площадки.
В скоуп наших проектов попадают как системы, управляющие (или частично управляющие) технологическим процессом (например, флотация или плавка), так и системы промышленного машинного зрения, которые по сути представляют из себя одну из разновидностей датчиков.
В этой статье я расскажу про основные архитектуры генеративных сетей для задачи перевода изображения из одного домена в другой (image-to-image translation). В конце расскажу, для чего именно мы применяем синтетические данные и приведу примеры изображений, которых нам удалось достичь. Но перед погружением в данную тему рекомендую ознакомиться с тем, что такое свёрточная сеть, U-Net и генеративная сеть. Если же Вы готовы, поехали.
Архитектура Transformer улучшила производительность моделей глубокого обучения в таких областях, как компьютерное зрение и обработка естественного языка. Вместе с лучшей производительностью приходят и большие размеры моделей. Это создает проблемы производительности аппаратного обеспечения. Не разумно тренировать большие модели, такие как Vision Transformer, BERT, GPT, на одном графическом процессоре или одной машине. Существует острая потребность в обучении моделей в распределенной среде. Однако распределенное обучение, особенно параллелизм моделей, часто требует знаний в области компьютерных систем и архитектуры. Для исследователей ИИ остается сложной задачей внедрение сложных распределенных обучающих решений для своих моделей. В этой статье рассмотрим систему Colossal-AI, которая представляет собой единую параллельную обучающую систему, предназначенную для плавной интеграции различных парадигм методов распараллеливания. Она позволяет исследователям данных сосредоточиться на разработке архитектуры модели и отделяет проблемы распределенного обучения от процесса разработки.
Занимаясь goldengate-репликацией столкнулся с необходимостью выполнить сравнение таблицы, в исходной бд и её таблицы-реплики, в бд-приёмнике.
Для случая когда таблица и таблица-реплика обе имеют, одинаково устроенные ключи (как оно и д.б., по идее), есть замечательный пакет dbms_comparison.
Однако, что делать, если ключей нет никаких, нет и unique-индекса, с not-null. А такое — бывает.
Тут нужно велосипедить какое то решение.
Или договариваться с заказчиками репликации чтобы — добавляли ключи, на таблицы и им релевантные таблицы-реплики.
Добавление ключей — не всегда желательно, с т.з. заказчика, например потому что прикладной код может нехорошо отреагировать, на появление в таблице/таблице-реплике нового столбца.
Это можно обойти, сделав новый, ключевой столбец не видимым, gg-такие ключевые столбцы: поддерживает, это интересный способ, но о нём — в другой раз.
В этой статье — про велосипед.
Алгоритм ECDSA (Elliptic Curve Digital Signature Algorithm) — это реализация схемы цифровой подписи, основанная на использовании эллиптических кривых и модульной арифметики.
Мы оставим подробный разбор всех тонкостей этого алгоритма и соответствующей математической теории для будущих статей. Здесь же просто покажем основные идеи, за счет которых в ECDSA реализуются алгоритмы KeyGen, Sig и Ver.
Модульную арифметику пока полностью оставим в стороне. Эта тема несложная, но требует подробного рассмотрения. Поговорим сейчас только об эллиптических кривых — для начала нам этого будет достаточно.
Эллиптическая кривая в ECDSA — это линия на плоскости, задаваемая уравнением y²=x³+a∙x+b, где a и b — такие числа, что 4∙a³+27∙b²≠0. Например, Bitcoin и Ethereum используют кривую y²=x³+7 (рис. 1).
В предыдущей статье мы познакомились с терминами и определениями теории графов. В этой же статье обсудим различные способы представления графа в памяти компьютера для его обработки. Покажем, какие структуры данных можно использовать, а также проговорим преимущества и недостатки каждого способа.
Завершающий урок из цикла про линейную алгебру для 3D-приложений от Александра Паничева — ведущего разработчика логики в UNIGINE. В прошлом уроке мы разобрали углы Эйлера и кватернионы, а в этот раз говорим о матрицах и подводим итоги.
За 16 лет существования Хабра на его страницах не один, и даже не тысячу раз публиковались топики, так или иначе касающиеся вопросов решения задач оптимизации и алгоритмов в целом. В этой статье я хочу рассказать о достаточно новом алгоритме — «алгоритме диких гусей».
Прочитав название книги, многие из вас, наверное, скажут: «Ну вот, ещё одна книга для чайников. Опять нам будут рассказывать о том, что такое двоичная система исчисления и какие бывают циклы». Отчасти вы будете правы: в книге рассказывается о простых и базовых понятиях и принципах, которые должен знать каждый программист. Только вот «теоретический минимум», изложенный в книге, включает в себя множество интересных и полезных вещей, о которых мало пишут в подобной литературе начального уровня. Задайте себе вопрос: действительно ли вы так хорошо знаете основы того, что называется Computer Science?
Привет, Хабр. Мне не удалось найти русскоязычные статьи, посвященные генерации артов с помощью архитектуры CPPN, поэтому я сам расскажу о том, что можно с ней сделать. Это позволит скрасить пару вечеров и сгенерировать себе, например, обои на рабочий стол. А может и придумать что-нибудь серьезное.
Лично я воспользовался такой архитектурой, чтобы сгенерировать абстрактное музыкальное видео на одну из своих композиций. Плюс добавил к нему ритмических пульсаций, о чем расскажу далее.
Традиционно рынок спортивных событий воспринимается обществом весьма негативно. Принято считать, что какой-либо заработок в этой области маловероятен или невозможен вовсе, а мат. аппарат в лице теории вероятностей и математической статистики представляет мало интереса с точки зрения эффективного для заработка применения.
В какой-то мере такая позиция является обоснованной, ведь эффективность исследования этого рынка напрямую определяется пониманием, достичь которого не так просто. Сегодня мы с вами рассмотрим рынок спортивных событий под абсолютно новым углом, сделав акцент на системности и распределениях, а за одним и узнаем, при чём же здесь печатный станок.
Привет, Хабр! Сегодня речь пойдет о предсказывании будущего, поведении людей, математике и котиках.
В повседневной жизни, общаясь с людьми, мы всегда смотрим на поведение собеседника. Поведение человека может много о нем сказать: о его воспитании, привычках, увлечениях, принципах и о личности в целом. Для нас, как для социальных существ, это очень важная информация, так как мы делаем выводы о человеке: можно ли ему доверять, на что обратить внимание, стоит ли с ним вообще иметь дело. Для нас, как для работников сферы информационной безопасности, это очень важная информация, так как мы можем делать выводы: можно ли ему доверять, на что обратить внимание, стоит ли с ним вообще иметь дело.
