Все потоки
Поиск
Написать публикацию
Обновить
159.41

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

На чем основана логика? Часть 1. Алгебра множеств без аксиом

Уровень сложностиСредний
Время на прочтение9 мин
Количество просмотров8.1K

Сразу начну с гипотезы, положенной в основу данной статьи: вся классическая логика основана на множествах, точнее, на алгебре множеств. Должен сказать, что в современной логике и математике эта гипотеза считается ошибочной, так как еще на рубеже XIX и XX столетий сложилось убеждение (точнее, заблуждение), что понятие «множество» противоречиво. Мне представляется, что настала пора избавляться от этого и некоторых других заблуждений, связанных с логикой.

Читать далее

Фильтр Блума для эффективной синхронизации хеш-графов

Время на прочтение8 мин
Количество просмотров3.6K
В одном из совместных исследований нам с Хайди требовалось решить такую задачу. Допустим, нам требуется синхронизировать между двумя узлами хеш-граф, например, как в репозитории Git. В Git каждый коммит идентифицируется через соответствующий ему хеш, причём, в коммит могут включаться хеши коммитов-предшественников (то есть, конкретный коммит может содержать более одного хеша, если он получен слиянием). Мы хотели получить минимальное множество таких коммитов, которыми должны обменяться два узла, чтобы их графы получились одинаковыми.

Вы могли бы спросить: «а разве эта задача ещё не решена»? Git приходится выполнять такую операцию всякий раз, когда вы направляете ему команду git pull или git push! Да, так и есть, и некоторые случаи довольно просты, но другие гораздо сложнее. Более того, тот алгоритм, что используется в Git, не слишком хорошо документирован – в общем, мы полагали, что у нас может получиться лучше.
Читать дальше →

FizzBuzz for Senior

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров10K

Алоха всем.

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

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

Я наткнулся на интересную статью по интервью на Senior инженера C++. Там у парня спрашивают базовую задачу FizzBuzz.

В этой статье мы рассмотрим бенчмарки различных решений на Java, начиная от простых вариантов и заканчивая многопоточными реализациями. Давайте разбираться вместе!

Читать далее как "Senior" решает FizzBuzz

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

Время на прочтение24 мин
Количество просмотров25K

Векторные представления (эмбеддинги, векторы) — это по‑настоящему приятный инструмент, но в любом рассказе о векторных представлениях эта техника скрыта за ворохом каких‑то страшных словес.

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

Я выступал с лекцией о векторных представлениях на конференции PyBay 2023. Эта статья — улучшенная версия той самой лекции, и она должна быть интересна сама по себе, даже если не смотреть видео.

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

38-минутная видеоверсия

Вот видеоверсия той лекции, которую я прочитал на PyBay.

Читать далее

MIDI → Метр → MIDI

Уровень сложностиПростой
Время на прочтение11 мин
Количество просмотров2.8K

Статья поведёт нас через границу, где сходятся MIDI и метрическое время. В этом путешествии мы откроем брошюру по Международной системе единиц СИ, повстречаем файлы с более чем 6000 изменений темпа, столкнёмся с ошибками округления и напишем немного кода. Звучит заманчиво? Тогда добро пожаловать!

Читать далее

WF2M сеть. Формализм и математика workflow

Уровень сложностиПростой
Время на прочтение24 мин
Количество просмотров2.8K

Кому нужны книжки без картинок … или хоть стишков, не понимаю! – думала Алиса

Кому нужны регламенты бизнес-процессов без схемок … или хоть скриптов, не понимаю! –осенило бизнес-аналитика Алису

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

Существует широкий спектр workflow нотаций (стандартов): от классических ГОСТ 19.701-90 (ИСО 5807-85, flowchart), IDEF3, UML2-AD и XML-сериализованных BPMN\YAWL\XPDL\EPML до специфических, например, Дракон.

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

Ниже предложен математический формализм workflow-сетей: Модель WF2M (From workflow to mathematic), WF2M-сеть, как механизм формализации алгоритмов бизнес-процессов в части потока работ (workflow) путем задания аналитическими выражениями функций переходов между дискретными состояниями, маркировки состояний моделируемого объекта. Механизм (механика интерпретации алгоритма бизнес-процесса) заимствует от сетей Петри терминологию (маркировка сети, активация перехода, реализация перехода и т.п.) и частично концептуализм и классификацию. Предложенная WF2M сеть имеет иной механизм формализации (абстракцию) по сравнению с WF-nets.

Читать далее

Генезис-файлы. Часть II: Hashcash или как Адам Бэк разработал сердце Биткоина

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров2.5K

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

Читать далее

Генезис-файлы. Часть I: eCash Дэвида Чаума и зарождение мечты шифропанков

Уровень сложностиПростой
Время на прочтение10 мин
Количество просмотров2.3K

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

Читать далее

Изучаем и парсим биржевую информацию Мосбиржи. Наш первый парсер на Python, разбор кода

Время на прочтение7 мин
Количество просмотров29K

Как устроен ISS MOEX (информационно-статистический сервер Московской Биржи) и как можно парсить с него биржевые данные. Разбор кода программы. Это первое знакомство с MOEX, дальше будем изучать куда как более актуальный для алготрейдинга продукт мосбиржи - ALGOPACK. Однако перед этим общее знакомство с архитектурой iss moex должно быть. Стратегическая задача - использовать данные для алготрейдинга (работы торгового робота) напрямую с московской биржи.

