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

Алгоритмы *

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

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

Введение в трассировку лучей: простой метод создания 3D-изображений. Часть 2 — прямая трассировка

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

Феномен из прошлой статьи, описанный Ибн аль-Хайсамом, объясняет, почему мы видим объекты. На основе его наблюдений можно сделать два интересных замечания: во-первых, без света мы ничего не можем видеть, а во-вторых, без объектов в нашем окружении мы не можем видеть свет. Если бы мы путешествовали в межгалактическом пространстве, именно это обычно и происходило бы. Если вокруг нас нет материи, мы не можем видеть ничего, кроме темноты, даже несмотря на то, что фотоны потенциально движутся через это пространство (конечно, если бы фотоны были, они должны были бы откуда-то взяться. И если бы вы посмотрели на них прямо, если бы они попали вам в глаза, вы бы увидели изображение объекта, от которого они отразились или испустились).

Отрендерить далее
Всего голосов 10: ↑8 и ↓2 +6
Комментарии 14

Введение в трассировку лучей: простой метод создания 3D-изображений. Часть 1 — как создается изображение?

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

Введение в трассировку лучей: простой метод создания 3D-изображений
Часть 1 - как создается изображение?

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

Отрендерить статью полностью
Всего голосов 11: ↑8 и ↓3 +5
Комментарии 9

Сжать и не пожалеть: как работает сжатие без потерь

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

Более 9 миллиардов гигабайт информации ежедневно путешествуют по интернету, заставляя постоянно искать все новые и новые методы упаковки данных. Самые эффективные решения используют подходы, которые позволяют достичь большей плотности за счет "потерь" информации в процессе сжатия. В то же время очень мало внимания уделяется сжатию без потерь. Почему? Ответ прост - методы сжатия без потерь уже невероятно эффективны. С их помощью работает буквально всё, от формата PNG до утилиты PKZip. И это все благодаря студенту, что захотел пропустить экзамен.

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

Поиск с помощью регулярных выражений: подход с Виртуальной Машиной

Уровень сложности Сложный
Время на прочтение 28 мин
Количество просмотров 2.7K

Это вторая статья из серии статей про устройство движков поиска по регулярным выражениям от одного из авторов библиотеки регулярных выражений RE2. Статья датируется 2009 годом, но не потеряла своей актуальности. Перевод первой статьи можной прочитать здесь.

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

Так же в статье приведена любопытнейшая историческая справка и особенности реализации POSIX.

Об ошибка, опечатках и неточностях большая просьба сообщать.

Заблудиться в тёмном лесу
Всего голосов 8: ↑8 и ↓0 +8
Комментарии 2

Истории

Приложения алгебры кортежей. Часть 2. Математическая модель вопроса

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

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

Об алгебре кортежей (АК) и ее использовании для логико-семантического анализа было рассказано в моей статье в Хабре. В комментариях к статье предлагалось обратить внимание на функцию SELECT в языке SQL, которая соответствует операции Selection (Выборка) в реляционной алгебре. Эта операцию можно рассматривать как один из вариантов математической модели вопроса.

Предлагаемый здесь вариант смысла вопроса заключается в том, что в вопросе заданы некоторые ограничения (область знания, ситуация, значения некоторых атрибутов и т.д.), которые требуется использовать для того, чтобы найти или вычислить значение определенного атрибута или проверить правильность заданных в вопросе соотношений. Эта семантика применима к восполняющим вопросам типа «Что?», «Где?», «Когда?», к уточняющим вопросам типа «Верно ли, что А?» и к ИЛИ-вопросам типа «Что правильно: А или Б?». Назовем такие вопросы ограничительными. Их можно считать вариантами известной в искусственном интеллекте задачи удовлетворения ограничений.

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

Helena.4.0 – новый алгоритм для подбора гиперпараметров

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

С целью автоматизации процесса подбора гиперпараметров автором данной статьи разработан алгоритм Helena.4.0. Конечной целью является создание автоматической системы построения моделей (auto-ML), которая бы подбирала гиперпараметры за минимальное время.

