Как стать автором
Обновить
158.77

Алгоритмы *

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

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

Квантомания и криптография))

Уровень сложности Простой
Время на прочтение 12 мин
Количество просмотров 144
Блог компании FirstVDS Занимательные задачки Алгоритмы *

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

Возможно, всё не так страшно, но бережёного бог бережёт, поэтому чем раньше начнут внедряться постквантовые системы, тем вероятнее шанс избежать неприятных последствий этого технологического рывка. Сегодня существует несколько подходов к реализации такой защиты. Хотя, пожалуй, самый реалистичный в ближайшем будущем подход будет основываться на криптографии на основе хэшей. Примером такой системы является схема с открытым ключом в виде хэш-дерева Меркла, разработанная ещё в 1979 году и основанная на идеях Лэмпорта и Диффи.

Квантуем, сегодня мы с тобой квантуем!!!
Всего голосов 3: ↑3 и ↓0 +3
Комментарии 0

Новости

Удивительные клеточные автоматы: клетки-киллеры, BSFK[L]

Уровень сложности Простой
Время на прочтение 6 мин
Количество просмотров 415
Блог компании Timeweb Cloud Алгоритмы *Математика *Научно-популярное Программирование *
Обзор


👾, Хабр!

После небольшого перерыва продолжим нашу экскурсию по различным вариациям классической конфигурации клеточных автоматов. Сегодня мы рассмотрим правила с «деструктивными клетками». Первоначальный вид подобной модификации, известной как BSFK, предложил энтузиаст под ником c0b0p0, всего 9 лет назад, спустя более чем 40 лет, после первого описания «Жизни» Джона Конвея.
Что здесь происходит (для новых читателей серии)
В этой серии мы разбираем клеточные автоматы – дискретную модель, основой которой является сетка из ячеек-клеток, которые изменяют (или не изменяют) своё состояние в зависимости от количества соседей.
Учёт соседей определяется правилами, которые устанавливаются нами. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.
Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.
В каждой статье серии мы углубляемся в данную конфигурацию, добавляя новые параметры, либо дополняя существующие. Иногда заглядываем и в прочие конфигурации.
Начало серии здесь, если желаете ознакомиться последовательно.
Рассматриваемая модификация предполагает три состояния клеток – мёртвые, живые и деструктивные, и добавляет два числовых параметра в наше правило – F и K. Переходы говорят, что если у живой клетки есть как минимум K деструктивных соседей («киллеров»), она умирает. Если это условие не выполняется, то, как и в прошлых конфигурациях, происходит проверка на вхождение в множество S, но с тем отличием, что при отсутствии вхождения такая клетка не умирает, а сама превращается в киллера. Киллеры же умирают, если у них есть как минимум один живой сосед.

К условию зарождения жизни на пустых (мёртвых) клетках по числу живых соседей B добавляется «и количество соседей-киллеров не больше F».
Читать дальше →
Всего голосов 8: ↑7 и ↓1 +6
Комментарии 0

Тестируем нестандартный алгоритм обработки реальных данных в Excel на Visual Basic for Application

Время на прочтение 2 мин
Количество просмотров 488
Алгоритмы *Visual Basic for Applications *

В первом приближении надо загрузить wav или mp3 файл с музыкой в Excel, провести над загруженными данными Digital Signal Processing (DSP) или Цифровую Обработку Сигнала (ЦОС) по определенному алгоритму на Visual Basic for Application (VBA) ), сохранить результат в wav файл и прослушать его.

Читать далее
Всего голосов 9: ↑9 и ↓0 +9
Комментарии 11

Алгоритм backtracking

Время на прочтение 10 мин
Количество просмотров 1.5K
Блог компании OTUS Алгоритмы *

Автор статьи: Артем Михайлов

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

Читать далее
Всего голосов 5: ↑5 и ↓0 +5
Комментарии 0

Истории

Бинарное дерево поиска в Swift

Уровень сложности Простой
Время на прочтение 10 мин
Количество просмотров 689
Алгоритмы *Swift *

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

Читать далее
Всего голосов 2: ↑1 и ↓1 0
Комментарии 2

Преобразование Хафа

Уровень сложности Простой
Время на прочтение 3 мин
Количество просмотров 1.4K
Блог компании OTUS Алгоритмы *Обработка изображений *
Туториал

Автор статьи: Рустем Галиев

Сегодня мы рассмотрим преобразование Хафа — популярный метод обнаружения фигур среди граней и границ. Поговорим про использование преобразования Хафа для обнаружения линий и кругов.

Читать далее
Всего голосов 23: ↑15 и ↓8 +7
Комментарии 4

Архитектура кеша DragonflyDB

Уровень сложности Средний
Время на прочтение 6 мин
Количество просмотров 1.2K
Высокая производительность *Алгоритмы *Хранилища данных *
Обзор
Перевод

DragonflyDB - молодая in-memory база данных, написанная на C++ и совместимая с Redis (не форк). Под капотом используется многопоточная архитектура (в отличии от однопоточного Redis) для лучшей утилизации современных процессоров и более простого вертикального масштабирования.