Читать далее

Так всё-таки нужны программисту алгоритмы или нет?

Уровень сложностиСредний
Время на прочтение10 мин
Количество просмотров32K

Когда я был маленький, то на меня снизошла милость божЫя и ниспослала мне две книжки. Одна книжка была про бейсик для студентов каких-то там ВУЗов, а вторая - «Паскаль в иллюстрациях». По одному из абзацев первой книжки я в принципе научился программировать в пятом классе - там был мозголомающий отрывок с программой, заставляющей нолик летать по экрану, отталкиваясь от стенок. Вторая книжка, отданная мне соседом-алкашом, познакомила с алгоритмами. На дворе стояли 90-е — начало компьютерной эры человечества. Компьютера у меня при этом не было — я видел его пару раз в неделю на компьютерном кружке, ведущей которого была вчерашняя или даже сегодняшняя студентка, отпирающая и запирающая дверь — большего от неё нам и не требовалось.

Читать далее

Генезис-файлы. Пролог: день, когда криптография изменилась навсегда

Уровень сложностиПростой
Время на прочтение10 мин
Количество просмотров3.7K

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

Читать далее

Массивы в Kotlin

Уровень сложностиПростой
Время на прочтение17 мин
Количество просмотров13K

Я - Денис, Android-разработчик в «Лайв Тайпинге». В этой статье расскажу о массивах. Вы узнаете: как они устроены в памяти компьютера, особенности реализации в разных ЯП, оптимизациях, а также частых вопросах на собеседованиях.

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

Погнали!

Вычисление значений при угловом обходе квадратной матрицы

Время на прочтение8 мин
Количество просмотров3.9K

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

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

Читать далее

Ближайшие события

Удивительные клеточные автоматы: обратные и расширенные поколения

Уровень сложностиПростой
Время на прочтение7 мин
Количество просмотров3.9K


👾, Хабр!
Давно не виделись.

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

В первых статьях цикла мы познакомились с поколениями, одной из базовых и простейших модификаций стандартной конфигурации клеточных автоматов. До этого дополнения наши клетки могли находиться лишь в двух логических состояниях – пустая и живая (0 и 1, соответственно). После же, с новым параметром G, мы добавили третье положение – старение, что значило, что клетка, после выхода из состояния 1, начинала отмирать, доходя до состояния G-1, и только после возвращая состояние к 0. Во время старения клетки не влияют на соседей, не проходят проверки выживания, увеличивая собственный счётчик состояния с каждым шагом, но они и не позволяют новым клеткам рождаться на их месте.

Дополнение поколений является самым популярным, среди всех модификаций стандартной модели, и даже, фактически, оно стало частью правила по умолчанию, наравне с B/S, используясь практически во всех прочих расширениях, хотя использование поколений, конечно, опционально.

Со временем участники сообщества начали предлагать дополнения и к этому варианту конфигурации. На поверхности лежали многие вариации, как ещё возможно изменить или переставить состояния клеток. Одним из них были и обратные поколения, a.k.a. snoitareneG, с которых мы и начнём.
Читать дальше →

Искусственный интеллект для игры в Тетрис

Уровень сложностиСредний
Время на прочтение5 мин
Количество просмотров7.2K

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

Читать далее

Внутренний Я(ндекс)

Уровень сложностиПростой
Время на прочтение8 мин
Количество просмотров116K

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

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

Читать далее

Тридцать лет спустя: увеличение скорости квантовой факторизации

Время на прочтение10 мин
Количество просмотров5.4K

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

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

Читать далее

Польза создания однородных задач для параллельного вычисления

Уровень сложностиПростой
Время на прочтение14 мин
Количество просмотров3.6K

Как правильно использовать возможности параллельного программирования?
Зачем программистам математика и зачем знать алгоритмы?

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

Весь код из статьи находится здесь.

Читать далее

Зачем мне пылесос с ананасом или как оценить корректность рекомендательной системы

Уровень сложностиПростой
Время на прочтение10 мин
Количество просмотров3.6K

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

На связи участница профессионального сообщества NTA Ульянова Дарья.

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

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

К метрикам recsys

CatBoost

Уровень сложностиПростой
Время на прочтение11 мин
Количество просмотров38K

Добрый день, уважаемые читатели Хабра!

CatBoost – алгоритм, разработанный специалистами из Yandex, представляет собой нечто большее, чем просто ещё один инструмент в арсенале данных науки. CatBoost – это гармоничное сочетание инноваций и эффективности, особенно когда дело доходит до работы с категориальными данными.

Первые шаги CatBoost были сделаны в 2017 году, когда мир уже знал о таких гигантах, как XGBoost и LightGBM. В чем же заключается уникальность CatBoost? Его разработка была направлена на решение специфических проблем, связанных с категориальными данными – той самой головной боли многих специалистов в области машинного обучения. С тех пор CatBoost прошёл долгий путь развития и совершенствования, став не просто эффективным инструментом, но и частью больших исследовательских проектов в различных сферах от финансов до биоинформатики.

CatBoost выделяется на фоне других алгоритмов градиентного бустинга благодаря ряду ключевых особенностей:

Читать далее

Вклад авторов