С помощью алгоритма Helena.4.0 можно подбирать гиперпараметры для моделей градиентного бустинга, нейросетей, и более того – для генетических алгоритмов. Автор считает, что алгоритмы Helena могут заменить в генетических алгоритмах генеративную часть – т.е. уйти от биологических аналогий, заменив псевдобиологическую генерацию признаков путем процедур «скрещивания» и «мутаций» на генерацию с помощью указанных алгоритмов.

Для поиска максимума функции алгоритм Helena.4.0 использует только ее значения, и  не используют первые и последующие производные. Таким образом, этот алгоритм не требуют ни дифференцируемости, ни непрерывности максимизируемой функции.

Сравнение алгоритма Helena.4.0 с наиболее популярными конкурентами (Optuna, HyperOpt, RandomSearch) показывает его высокую конкурентоспособность.

В отличие от других алгоритмов, не использующих градиент для максимизации функции, алгоритмов Helena.4.0 способен успешно противостоять комбинаторному взрыву. Т.е. алгоритм Helena.4.0 достаточно стабильно работает, несмотря на увеличение размерности пространства. Время, необходимое алгоритму Helena.4.0 для поиска максимума функции, оценивается как квадратичная функция от размерности пространства.

Ниже в статье приведено подробное описание алгоритма Helena.4.0 и результаты сравнительных тестов с алгоритмами-конкурентами.

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

Битва за производительность: SparseMap vs GenerationsMap

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

Есть такая занимательная структура данных, описанная в статье Russ Cox — sparse map.


Она используется, например, в недрах компилятора Go. А ещё в некоторых пакетах его стандартной библиотеки.


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


Читать дальше →
Всего голосов 33: ↑32 и ↓1 +31
Комментарии 8

Визуализация алгоритмов стандартной библиотеки C++

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

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

Читать далее
Всего голосов 28: ↑27 и ↓1 +26
Комментарии 6

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

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

Привет, Хабр! На связи Егор Гершевский и Никита Горбачёв, участники профессионального сообщества NTA.

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

Сегодня почти каждая крупная технологическая компания внедряет машинное обучение (ML) в аудит. Вот, например, как оно применяется в Facebook и Amazon. Его можно задействовать в разных аспектах, включая анализ данных, обнаружение мошенничества, прогнозирование рисков и оптимизацию процессов. Алгоритмы машинного обучения могут обрабатывать и анализировать огромные объёмы данных, выявлять скрытые зависимости и аномалии, что помогает аудиторам принимать более обоснованные и точные решения. Далее мы рассмотрим различные типы задач машинного обучения, которые могут быть применены в аудите.

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

Удивительные клеточные автоматы: дефицитные правила

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


👾, Хабр!

Возвращаемся к нашей экскурсии по модификациям клеточных автоматов. Объект сегодняшнего внимания – дефицитные правила (deficient rules). Это ещё более свежая вариация, чем рассмотренный в прошлом посте BSFKL, и была описана 5 лет назад энтузиастом 83bismuth38.

Модификация предполагает, что при рождении клетки на окружающих соседей налагается ограничение на рождение по этому переходу, согласно нотации Хенселя. Освежить в памяти, что из себя представляют переходы можно здесь.
Читать дальше →
Всего голосов 43: ↑43 и ↓0 +43
Комментарии 13

Двухракурсная томография. Теперь — у вас в голове

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

Привет, Хабр! Всем давно известно, что мы в Smart Engines занимаемся компьютерной томографией (КТ) и развиваем Smart Tomo Engine (STE) - программу для томографической реконструкции и визуализации.

Результирующее томографическое изображение в КТ получается с использованием вычислительно затратных алгоритмов реконструкции, которые применяются к набору зарегистрированных двумерных рентгеновских изображений. Однако сегодня мы хотим рассказать не об алгоритмах КТ, а о том как можно попытаться обойтись без них, но все же увидеть объемное реконструированное изображение внутренней структуры изучаемого объекта. В статье мы расскажем, как с помощью правильно выбранных двумерных проекций построить в голове человека трехмерное изображение. А исходить мы будем из физических принципов восприятия человеком объемных изображений. Картинки прилагаются! По ним можно не только убедиться, что теория работает, но и вспомнить детство со стереопарами и анаглифом. Запасайтесь попкорном и 3D очками. Приятного прочтения.