Особое внимание в DragonflyDB привлекает устройство кеша и его очистки, которая должна превосходить известные LRU и LFU политики.

Читать далее
Всего голосов 5: ↑5 и ↓0 +5
Комментарии 17

Алгоритмы компрессии данных: принципы и эффективность

Уровень сложности Средний
Время на прочтение 12 мин
Количество просмотров 2.4K
Блог компании OTUS Алгоритмы *Сжатие данных *
Обзор


Автор статьи: Артем Михайлов

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

Компрессия данных — это процесс сокращения объема данных без потерь или с минимальной потерей информации. Путем применения алгоритмов и методов компрессии, мы можем существенно уменьшить размер данных, сохраняя при этом их суть и основные характеристики. Это может быть полезно во множестве ситуаций, начиная от экономии места на хранилище и ускорения передачи данных до минимизации затрат на интернет-трафик и повышения производительности систем обработки и анализа информации.
Читать дальше →
Всего голосов 26: ↑22 и ↓4 +18
Комментарии 2

Развлечения с хеш-коллизиями

Уровень сложности Средний
Время на прочтение 9 мин
Количество просмотров 2.3K
Блог компании Wunder Fund Разработка веб-сайтов *Python *Программирование *Алгоритмы *
Перевод

Мой друг и коллега по цеху, блоггер Сэм, недавно опубликовал своё третье иллюстрированное руководство, темой которого стало хеширование. Нет острой необходимости читать его руководство перед прочтением моей статьи, но я очень рекомендую вам это сделать. Хотя бы ради того, чтобы посмотреть на восхитительные анимации, от которых невозможно оторваться. Честно — они просто потрясающие. Тут, к сожалению, анимаций вы не найдёте, поэтому насмотритесь на них в той статье, а потом возвращайтесь сюда. Здесь вы сможете немного позабавиться поиском коллизий алгоритма хеширования MurmurHash3.

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

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

Читать далее
Всего голосов 20: ↑17 и ↓3 +14
Комментарии 4

Кодеки новой эпохи: HEVC, AV1, VVC и нейросети

Уровень сложности Средний
Время на прочтение 6 мин
Количество просмотров 8.2K
Блог компании RUVDS.com Работа с видео *Алгоритмы *Сжатие данных *Машинное обучение *
Аналитика
Сжатие с учётом контекста, источник: WaveOne (сайт удалён)

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

В новом поколении кодеков алгоритмы машинного обучения используются для анализа и понимания визуального содержания видео, выявления избыточных данных и более эффективного сжатия. Вместо написанных вручную алгоритмов, тут применяют методы Software 2.0, основанные на обучении. Данная область развивается на протяжении десятилетий, но в последние годы получила сильный толчок. Все знают, что в 2017 году произошёл прорыв в разработке ИИ благодаря изобретению трансформеров. В свою очередь, они основаны на концепции внимания, которую придумали в 90-е. Эта техника впервые позволила соотносить друг с другом отдельные части текста или видеокадра.
Читать дальше →
Всего голосов 54: ↑52 и ↓2 +50
Комментарии 24

Одна задачка на литкоде

Время на прочтение 2 мин
Количество просмотров 7.8K
Алгоритмы *

Иногда хочется решить задачу просто потому что решение легко проверить, прям сразу для множество вариантов. Взяли список из 25 элементов, отсортировали его, и применили искомую функцию 25 раз, профит. Плюс задачка напоминает обложку тетрадки по арифметике за пятый класс, там где табличка произведений, ну та где находим пятый столбец и седьмой ряд и на пересечений их будет произведение. Там же в табличке видно что 6x6 - это квадрат, а 9x4 это совсем не квадрат (скорее ближе к прямоугольнику) хотя площадь у них равная. Так вот, "литкод" хочет чтобы мы нашли n-ый элемент в данной табличке по возрастанию.

Читать далее
Всего голосов 23: ↑2 и ↓21 -19
Комментарии 25

Генерация и валидация чисел по алгоритму Луна

Уровень сложности Простой
Время на прочтение 6 мин
Количество просмотров 4.5K
PHP *Алгоритмы *Laravel *
Обзор

Алгоритм Луна (Luhn algorithm) - это процесс вычисления контрольной цифры для числа в соответствии со стандартом ISO/IEC 7812. Процесс предназначен, в первую очередь, для выявления ошибок, вызванных с непреднамеренным искажением данных. Например, при ручном вводе номера карты или любого другого числа.

Разберём как он работает и рассмотрим инструмент для формирования номеров по алгоритму.

Читать далее
Всего голосов 15: ↑13 и ↓2 +11
Комментарии 31

Волновой алгоритм

Уровень сложности Средний
Время на прочтение 7 мин
Количество просмотров 4.8K
Программирование *C++ *Алгоритмы *
Туториал

Волновой алгоритм — алгоритм поиска пути, алгоритм поиска кратчайшего пути. Принадлежит к алгоритмам, основанным на методах поиска в ширину.

Читать далее
Всего голосов 7: ↑6 и ↓1 +5
Комментарии 14