Читать далее
Всего голосов 10: ↑9 и ↓1 +8
Комментарии 4

Reinforcement learning для оптимизации цен в ритейле

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

Динамическое ценообразование является современным подходом к ценообразованию в ритейле. Оно напрямую связано с моделированием спроса, что позволяет проводить оптимизацию цен на будущий период. В этой задаче популярным решением является использование машинного обучения, однако, есть мнение, что Reinforcement Learning (а именно, многорукие бандиты), способны выступить сильной альтернативой моделям ML для динамического ценообразования. Но так ли это на самом деле? Попробуем разобраться в этой статье, держа в уме практические аспекты.

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

Римские числа или как не запоминать составные варианты

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

Откройте почти любую реализацию перевода чисел из арабской системы в римскую и вы почти со 100% вероятностью увидите там знаменитые дифтонги "CM" (900), "CD" (400) и так далее. И поначалу кажется, что без них не обойтись. Но это не так!

Читать далее
Всего голосов 21: ↑18 и ↓3 +15
Комментарии 45

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

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн

Предельный анализ распределения простых чисел, и допуск к решению задачи равенство классов p и Np

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

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

Читать далее
Всего голосов 19: ↑9 и ↓10 -1
Комментарии 5

Создаём субтитры для любого видео в интернете с помощью нейросети в браузере

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

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

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

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

Читать далее
Всего голосов 24: ↑23 и ↓1 +22
Комментарии 19

Циркуль и линейка. Часть 1

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

Всем привет!

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

Всё дальнейшей вылилось в эту статью.

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

PKI, прикладная криптография и электронная подпись: о чем здесь речь и как это работает в нашей блокчейн-платформе

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

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

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

Книга «Golang для профи: Создаем профессиональные утилиты, параллельные серверы и сервисы, 3-е изд.»

Время на прочтение 12 мин
Количество просмотров 10K
image Привет, Хаброжители!

Язык Go — это простой и понятный язык для создания высокопроизводительных систем будущего. Используйте Go в реальных производственных системах. В новое издание включены такие темы, как создание серверов и клиентов RESTful, знакомство с дженериками Go и разработка серверов и клиентов gRPC.

Третье издание «Golang для профи» исследует практические возможности Go и описывает такие продвинутые темы, как параллелизм и работа сборщика мусора Go, использование Go с Docker, разработка мощных утилит командной строки, обработка данных в формате JSON (JavaScript Object Notation) и взаимодействие с базами данных. Кроме того, книга дает дополнительные сведения о работе внутренних механизмов Go, знание которых позволит оптимизировать код на Go и использовать типы и структуры данных новыми и необычными способами.

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

Станьте опытным программистом на Go, создавая системы и внедряя передовые методы программирования на Go в свои проекты!
Читать дальше →
Всего голосов 18: ↑17 и ↓1 +16
Комментарии 10

Как мы создали нейросеть, которая составила рейтинг компаний, занимающихся ИИ в России

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

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

Идея проекта

Откуда вообще может появиться идея? Иногда она просто витает в воздухе и ждёт, пока её кто-нибудь подхватит. Честно говоря, мне бы никогда в голову не пришло отранжировать компании по их влиянию в сфере ИИ. Но ребята из нашего PR-отдела оказались более прозорливыми и пришли к нам с запросом о создании такого рейтинга. Забегая вперед, можно подчеркнуть, что весь проект сам по себе стал прецедентом с точки зрения взаимодействия представителей PR и специалистов по машинному обучению и анализу данных.

Читать далее
Всего голосов 10: ↑9 и ↓1 +8
Комментарии 3

Головоломка ассасина

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

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

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

Рассмотрим квадратную комнату в плоскости XY, и пусть A («ассасин») и T («цель») — две произвольные, но фиксированные точки внутри комнаты. Предположим, что комната схожа по физическим характеристикам с бильярдным столом, так что любой «выстрел» А рикошетит от стен, причём угол падения равен углу отражения. Можно ли заблокировать любой возможный «выстрел» А в Т, разместив конечное количество аналогичных по свойствам точек («телохранителей») в комнате?

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

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