Вычислительная сложность некоторых игр и головоломок (часть 2)

Уровень сложности Простой
Время на прочтение 14 мин
Количество просмотров 2.1K
Блог компании FirstVDS Алгоритмы *Математика *Логические игры

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

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

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

Читать далее
Всего голосов 14: ↑14 и ↓0 +14
Комментарии 4

Разработка — всё? Действительно ли нас всех заменят роботы

Уровень сложности Простой
Время на прочтение 12 мин
Количество просмотров 6.9K
Блог компании AvitoTech Алгоритмы *Машинное обучение *Визуальное программирование *
Мнение

Александр Пряхин, руководитель разработки юнита в Авито Работа, рассказал, так ли мрачно выглядит будущее для разработчиков «из плоти и крови» на фоне активного развития No Code, Low Code и нейросетей.

Читать далее
Всего голосов 16: ↑13 и ↓3 +10
Комментарии 19

Каково расстояние между «Будапештом» и «Бухарестом» или об отождествлении слов с помощью расстояния Левенштейна

Уровень сложности Средний
Время на прочтение 6 мин
Количество просмотров 1.5K
Блог компании Smart Engines Алгоритмы *Обработка изображений *Математика *

Каждый из нас из школы помнит определение Евклидова расстояния между двумя точками на плоскости. С помощью расстояния Евклида можно вычислить расстояние между двумя точками на карте, например, между вашим местоположением и станцией метро. Но для пешехода в Нью-Йорке расстояние между двумя точками в городе будет отличаться от расстояния Евклида между двумя точками из-за невозможности передвигаться иначе, как по проезжим улицам, пересекающимся под прямыми углами. Такое расстояние так и называется: "расстояние городских кварталов" или манхэттенское расстояние. При любом способе расстояние характеризует меру близости точек. В сегодняшней статье мы расскажем о способах вычисления расстояния между двумя словами.

Читать далее
Всего голосов 5: ↑4 и ↓1 +3
Комментарии 6

Проектирование алгоритма под рекомендательную систему

Уровень сложности Средний
Время на прочтение 5 мин
Количество просмотров 2.2K
Алгоритмы *
Из песочницы

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

Читать далее
Всего голосов 9: ↑7 и ↓2 +5
Комментарии 14

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

Уровень сложности Средний
Время на прочтение 13 мин
Количество просмотров 7.9K
Блог компании RUVDS.com Программирование *C++ *Алгоритмы *Хранение данных *
Туториал
Перевод

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

Ресурсы


Прежде чем мы приступим к разбору того, что я сделал, важно упомянуть очень полезные ресурсы для создания собственного текстового редактора:

  • Build Your Own Text Editor — наверно, самый фундаментальный пост о создании текстового редактора с нуля, который я видел. Это превосходный туториал на случай, если вы хотите начать писать собственный текстовый редактор. Стоит заметить, что в редакторе из этого туториала в качестве внутренней структуры для текста используется, по сути, вектор строк.
  • Text Editor: Data Structures — отличный обзор множества структур данных, которые можно использовать при реализации текстового редактора. (Спойлер: как минимум одна из них будет рассмотрена в моём посте)
  • Плейлист Ded (Text Editor) на YouTube — это потрясающая серия, в которой @tscoding фиксирует процесс создания с нуля текстового редактора. Эти видео стали для меня источником вдохновения.

Зачем?


Если в сети есть так много хороших ресурсов о создании собственного текстового редактора (не говоря уже о том, что уже существует множество феноменальных текстовых редакторов), то зачем я это пишу? На то есть несколько причин:

  1. Я хотел заняться проектом, непохожим ни на один свой прошлый.
  2. Я хотел создать инструмент, которым смогу пользоваться.
  3. Мне всегда хотелось глубже разобраться с созданием собственных структур данных.
Читать дальше →
Всего голосов 56: ↑55 и ↓1 +54
Комментарии 18

Шумные разработчики, или Какие виды шума бывают?

Время на прочтение 4 мин
Количество просмотров 2.4K
Работа с 3D-графикой *Разработка игр *Алгоритмы *Обработка изображений *Дизайн игр *
Из песочницы

Играясь с генерацией карт высот в unity, я заметил одну неприятную тенденцию: большинство статей и материалов рассказывают либо о Value Noise, либо о Perlin Noise, либо о Voronoi Noise. Возможно я плохо искал, но это не отменяет того факта, что я сел писать эту статью, поэтому для всех нуждающихся я сделал шпаргалку.

Продолжение следует
Всего голосов 6: ↑6 и ↓0 +6
Комментарии 6

Вероятностные структуры данных и где они обитают

Уровень сложности Средний
Время на прочтение 3 мин
Количество просмотров 5.3K
Алгоритмы *
Туториал

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

В этой статье я сделаю обзор таких структур данных и расскажу, какую пользу они могут принести на практике. К базовым вероятностным структурам данных можно отнести фильтр Блума, HyperLogLog и Count-Min Sketch.

Читать далее
Всего голосов 32: ↑32 и ↓0 +32
Комментарии 8

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